[antlr-interest] Exploit ambiguity in tree rewriter

nafur nafur42 at gmail.com
Tue May 29 03:48:30 PDT 2012


I'm using tree rewriters to manipulate formulas that are represented as
ASTs. One operation I'd like to do is: "remove any identity from a

The replacement rule I'm currently working with is the following:

topdown :
	^( MULT (before += .)* x=. (after += .)* )
	{ $x.has("IDENTITY") }?
	-> ^( MULT $before* $after* )

As you probably see, we have some ambiguity here: before and after can
both take arbitrarily many elements. If I take an AST like
^( MULT A I x ), the replacement will not match. printing some debug
output reveals, that ANTLR will only check $x.has("IDENTITY"), i.e. will
only try to match the last element in a multiplication.
(That is actually not a surprise, as ANTLR issues a warning...)

Is there any way to resolve this ambiguity in a way, such that I can
match all occurrences?


More information about the antlr-interest mailing list