parsing - Antlr 解析器运算符优先级

Question

考虑以下语法。我对运算符优先级有疑问，例如:res=2*a+b 具有与 res=2*(a+b) 类似的解析树。我知道问题出在哪里，但我没有想到没有相互左递归的“漂亮”解决方案。你能帮我一点忙吗？该语法与自定义访问者一起使用。

grammar Math;

expression: expression add=('+'|'-') expression # expressionAddExpression
            | expression mult='*' expression    # expressionMultExpression
            |'(' expression ')'  # bracketExpression
            | number                            # numberExpression
            ;
    number: INT                                                                 #int
            | '(' number ')'                                                    #bracketNumber
            | VARIABLE                                                          #var

            ;
    VARIABLE: [A-Za-z][A-Za-z0-9]*;



INT: [0-9]+;

Answer 1

来自The Definitive ANTLR 4 Reference , 5.4 处理优先级、左递归和关联性:

expr : expr '*' expr // match subexpressions joined with '*' operator
     | expr '+' expr // match subexpressions joined with '+' operator
     | INT // matches simple integer atom
     ;

The problem is that this rule is ambiguous for some input phrases. ...

This is a question of operator precedence, and conventional grammars simply have no way to specify precedence. Most grammar tools, such as Bison, use extra notation to specify the operator precedence.

Instead, ANTLR resolves ambiguities in favor of the alternative given first, implicitly allowing us to specify operator precedence.

所以只需将乘法放在加法之前即可。

文件Question.g4:

grammar Question;

question
@init {System.out.println("Question last update 1213");}
    :   line+ EOF
    ;

line
    :   expression NL
        {System.out.println("Expression found : " + $expression.text); }
    ;

expression
    :   expression mult='*' expression          # expressionMultExpression
    |   expression add=( '+' | '-' ) expression # expressionAddExpression
    |   VARIABLE '=' expression                 # expressionAssign
    |   '(' expression ')'                      # parenthesisedExpression
    |   atom                                    # atomExpression
    ;

atom
    :   INT                                     #int
    |   VARIABLE                                #var
    ;

VARIABLE : LETTER ( LETTER | DIGIT )*;
INT      : DIGIT+;

NL      : [\r\n] ;
WS      : [ \t] -> channel(HIDDEN) ; // -> skip ;

fragment LETTER : [a-zA-Z] ;
fragment DIGIT  : [0-9] ;

文件input.txt:

res = 2 * a + b
res = 2 * ( a + b )

执行:

$ grun Question question -tokens -diagnostics input.txt 
[@0,0:2='res',<VARIABLE>,1:0]
[@1,3:3=' ',<WS>,channel=1,1:3]
[@2,4:4='=',<'='>,1:4]
[@3,5:5=' ',<WS>,channel=1,1:5]
[@4,6:6='2',<INT>,1:6]
[@5,7:7=' ',<WS>,channel=1,1:7]
[@6,8:8='*',<'*'>,1:8]
[@7,9:9=' ',<WS>,channel=1,1:9]
[@8,10:10='a',<VARIABLE>,1:10]
...
[@32,36:35='<EOF>',<EOF>,3:0]
Question last update 1213
Expression found : res = 2 * a + b
Expression found : res = 2 * ( a + b )

和

$ grun Question question -gui input.txt