[antlr-interest] Re: Code bloat for mulitple passes with point changes.

Bryan Ewbank ewbank at gmail.com
Mon Jun 13 14:32:15 PDT 2005


And now, for the list, ...

I've observed the same problem, and ended up avoiding the code
duplication by using an alternate construct that I think is the
"visitor" implemented in ANTLR.  It especially saves me pain when I
want to add a new operator or other node type.

doIdentityTransform
:
    ( (PLUS) => #(PLUS lhs:doIdentityTransform rhs:doIdentityTransform)
             { ... bleah ... }   /* lhs and rhs are already processed */
    | (MULT) => #(MULT lhs:doIdentityTransform rhs:doIdentityTransform)
             { ... bleah ... }   /* lhs and rhs are already processed */
    | #( . ( doIdentityTransform )* )
                                 /* no action; just drill down */
    )
;

Note that I define "high level" and "low level" tree audit passes that
have the whole structure of the tree defined, and I use these between
the other passes to catch broken operations (in debug mode, of course
;-).  For the audit passes, the rules would look something like this:

    #( op:PLUS expr expr noKids[op] )
    #( op:MULT expr expr noKids[op] )

and "noKids" throws an exception if it matches anything, thus:
    noKids[RefTreeNode op]
    : ( badnode:. { diediedie(badnode, op); } )?
    ;

Note that the skeleton for the above is:

     walker : #( . ( walker )* );    // one function call per node

I think that it might be better, because it replaces recursion with a
while loop, to do this:

     walker : ( #( . walker ) )* ;   // one function call per group-of-kids

It avoids some of the stack thrash from the "(walker)*" in the first
production as it bangs into the terminal nodes in the AST; however, it
requires a bit more explicit actions because the children are not
named.

On 6/13/05, pganelin <ganelin at mail.com> wrote:
> Problem Summary: multiple transformations passes with small changes
> results in code bloat.  Nodes to be changed are located deeply within tree.
> Description:
> In ANTLR documentation (Tree Parser Chapter) there is an example of tree
> transformation (optimizing identity operations) and I will use this
> example for illustration.
> X+0 -> X
> X*1 -> X
>
> I have multiphase transformation. During stage number N I want to do
> "identity optimization".  I can easily implement the transformation
> using visitor pattern without TreeWalker with a few lines of code. If I
> want to use TreeWalker instead I will need to duplicate (really inherit)
> the whole tree grammar file for phase N with most rules without any
> action. Only two rules (plus and multiply) have the explicit
> transformation action. The generated file would be huge, because it
> creates duplicate tree for all these grammar rules without action. As a
> result the code would be bloated and very ineffective compare with
> visitor pattern.
>
> Do I miss something or Tree Walker is not appropriate tool for such job?
> Sincerely,
>  Pavel
>
>


More information about the antlr-interest mailing list