[antlr-interest] tree pattern matching and list rewriting

Chris DiGiano digi+antlr-interest at google.com
Tue Nov 10 06:01:14 PST 2009


I think I may have uncovered some problems with the new 3.2 Tree
Pattern Matching and rewriting a matching list of AST nodes. I get
errors when I try to:
1. Pair: match against 2 nodes in sequence and return a new parent
node that has the matching nodes as children (error: Can't set single
child to a list)
2. Duplicate: match a node and return a sequence of two nodes
containing the original node and a duplicate (error: Can't set single
child to a list)
3. Delete: match a node and remove it from the AST altogether by
returning nothing (NullPointerException)

To illustrate these problems I extended the scalar-vector
multiplication example found in the new Language Implementation
Patterns book (a wonderful source of ideas, by the way!). I created
three grammars—Pair.g, Dup.g, and Del.g—for each of the above cases.
Below are the "bottomup" rules in each. (Complete grammars and stack
traces are at the very end this message.)

pair: ^(ASSIGN id1=ID e1=.) ^(ASSIGN id2=ID e2=.)
    -> ^(PAIR ^(ASSIGN $id1 $e1) ^(ASSIGN $id2 $e2));

dup: ^(ASSIGN ID e=.) {$ASSIGN.text.equals("=")}?
    -> ^(ASSIGN["_="] ID $e) ^(ASSIGN["_="] ID[$ID.text + "2"]
{adaptor.dupTree($e)});

del: ^(ASSIGN ID .) {$ID.text.equals("x")}?
    -> ;

Unless there's something wrong with my grammars, I would claim these 3
kinds of Tree Pattern Matching operations ought to work, especially if
Tree Pattern Matching is being promoted as a kind of AWK replacement.

I was able to work around the pairing problem by patching
TreeVisitor.visit so that the invariant of the for loop continuously
recomputes the child count:
for (int i=0; i<adaptor.getChildCount(t); i++)
But I'm not familiar enough with the source to know how to neatly
solve all three problems.

Is anyone else having trouble with list rewriting? Any better workaround?

Chris

----

tree grammar Pair;
options {
    tokenVocab=VecMath;      // use tokens from VecMath.g
    ASTLabelType=CommonTree; // we're using CommonTree nodes
    output=AST;              // build new ASTs from input AST
    filter=true;             // tree pattern matching mode
    backtrack=true;          // allow backtracking if it's needed
}

bottomup
    :  pair
    ;

pair: ^(ASSIGN id1=ID e1=.) ^(ASSIGN id2=ID e2=.)
    -> ^(PAIR ^(ASSIGN $id1 $e1) ^(ASSIGN $id2 $e2));

/*
Original tree: (= x (* 4 (VEC 0 (* 5 0) 3))) (= y 6)
(= x (* 4 (VEC 0 (* 5 0) 3))) -> (PAIR (= x (* 4 (VEC 0 (* 5 0) 3))) (= y 6))
Exception in thread "main" java.lang.IllegalArgumentException: Can't
set single child to a list
  at org.antlr.runtime.tree.BaseTree.setChild(BaseTree.java:144)
  at org.antlr.runtime.tree.BaseTreeAdaptor.setChild(BaseTreeAdaptor.java:225)
  at org.antlr.runtime.tree.TreeVisitor.visit(TreeVisitor.java:36)
  at org.antlr.runtime.tree.TreeRewriter.downup(TreeRewriter.java:95)
  at PairTest.main(PairTest.java:33)
 */

----

tree grammar Dup;
options {
    tokenVocab=VecMath;      // use tokens from VecMath.g
    ASTLabelType=CommonTree; // we're using CommonTree nodes
    output=AST;              // build new ASTs from input AST
    filter=true;             // tree pattern matching mode
    backtrack=true;          // allow backtracking if it's needed
}

bottomup
    :  dup
    ;

dup: ^(ASSIGN ID e=.) {$ASSIGN.text.equals("=")}?
    -> ^(ASSIGN["_="] ID $e) ^(ASSIGN["_="] ID[$ID.text + "2"]
{adaptor.dupTree($e)});

/*
Original tree: (= x (* 4 (VEC 0 (* 5 0) 3))) (= y 6)
(= x (* 4 (VEC 0 (* 5 0) 3))) -> (_= x (* 4 (VEC 0 (* 5 0) 3))) (_= x2
(* 4 (VEC 0 (* 5 0) 3)))
Exception in thread "main" java.lang.IllegalArgumentException: Can't
set single child to a list
  at org.antlr.runtime.tree.BaseTree.setChild(BaseTree.java:144)
  at org.antlr.runtime.tree.BaseTreeAdaptor.setChild(BaseTreeAdaptor.java:225)
  at org.antlr.runtime.tree.TreeVisitor.visit(TreeVisitor.java:36)
  at org.antlr.runtime.tree.TreeRewriter.downup(TreeRewriter.java:95)
  at DupTest.main(DupTest.java:33)
 */

----

tree grammar Del;
options {
    tokenVocab=VecMath;      // use tokens from VecMath.g
    ASTLabelType=CommonTree; // we're using CommonTree nodes
    output=AST;              // build new ASTs from input AST
    filter=true;             // tree pattern matching mode
    backtrack=true;          // allow backtracking if it's needed
}

bottomup
    :  del
    ;

del: ^(ASSIGN ID .) {$ID.text.equals("x")}?
    -> ;

/*
Original tree: (= x (* 4 (VEC 0 (* 5 0) 3))) (= y 6)
Exception in thread "main" java.lang.NullPointerException
  at org.antlr.runtime.tree.BaseTree.replaceChildren(BaseTree.java:183)
  at org.antlr.runtime.tree.CommonTreeAdaptor.replaceChildren(CommonTreeAdaptor.java:165)
  at org.antlr.runtime.tree.CommonTreeNodeStream.replaceChildren(CommonTreeNodeStream.java:142)
  at Del.del(Del.java:188)
  at Del.bottomup(Del.java:83)
  at Del.bottomup(Del.java:1)
  at org.antlr.runtime.tree.TreeRewriter$3.rule(TreeRewriter.java:112)
  at org.antlr.runtime.tree.TreeRewriter.applyOnce(TreeRewriter.java:61)
  at org.antlr.runtime.tree.TreeRewriter.applyRepeatedly(TreeRewriter.java:79)
  at org.antlr.runtime.tree.TreeRewriter$1.post(TreeRewriter.java:93)
  at org.antlr.runtime.tree.TreeVisitor.visit(TreeVisitor.java:39)
  at org.antlr.runtime.tree.TreeVisitor.visit(TreeVisitor.java:33)
  at org.antlr.runtime.tree.TreeRewriter.downup(TreeRewriter.java:95)
  at DelTest.main(DelTest.java:33)
 */


More information about the antlr-interest mailing list