为什么这个 ANTLR4 语法有歧义？

Question

我正在努力理解 ANTLR4 算法以及它如何处理左递归。希望有人可以教育我一点。

采用左下递归语法：

grammar Dummy;

TOK1 : 'foo';
TOKE_OPT : 'bar';
TOK2 : 'baz';
TOKDERP : 'derp';

SPACES
 : [ \u000B\t\r\n] -> channel(HIDDEN)
 ;

rr
    : rr TOK1 rr TOKE_OPT?
    | '(' TOK2 ')'
    | TOKDERP
    ;

以及以下输入字符串：

derp foo derp foo  derp

当运行TestRig -diagnosticsANTLR 时，得出的语法是模棱两可的，我不明白为什么：

line 1:5 reportAttemptingFullContext d=2 (rr), input='foo'
line 1:9 reportContextSensitivity d=2 (rr), input='foo derp'
line 1:14 reportAttemptingFullContext d=2 (rr), input='foo'
line 2:0 reportAmbiguity d=2 (rr): ambigAlts={1, 2}, input='foo  derp
'

如果有人能解释为什么这种语法有歧义以及如何消除歧义，将不胜感激。我也有可能不明白为什么歧义意味着:)。

如果我删除该TOKE_OPT?条款，警告就会消失。

我正在使用 ANTLR 版本 4.7.2

Answer 1

该语法确实是模棱两可的，因为该语法允许对 的两种解释derp foo derp foo derp：

(rr (rr (rr derp) foo (rr derp)) foo (rr derp))
(rr (rr derp) foo (rr (rr derp) foo (rr derp)))

（我个人认为，如果不是从表达式中抽象出来，而是使用合理的运算符和操作数标记，我认为整个问题会更容易阅读。但我离题了。）

Antlr4 是一种 LL 解析器，无法真正处理左递归。它通过将左递归规则翻译成一个简单的等效形式来解决这个问题，有效地改变：

rule: base
    | rule more
    ;

进入

rule: base (more)* ;

但这并不足以处理左递归规则的典型情况，即代数表达式。在这里，典型的语法可能是：

expr: expr '*' expr
    | expr '+' expr
    | atom
    ;

意图是这样的：

expr: atom ('*' atom)* ('+' ('*' atom)*)*

但这是一个复杂的转换并且不能很好地概括，所以 Antlr 真正做的是将谓词引入每个规则，以强制运算符优先顺序。有了这些谓词，语法就变得明确了，并且（通常）也符合对表达式语法应该如何解析的期望。

但是，如果没有“隐藏的”左递归或右递归，Antlr 只能获得正确的优先谓词。（“隐藏的右递归”并不意味着递归是隐藏的。隐藏的是递归发生在规则末尾的事实。）特别是，在规则末尾放置一个可选标记隐藏了这个事实可选标记前面的非终结符可以是右递归的，因此 Antlr4 不会尝试使用优先谓词来消除规则的歧义。这使得语法含糊不清。

您可以通过避免隐藏的右递归来解决此问题：

rr
    : rr  TOK1 rr TOKE_OPT
    | rr  TOK1 rr
    | '(' TOK2 ')'
    | TOKDERP
    ;

现在，右递归规则是明确的，而另一个规则（以 结尾TOKE_OPT）也没有歧义。（或者至少不会以同样的方式模棱两可。）

有关 Antlr4 用于重写规则的算法的更精确描述，请参阅本技术报告末尾的附录。