使用递归下降解析器解析算术表达式的无限递归

Question

我正在尝试在 python 中创建我自己的递归下降解析器，但是当我的解析器遇到有关算术表达式的规则时，它超过了 python 递归限制。这是语法：

Term --> Factor {( "+" | "-" ) Factor}
Factor --> Grouping {( "*" | "/" | "%" ) Grouping}
Grouping --> Expression | "(" Expression ")" | "-" Factor


Expression --> Integer | Float | Tuple | ID | Term

语法中的大括号表示它们可以重复（但也是可选的），并且是在我的解析器中使用 while 循环实现的。我觉得造成这种情况的原因是 Grouping 规则可以和 Expression （可以反复出现，因为 Factor 和 Term 的右侧规则是可选的）。

我想问的是：有没有办法用递归下降解析器实现左回避或以某种方式在我的语法中消除它？

编辑：我四处浏览，似乎这种类型的递归称为 indirect left recursion，也许这与它有关？

Answer 1

如你所见，无限递归是无限循环的结果

Expression ⇒ Term ⇒ Factor ⇒ Grouping ⇒ Expression

必须打破。但这是一个简单的转录错误； Expression 需要从顶部开始，在语法优先级层次结构中：

Expression ⇒ Term {( "+" | "-" ) Term}
Term ⇒ Factor {( "*" | "/" | "%" ) Factor}
Factor ⇒ Item | "-" Factor
Item ⇒ Integer | Float | Tuple | ID | "(" Expression ")"

使用递归下降解析器解析算术表达式的无限递归

Infinite recursion for parsing arithmetic expressions using a recursive descent parser

parsing

recursive-descent

infinite-recursion