[antlr-interest] tree pattern matching and list rewriting
Jim Idle
jimi at temporal-wave.com
Tue Nov 10 08:53:49 PST 2009
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
More information about the antlr-interest
mailing list