CODEWITHSUNDEEP
regexantlrgrammarantlr4
Javier Rivera
Javier Rivera

Reputation: 89

is antlr parser greedy?

I don't understand why this antlr4 grammar

grammar antmath1;

expr
    :   '(' expr ')'                         # parensExpr
    |   op=('+'|'-') expr                    # unaryExpr
    |   left=expr op=('*'|'/') right=expr    # infixExpr
    |   left=expr op=('+'|'-') right=expr    # infixExpr
    |   value=NUM                            # numberExpr
    ;

NUM :   [0-9]+;
WS  :   [ \t\r\n] -> channel(HIDDEN);

works properly: antlr tree produced by -(5+9)+1000; result=986

but why this one:

grammar antmath;

expr
    :   '(' expr ')'                         # parensExpr
    |   left=expr op=('*'|'/') right=expr    # infixExpr
    |   left=expr op=('+'|'-') right=expr    # infixExpr
    |   op=('+'|'-') expr                    # unaryExpr
    |   value=NUM                            # numberExpr
    ;

NUM :   [0-9]+;
WS  :   [ \t\r\n] -> channel(HIDDEN);

fails: antlr tree produced by the same expression; result=-1014

I expect the first grammar1 (which outputs correct result) to produce the same result as grammar2 (wrong output). The reasoning behind this: the only rule that admits '-' as first token is #unaryExpr so parser generated by any of the grammars would try to match that rule first. Then, provided the parser is greedy (for any of the two grammars), I would expect it to take the "(5+9)+1000" as a whole and match it with expr which it does because it is a valid expr.

where's the fault in my reasoning?

Upvotes: 2

Views: 923

Answers (1)

that other guy
that other guy

Reputation: 123550

the grammars would try to match that rule first

It does. However, you've made unary minus have lower precedence than binary plus.

That means that the expression is being interpreted as -((5+9)+1000) instead of (-(5+9))+1000.

Upvotes: 2

Related Questions