Page Comparison

...

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

Code Block

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
    ;

...

Code Block

        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:

Code Block


$ 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.

Code Block


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:

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

Running:

Code Block


$ 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.

Versions Compared

Old Version 2

New Version Current

Key