[antlr-interest] CommonTree & Tree grammar versus DIY

Terence Parr parrt at cs.usfca.edu
Thu Aug 21 15:51:39 PDT 2008

On Aug 21, 2008, at 3:33 PM, Andy Tripp wrote:
>> Apparently you've never made a cycle in a tree before ;)
>> Recursive/self-similar data structures *ARE* more difficult to alter
>> properly than a List; by hand anyway.
> Hmm. I guess I just don't see it.
> A List of Person objects doesn't get much harder when the Person class
> has a "Person mom" field. Sure, you can accidentally create a cycle,  
> but
> you can also accidentally make the same mistake with a List (e.g.
> having a "next" pointer in a linked list point somewhere invalid, like
> to itself).

OnlyIf you have not found a library to implement List, right?

>> For lang X to X, morphing trees
>> is ok but altering language makes each new pass have to match a new  
>> kind
>> of tree.
> No, it doesn't. There is no "new kind of tree" -

well, it was assumed you knew I meant different structure. obviously,  
I always make a single node class so all nodes are always of the same  

> it stays a tree data structure
> always. It's the ANTLR treewalker implementation that makes it seem  
> like there's
> "something new" going on.

Actually, you are trying to pretend that there is no new structure.  
But, as you have pointed out to me many times you have to do all sorts  
of weird matching to try the test for the new possibilities. This is a  
new structure. Yes, you are parsing the same kind of raw elements, but  
the structure is different. Structure imparts meaning. If this were  
not true, we would not parse at all. We would simply do "while more  
tokens, consume". That is not recognition or it without recognition  
you can do nothing. If you change the language, you must change the  
code that does the recognition. I believe you simply didn't get my  

> The "shape" of the tree is changing, just as any
> other data structure's "shape" changes over time.

Oh, so you did make that assumption. strange.

> It's the ANTLR treewalker
> forcing you to provide a "snapshot" of that evolving shape that's  
> making
> it seem like the tree is somehow now of "a new kind of tree".

Yes. How could it be otherwise, if you are walking the entire tree? If  
you choose to parse only those parts of the tree that have not  
changed, then you don't have to change your recognition rules or  
rewrite rules in your case. In your case, you have to make many many  
passes over the input so you probably just ignore what has been  
rewritten if it is written to a new language. If you need to parse  
things that have been transformed from one language to the other, how  
do you propose to recognize them without rules to handle the new  
constructs?  Andy, I respect the work you have done immensely in  
rewriting, but I just never understand your perspective on tree walking.


More information about the antlr-interest mailing list