[antlr-interest] Contextual Tree Matching

Gerald Rosenberg gerald at certiv.net
Thu Oct 22 22:23:05 PDT 2009


At 08:47 PM 10/22/2009, Joseph Cottam wrote:
>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.

So, the rule would be:

matchRule: { hasAncestor(UPDATE) && !hasAncestor(QUERY) }? RULE ;

Or, if queries and update don't nest:

matchRule: { hasAncestor(UPDATE) }? RULE ;


The semantic predicate convenience methods are implemented in the 
members block or in a superclass:

@members{
/**
  * Determines whether the ancestor Tree node exists.
  *
  * @param the ancestor token <code>type</code> to search for
  * @return <code>true</code> if the token is an ancestor, 
<code>false</code> otherwise
  */
public boolean hasAncestor(int ttype) {
return getAncestor(ttype) != null;
}

/** Walk upwards and get first ancestor with this token type. */
public Tree getAncestor(int ttype) {
Tree t = (Tree) input.LT(1);
t = t.getParent();
while (t != null) {
if (t.getType() == ttype) return t;
t = t.getParent();
}
return null;
}

/**
  * Determines whether the parent Tree node exists.
  *
  * @param the parent token <code>type</code> to check
  * @return <code>true</code> if the token is the parent, 
<code>false</code> otherwise
  */
public boolean hasParent(int ttype) {
Tree t = (Tree) input.LT(1);
return (t != null && t.getParent().getType() == ttype);
}
}



>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?

There has been discussion of more "complicated" convenience methods, 
but so far hasAncestor and hasParent have proven sufficient (BTW, 
these methods are planned to be implemented in TreeParser in the next 
version of Antlr).  If you have a use case where they are not 
sufficient or appropriate, please post to discuss.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20091022/65cdbb80/attachment.html 


More information about the antlr-interest mailing list