{ parsec }

  • 使用 Parsec 处理左递归

    |

    在给之前写的 Lisp 解释器之前套上表达式语法时,遇到这样几条文法

    Expr→Factor...Exprs→Expr,ExprsFactor→Integer∣Apply∣Identify∣...∣(Expr)Integer→......Apply→Factor(Exprs)\begin{aligned} Expr & \rightarrow Factor ... \\\\ Exprs & \rightarrow Expr , Exprs\\\\ Factor & \rightarrow Integer|Apply|Identify|...|{(} {Expr} {)} \\\\ Integer & \rightarrow... \\\\ ...\\\\ Apply & \rightarrow Factor ( Exprs ) \end{aligned}

    显然,non-terminal ApplyApply 的派生最左端会进入 FactorFactor ,之后又会回到 ApplyApply 。教科书式的左递归。