[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