Antlr解析器运算符优先级 [英] Antlr parser operator priority

问题描述

请考虑以下语法.我在运算符优先级方面遇到问题，例如:res=2*a+b具有与res=2*(a+b)类似的解析树.我知道问题出在哪里，但是我想到没有相互左递归的美丽"解决方案.你能帮我一下吗?语法与自定义访问者一起使用.

Consider the following grammar. I have issues with the operator priority, for instance: res=2*a+b has a similar parse tree as res=2*(a+b). I know where the problem is, but no "beautiful" solution without mutual left recursion comes to my mind. Can you please help me out a little? The grammar is used with a custom visitor.

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]+;

推荐答案

来自权威的ANTLR 4参考，5.4处理优先级，左递归和关联性:

From The Definitive ANTLR 4 Reference, 5.4 Dealing with Precedence, Left Recursion, and Associativity :

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.

相反，ANTLR解决了模棱两可的问题，转而采用了给定的替代方案 首先，隐式允许我们指定运算符优先级.

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

因此，只需将乘法放在加法之前即可.

So simply put multiplication before addition.

文件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

这篇关于Antlr解析器运算符优先级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！