parsing - ANTLRルールをネストされたツリーに書き換えます

Question

ネストされたツリー（二分木に似ています）に書き換えるルールを作成しようとしています。

例えば：

a + b + c + d;

のようなツリーに解析されます( ( (a + b) + c) + d)。基本的に、各ルートノードには3つの子（LHS'+' RHS）があり、LHSはよりネストされたノードになる可能性があります。

私は次のようなことを試みました：

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

と

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

（いくつかのツリーの書き直しを伴う）しかし、それらはすべて、それが左再帰的であるというエラーを私に与えました。ある種の再帰なしでこれを解決する方法がわかりません。

編集：私の最新の試みは右側で繰り返され、私が望むものの逆を与えます：

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

与える(a + (b + (c + d) ) )

Answer 1

次の文法：

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();};

"a + b + c + d;"入力を次のように解析します。

Answer 2

試しましたか

rule: ID '+' rule | ID;

？