[antlr-interest] Tree Rewriting: Enumerate all possibilities to match

nafur nafur42 at gmail.com
Tue Jul 31 06:33:08 PDT 2012

Hi all,

I'm performing tree rewrites to manipulate my ASTs, however I have rules
that I want to apply only once (i.e. if there are multiple possibilities
to apply this rule within my AST, I want to apply it only in one place).

More general, I'm searching for a way to somehow enumerate all
possibilities to apply a bottomup rule on a tree.

With [1] I figured I have to write my own downup method. This is what I
got so far:

public Object downup(Object t, final int skip) {
	TreeVisitor v = new TreeVisitor(new CommonTreeAdaptor());
	TreeVisitorAction actions = new TreeVisitorAction() {
		public int skips = skip;
		public Object pre(Object t) { return t; }
		public Object post(Object t) {
			Object res = applyOnce(t, BaseTreeRewriter.this);
			if (res == t) return t;
			if (skips != 0) res = t;
			return res;

I try to apply the rule, if it doesn't change anything, I just return t;
If it changed something, but skips is not zero yet, I drop the result.
If skip is zero, I "use" the match.

However, I have the problem that for matches that I want to skip, the
actions in the rule are executed...

How should one implement this? Is there a way to test, if a rule can be
applied without actually applying it?


[1] http://www.antlr.org/wiki/display/ANTLR3/Tree+pattern+matching

More information about the antlr-interest mailing list