这个右递归Antlr规则的非LL(*)是什么

Question

考虑以下Antlr3语法：

grammar stat;
s : 
label ID '=' ID
| label 'return' ID
;
label
: ID ':' label
|
;
ID: 'a'..'z' + ;

假设Antlr3是LL(*)，这意味着解析器在选择替代方案时可以任意地向前查看令牌流，为什么我会出现以下错误？

[fatal] rule s has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

问题：

1. 如何修复上述语法(非常感谢对修复的解释。)

2. 如果在一次不成功的、任意长的前瞻之后没有回溯，那么LL(*)中的*是什么？与LL(k)的静态k相比？

3. 自动左因子分解不是Antlr3自动完成的吗？

4. 奇怪的是，这怎么可能也通过使用句法谓词来解决呢？

我使用的是Antlr 3.5.2.

Answer 1

这个确切的例子(逐个字符)可以在最终ANTLR参考的ANTLR3版本的第277页找到，该参考可以在线获得(至少用于有限预览和付费下载)。它被用来解释ANTLR3中使用的LL(*)算法的一个方面，因此下面几页的解释可能是对您问题的最佳详细回答。此外，还讨论了各种可能的解决方案。

所以，让我只关注你的一个问题，我认为这也会回答帖子标题中的问题。

2. 如果在不成功、任意长时间的前瞻后不回溯，LL(*)中的*是什么

LL(*)是一个启发式算法，而不是一个形式语言类别；Terence Parr(ANTLR的作者)使用该术语来标记ANTLR3中使用的特定解析算法。(ANTLR4使用不同的算法，Parr称之为自适应LL(*)。我不想谈这个。)

一般来说，LL解析决定在开始解析产品之前使用哪个产品。LL(k)解析基于以下k个令牌做出决定，其中k是某个固定(通常是小)整数。这基本上就是ANTLR2中使用的算法，它还不足以处理许多语法。

为了使算法更通用，您可以添加回溯(ANTLR会这样做)；如果在检查了k个令牌之后，解析器仍然无法决定使用哪个产品，那么它会按顺序尝试它们，直到找到一个有效的。如果尝试的生产失败，解析器返回到决策点并尝试下一个生产。如果生成成功，解析器会接受它并继续，即使这可能会导致以后的解析失败。(因此，语法中的生成顺序在回溯解析器中很重要。)

LL(*)不涉及回溯。相反，它构造了一个基于有限自动机的前向扫描，该扫描将任意长的前瞻序列与正则表达式(令牌，而不是字符，但原理相同)相匹配。如果它能够(在编译语法时)为每个候选产品构造正则表达式，明确区分备选方案，那么它就可以在决策点快速并行运行有限自动机并做出决策。LL(*)中的*指的是前瞻没有任意长度限制的事实；正则表达式只需要在将来的某个时刻发生分歧。

作为一个实际的例子，在语法中，你提出了替代

label ID '=' ID

如果前瞻性匹配(ID ':')* ID '='，则应选择

| label 'return' ID

如果前瞻性匹配CCD_ 2，则应该选择。这些显然是不同的正则表达式；最多可以匹配任何前瞻序列。

然而，所有这些都取决于解析器生成器是否能够计算出前瞻模式。在一般情况下，这是一个困难的(可能是不可能的)问题。ANTLR3尽其所能，但它无法处理前瞻序列中的递归非终端(如label)。

由于它可以处理重复运算符，您可以通过简单地将label的定义更改为非递归替代方案来解决此问题。(这直接出自前面提到的书。)

label: (ID ':')*

该定义已经是正则表达式形式的，ANTLR3可以将其插入到产品中，以生成有效的前瞻模式。

这在实践中可能很好，因为在实践中不太可能出现长序列的标签。但就我个人而言，我会选择一个简单的LL(2)解决方案，它根本不使用label非终端：

s : 
ID '=' ID
| 'return' ID
| ID ':' s
;

此解决方案不需要无限的前瞻性搜索。它仍然允许您为每个备选方案插入任意操作。

Answer 2

除了rici的精彩回答之外，我还有一些评论：

1. ANTLR3是不是LL(*)，而是LL(k)，只有少量的k(您必须在生成步骤中指定k，所以它不是动态的)对于每个k级别，它都会创建一个switch语句来确定路径，这可以快速导致巨大(且不可编译)的嵌套结构。因此，k>3通常是不可用的(因此前瞻性根本不是无限的)。

2. ANTLR3可以选择使用回溯来提高解析的准确性。

3. ANTLR3不支持直接左递归-ANTLR4支持。因此根本没有自动重构。

4. 我认为，从语法分析器生成的角度来看，不能将递归与谓词结合使用。谓词将动态地引导解析过程，它确实可以在运行时解决问题，但无论如何都无法完成生成步骤。

更新

你的评论可能是对的。我忘记了ANTLR3在代码生成过程中进行前瞻(而ANTLR4在运行时进行前瞻)。所以，即使我对结果代码(嵌套的switch语句，每个k一个级别)是正确的，我也不能真正证明我关于LL(k)的说法。ANTLR3文档指出，k参数阻止使用非循环LL*DFA。

因此，这只是对公认答案的补充。