[antlr-interest] Converting Tree operands ('^' '!') to rewrite rules ( '-> ^(...)')

[Johannes Luber]

Jens Boeykens schrieb:
> Bounced on a problem:
> 
> What should be the rewrite rule for this operand rule:
> rule   :    id ('+'^ id)*;

Try this:

rule : (i1=id -> $i1) ( '+' i2=id -> ^('+' $rule $i2))*;

BTW, is your tool to create tree grammars slated to become open source?

Johannes
> 
> I can't even find one. Tried several things, and I assume you are 
> forced to use recursion, or are there other (as simple as possible) ways?
> 
> rule :  id | (id '+' rule) -> ^('+' id rule);
> rule :  | id rule | ('+' id rule);
> 
> But these rules don't parse because the first alternative is 
> unreachable in both cases. I don't understand why though... id doesn't 
> have an empty alternative or a '+'.
> 
> Jens
> 
> 2008/7/11 Jens Boeykens <jens.boeykens at gmail.com 
> <mailto:jens.boeykens at gmail.com>>:
> 
>     Hello,
> 
>     I'm a student in computer science and for the moment I'm doing
>     internship  in a  company (Sigasi <http://www.sigasi.com/>) mainly
>     working on hardware refactoring.
>     So far, I have written a program which can read a .g grammar as
>     input, parse it into a tree and automatically regenerate the grammar
>     by using a stringtemplate I have written. This regeneration allows
>     some useful things. e.g. I have written something to sort the rules
>     alphabetically using the  trees, and then  regenerate the  grammar
>     from the tree resulting in a grammar with sorted rules.
> 
>     The next step is to convert tree operands to rewrite rules. Eg.
> 
>     /rule : a b^ c d^ e;/  
>     will be automatically converted to/
>     rule: a b c d e -> ^(d  ^(b a c) e);/
> 
>     My question is: does there already exists something that I could
>     reuse (and where to find it) or can you give me some tips to achieve
>     this? The convertion will probably be done on the trees which are
>     created with my (slightly modified) ANTLRv3.g. Thus for the previous
>     example:
> 
>     /(RULE rule (BLOCK (ALT a (^ b) c (^ d) e EOA) EOB) EOR) /
>     needs to be converted somehow to
>     /(RULE rule (BLOCK (ALT a b c d e EOA) (-> (ALT (TREE_BEGIN d
>     (TREE_BEGIN b a c) e) EOA)) EOB) EOR)/
> 
>     My regenerator will then read in the second tree and thus generate a
>     grammar with a tree rewrite rule.
>     The conversion itself is not very simple so any  help is appreciated.
>     Difficulties are rules with alternatives which have complex trees:
>     /rule : (a^ | b^) c ;/
> 
>     Am I correct that rules like /rule : (a b)^ c ;   /and/ //rule : (a
>     b)! c ; /are no longer allowed? It parses but doesn't really make
>     sense in my oppinion.
> 
>     So why would I want to do all this? Well with the rewrite rules it
>     is easier to create the tree walker from a parser. This is the final
>     goal: when you have written a parser grammar for a language, you can
>     give it to my tool, and it will automatically generate a tree
>     grammar from it. Thus no need to do it manually or to create 2 grammars.
> 
>     Best regards,
>     Jens
> 
>