parsing - ANTLR规则重写为嵌套树

Question

我正在尝试制定一条规则，将其重写为嵌套树(类似于二叉树)。

例如:

a + b + c + d;

将解析为类似 ( ( (a + b) + c) + d) 的树。基本上每个根节点都有三个子节点(LHS '+' RHS)，其中 LHS 可以是更多嵌套节点。

我尝试了一些事情，例如:

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

和

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

(有一些树重写)但他们都给了我一个关于它是左递归的错误。我不确定如何在没有某种类型的递归的情况下解决这个问题。

编辑:我最近的尝试在右侧递归，这与我想要的相反:


rule:<br/>
ID (op='+' rule)?<br/>
-> {op == null}? ID<br/>
-> ^(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;”如下: