Example tree rewriting with patterns

So, let's do some rewriting using the pattern matching filter=true mode. Again, the VecMath.g parser will build trees but we'll avoid building an entire tree grammar. We'll focus on some patterns we want to rewrite.

Here's the grammar to build trees.


grammar VecMath;
options {output=AST;} // we want to create ASTs
tokens {
    MULT='*';
    SHIFT;    // needed during simplification
    VEC;      // define imaginary VEC for vector literal
}

prog:   stat+ ;                         // build list of stat trees
stat:   ID '=' expr  -> ^('=' ID expr)  // '=' is operator subtree root
    |   'print' expr -> ^('print' expr) // 'print' is subtree root
    ;

expr:   multExpr ('+'^ multExpr)* ;     // '+' is root node

multExpr
    :   primary (('*'^|'.'^) primary)*  // '*', '.' are roots
    ;

primary
    :   INT
    |   ID
    |   '[' expr (',' expr)* ']' -> ^(VEC expr+)
    |   '(' expr ')'             -> expr
    ;

ID  :   'a'..'z'+ ;
INT :   '0'..'9'+ ;
WS  :   (' '|'\r'|'\n')+ {skip();} ;

And now, let's distribute scalar-vector multiplies. 4*[1,2] -> [4*1,4*2].


tree grammar Simplify;
options {
    tokenVocab=VecMath;      // use tokens from VecMath.g
    ASTLabelType=CommonTree; // we're using CommonTree nodes
    output=AST;              // build ASTs from input AST
    filter=true;             // tree pattern matching, rewrited mode
}

topdown
    :   ^('*' INT ^(VEC (e+=.)+)) -> ^(VEC ^('*' INT $e)+)
    ;

bottomup
    :  ^('*' a=. b=INT {$b.int==0}?) -> $b // x*0 -> 0
    ;

Give it a shot:


        VecMathLexer lex = new VecMathLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lex);
        VecMathParser g = new VecMathParser(tokens);
        RuleReturnScope r = g.prog();   // launch parser by calling start rule
        CommonTree t = (CommonTree)r.getTree();   // get tree result
        System.out.println("Original tree: "+t.toStringTree());

        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        Simplify s = new Simplify(nodes);
        t = (CommonTree)s.downup(t);
        System.out.println("Simplified tree: "+t.toStringTree());

Output:


$ cat t1
x = 4 * [0, 5*0, 3]
$ java Test < t1
Original tree: (= x (* 4 (VEC 0 (* 5 0) 3)))
(* 4 (VEC 0 (* 5 0) 3)) -> (VEC (* 4 0) (* 4 (* 5 0)) (* 4 3))
(* 4 0) -> 0
(* 5 0) -> 0
(* 4 0) -> 0
Simplified tree: (= x (VEC 0 0 (* 4 3)))
$

Now for stuff that needs to repeatedly get applied to subtrees.


tree grammar Reduce;
options {
    tokenVocab=VecMath;      // use tokens from VecMath.g
    ASTLabelType=CommonTree; // we're using CommonTree nodes
    output=AST;              // build ASTs from input AST
    filter=true;             // tree pattern matching, rewrited mode
}

/** Rewrite: x+x to be 2*x, 2*x to be x<<1, x<<n<<m to be x<<(n+m) */
bottomup
    :  ^('+' i=INT j=INT {$i.int==$j.int}?) -> ^(MULT["*"] INT["2"] $j)
    |  ^('*' x=INT {$x.int==2}? y=.)        -> ^(SHIFT["<<"] $y INT["1"])
    |  ^(SHIFT ^(SHIFT e=. n=INT) m=INT)
       -> ^(SHIFT["<<"] $e INT[String.valueOf($n.int+$m.int)])
    ;

Test code:


        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        Reduce red = new Reduce(nodes);
        t = (CommonTree)red.downup(t);

Running:


$ cat t2
x = 2*(3+3)
$ java Test2 < t2
Original tree: (= x (* 2 (+ 3 3)))
(+ 3 3) -> (* 2 3)
(* 2 3) -> (<< 3 1)
(* 2 (<< 3 1)) -> (<< (<< 3 1) 1)
(<< (<< 3 1) 1) -> (<< 3 2)
Simplified tree: (= x (<< 3 2))
$

I'm replacing multiply with shift left by 1 and then combining shifts.