[antlr-interest] avoiding infinite loop in tree rewriting

Tom Smith yotommy at gmail.com
Mon Feb 1 08:15:29 PST 2010

I could use some design help.

I have an AST that I walk with a few different tree grammars; the last
pass generates output using StringTemplate that matches the AST
structure quite well.

Now I have a new requirement: when a certain subtree is detected, I
need to generate output that largely duplicates an enclosing tree
(with one element of the output changed).

I can see two plausible approaches:

(1) Revise the AST by duplicating (and modifying) the enclosing subtree.

(2) Keep the AST the same, but have StringTemplate generate
nearly-duplicated output.

I tend to favor the first approach, because the revised AST can then
be semantically checked in subsequent passes, and the AST will
continue to match the output templates one-for-one.  However I am
encountering a problem with my current approach.  In a tree grammar
with filter=true, I have this rule:

scope {
	Predicate predicate;
	:	^(TRANSITION s1=stateName s2=stateName ab=arcBody[$s1.text])
	-> { $transition::predicate instanceof SucceededPredicate }?
	   ^(TRANSITION $s1 $s2 $ab) ^(TRANSITION $s1 $s2 $ab)
	-> ^(TRANSITION $s1 $s2 $ab)

A subrule of arcBody sets the predicate variable that is scoped to
transition.  If the value is a certain subclass, then I need to
duplicate the enclosing subtree.  (For the moment, I am deferring the
task of modifying the duplicated subtree so that the arcBody is
slightly different.)

When I execute this tree grammar, then I get into an infinite loop,
because I keep inserting subtrees that match the transition rule, and
so on.

Any suggestions?

Tom Smith.

More information about the antlr-interest mailing list