# Packrat记忆化Parser与Recoverable Parser

## Packrat Parser用于解决左递归1

### 算法

• $Pos: \mathrm{P{\scriptsize OSITION}}$
• $\mathrm{H{\scriptsize EADS}}: \mathrm{P{\scriptsize OSITION}}\to\mathrm{H{\scriptsize EAD}}$
• $LRStack:\mathrm{LR}~\text{or}~\mathrm{\scriptsize NIL}$ （链表）
• $\mathrm{M{\scriptsize EMO}}:(\mathrm{R{\scriptsize ULE}},\mathrm{P{\scriptsize OSITION}})\rightarrow\mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}$

• $\mathrm{LR}=(seed:\mathrm{AST},rule:\mathrm{R{\scriptsize ULE}},head:\mathrm{H{\scriptsize EAD}}~\text{or}~\mathrm{\scriptsize NIL},next:\mathrm{lR})$
• $\mathrm{H{\scriptsize EAD}}=(rule: \mathrm{R{\scriptsize ULE}},involvedSet:\mathrm{S{\scriptsize ET}}~\text{of}~\mathrm{R{\scriptsize ULE}},evalSet:\mathrm{S{\scriptsize ET}}~\text{of}~\mathrm{R{\scriptsize ULE}})$
• $\mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}=(ans: \mathrm{AST}~\text{or}~\mathrm{LR},pos:\mathrm{P{\scriptsize OSITION}})$

#### $\mathrm{G{\scriptsize ROW}\text{-}LR}(R, P, M, H)$

• $R: \mathrm{R{\scriptsize ULE}}$
• $P: \mathrm{P{\scriptsize OSITION}}$
• $M: \mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}$
• $H: \mathrm{H{\scriptsize EAD}}$

• $\mathrm{AST}$

• $\mathrm{H{\scriptsize EADS}}(P)\leftarrow H$
• $\mathbf{while}~\mathrm{\scriptsize TRUE}$
• $Pos\leftarrow P$
• $H.evalSet\leftarrow\mathrm{C{\scriptsize OPY}}(H.involvedSet)$
• $\mathbf{let}~ans=\mathrm{E{\scriptsize VAL}}(R.body)$
• $\mathbf{if}~ans=\mathrm{\scriptsize FAIL}~\text{or}~Pos\leq M.pos$
• $\mathbf{break}$
• $M.ans\leftarrow ans$
• $M.pos\leftarrow Pos$
• $\mathrm{H{\scriptsize EADS}}(P)\leftarrow\mathrm{\scriptsize NIL}$
• $Pos\leftarrow M.pos$
• $\mathbf{return}~M.ans$

#### $\mathrm{A{\scriptsize PPLY}\text{-}R{\scriptsize LUE}}(R, P)$

• $R: \mathrm{R{\scriptsize ULE}}$
• $P: \mathrm{P{\scriptsize OSITION}}$

• $\mathrm{AST}$

• $\mathbf{let}~m=\mathrm{R{\scriptsize ECALL}}(R, P)$
• $\mathbf{if}~m=\mathrm{\scriptsize NIL}$
• $\triangleright$创建一个新的$\mathrm{LR}$，并入栈
• $\mathbf{let}~lr=\mathbf{new}~\mathrm{LR}(\mathrm{\scriptsize FAIL},R,\mathrm{\scriptsize NIL},LRStack)$
• $LRStack\leftarrow lr$
• $\triangleright$记忆化$lr$，并解析$R$
• $m\leftarrow\mathbf{new}~\mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}(lr,P)$
• $\mathrm{M{\scriptsize EMO}}(R,P)\leftarrow m$
• $\mathbf{let}~ans=\mathrm{E{\scriptsize VAL}}(R.body)$
• $\triangleright lr$出栈
• $LRStack\leftarrow LRStack.next$
• $m.pos\leftarrow Pos$
• $\mathbf{if}~lr.head\neq\mathrm{\scriptsize NIL}$
• $lr.seed\leftarrow ans$
• $\mathbf{return}~\mathrm{LR}\text{-}\mathrm{A{\scriptsize NSWER}}(R,P,m)$
• $\mathbf{else}$
• $m.ans\leftarrow ans$
• $\mathbf{return}~ans$
• $\mathbf{else}$
• $Pos\leftarrow m.pos$
• $\mathbf{if}~m.ans~\text{is}~\mathrm{LR}$
• $\mathrm{S{\scriptsize ETUP}}\text{-}\mathrm{LR}(R,m.ans)$
• $\mathbf{return}~m.ans.seed$
• $\mathbf{else}$
• $\mathbf{return}~m.ans$

#### $\mathrm{S{\scriptsize ETUP}\text{-}LR}(R, L)$

• $R: \mathrm{R{\scriptsize ULE}}$
• $L: \mathrm{LR}$

• $\mathbf{if}~L.head=\mathrm{\scriptsize NIL}$
• $L.head\leftarrow\mathbf{new}~\mathrm{H\scriptsize{EAD}}(R,\{\},\{\})$
• $\mathbf{let}~s=LRStack$
• $\mathbf{while}~s.head\neq L.head$
• $s.head\leftarrow L.head$
• $L.head.involvedSet\leftarrow L.head.involvedSet\cup\{s.rule\}$
• $s\leftarrow s.next$

#### $\mathrm{LR\text{-}A{\scriptsize NSWER}}(R, P, M)$

• $R: \mathrm{R{\scriptsize ULE}}$
• $P: \mathrm{P{\scriptsize OSITION}}$
• $M: \mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}$，其中$M.ans~\mathbf{is}~\mathrm{LR1}$

• $\mathrm{AST}$

• $\mathbf{let}~h=M.ans.head$
• $\textbf{if}~h.rule\neq R$
• $\textbf{return}~M.ans.seed$
• $\textbf{else}$
• $M.ans\leftarrow M.ans.seed$
• $\textbf{if}~M.ans=\mathrm{\scriptsize FAIL}$
• $\textbf{return}~\mathrm{\scriptsize FAIL}$
• $\textbf{else}$
• $\textbf{return}~\mathrm{G{\scriptsize ROW}\text{-}LR}(R, P, M, h)$

#### $\mathrm{R{\scriptsize ECALL}}(R, P)$

• $R: \mathrm{R{\scriptsize ULE}}$
• $P: \mathrm{P{\scriptsize OSITION}}$

• $\mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}~\text{or}~\mathrm{\scriptsize NIL}$

• $\textbf{let}~m=\mathrm{M{\scriptsize EMO}}(R, P)$
• $\textbf{let}~h=\mathrm{H{\scriptsize EADS}}(P)$
• $\triangleright$如果不是在扩展种子的阶段，直接返回存储的值
• $\textbf{if}~h=\mathrm{\scriptsize NIL}$
• $\mathbf{return}~m$
• $\triangleright$不要计算那些这次左递归没涉及的规则
• $\textbf{if}~m=\mathrm{\scriptsize NIL}~\text{and}~R\notin\{h.read\}\cup h.involvedSet$
• $\mathbf{return}~\mathbf{new}~\mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}(\mathrm{\scriptsize FAIL},P)$
• $\triangleright$只允许涉及的规则被计算一次
• $\textbf{if}~R\in h.evalSet$
• $h.evalSet\leftarrow h.evalSet\setminus\{R\}$
• $\textbf{let}~ans=\mathrm{E{\scriptsize VAL}}(R.body)$
• $m.ans\leftarrow ans$
• $m.pos\leftarrow pos$
• $\textbf{return}~m$

### 合并后的算法

• $R: \mathrm{R{\scriptsize ULE}}$
• $P: \mathrm{P{\scriptsize OSITION}}$

• $\mathrm{AST}$

• $\textbf{let}~m=\mathrm{M{\scriptsize EMO}}(R, P)$
• $\textbf{let}~h=\mathrm{H{\scriptsize EADS}}(P)$
• $\triangleright$如果不是在扩展种子的阶段，直接返回存储的值
• $\textbf{if}~h\neq\mathrm{\scriptsize NIL}$
• $\triangleright$不要计算那些这次左递归没涉及的规则
• $\textbf{if}~m=\mathrm{\scriptsize NIL}~\text{and}~R\notin\{h.read\}\cup h.involvedSet$
• $m\leftarrow~\mathbf{new}~\mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}(\mathrm{\scriptsize FAIL},P)$
• $\triangleright$只允许涉及的规则被计算一次
• $\textbf{elif}~R\in h.evalSet$
• $h.evalSet\leftarrow h.evalSet\setminus\{R\}$
• $\textbf{let}~ans=\mathrm{E{\scriptsize VAL}}(R.body)$
• $m.ans\leftarrow ans$
• $m.pos\leftarrow pos$
• $\mathbf{if}~m=\mathrm{\scriptsize NIL}$
• $\triangleright$创建一个新的$\mathrm{LR}$，并入栈
• $\mathbf{let}~lr=\mathbf{new}~\mathrm{LR}(\mathrm{\scriptsize FAIL},R,\mathrm{\scriptsize NIL},LRStack)$
• $LRStack\leftarrow lr$
• $\triangleright$记忆化$lr$，并解析$R$
• $m\leftarrow\mathbf{new}~\mathrm{M{\scriptsize EMO}E{\scriptsize NTRY}}(lr,P)$
• $\mathrm{M{\scriptsize EMO}}(R,P)\leftarrow m$
• $\mathbf{let}~ans=\mathrm{E{\scriptsize VAL}}(R.body)$
• $\triangleright lr$出栈
• $LRStack\leftarrow LRStack.next$
• $m.pos\leftarrow Pos$
• $\mathbf{if}~lr.head\neq\mathrm{\scriptsize NIL}$
• $lr.seed\leftarrow ans$
• $\mathbf{let}~h=m.ans.head$
• $\textbf{if}~h.rule\neq R$
• $\textbf{return}~m.ans.seed$
• $\textbf{else}$
• $m.ans\leftarrow m.ans.seed$
• $\textbf{if}~m.ans=\mathrm{\scriptsize FAIL}$
• $\textbf{return}~\mathrm{\scriptsize FAIL}$
• $\textbf{else}$
• $\mathrm{H{\scriptsize EADS}}(P)\leftarrow h$
• $\mathbf{while}~\mathrm{\scriptsize TRUE}$
• $Pos\leftarrow P$
• $h.evalSet\leftarrow\mathrm{C{\scriptsize OPY}}(h.involvedSet)$
• $\mathbf{let}~ans=\mathrm{E{\scriptsize VAL}}(R.body)$
• $\mathbf{if}~ans=\mathrm{\scriptsize FAIL}~\text{or}~Pos\leq m.pos$
• $\mathbf{break}$
• $m.ans\leftarrow ans$
• $m.pos\leftarrow Pos$
• $\mathrm{H{\scriptsize EADS}}(P)\leftarrow\mathrm{\scriptsize NIL}$
• $Pos\leftarrow m.pos$
• $\mathbf{return}~m.ans$
• $\mathbf{else}$
• $m.ans\leftarrow ans$
• $\mathbf{return}~ans$
• $\mathbf{else}$
• $Pos\leftarrow m.pos$
• $\mathbf{if}~m.ans~\text{is}~\mathrm{LR}$
• $\mathbf{let}~L=m.ans$
• $\mathbf{if}~L.head=\mathrm{\scriptsize NIL}$
• $L.head\leftarrow\mathbf{new}~\mathrm{H\scriptsize{EAD}}(R,\{\},\{\})$
• $\mathbf{let}~s=LRStack$
• $\mathbf{while}~s.head\neq L.head$
• $s.head\leftarrow L.head$
• $L.head.involvedSet\leftarrow L.head.involvedSet\cup\{s.rule\}$
• $s\leftarrow s.next$
• $\mathbf{return}~L.seed$
• $\mathbf{else}$
• $\mathbf{return}~m.ans$

1. Warth, Alessandro, James R. Douglass, and Todd Millstein. “Packrat parsers can support left recursion.” Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. 2008. ↩︎