parsing - 为什么这个 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 -diagnostics 时，ANTLR 断定语法有歧义，我不明白为什么:

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 用于重写规则的算法的更精确描述，请参阅 this technical report 末尾的附录.