{ parsec }

  • 使用 Parsec 处理左递归

    |

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

    ExprFactor...ExprsExpr,ExprsFactorIntegerApplyIdentify...(Expr)Integer......ApplyFactor(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 。教科书式的左递归。