ANTLR Operator Precedence

Question

How is operator precedence implemented in ANTLR?

I'm using the XText/Antlr package at the moment.

Edit:

I did what sepp2k suggested, and operator precedence works now, but stuff like 3 +* also work now. The operators are basically "falling through" the tree.

Also, I tried the C grammar on ANTLR's website and the same thing happened in ANTLRworks.

Anyone know what the issue is?

BinaryExpression:
  'or'? AndOp; //or op

AndOp:
  'and'? ComparisonOp;

ComparisonOp:
  ('>'|'<'|'>='|'<='|'=='|'~=')? ConcatOp;

ConcatOp:
  '..'? AddSubOp;

AddSubOp:
  ('+' | '-')? MultDivOp;

MultDivOp:
  ('*' | '/')? ExpOp;

ExpOp:
  '^'? expr=Expression;

The call to Expression should probably be between '(' and ')'. Also your operators all seem to be missing a left operand. — sepp2k, Sep 21 '09 at 21:22
I fixed it by using the method found in my comment. Also, the left operand has been moved to the 1st expression to prevent left-recursion. — jameszhao00, Sep 21 '09 at 22:09

sepp2k · Accepted Answer · 2020-09-05T09:07:42.417

15

With Xtext / ANTLR 3 you encode the precedence in the grammar rules like this:

Expr:  mult ('+' mult)* ;
Mult:  atom ('*' atom)* ;
Atom:  INT | '(' expr ')' ;

This would parse "1 + 2 * 3 + ( 4 * 5 + 6)" as "(1 + (2 * 3)) + ((4 * 5) + 6)"

edited Sep 05 '20 at 09:07

answered Sep 20 '09 at 19:18

sepp2k

363,768
54
674
675

Maybe I could do stuff like AndOp: ('and' Expression) | ComparisonOp – jameszhao00 Sep 21 '09 at 21:03
To clarify the more detailed a grammar rule will match the greater its precedence. In the example above "expr -> multi -> atom *" is more detailed then the path to the plus sign. Therefore the * path has precedence. – Th 00 mÄ s Nov 23 '12 at 13:40

score 3 · Answer 2 · edited May 29 '18 at 12:50

3

Since you use Xtext, I'd recommend to use the action concept of Xtext. That is, a simple expression grammar would typically look similar to this one:

Sum: Product ({Sum.left=current} operator=('+'|'-') right=Product)*;
Product: Atom ({Product.left=current} operator=('+'|'-') right=Atom)*;
Atom: Number | Paren;
Paren: '(' Sum ')';
Number: value=INT;

Please have a look at the docs for details.

edited May 29 '18 at 12:50

thSoft

21,755
5
88
103

answered Apr 26 '11 at 20:13

Sebastian Zarnekow

6,609
20
23

ANTLR Operator Precedence

2 Answers2