ANTLR 不会自动进行前瞻匹配吗？

Question

我目前正在编写一种简单的语法，它要求在一个表达式中使用运算符优先级和混合结合性。一个示例表达式是 a -> b ?> C ?> D -> e，它应该被解析为 (a -> (((b ?> C) ?> D) -> e)。也就是说，?> 运算符是高优先级左结合运算符，而 -> 运算符是低优先级右结合运算符。

我正在对 ANTLR 3.5.1 中的语法进行原型设计（通过 ANTLRWorks 1.5.2），发现它无法处理以下语法：

prog    :   expr EOF;
expr    :   term '->' expr
        |   term;
term    :   ID rest;
rest    :   '?>' ID rest
        |   ;

它会产生 rule expr has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2 错误。

term 和 rest 产品在我测试时单独运行良好，所以我假设这是因为解析器被 expr 弄糊涂了。为了解决这个问题，我进行了以下重构：

prog    :   expr EOF;
expr    :   term exprRest;
exprRest 
        :   '->' expr
        |   ;
term    :   ID rest;
rest    :   DU ID rest
        |   ;

这很好用。但是，由于这种重构，我现在需要检查输出解析树中的空 exprRest 节点，这是不理想的。有没有办法让 ANTLR 解决 expr 初始声明中的歧义？我假设生成的解析器将完全匹配 term，然后对 "->" 进行前瞻搜索，然后继续解析或 return 单独的 term。我错过了什么？

Answer 1

如上所述，问题出在这条规则中：

expr    :   term '->' expr
        |   term;

有问题的部分是 term 这两个备选方案共有。

LL(1) 语法根本不允许这样做（除非 term 只匹配零个标记 - 但这样的规则将毫无意义），因为它不能决定使用哪种替代方案，只能看到前面的一个标记（即 LL(1) 中的 1）。
LL(k) 语法仅在 term 规则最多匹配 k - 1 个标记时才允许这样做。
LL(*) 语法做了一些技巧，允许它处理匹配任意数量标记的规则（ANTLR 作者称这个 "variable look-ahead").
- 但是，这些技巧无法处理的一件事是规则是否是递归的，即如果它或它调用的任何规则以任何方式（直接或间接）引用自身 - 而这正是您的 term 规则：
```
term    :   ID rest;
rest    :   '?>' ID rest
        |   ;
```
  - 规则 rest，引用自 term，递归引用自身。因此，错误消息
  
  rule expr has non-LL(*) decision due to recursive rule invocations ...

解决LL文法这个限制的方法叫left-factoring:

expr    :   term 
            ( '->' expr )?
        ;

我这里说的是"match term first"（既然你想在两个备选方案中都匹配它，那么决定在哪一个匹配它是没有意义的），然后决定是否匹配'->' expr （这可以通过查看下一个标记来决定 - 如果它是 ->，使用它 - 所以这甚至是 LL(1) 决定）。

这也与您得到的结果非常相似，但解析树应该看起来非常像您对原始语法的预期。

ANTLR 不会自动进行前瞻匹配吗？

ANTLR does not automatically do lookahead matching?

parsing

antlr

antlr3