parsing - ANTLR 不会自动进行前向匹配？

Question

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

我正在 ANTLR 3.5.1 中对语法进行原型(prototype)设计(通过 ANTLRWorks 1.5.2)，发现它无法处理以下语法:

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

由于可从 alts 1,2 到达的递归规则调用，它会产生rule expr has non-LL(*) Decision 错误。

当我测试时，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;

有问题的部分是两个替代方案所共有的术语。

• LL(1) 语法根本不允许这样做(除非 term 只匹配零个标记 - 但这样的规则毫无意义)，因为它无法决定哪个另一种只能看到前面一个标记的情况(即 LL(1) 中的 1)。
• LL(k) 语法仅在 term 规则最多匹配 k - 1 个标记时才允许这样做。
ANTLR 3.5 使用的

• LL(*) 语法做了一些技巧，使其能够处理与任意数量的标记匹配的规则(ANTLR 作者将此称为“变量前瞻”)。

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

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

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

    rule expr has non-LL(*) decision due to recursive rule invocations ...

---

解决 LL 语法这一限制的方法称为左分解:

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

我在这里所做的是“首先匹配术语”(因为你想在两种选择中匹配它，所以没有必要决定匹配哪一个)，然后决定是否匹配 '->' expr (这可以通过查看下一个标记来决定 - 如果它是 ->，则使用它 - 所以这甚至是 LL(1) 决策)。

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