[antlr-interest] tree pattern matching and list rewriting

[Jim Idle]

Did you try using cardinality in your $e{n} references? Such as $e* $e+ etc? I have not tried that, but it is what my first attempt at typing in would have been ;-)

Jim

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Chris DiGiano
> Sent: Tuesday, November 10, 2009 6:01 AM
> To: antlr-interest at antlr.org
> Subject: [antlr-interest] tree pattern matching and list rewriting
> 
> 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:22
> 5)
>   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:22
> 5)
>   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(CommonTreeAdap
> tor.java:165)
>   at
> org.antlr.runtime.tree.CommonTreeNodeStream.replaceChildren(CommonTreeN
> odeStream.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:7
> 9)
>   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)
>  */
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-
> email-address