Uncategorized

ANTLR Operator precedence grammar

This is snipper of my ANTLR grammar for parsing expressions with operator precedence,
By default the expressions are evaluated left to right which in some cases may produce undesired results, in order to fix that use of left and right parenthesis is required.

For example this two expressions will be evaluated differently

3 > 2 > 1
3 > (2 > 1)

Precedence


&&
||
< > <= >=
^
*/
+-

Grammar

According to ANTRL author currently we need a new rule for each precedence , which make is really messy but its not too bad after you get a hand of it. This grammar includes rewrite rules to generate our Abstract Syntax Tree(AST)

expression 
	: subExpr -> ^(EXPR subExpr)
	;
 
subExpr : logicalAndExp (addSubtractOp^ logicalAndExp)*
	;	
 
logicalAndExp
	: logicalOrExp (multiplyDivideOp^  logicalOrExp)*	 
	;
 
logicalOrExp
	: comparatorExp (CARET^  comparatorExp)* 	
	;
 
comparatorExp
	: powExp (comparatorOp^  powExp)* 	
	;
 
powExp 	: multExp (BARBAR^   multExp)*  
	;
 
multExp	
	:  expressionAtom (AMPAMP^ expressionAtom)*
	;
 
expressionAtom
	: 
	|   NUMBER
	|  ( LPAREN! subExpr^ RPAREN! ) 
	|   VARNAME
	|   function 
	;
 
 
addSubtractOp 
	:	PLUS
	|       MINUS
	;    
 
multiplyDivideOp 
	:	STAR
	|       SLASH
	;    
 
comparatorOp 
	:	GT
	|       LT
	| 	GTE
	|	LTE
	|	NEQ
	;

Abstract Syntax Trees

As stated before following two expression produce two different AST, ignore the semantics of the operators as they are only to show proper AST construction.

3 > 2 > 1
3 > (2 > 1)



Here is a expression parsed left to right

SET @me = 1+2+3*2

Here is a more complex expression that shows precedence and parenthesis operations

SET @me = 1*(2*3 + 3*2)/5+1

I think that for next post I will show on how to evaluate given expressions, also I am always looking for suggestions and comments

2 thoughts on “ANTLR Operator precedence grammar

Leave a Reply

Your email address will not be published. Required fields are marked *

* Copy This Password *

* Type Or Paste Password Here *