[antlr-interest] Re: Translators Should Use Tree Grammars
lgcraymer
lgc at mail1.jpl.nasa.gov
Fri Nov 19 16:29:54 PST 2004
Well, I hassled Ter about his under-analyzing what could and could not
be done with visitors, so I feel perfectly free to complain that you
have mis-analyzed what can and can't be done with trees.
First of all, your "tree library" description and examples are exactly
the sort of thing that one does with a tree walker and cannot be done
generically by hand (declarations have syntax and are identified by
subtree structure--syntax and semantics vary across languages, so
defining a canonical structure can be difficult).
"getAllGlobalVars()" is easily done as a tree walker pass; I do that
sort of thing as a matter of routine unless I have to worry about
speed, and I'm hardly alone in that. The renaming is then just a
second pass. Your "bottom up" algorithm is messier (findDeclaration()
will be pretty ugly) and will be slower than the approach of
constructing symbol tables during a tree walk and then checking
VAR_REFS against the local and global symbol tables as they are
encountered.
I don't understand your TreeStack. It sort of sounds like an
attribute stack, but not quite.
As to the multiple passes: multiple tree walker passes are the norm,
not something that is difficult to do. That is one of the real
strengths of ANTLR syntax trees, and is a feature that separates ANTLR
from translator generators that use parse trees. The first
applications of SORCERER involved a 13-pass FORTRAN translator that
Ter did and a 7-pass Pascal-to-Ada translator by Gary Funck.
Your pretty-printer example is the sort of thing that can be done with
either a visitor or tree walker without much trouble; in the latter
case, I would usually either factor out the sets of alternative node
types so that the actions are not much different than your case
statement and are clustered in only a few rules or use a heteroAST
with type-specific toString() variants.
In your "Limitations" example, you manually match a subtree and decide
how to print accordingly. The equivalent tree snippet is something like
ad :
#( ARRAY_DECLARATOR
( { out.print("["); } e:EXPR { out.print(e.toString() + "]"); }
| i:ID { out.print(#i.toString() + "[]"); }
)
)
;
Note that you can put actions in reasonable places--they won't execute
unless matching is successful.
In short, I think that you still haven't yet grokked the power of trees.
--Loring
--- In antlr-interest at yahoogroups.com, "atripp54321" <atripp at c...> wrote:
>
> Terence,
>
> Here's my 8-page-or-so furiously written diatribe against
> treewalkers:
> http://jazillian.com/antlr/trees.html
>
> I don't address the Visitor pattern, and I haven't even finished
> reading your page and the posted responses. I just thought I'd
> get my early, uninformed thoughts down on paper first.
> Wouldn't want to let well-argued points that you gurus
> make make get in my way of opinions :)
>
> Andy
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