左结合性与左递归

Question

我正在尝试为 C 编写编译器（虽然语法更简单）。

有些事情我一直坚持了一段时间。如果我没说错的话，所有二元运算都是左结合的。所以如果我们有 "x+y+z"，x+y 首先出现，然后是加 z。

但是，强制左结合性不会导致无限左递归吗？

到目前为止，我检查过的所有解决方案要么是左关联的，要么是没有左递归的，但不是两者。是否有可能具有同时具有这两个属性的语法。有可能吗？

示例：

左结合：

Expr = Term | Expr + Term
Term = Element | Term ∗ Element
Element = x|y|z|(Expr)

消除了左递归：

Expr = Term ExprTail
ExprTail = epsilon | + Term ExprTail

Term = Element TermTail
TermTail = epsilon | * Element TermTail

Element = x|y|z|(Expr)

有什么想法吗？

Answer 1

如果运算符是左结合的，则相应的产生式将是左递归的。

如果你用的是LR解析器生成器，那就没问题了。 LR 算法在处理左递归时没有问题（并且在处理任何其他类型的递归时几乎没有问题，尽管它可能需要更多堆栈 space）。

您也可以使用其他自下而上的技术，例如经典的运算符优先算法（即调车场），但 LR 解析严格来说更具表现力，解析器生成器使实现相对简单。

如果您坚持递归下降解析，那是可能的，因为您可以使用循环（理论上是右递归）解析重复模式，但从左到右组合元素。从某种理论上讲，这是对 AST 的树重写，但我怀疑很多程序员在没有注意到树修复的情况下编写了代码。

Left Associativity vs Left Recursion