Antlr4：另一个"No Viable Alternative Error"

Question

我已经检查了围绕此问题的类似问题，但似乎没有一个能为我的问题版本提供解决方案。 我最近刚开始 Antlr4，一切都很顺利，直到我遇到这个特定的障碍。

我的语法是基本的数学表达式语法，但由于某种原因，我注意到生成的解析器(？)无法从帕瑟规则"等于"到帕瑟规则"expr"，以达到词法分析规则"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
;

如果我传递一个单词作为输入，就像"变量"一样，解析器会抛出上面的错误，但是如果我传递一个数字作为输入(比如"78")，解析器会成功遍历树(即从规则"等于"到"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

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

正如Raven所说，ANTLR 4的功能要强大得多。请注意幂规则中的<assoc = right>规范，该规范通常是右关联的。

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  : [rn]+ ;

使用 -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]
$ 

使用-gui选项运行grun，您将看到差异： 使用expr运行，输入令牌variable在 NAME 中捕获，规则expr满足并终止; 运行equal这一切都是错误的。解析器尝试第一个替代相等的 ->添加 -> mul -> 指数 -> expr -> NAME => OK。它使用令牌variable并尝试对下一个令牌78执行某些操作。它在每个规则中回滚，看看它是否可以对规则的 alt 做一些事情，但每个 alt 都需要一个运算符。因此，它到达equal并以令牌variable重新开始，这次使用 alt| NAME '='。NAME使用令牌，则规则需要'='，但输入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是唯一的标记，同样的推理：第一个备选方案等于 ->添加 -> mul ->指数 -> 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是唯一的标记，请执行相同的推理：第一个备选方案等于 -> 添加 -> mul -> 指数 -> expr -> NUM => OK，消耗78，回到equal。替代方案不是一种选择。满意？哎呀，EOF呢。

现在让我们添加一个 NUM alt 到equal：

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'

第一个备选方案等于 -> 添加 -> mul -> 指数 -> 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]

输入对应于语法，并且没有更多消息。

Answer 2

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

math:
assignment
| expression
;
assignment:
ID '=' (assignment | expression)
;
expression:
expression '^' expression
| expression ('*' | '/') expression
| expression ('+' | '-') expression
| NAME
| NUM
;

该语法恰好需要NAME作为expression的一部分，所以我想它会解决您的问题。

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