parsing - 左结合与左递归

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 算法在处理左递归时没有问题(并且任何其他类型的递归都没有问题，尽管它可能需要更多的堆栈空间)。

您还可以使用其他自下而上的技术，例如经典的运算符优先算法(即分流码)，但严格来说 LR 解析更具表现力，并且解析器生成器使实现相对简单。

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