Antlr4：另一个“无可行替代错误”

Question

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

我的语法是一个基本的数学表达式语法，但由于某种原因，我注意到生成的解析器（？）无法从paser规则“等于”到paser规则“exr”，以达到lexer-规则“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”），解析器会成功地遍历树（即，从规则“相等”到“exr”）。

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中无法访问名称的问题，但我想指出，使用Antlr4，您可以在规则规范中使用直接左递归，这会使语法更加紧凑，提高可读性<记住这一点，你的语法可以改写为

math:
    assignment
    | expression
;

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

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

该语法愉快地将NAME作为表达式的一部分，因此我想它会解决您的问题。

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

Answer 2

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

正如Raven所说，ANTLR 4要强大得多。注意

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

这是数据。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

.

补充

使用原始语法，从相等规则开始，我有以下错误：

$ 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'

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

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

使用-gui选项运行grun，您将看到区别：使用expr运行时，输入标记变量在名称中被捕获，规则expr得到满足并终止；以相等的速度运行时，一切都是错误的。解析器尝试第一个替换相等-

$ 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'

如果变量是唯一的标记，同样的推理是：第一个备选方案等于-

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

如果78是唯一的标记，请执行相同的推理：第一个替代方案等于-

现在，让我们将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'

第一个备选方案等于-

现在，让我们使用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]

输入与语法相对应，没有更多消息。