« Home

消除左遞迴的方法 [cs-000C]

現在你知道為什麼我們需要了解遞歸下降解析中消除左遞迴的方式，以下面文法來說

Expr→Expr+Expr∣Int∣ExprExpr \to Expr + Expr \\ \mid Int \\ \mid Expr

我們可能會將定義改成

Expr→Term+TermTerm→Int∣ExprExpr \to Term + Term \\ Term \to Int \mid Expr

這個解法在對應的 parser combinator 中看起來像是

mutual
  def term := parse_int <|> parens expr
  def expr : Parsec E :=
    let l <- term
    match '+'
    let r <- term
    return E.add l r
end