[antlr-interest] Contextual Tree Matching

Joseph Cottam jcottam at umail.iu.edu
Thu Oct 22 20:47:27 PDT 2009


I'm working with the tree pattern matching and think it is excellent
(especially re-writing).
I have repeatedly come across the need to match trees that are descents of
other sub-trees, but have not found an elegant way to do so.

For example...
Given the tree:
  ^(GROUP
        ^(UPDATE ^(SET RULE)  ^(SET RULE))
        ^(UPDATE ^(SET RULE RULE ^(SET RULE RULE))  ^(SET RULE))
        ^(QUERY ^(SET RULE) ^(SET RULE RULE)))

I would like to match all RULE entries that are under an UPDATE but not a
QUERY.

I have come up with two solutions but I'm not happy with either and I'm
wondering if anybody else has a suggestion.

Solution #1:  Specify the nesting path...
topdown: ^(UPDATE matchSet);
matchSet: ^(SET (matchRule | matchSet));
matchRule: RULE {...}

This requires enumerating all of the paths that a value COULD be at, so
things get really ugly if a SET can contain many types of items that can
also contain RULE entries.


Solution #2:  Flag and filter
@members{boolean inUpdate = false;}

topdown
  : ^(UPDATE .*) {inUpdate = true;}
  | {inUpdate}?=> RULE -> ^(RULE NEW STUFF);

bottomup: ^(UPDATE .*) {inUPdate = false;}

The use of state makes a serialization point to flag when I am in a in my
otherwise nicely concurrent application, since there is now a global
variable of the parser called inUpdate.


This need is similar to recursive path operations in Apache Ant with **
specifier (at some depth below).
Is there a similar syntax for ANTLR contextual sub-tree matching?

Many thanks,
-Joseph A. Cottam
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20091022/d1704523/attachment.html 


More information about the antlr-interest mailing list