已经废弃了，因为算法感觉很复杂不可靠。主要介绍Tilly的前端所用到的技术。包括记忆化的Packrat Parser（包括它们带来的增量和解决左递归的方法）、Parser Combinator和基于PEG的Recoverable Parser。

Packrat Parser用于解决左递归¹

算法

全局变量：

• $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...