Parsing expressions with subexpressions in ANTLR

Question

I am trying to parse recursive expressions in ANTLR such as:

(a + (b + C))

or

((a + b))

I read this supposed solution: ANTLR Grammar for expressions

However when I try to create a rule such as:

ParenthesisExpression: '(' (ParenthesisExpression | Expression) ')';

ANTLR complains that "Rule ParenthesisExpression is left-recursive".

How can I parse expressions that can have within themselves, subexpressions of the same form?

Don't look to closely to the post you linked to: it is littered with false information, and the grammar the OP posted doesn't even come close to being a valid ANTLR grammar. I am amazed that you managed to dig up that old (incorrect!) Q&A, while there are quite some other ones posted more recently (like: [this one](http://stackoverflow.com/questions/1931307/antlr-is-there-a-simple-example/1932664#1932664), or [this one](http://stackoverflow.com/questions/4396080/antlr-3-3-c-tutorials/4397799#4397799) geared towards C#). — Bart Kiers, Apr 07 '11 at 05:37
Or this one: http://bkiers.blogspot.com/2011/03/2-introduction-to-antlr.html — Kobi, Apr 07 '11 at 05:48

Bart Kiers · Accepted Answer · 2011-04-07T05:39:37.700

You could do something like this:

parse
  :  addExp EOF
  ;

addExp
  :  multExp (('+' | '-') multExp)*
  ;

multExp
  :  atom (('*' | '/') atom)*
  ;

atom
  :  ID
  |  '(' addExp ')'
  ;

ID    : 'a'..'z' | 'A'..'Z';

The closer you come to the atom rule, the higher the precedence: so + and - have the lowest precedence, followed by * and /, and lastly, ID and ( ... ) have the highest precedence.

It parses the input:

((a / b)) - x

as follows:

enter image description here

and the input:

(a * (b + C))

is parsed like:

enter image description here

Parsing expressions with subexpressions in ANTLR

1 Answers1