ANTLR rule rewrite to nested tree

Question

I'm trying to make a rule that will rewrite into a nested tree (similar to a binary tree).

For example:

a + b + c + d;

Would parse to a tree like ( ( (a + b) + c) + d). Basically each root node would have three children (LHS '+' RHS) where LHS could be more nested nodes.

I attempted some things like:

rule: lhs '+' ID;
lhs: ID | rule;

and

rule
    : rule '+' ID
    | ID '+' ID;

(with some tree rewrites) but they all gave me an error about it being left-recursive. I'm not sure how to solve this without some type of recursion.

EDIT: My latest attempt recurses on the right side which gives the reverse of what I want:

rule:
ID (op='+' rule)?
-> {op == null}? ID
-> ^(BinaryExpression<node=MyBinaryExpression> ID $op rule)

Gives (a + (b + (c + d) ) )

Answer 1

The follow grammar:

grammar T;

options {
  output=AST;
}

tokens {
  BinaryExpression;
}

parse
 : expr ';' EOF -> expr
 ;

expr
 : (atom -> atom) (ADD a=atom -> ^(BinaryExpression $expr ADD $a))*
 ;

atom
 : ID
 | NUM
 | '(' expr ')'
 ;

ADD   : '+';
NUM   : '0'..'9'+;
ID    : 'a'..'z'+;
SPACE : (' ' | '\t' | '\r' | '\n')+ {skip();};

parses your input "a + b + c + d;" as follows: