[antlr-interest] 'DOWN' and <UP> tokens

[Gavin Lambert]

At 21:15 24/08/2009, Safiye Celik wrote:
>Yes, the problem was that my parser and tree grammars were not 
>consistent. And the inconsistency is about the tree of below rule 
>a:
>
>a : e (d^ e)* ;
>e : b | c! a c! ;
>
>How would I create the tree of a? I have no idea about dealing 
>with repetition of the token d, which is the root of a tree 
>itself.

It helps if you think of how the corresponding rewrite rule will 
look.  (Or, failing that, some example trees.)

Rule 'a' above can produce several different kinds of tree, but 
they form a pattern:

   1. e
   2. ^(d e e)
   3. ^(d ^(d e e) e)

etc.  In fact, this first child is pretty much equivalent to 'a' 
itself.  So you can use:

a : e
   | ^(d a e)
   ;

Or, for symmetry (or in case you get a tree from something that 
might affect the second child as well):

a : e
   | ^(d a a)
   ;

Rule 'e', however, is going to get you into trouble.  Taken in 
isolation, its tree rule would be this:

e : a | b ;

Putting that with the other rule, though, you have a cycle.  An 
'a' can be an 'e' which can be an 'a'... that just won't 
work.  You'll probably need to resolve this by keeping one of the 
'c's and making it the root node, or by adding an imaginary root.

Alternatively, you could just drop the reference to 'a' entirely; 
if you do use the symmetric version of 'a' (and don't use 'e' in 
other contexts) then it's pretty much already taken care of.  So, 
from all the above:

a : e
   | ^(d a a)
   ;

e : b ;