这个右递归 Antlr 规则的非 LL(*) 是什么？
What is non LL(*) about this right-recursive Antlr rule?
考虑以下 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.
问题：
如何修改上面的语法？ （非常感谢修复背后的解释。）
LL(*) 中的 * 如果在不成功、任意长的前瞻后不回溯，与 LL(k) 的静态 k 相比，是什么？
自动左因式分解不是由 Antlr3 自动完成的吗？
好奇，如何通过使用句法谓词来解决这个问题？
我正在使用 Antlr 3.5.2。
这个确切的例子 (character-by-character) 可以在 The Definitive ANTLR Reference 的 ANTLR3 版本的第 277 页找到，可在 on-line（位于至少对于有限的预览和付费下载）。它被用作对 ANTLR3 中使用的 LL(*) 算法的一个方面的解释，因此以下页面上的解释可能是对您的问题的最详细的回答。此外，还讨论了各种可能的解决方案。
所以让我只关注您的一个问题，我认为这也将回答 post 标题中的问题。
- What is * in LL(*) if not backtracking after an unsuccessful, arbitrarily long lookahead?
LL(*) 是启发式算法，不是形式语言范畴； Terence Parr（ANTLR 的作者）使用该术语来标记 ANTLR3 中使用的特定解析算法。 （ANTLR4 使用不同的算法，Parr 将其称为 Adaptive LL(*)。我不会深入讨论。）
LL解析，笼统地说，就是在开始解析产生式之前决定使用哪个产生式。 LL(k) 解析基于以下 k 个标记做出该决定，其中 k 是某个固定的（通常是小的）整数。这基本上是 ANTLR2 中使用的算法，它不足以处理许多语法。
为了使算法更通用，您可以添加回溯（ANTLR 所做的）；如果在检查了 k 个标记之后，解析器仍然无法决定使用哪个产生式，它会按顺序尝试它们，直到找到一个有效的产生式。如果尝试的产生式失败，解析器 returns 到决策点并尝试下一个产生式。如果产生式成功，解析器就会接受它并继续，即使这可能会导致稍后的解析失败。 （因此语法中的产生式顺序在回溯解析器中很重要。）
LL(*) 不涉及回溯。相反，它构建了一个 finite-automaton-based 正向扫描，将任意长的前瞻序列与正则表达式（标记，而不是字符，但原理是相同的）相匹配。如果它可以为每个候选产生式构造（在编译语法时）明确区分备选方案的正则表达式，那么它可以快速 运行 在决策点并行的有限自动机并做出决策。 LL(*) 中的 * 引用了这样一个事实，即前瞻没有任意长度限制；只需要正则表达式在将来的某个时候发散即可。
作为一个实际的例子，在语法中你提出了替代方案
label ID '=' ID
如果前瞻匹配 (ID ':')* ID '='，则应选择 ，而
| label 'return' ID
如果前瞻匹配 (ID ':')* ID 'return'，则应选择 。这些显然是不同的正则表达式；至多一个可以匹配任何前瞻序列。
但是，所有这些都取决于能够计算出前瞻模式的解析器生成器。在一般情况下，这是一个困难的（可能是不可能的）问题。 ANTLR3 尽力而为，但它无法处理前瞻序列中的递归 non-terminals（如 label）。
由于它可以处理重复运算符，您只需将 label 的定义更改为 non-recursive 替代方案即可解决此问题。 （这直接来自前面提到的书中。）
label: (ID ':')*
该定义已经采用正则表达式形式，ANTLR3 只需将其插入生产中即可生成有效的先行模式。
这在实践中可能很好，因为在实践中不太可能出现长序列的标签。但就个人而言，我会选择一个根本不使用 label non-terminal 的简单 LL(2) 解决方案：
s :
ID '=' ID
| 'return' ID
| ID ':' s
;
此解决方案不需要无限制的先行搜索。它仍然允许您为每个备选方案插入任意操作。
除了 rici 的精彩回答，我还有几点意见：
ANTLR3 是不是 LL(*)，而是 LL(k)，k 的数量很少（而且你必须在生成步骤中指定 k，因此它不是动态的。 对于每个 k 级别，它都会创建一个 switch 语句来确定路径，这会很快导致巨大的（且不可编译的）嵌套结构。因此 k > 3 通常不可用（因此前瞻根本不是无限的）。
ANTLR3 可以选择使用回溯来提高解析准确性。
ANTLR3 不支持直接左递归 - ANTLR4 支持。因此根本没有自动重构。
我认为，从解析器生成的角度来看，您不能将递归与谓词一起使用。谓词将动态引导解析过程，它确实可以在运行时解决问题，但无论如何您都无法完成生成步骤。
更新
您的评论可能是对的。我忘记了 ANTLR3 在代码生成期间进行前瞻（而 ANTLR4 在运行时进行）。因此，即使我的结果代码是正确的（嵌套的 switch 语句，每个 k 一个级别），我也无法真正证明我对 LL(k) 的主张。 ANTLR3 documentation 表示 k 参数阻止使用非循环 LL* DFA。
因此，这只是对已接受答案的补充。
考虑以下 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.
问题：
如何修改上面的语法？ （非常感谢修复背后的解释。）
LL(*) 中的 * 如果在不成功、任意长的前瞻后不回溯，与 LL(k) 的静态 k 相比，是什么？
自动左因式分解不是由 Antlr3 自动完成的吗？
好奇，如何通过使用句法谓词来解决这个问题？
我正在使用 Antlr 3.5.2。
这个确切的例子 (character-by-character) 可以在 The Definitive ANTLR Reference 的 ANTLR3 版本的第 277 页找到，可在 on-line（位于至少对于有限的预览和付费下载）。它被用作对 ANTLR3 中使用的 LL(*) 算法的一个方面的解释，因此以下页面上的解释可能是对您的问题的最详细的回答。此外，还讨论了各种可能的解决方案。
所以让我只关注您的一个问题，我认为这也将回答 post 标题中的问题。
- What is * in LL(*) if not backtracking after an unsuccessful, arbitrarily long lookahead?
LL(*) 是启发式算法，不是形式语言范畴； Terence Parr（ANTLR 的作者）使用该术语来标记 ANTLR3 中使用的特定解析算法。 （ANTLR4 使用不同的算法，Parr 将其称为 Adaptive LL(*)。我不会深入讨论。）
LL解析，笼统地说，就是在开始解析产生式之前决定使用哪个产生式。 LL(k) 解析基于以下 k 个标记做出该决定，其中 k 是某个固定的（通常是小的）整数。这基本上是 ANTLR2 中使用的算法，它不足以处理许多语法。
为了使算法更通用，您可以添加回溯（ANTLR 所做的）；如果在检查了 k 个标记之后，解析器仍然无法决定使用哪个产生式，它会按顺序尝试它们，直到找到一个有效的产生式。如果尝试的产生式失败，解析器 returns 到决策点并尝试下一个产生式。如果产生式成功，解析器就会接受它并继续，即使这可能会导致稍后的解析失败。 （因此语法中的产生式顺序在回溯解析器中很重要。）
LL(*) 不涉及回溯。相反，它构建了一个 finite-automaton-based 正向扫描，将任意长的前瞻序列与正则表达式（标记，而不是字符，但原理是相同的）相匹配。如果它可以为每个候选产生式构造（在编译语法时）明确区分备选方案的正则表达式，那么它可以快速 运行 在决策点并行的有限自动机并做出决策。 LL(*) 中的 * 引用了这样一个事实，即前瞻没有任意长度限制；只需要正则表达式在将来的某个时候发散即可。
作为一个实际的例子，在语法中你提出了替代方案
label ID '=' ID
(ID ':')* ID '='，则应选择 ，而
| label 'return' ID
(ID ':')* ID 'return'，则应选择 。这些显然是不同的正则表达式；至多一个可以匹配任何前瞻序列。
但是，所有这些都取决于能够计算出前瞻模式的解析器生成器。在一般情况下，这是一个困难的（可能是不可能的）问题。 ANTLR3 尽力而为，但它无法处理前瞻序列中的递归 non-terminals（如 label）。
由于它可以处理重复运算符，您只需将 label 的定义更改为 non-recursive 替代方案即可解决此问题。 （这直接来自前面提到的书中。）
label: (ID ':')*
该定义已经采用正则表达式形式，ANTLR3 只需将其插入生产中即可生成有效的先行模式。
这在实践中可能很好，因为在实践中不太可能出现长序列的标签。但就个人而言，我会选择一个根本不使用 label non-terminal 的简单 LL(2) 解决方案：
s :
ID '=' ID
| 'return' ID
| ID ':' s
;
此解决方案不需要无限制的先行搜索。它仍然允许您为每个备选方案插入任意操作。
除了 rici 的精彩回答，我还有几点意见：
ANTLR3 是不是 LL(*)，而是 LL(k)，k 的数量很少（而且你必须在生成步骤中指定 k，因此它不是动态的。对于每个 k 级别，它都会创建一个 switch 语句来确定路径，这会很快导致巨大的（且不可编译的）嵌套结构。因此 k > 3 通常不可用（因此前瞻根本不是无限的）。ANTLR3 可以选择使用回溯来提高解析准确性。
ANTLR3 不支持直接左递归 - ANTLR4 支持。因此根本没有自动重构。
我认为，从解析器生成的角度来看，您不能将递归与谓词一起使用。谓词将动态引导解析过程，它确实可以在运行时解决问题，但无论如何您都无法完成生成步骤。
更新
您的评论可能是对的。我忘记了 ANTLR3 在代码生成期间进行前瞻（而 ANTLR4 在运行时进行）。因此，即使我的结果代码是正确的（嵌套的 switch 语句，每个 k 一个级别），我也无法真正证明我对 LL(k) 的主张。 ANTLR3 documentation 表示 k 参数阻止使用非循环 LL* DFA。
因此，这只是对已接受答案的补充。