[antlr-interest] Converting Tree operands ('^' '!') to rewrite rules ( '-> ^(...)')
Johannes Luber
jaluber at gmx.de
Fri Jul 11 03:05:26 PDT 2008
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
>
>
More information about the antlr-interest
mailing list