[antlr-interest] tree pattern matching and list rewriting

[Chris DiGiano]

I should have mentioned that I traced the errors to when ANTLR is
trying to replace children to affect the rewrite. The replacement
nodes all look well-formed; it's just the mechanics of actually
performing the replacement that seems broken.

Chris

On Tue, Nov 10, 2009 at 9:53 AM, Jim Idle <jimi at temporal-wave.com> wrote:
> 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
>
>
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>