Antlr4：另一个 "No Viable Alternative Error"

Question

我已经检查过围绕此问题的类似问题，但 none 似乎为我的问题版本提供了解决方案。我最近刚开始使用 Antlr4，一切都进行得很顺利，直到我遇到了这个特殊的障碍。

我的语法是基本的数学表达式语法，但出于某种原因，我注意到生成的解析器 (?) 无法按顺序从 paser-rule "equal" 走到 paser-rule "expr"达到 lexer-rule "NAME".

grammar MathCraze;

NUM : [0-9]+ ('.' [0-9]+)?;
WS  : [ \t]+ -> skip;
NL  : '\r'? '\n' -> skip;
NAME: [a-zA-Z_][a-zA-Z_0-9]*;
ADD: '+';
SUB : '-';
MUL : '*';
DIV : '/';
POW : '^';

equal
    : add # add1
    | NAME '=' equal # assign
    ;
add
    : mul # mul1
    | add op=('+'|'-') mul # addSub
    ;
mul
    : exponent # power1
    | mul op=('*'|'/') exponent # mulDiv
    ;
exponent
    : expr # expr1
    | expr '^' exponent # power
    ;
expr
    : NUM # num
    | NAME # name
    | '(' add ')' # parens
    ;

如果我传递一个单词作为输入，比如 "variable"，解析器会抛出上面的错误，但是如果我传递一个数字作为输入（比如“78”），解析器会成功遍历树（即，从规则 "equal" 到 "expr").

equal                 equal
 |                     |
add                   add
 |                     |
mul                   mul
 |                     |
exponent              exponent
 |                     |
expr                  expr
 |                     |
NUM                   NAME
 |                     | 
"78" # No Error      "variable" # Error! Tree walk doesn't reach here.

我已经检查了我所知道的每一种类型的歧义，所以我可能在这里遗漏了一些东西。

顺便说一句，我正在使用Antlr5.6，如果这个问题得到解决，我将不胜感激。提前致谢。

Answer 1

虽然我无法回答您关于为什么解析器无法在 expr 中到达 NAME 的问题，但我想指出的是，对于 Antlr4，您可以在您的代码中使用直接左递归规则规范，使您的语法更紧凑并提高可读性。
考虑到这一点，您的语法可以重写为

math:
    assignment
    | expression
;

    assignment:
        ID '=' (assignment | expression)
    ;

    expression:
        expression '^' expression
        | expression ('*' | '/') expression
        | expression ('+' | '-') expression
        | NAME
        | NUM
    ;

该语法很乐意将 NAME 作为 expression 的一部分，所以我想它可以解决您的问题。

如果您真的对为什么它不适用于您的语法感兴趣，那么我会首先检查词法分析器是否已将输入与预期的标记相匹配。之后我会看一下解析树，看看解析器对给定的标记序列做了什么，然后尝试根据你的语法手动进行解析，在此期间你应该能够找到解析器的位置与您期望的有所不同。

Answer 2

您的表达式层次结构样式是我们在手写或 ANTLR v3 中使用的解析器样式，优先级从低到高。

正如 Raven 所说，ANTLR 4 更强大。注意power rule中的<assoc = right>规范，通常是right-associative.

grammar Question;

question
    :   line+ EOF
    ;

line
    :   expr   NL
    |   assign NL
    ;

assign
    :   NAME '=' expr                 # assignSingle
    |   NAME '=' assign               # assignMulti
    ;

expr // from high to low precedence
    :   <assoc = right> expr '^' expr # power
    |   expr op=( '*' | '/' ) expr    # mulDiv
    |   expr op=( '+' | '-' ) expr    # addSub
    |   '(' expr ')'                  # parens
    |   atom_r                        # atom
    ;

atom_r
    : NUM
    | NAME
    ;

NAME: [a-zA-Z_][a-zA-Z_0-9]*;
NUM : [0-9]+ ('.' [0-9]+)?;
WS  : [ \t]+  -> skip;
NL  : [\r\n]+ ;

运行使用 -gui 选项查看解析树：

$ echo $CLASSPATH
.:/usr/local/lib/antlr-4.6-complete.jar
$ alias grun
alias grun='java org.antlr.v4.gui.TestRig'
$ grun Question question -gui data.txt

和这个 data.txt 文件：

variable
78
a + b * c
a * b + c
a = 8 + (6 * 9)
a ^ b
a ^ b ^ c
7 * 2 ^ 5
a = b = c = 88

.

已添加

使用您的原始语法并从 equal 规则开始，出现以下错误：

$ grun Q2 equal -tokens data.txt
[@0,0:7='variable',<NAME>,1:0]
[@1,9:10='78',<NUM>,2:0]
...
[@41,89:88='<EOF>',<EOF>,10:0]
line 2:0 no viable alternative at input 'variable78'

如果我从规则 expr 开始，没有错误：

$ grun Q2 expr -tokens data.txt
[@0,0:7='variable',<NAME>,1:0]
...
[@41,89:88='<EOF>',<EOF>,10:0]
$

运行 grun 与 -gui 选项，你会看到区别：运行 expr，输入令牌 variable 被 NAME 捕获，满足规则 expr 并终止；运行 equal 都是错误的。解析器尝试第一个替代方法 equal -> add -> mul -> exponent -> expr -> NAME => OK。它使用令牌 variable 并尝试对下一个令牌 78 执行某些操作。它在每个规则中回滚，看看它是否可以用规则的 alt 做一些事情，但每个 alt 都需要一个操作员。因此它到达 equal 并再次以令牌 variable 开始，这次使用 alt | NAME '='。 NAME消耗token，则规则要求'='，但输入为78，不满足。由于没有其他选择，它说没有可行的选择。

$ grun Q2 equal -tokens data.txt
[@0,0:7='variable',<NAME>,1:0]
[@1,8:7='<EOF>',<EOF>,1:8]
line 1:8 no viable alternative at input 'variable'

如果 variable 是唯一的标记，相同的推理：第一个替代方案等于 -> 加 -> 乘 -> 指数 -> expr -> NAME => OK，消耗 variable，回到equal，尝试需要 '=' 的 alt，但输入在 EOF。这就是为什么它说没有可行的选择。

$ grun Q2 equal -tokens data.txt
[@0,0:1='78',<NUM>,1:0]
[@1,2:1='<EOF>',<EOF>,1:2]

如果 78 是唯一的标记，则进行相同的推理：第一个替代方法等于 -> 加法 -> 乘法 -> 指数 -> expr -> NUM => OK，消耗 78，回到 equal。替代方案不是一个选项。使满意？哎呀，EOF 呢。

现在让我们向 equal 添加 NUM alt :

equal
    : add # add1
    | NAME '=' equal # assign
    | NUM  '=' equal # assignNum
    ;

$ grun Q2 equal -tokens data.txt
[@0,0:1='78',<NUM>,1:0]
[@1,2:1='<EOF>',<EOF>,1:2]
line 1:2 no viable alternative at input '78'

第一个替代方案等于 -> 加法 -> 乘法 -> 指数 -> expr -> NUM => OK，消耗 78，回到 equal。现在还有 NUM 的 alt，再次开始，这次使用 alt | NUM '='。 NUM 消耗令牌 78，然后解析器需要 '='，但输入在 EOF，因此消息。

现在让我们添加一个带有 EOF 的新规则，让我们运行来自所有的语法 :

all : equal EOF ;

$ grun Q2 all -tokens data.txt
[@0,0:1='78',<NUM>,1:0]
[@1,2:1='<EOF>',<EOF>,1:2]
$ grun Q2 all -tokens data.txt
[@0,0:7='variable',<NAME>,1:0]
[@1,8:7='<EOF>',<EOF>,1:8]

输入符合语法，没有更多信息

Antlr4：另一个 "No Viable Alternative Error"

Antlr4: Another "No Viable Alternative Error"

grammar

parsing

expression

antlr

antlr4