Antlr single child tree using rewrite rules

I have this formula:

negationExpr : NEGATION^* atom ;

atom

: 'a'..'z' | 'A'..'Z';

With grammer rules above, if I input formula ¬¬a, I wo开发者_运维技巧uld get this tree structure:

¬ being the root node, ¬ being left child; a being right child

However, What I would like to have is: ¬ being the root node, second ¬ being the only child of the above node a being the only child of the second ¬

Basically, I wat all the NEGATION sign have only have one child, it is possible? I know we could probabely use "rewrite rule" to restructure the tree, but I dont know how to do this.

Any help or advises is appreciated! Thanks!

Rewrite rules can follow each alternative for your parser rule.

rule :
   alt1 -> rewriteRule1
 | alt2 -> rewriteRule2
 ...
 | altN -> rewriteRuleN;

You'll find that even after your parser grammar is working, you may need to restructure it to generate the correct tree. To address your specific problem, I suggest the following:

negationExpr :
   NEGATION negationExpr 
     -> ^(NEGATION negationExpr)
 | atom 
     -> atom;

This will add a level in the tree for each negation operator. The ^ will create a root for the token immediately following the parentheses and add the result of the next negationExpr rule as the child.

Adam12's suggestion is an elegant solution. I just have one remark about your (JiandongC) code snippet, and another possible way to construct the AST.

Note that the .. (range operator) is invalid inside parser rules! You'll need to make atom a lexer rule, or do:

atom 
  :  LETTER
  ; 

LETTER 
  :  'a'..'z' | 'A'..'Z'
  ;

As to the creation of the AST, you could also let an even number of NEGATION tokens simply be ignored because - - will be positive.

negationExpr 
  :  (NEGATION NEGATION)* ( NEGATION atom -> ^(NEGATION atom)
                          | atom          -> atom
                          )
  ;

the rule above simply constructs ^(NEGATION atom) if there are an uneven number of NEGATION tokens, else atom will be created as a single node (root).