[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