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?

Answer 1

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:

---

and the input:

(a * (b + C))

is parsed like: