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

Question

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

我正在ANTLR3.5.1中对语法进行原型设计(通过ANTLRWorks1.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，然后对"->"进行前瞻性搜索，并继续解析或返回唯一的term。我错过了什么？

Answer 1

如前所述，问题在于这个规则：

expr    :   term '->' expr
|   term;

有问题的部分是term，它对两种备选方案都是通用的。

• LL(1)语法根本不允许这样做(除非term只匹配零个令牌，但这样的规则毫无意义)，因为它无法决定使用哪种替代方案，而只能看到前面的一个令牌(即LL(2)中的1)
• 只有当term规则最多可以匹配k - 1令牌时，LL(k)语法才允许这样做

• LL(*)ANTLR 3.5使用的语法做了一些技巧，允许它处理与任何数量的令牌匹配的规则(ANTLR作者称之为"变量前瞻")。

  • 然而，这些技巧无法处理的一件事是，如果规则是递归的，即，如果它或它以任何方式(直接或间接)调用引用本身的任何规则，这正是term规则所做的：

    term    :   ID rest;
    rest    :   '?>' ID rest
    |   ;
    

    -从term引用的规则rest递归地引用其自身。因此，错误消息

    rule-expr由于递归规则调用而具有非LL(*)决策。。。

---

解决LL语法这一限制的方法称为左因子分解：

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

我在这里所做的是说"先匹配术语"(因为你想在两个选项中匹配它，所以决定在哪个选项中匹配是没有意义的)，然后决定是否匹配'->' expr(这可以通过查看下一个令牌来决定-如果是->，就使用它-所以这甚至是LL(1)决定)。

这也与您所得到的非常相似，但解析树看起来应该与原始语法非常相似。