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) ) )

You have to use nested expressions since ANTLR is LL(*). See [this question](http://stackoverflow.com/questions/1452729/antlr-grammar-for-expressions?rq=1). Or you can do it in the tree parser, which may be easier/faster depending on your grammar. — , Jun 26 '12 at 21:59
If `a + b` are all child nodes, what is the root? Why don't you want the operator as root? — Bart Kiers, Jun 27 '12 at 06:49
The root node is an imaginary node. The tree structure is part of the requirements I'm working within. — midgetspy, Jun 27 '12 at 16:01

score 2 · Accepted Answer · answered Jun 27 '12 at 21:21

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:

enter image description here

score 0 · Answer 2 · answered Jun 27 '12 at 02:46

0

Did you try

rule: ID '+' rule | ID;

?

answered Jun 27 '12 at 02:46

stryba

1,979
13
19

Yes, that gives me a tree that's backwards to what I want: `(a + (b + (c + d) ) )` – midgetspy Jun 27 '12 at 15:50

ANTLR rule rewrite to nested tree

2 Answers2