[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