CODEWITHSUNDEEP
antlr4
Willy
Willy

Reputation: 581

Confusion about ANTLR v4 rule priority

The example from ANTLR website (https://www.antlr.org/) makes *// be higher priority than +/-, but I'm confused with the meaning.

grammar Expr;       
prog:   (expr NEWLINE)* ;
expr:   expr ('*'|'/') expr
    |   expr ('+'|'-') expr
    |   INT
    |   '(' expr ')'
    ;
NEWLINE : [\r\n]+ ;
INT     : [0-9]+ ;

Because I think it's top-down parsing, if we input 100+2*34, the *// rule should be select first, makes it higher in the parsing tree, and so the result should be interpreted as (100+2)*34. But from the resulting parsing tree on the website, it's 100+(2*34). Can someone help me to clarify this?

Upvotes: 0

Views: 462

Answers (1)

Mike Lischke
Mike Lischke

Reputation: 53582

The precedence for operators is indeed defined by the order of the alternatives in the expr rule. I assume by "higher in the parse tree" you mean the vertical position when printing the tree top-down, correct? However, when talking about the position of a tree node, you usually use the tree level (with the root being level 0). So, the deeper a node is in the tree, the higher is its position.

With that out of the way we can now look at your question: Of course the operators with lower precedence (here plus and minus) should appear at a lower level (closer to the root node), because evaluation of expressions begins at the leafs, that is, the deepest tree level.

Upvotes: 1

Related Questions