[antlr-interest] TreeDL news: tutorial, new releases, mailing lists

[Alexey Demakov]

From: "Tiller, Michael (M.M.)" <mtiller at ford.com>
> > From: Alexey Demakov [mailto:demakov at ispras.ru]
> > Subject: Re: [antlr-interest] TreeDL news: tutorial, new releases,
> mailing lists
> > 
> > >   I find this TreeDL system quite interesting.  It is closer to the way
> > > I think than the typical homogeneous ASTs in ANTLR.  However, I see a
> > > couple of issues when comparing it to things I've done:
> > >
> > > 2) Your visitor pattern include "visitXYZ" methods.  I've found that for
> > > many structures an "enterXYZ" and "leaveXYZ" pattern is more suitable.
> > > In fact, one might argue that anything that has children would probably
> > > benefit from the "enter-leave" pattern (also found in SableCC if I'm not
> > > mistaken).  It doesn't matter for things like evaluation, but if you
> > > want to output HTML (for example), it is nice.
> > 
> > Automatic tree traversing is not provided because there is no way to suit
> > all tasks. As you can see in interpreter visitor (step 5) I call visit
> > methods for children explicitly (through accept() of course).
> > However, code generation library allows to visit children referenced
> > in patterns:
> > 
> > public void visitBinaryExpr( BinaryExpr node )
> > {
> >     txt( "${left} ${Sign:sign} ${right}" );
> > }
> > 
> > Results of visit method for left and right children will be substituted
> > automatically.
> 
> Well, regarding the visitor pattern there are really two issues here.
> First is the interface of the visitor.  The interface defines what
> operations are involved.  This is where I think the "enter" and "leave"
> methods would be preferable to a "visit" method for anything that has
> children.  This has nothing to do with the tree walking itself (i.e. the
> 'accept' method invocations), it just provides a comprehensive list of
> methods associated with each node type.  Looking at the documentation
> you mentioned I see that TreeDL appears to do this part (although it is
> restricted to 'visit' methods).

If you don't mind to write enter/leave in different classes, this pattern can be
implemented using two visitors. Generated tree walker will be like this:

class EnterLeaveTreeWalker implements TreeVisitor
{
    TreeVisitor enterVisitor;
    TreeVisitor leaveVisitor;

    // for each node
    void visitNode( Node node )
    {
        node.accept( enterVisitor );
        // walk children
        node.accept( leaveVisitor );
    }
}
 
> The second part is the tree walking part.  Here it is possible to write
> tree walkers automatically but you have to choose a pattern (e.g.
> depth-first).
> 
> My suggestion is to look at SableCC.  It does both of these things and
> they I believe their scheme also allows for users to modify tree walkers
> or create whole new ones with minimal effort.  It would be great if you

Of course, user can extend tree walker class and change order of traversal
for some nodes.

> could provide much of the same functionality in your library.  If I
> recall correctly, SableCC does something slightly different from your
> scheme because the traversal pattern is not written into the node
> definitions (I forget exactly what they do though).
> 
> > May be it is good idea to have a library of tree walker generators for
> > particular  cases.
> 
> Precisely.  I suspect this will change the way you handle 'accept'
> methods.  You would have to look at SableCC to see how they achieve
> this.

IMHO, accept() always should call right method of visitor only. All other 
work can be done by tree walker as in above example.

> How do you deal with C# vs. Java differences?  (just curious...always an
> issue for high-level schemes, like TreeDL and ANTLR, that allow embedded
> code).  Do you just digest everything between the {}s and pass it
> straight through?

TreeDL uses different lexers for embedded code. It depends on value of
tree property translate.language. Thanks to ANTLR parser-like lexers :)
it is possible to count balance of { ... } and return whole embedded code 
as one token when final } is found. Java and C# share the same lexer
but may be in the future for other languages will be used different lexer.
At least, it is possible.
Lexer class for each language is specified in configuration file, so new 
languages can be added without modification of existing TreeDL tool code.

> I'm not sure I found Calc.java.  That probably would have answered most
> of these questions.  Sorry about that.

No, it's my mistake. Maven doesn't generate xref for generated Java files,
I found it answering your message :)

TreeDL generated code is well-formatted and easy to read. If you are not 
sure what was generated - just inspect it.

> > > 5) It isn't clear what the purpose of the "Syntax Grammar" section
> is.
> > > How is this used?  It seems like the tree definition + ANTLR grammar
> is
> > > pretty complete.  I don't see what the .bnf file is needed for.
> > 
> > As I mentioned in one of previos messages, we have BNF tool that
> generates
> > syntax tests
> > from .bnf file. But primary usage of this file is documentation - it
> is
> > useful if language design
> > and parser implementation are done by different persons.
> 
> Interesting.  So in some sense it provides independent validation of the
> parser?  Does it generate cases to exercise all possible syntax
> combinations or something?

Yes :) If you have some formal specification of your program, there are two
ways to implement it without errors:
1. Generate it from specification. It is not always possible, but if can 
be done, generated programs do exactly what was specified (assuming that 
generator/translator doesn't contain errors).
2. Generate tests from specification and make sure they are passed.

If BNF of grammar is not suitable for parser generation, it should be tuned
to be processed by parser generator. To be sure that source and modified
grammars describe the same language, tests can be generated from source BNF
(because test generation tool doesn't put limitations on BNF).

Generated set of test cases covers all alternatives in all grammar rules.

There is agreement that BNF tool will be published as open source,
but I can't say exact date.

> > > 6) Your tree directive seems to be used to indicate what package the
> > > eventual definitions will be included in.  Why not use the word
> > > "package" instead of "tree".  To me, "tree" implies it has something
> > > to do with the data structures themselves rather than just their
> > > location in the package hierarchy.

I've just noticed that tree name defines not package name, but full name of
top level class containing all node classes.

> > TreeDL tries to be as language independent as possible. So "package" is
> > not good from my point of view.
> > In fact it should be not "tree" but "tree desription" but it is much
> > longer :(
> 
> Well, package is a pretty generic term.  Actually, it is used in all
> languages that I'm currently working with (Java, Python and Modelica).

I have to use C# almost as often as Java. It has namespaces instead of packages.
So for me "package" is Java thing. :)
I'm planning to extends TreeDL with basic types such as object, string, bool,
int etc, and their names propably will be borrowed from C#.

Regards,
Alexey

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




 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
    antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/