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

问题描述

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

grammar Math;表达式:表达式 add=('+'|'-') 表达式 # expressionAddExpression|表达式 mult='*' 表达式 # expressionMultExpression|'('表达式')'#括号表达式|number # numberExpression;数字:INT #int|'(' number ')' #bracketNumber|变量#var;变量:[A-Za-z][A-Za-z0-9]*；INT:[0-9]+；

解决方案

来自

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

解决方案

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.

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

So simply put multiplication before addition.

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

File input.txt :

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

Execution :

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

and

$ grun Question question -gui input.txt

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