parsing - 为什么自顶向下解析器不能处理左递归？

Question

我想知道为什么自上而下的解析器不能处理左递归，我们需要消除左递归，正如龙书中提到的那样。

Answer 1

想想它在做什么。假设我们有一个左递归生产规则A -> Aa | b，现在我们尝试匹配该规则。所以我们在这里检查我们是否可以匹配一个 A，但是为了做到这一点，我们必须首先检查我们是否可以在这里匹配一个 A。这听起来不可能，而且大多数情况下是这样。使用递归下降解析器，这显然代表了无限递归。

可以使用仍然自上而下的更高级技术，例如参见 [​​1] 或 [2]。

[1]：Richard A. Frost 和 Rahmatullah Hafiz。一种新的自顶向下解析算法，以适应多项式时间内的歧义和左递归。SIGPLAN Notices, 41(5):46–54, 2006.
[2]：R. Frost、R. Hafiz 和 P. Callaghan，模棱两可的左递归语法的模块化和高效自顶向下解析。ACL-IWPT，第 109-120 页，2007 年。

Answer 2

自顶向下解析器无法处理左递归 自顶向下解析器无法处理左递归产生式。为了理解为什么不这样做，让我们看一个非常简单的左递归语法。

1. S → 一个
2. S → S a 只有一个记号 a 和一个非终结符 S。所以解析表只有一个条目。两个产品都必须进入该一个表条目。

问题是，在前瞻 a 中，解析器无法知道在前瞻之后是否有另一个 a。但是使用哪种产品的决定取决于该信息。