antlr left recursion for nesting boolean expressions

Question

I am writing an antlr grammar in which I'd like to be able to have nested expressions, which can be either "simple" expressions or boolean expressions (with optional parentheses). A simple expression is just one with an lhs and rhs, such as a = 5

I'd like to be able to support these types of expressions:

a = 5
a = 5 OR b = 10
a = 5 OR (b = 10 AND c = 12)
(a = 5 AND b = 10) OR (c = 12 AND D = 13)

My grammar looks like:

STRING: CHAR+;
fragment CHAR: ('a'..'z' | 'A'..'Z' | '0'..'9'); 

booleanOp: 'AND' | 'OR';
simpleExpr: STRING '=' STRING;
expr: simpleExpr | parenExpr | booleanExpr;
parenExpr: '(' expr ')';
booleanExpr: expr (booleanOp expr)+;

I'm getting an error that expr and booleanExpr are mutually left recursive. I understand why that is happening, but I'm not really sure how to work around this if I want to be able to nest boolean expressions within each other.

monty0 monty0 · Accepted Answer · 2013-05-09T19:16:21

On the homepage of www.antlr.org you can see this sample grammar:

grammar Expr;
  prog: (expr NEWLINE)* ;
  expr: expr ('*'|'/') expr
  | expr ('+'|'-') expr
  | INT 
  | '(' expr ')' ;

A little editing and it will be what you need. This is for ANTLR 4. Which version are you using? I'm sure every version of ANTLR has an expression grammar sample.

antlr left recursion for nesting boolean expressions

1 Answers