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

Question

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

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


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

语法中的花括号表示它们可以重复（但也是可选的），并且在我的解析器中使用 while 循环来实现。我觉得造成这种情况的原因是Grouping规则可以是 and （它可以一遍又一遍地重复，因为and规则Expression的右侧是可选的）。FactorTerm

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

编辑：我在四处浏览，似乎这种类型的递归称为间接左递归，也许这与它有关？

Answer 1

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

Expression ⇒ Term ⇒ Factor ⇒ Grouping ⇒ Expression

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

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