[antlr-interest] Re: Please help me with homogeneous versus heterogeneous trees!

[cflowers at mindspring.com]

Alexey,

Thanks a ton for your response. I read with great interest the links you sent me. I can see how maintaining a compiler over a long term would be much easier with TreeDL. 

It is also clear that you vote strongly in favor of heterogeneous trees that name relationships. Can anyone who holds the opposite view share some thoughts? (I will search the archives later too, but right now the corporate firewall won't let me hit web pages that aren't from port 80).

I am not building a compiler. Rather, I envision a number of C# utilities, all of which might be based off of the same AST. So I am thinking of designing a general purpose AST that will become the contract all these other tools adhere to. And it is still a tough question ... homogeneous trees seem to not be "precise" enough (or self-documenting enough") to truly express what the input source says, because they don't name relationships. I guess one could name the relationships by using a lot of imaginary nodes, but that doesn't seem to be what a lot of the antlr community does (from examples and tutorials I've seen). 

So, what have you homogeneous folks learned through your experience that mitigates this itch for explicitly named relationships? Or compensates for the lack of named relationships?

THANKS.

-----------------------------------------------------------------
ALEXEY WROTE ...

Several monthes ago in this list there was the discussion about hetero vs home trees between Terrence, me and others.
You can find it in the archive of the list.

My main objection against homo trees and tree grammars was that homo trees force developers to use tree grammars.
But ANTLR require to learn its language, and it is not easy.
Terrence asked that Visitor pattern usually used to separate actions from AST description
has some drawbacks and I agreed. Visitors don't use any tool support and this is no surprise they lose to ANTLR.
But hetero tree approach with good tool support can overcome ANTLR homo trees.
There is Terrence's article written after this discussion:
http://www.antlr.org/article/1100569809276/use.tree.grammars.tml

Some time ago I've developed TreeDL - it is language and tool for heterogenous AST description.
After discussing hetero vs homo tree approach and this article:
http://www.southern-storm.com.au/treecc_essay.html
I've desided to add in TreeDL operations on trees similar to described in this article
and implemented in treecc tool http://www.southern-storm.com.au/treecc.html

I plan to release TreeDL with full documentation in August.
But if you interested, you can download beta version of TreeDL 2 from
http://sf.net/projects/treedl
with Java5 parser and AST description as example.
Of course TreeDL tool is implemented using TreeDL description of AST. :)

TreeDL homepage http://treedl.sf.net now contains outdated documentation for TreeDL 1 - without operations.
TreeDL 2 language description docbook source can be found in CVS repository:
http://cvs.sourceforge.net/viewcvs.py/treedl/TreeDL/treedl/src/docbook/
Write me if you need html or pdf version.