[antlr-interest] TreeDL way

Alexey Demakov demakov at ispras.ru
Wed Mar 15 01:56:16 PST 2006

From: "Andy Tripp" <antlr at jazillian.com>
> Alexey Demakov wrote:
>> My project, TreeDL (http://treedl.sf.net), is mentioned in the article 
>> "Manual Tree Walking Is Better Than Tree Grammars" by Andy Tripp. I 
>> generally agree with this statement
>> but can't agree with the context:
>>> The mapping from one AST structure to another is quite complex
>>> (see XSLT, TXL, or TreeDL for example), and a single BNF-like grammar 
>>> doesn't capture it.
> Hi Alexey,
> Yea, I guess I shouldn't mentioned TreeDL. Thanks for correcting that - 
> I'll take it out.
> As you can see, I was just trying to list a few technologies relating to 
> tree-transformation.
> As for the rest of your comments, I just have one place where I'm very 
> sceptical:
>> 2a. It is source of code generation. You need not write depth-first
>> walker by hands and update it on each AST change - just re-generate it.
> I'm not sure exactly what you're claiming here. You're not saying that, 
> for example,
> I could change ANTLR to produce a different AST structure for Java code 
> input,
> and have whatever AST-processing I've written still work correctly, are you?
> I mean, if the AST structure changes, whatever code is written that does 
> something
> with that AST (whether just print it, change it, or whatever) is now broken.

Of course, if your code is not generated, it can be broken. But I'm saying
about base classes that are fully defined by AST structure.
For example, depth-first walker that calls user methods in each node, can be 
generated automatically. User methods can require manual update.

The main problem is to find out when user code is broken.
For example, if you write your visitor as an inheritor of generated empty visitor,
after creation of new node type empty visitor will be re-generated. And you
will not have any messages telling that your visitor probably should be updated
to process new node type!

It is one of the main disadvantages of tree processing in general purpose programming
language (I'm thinking about Java, but the problem exists in other languages, may be not in all).
So, we need tool support to make additional checking, specific for our domain,
for our data structures. I contend that a set of tree node types allowed in AST
should be considered as specific data type with specific operations.
For example, when you are making switch by node type: switch(ast.getType())
you implicitly suppose that node type belongs to right AST structure,
because node type is unique only within AST structure.
So, we can talk about operations on AST that must be defined for eash node type in AST structure.
Or about partial operations on AST that must be defined for some node type
and all its inheritors in AST structure.
But in general-purpose programming language we have no support for such data types
and can't check that operation is defined correctly (on each required node type).
Simple domain-specific language (for example, TreeDL) solves the problem.


Alexey Demakov
TreeDL: Tree Description Language: http://treedl.sourceforge.net
RedVerst Group: http://www.unitesk.com

More information about the antlr-interest mailing list