[antlr-interest] Re: Translators Should Use Tree Grammars
Monty Zukowski
monty at codetransform.com
Mon Nov 22 13:00:42 PST 2004
Oliver Zeigermann wrote:
> On Mon, 22 Nov 2004 21:16:12 -0000, atripp54321 <atripp at comcast.net> wrote:
>
>>Only if a top-down walk of the tree is the basis of the
>>code that you need. If your code is something else (like
>>applying a series of pattern-matching rules), then
>>you have to write all the code even when using a tree grammar.
>
>
> I think this is a strong argument. When you think of natural language
> processing (or the translation Andy does) there hardly is
> one-after-the-other processing.
I found when doing my AREV translator that although I thought of my
translations as being very specific -- translate AREV case statements
into VB if-else statements, or translate dynamic array assignments into
function calls -- I would simply implement them by overriding the few
rules I needed to after subclassing from my tree grammar superclass.
This let me do the usual tree grammar tricks like keeping track of the
context. In one case I had to distinguish between the root of an
expression and sub-expressions -- this was easy in my tree grammar.
This may have not been very efficient since I was walking and building
trees for every other rule even though I didn't need to. The building
far outweighs the walking, and Loring has been addressing that issue
with his new tree code.
The dominant academic approach seems to be to let you define a "rule
soup" and the engine figures out which rules must happen before which
other rules. This prolog-type approach leads to very hard to debug
translators.
I agree that pattern-matching with ANTLR grammars is not fun, because
you do the actual testing in actions or semantic predicates. However,
this is actually implemented as a tree walker in the BaseAST or
CommonAST findAll and findAllPartial methods.
In the future ANTLR could have better support of pattern matching of
trees. I can't remember any specifics right now, but I'd be surprised
if Loring hasn't already addressed it with the 2.8/3.0 tree stuff.
The thing is, once I've matched a pattern I usually want to do a
transformation on it. A natural way to do that is with templates -- one
to match, the other to transform. Please see
http://www.erights.org/elang/quasi/overview.html for some examples (I
helped flesh out some implementation details of those but it's really
the work of Mark Miller). The pattern can be written as source language
code with special markers for generic expressions or whatnot. The
translation patter could be written in code as well and translated into
a tree (assuming a parser exists) with appropriate parts copied from the
original tree to the new tree.
The main point is that I still want to specify the order of my
translations. There are some directions ANTLR could go toward making
the specification of translations easier, namely pattern matching and
substitution.
Wish I had more time to flesh this out, maybe tomorrow.
Monty
http://www.codetransform.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/
More information about the antlr-interest
mailing list