使用 Parsec 处理左递归 2017-03-03 | { haskell } { compile } { 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}ExprExprsFactorInteger...Apply→Factor...→Expr,Exprs→Integer∣Apply∣Identify∣...∣(Expr)→...→Factor(Exprs) 显然,non-terminal ApplyApplyApply 的派生最左端会进入 FactorFactorFactor ,之后又会回到 ApplyApplyApply 。教科书式的左递归。 Read On »