[antlr-interest] Multiple pass tree walking Q

Terence Parr parrt at cs.usfca.edu
Wed Oct 4 10:28:29 PDT 2006


On Oct 3, 2006, at 11:23 PM, Hill, Robert wrote:

> I've pretty much gone down the multiple tree parser routes, its a  
> real pain in the ass though, as if you modify your parser, you then  
> have to modify all the tree parser grammars too. I must be missing  
> something here. :(

you are not missing anything in that it is a real problem.  But you  
are missing the tool that will make this easier.  I will be making a   
grammar diff tool that will be able to push changes forward from a  
prototypical grammar to all tree phases that derive from it.  This  
will be more of a revision control model rather than an inheritance  
model.  This tool does not exist yet.

> there must be a rule that ignores a whole branch, but i've tried  
> all sorts and haven't succeeded ,
>
> ignoreme : ^(.*) ... if only :)
>
> which is why i ended up with 3 tree parse phases. I just get this  
> nagging feeling im missing the point.

No,  Just implementation is missing this.  See my previous e-mail

> i think everyone's gone on holiday, the list is usually way busier  
> than this.
>
Nah, you are just asking really hard questions. ;)

Here is my new philosophy about translation:

Language L to L':  build a single tree structure and have multiple  
tree phases that use the same grammar but different actions.  Or, as  
we are discussing, you could have something that would skip certain  
pieces that you don't care about.  All of the phases up until last  
one will simply collect information, possibly annotating the tree  
nodes as well.  The last phase walks the tree grammar generating  
string templates that get put together and yield eventually one big  
string.  This is the approach I'm taking for Mantra.

Language L to L: if you are staying within the same language, then  
you will probably have the same AST structure.  In this case, you are  
free to manipulate the tree because the resulting tree structure will  
be identical to the existing structure.  What you want to avoid is  
having n phases each one with a different grammar.  A good example of  
a translation problem that keeps the same tree grammar but allows  
tree transformation is symbolic differentiation of polynomials.   
Every time you do a differentiation, you yield another valid  
polynomial and so your grammar will not have to change.

Ter



More information about the antlr-interest mailing list