[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