[antlr-interest] Tree parser eats up DOWN node when navigating optional child node

[Gerald Rosenberg]

  ------ Original Message (Wednesday, August 04, 2010 5:21:33 
PM) From: Junkman ------
Subject: Re: [antlr-interest] Tree parser eats up DOWN node when navigating
optional child node
>
> You wrote "AST ^( ^( PARENT A ) B )".  Can you describe the tree this
> notates?  I can see it as a node sequence, but I don't know what tree
> structure it is describing.
>
> Thanks for the reply.
>
> Jay
>

The AST

^( ^( PARENT A? ) B? )

should implement as

( ( PARENT Token.DOWN A? Token.UP ) Token.DOWN B? Token.UP )

but is actually

( PARENT Token.DOWN A? B? Token.UP )

Because parent_a is the root of parent, the parser is (for some reason) 
not actually generating the middle Token.UP Token.DOWN sequence.  That 
explains why P and PA work, but PB and PAB do not - after matching for 
A?, the tree parser is looking for UP, but finding B.  Not sure why 
Antlr is doing this - not expected.

Changing A and/or B to non-optional does not change this behavior.

If, however, you change the parent rule to

parent : parent_a B? -> ^( M parent_a B? )  ;

where M is an imaginary token (and make the corresponding change to the 
tree grammar), all four patterns will parse and match as expected:

AST:

^( M ^(PARENT A? ) B? )

properly implements as

( ( M Token.DOWN PARENT A? Token.UP ) Token.DOWN B? Token.UP )