[antlr-interest] summary of trip to Montreal/SableCC land

Terence Parr parrt at cs.usfca.edu
Mon Nov 15 09:44:43 PST 2004


On Nov 15, 2004, at 9:07 AM, Alexey Demakov wrote:
>> First, people are so in love with objects that
>> EVERYTHING must be a class.  It's amazing we got any work done before
>> oo, right? ;)
>
> Personally, I think that in Java vs C battle automatic memory 
> management
> is more important than objects :)

Agreed.  I won't program without GC anymore. ;)

>> Also, when doing translations, it is the tree structure
>> that is important.
>
> Agree. So, let's specify it! :)

you bet!  I have been doing so for over 10 years; I call them tree 
grammars :)

>> need to make this a separate object type just to access an overridden
>> method like "action()" because it is the action location in the 
>> grammar
>
> The main reason to have separate class for each node is reliability.
> With type checking you can be sure that every tree that can be 
> constructed
> corresponds to syntactically correct input program.

By "type checking", you mean grammatical structure.  Grammars are 
particularly good at structure I think you'd agree otherwise you 
wouldn't be using antlr for generating parsers. ;)

> After all, tree can be constructed not only by parser, but from XML 
> serialization or
> from another tree after some transformation. In this case we will 
> notice
> corrupted tree only at run-time.

You will only notice this at run-time no matter what if you have 
actions in your grammar that constructs trees.  Only statically 
specified trees (ala sablecc) can be checked statically.  Seriously 
though, this is a pretty limiting constraint.  The "meaning" of the 
input often requires different tree structures than strict syntax would 
imply else we'd all use parse trees not ASTs.

Further, and more importantly, complex translators require multiple 
passes over a tree that usually means altering the structure.  Your 
static checking is gone the minute you jump to actions (whether a 
grammar or a visitor) to manipulate the tree.  And, w/o actions of 
course you cannot translate ;)

>> that gives you the proper "event trigger".  It has context (where it
>> lives in a rule) and you can have actions communicate easily whereas
>> visitor actions are like "incommunicato islands".  This is why Etienne
>
> You have access to children and parent of node that is parameter of 
> visitor action.
> What else do you need?

Long distance info.  For example, you are deeply nested in an 
expression node.  What is the surrounding method name?  It is very 
inefficient to walk upwards in the tree each time you need info.  You 
should set a value in the method node action that is visible anywhere 
below.

>  Do you mean that it is not easy to locate node
> within parent's children?

No, just inefficient. :)

>  But I don't remember such situation in real life.
> In any case, context information can be passed through fields of 
> visitor.
> It solves the problem.

Almost.  You need a stack of them.  Imagine that you need a reference 
to the declarations for each {...} block.  Now if you set an instance 
variable, what happens when you nest {..}?  Clearly you need a stack.  
Why do this by hand?  Believe me, in my experience, you need context 
and generally you need it to nest.

>> particularly liked my dynamically-scoped attributes thingy (although I
>> think I need to give Gary Funck credit; he asked for these back in my
>> SORCERER days a decade ago--i think he has trouble remembering if he
>> invented them).  Visitors find it VERY difficult to pass in context;
>> can't use parameters, right?  You'd have to make each action method
>> have the combined set of parameters you need to pass.
>
> In fact, I don't think that visitor is the best solution.
> Recall the meaning of visitor pattern - to have virtual methods for 
> tree nodes
> without modification of node classes. There is another solution for 
> this problem
> - AOP-like powerful generation technics that allow to generate what 
> you need
> from clear description.

Yep, i am fond of the idea of aspects, but I'm not sure how I can use 
them effectively in antlr.  I use the "poor man's" version all the 
time, where I put behavior.action() code everywhere and then pass in a 
behavior object.

> Clear description is important - how to reveal tree structure to team 
> developers?

Certainly not by making coders read a manually written or auto 
generated parser.  Grammars are perfect.  Recall that I started out 
putting tree structure comments in my methods that handled trees only 
to realize I should make these suckers executable 
documentation--sorcerer was born. :)

>> Anyway, I should really flesh all this out in an article--and describe
>> why you need tree grammars more to get people using them.  First, I
>> suppose I need to get a less buggy tree parser going ;)
>
> Worth to read :)

I hope so.  I certainly have picked up some "best practices" ideas over 
the years. :)

> Btw, I begin to understand that separate tree description is closer to 
> ANTLR
> tree parsers than I thought before...

:)  Hooray!

> But what if I need more that one pass over tree - should I repeat tree 
> grammar
> in each tree walker? I don't like to have same info more than in one 
> place.

Agreed.  You have identified something that uses up lots of my spare 
"CPU" time.  One solution is to simply use a tree grammar to call 
action methods and then you can subclass the tree parser. Now, you are 
back to the visitor idea and don't have to repeat the tree, however, 
this is unsatisfying as I've said.  I believe that we need a model 
where you can cut/paste a grammar to multiple phases and then push 
updates to all phases when the structure changes.  In reality, this is 
called RCS (diff3).  For papers, i'll make up some fancy name ;)

Good discussion!  I think I'll post this conversation as a mini article 
on the antlr.org site.

Ter
--
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com
Cofounder, http://www.knowspam.net enjoy email again!





 
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/
 





More information about the antlr-interest mailing list