{"type":"doc","content":[{"type":"paragraph","content":[{"text":"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.","type":"text"}]},{"type":"paragraph","content":[{"text":"Here's the grammar to build trees.","type":"text"}]},{"type":"codeBlock","content":[{"text":"\ngrammar VecMath;\noptions {output=AST;} // we want to create ASTs\ntokens {\n MULT='*';\n SHIFT; // needed during simplification\n VEC; // define imaginary VEC for vector literal\n}\n\nprog: stat+ ; // build list of stat trees\nstat: ID '=' expr -> ^('=' ID expr) // '=' is operator subtree root\n | 'print' expr -> ^('print' expr) // 'print' is subtree root\n ;\n\nexpr: multExpr ('+'^ multExpr)* ; // '+' is root node\n\nmultExpr\n : primary (('*'^|'.'^) primary)* // '*', '.' are roots\n ;\n\nprimary\n : INT\n | ID\n | '[' expr (',' expr)* ']' -> ^(VEC expr+)\n | '(' expr ')' -> expr\n ;\n\nID : 'a'..'z'+ ;\nINT : '0'..'9'+ ;\nWS : (' '|'\\r'|'\\n')+ {skip();} ;\n","type":"text"}]},{"type":"paragraph","content":[{"text":"And now, let's distribute scalar-vector multiplies. ","type":"text"},{"text":"4*[1,2]","type":"text","marks":[{"type":"code"}]},{"text":" -> ","type":"text"},{"text":"[4*1,4*2]","type":"text","marks":[{"type":"code"}]},{"text":".","type":"text"}]},{"type":"codeBlock","content":[{"text":"\ntree grammar Simplify;\noptions {\n tokenVocab=VecMath; // use tokens from VecMath.g\n ASTLabelType=CommonTree; // we're using CommonTree nodes\n output=AST; // build ASTs from input AST\n filter=true; // tree pattern matching, rewrited mode\n}\n\ntopdown\n : ^('*' INT ^(VEC (e+=.)+)) -> ^(VEC ^('*' INT $e)+)\n ;\n\nbottomup\n : ^('*' a=. b=INT {$b.int==0}?) -> $b // x*0 -> 0\n ;\n","type":"text"}]},{"type":"paragraph","content":[{"text":"Give it a shot:","type":"text"}]},{"type":"codeBlock","content":[{"text":"\n VecMathLexer lex = new VecMathLexer(input);\n CommonTokenStream tokens = new CommonTokenStream(lex);\n VecMathParser g = new VecMathParser(tokens);\n RuleReturnScope r = g.prog(); // launch parser by calling start rule\n CommonTree t = (CommonTree)r.getTree(); // get tree result\n System.out.println(\"Original tree: \"+t.toStringTree());\n\n CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);\n Simplify s = new Simplify(nodes);\n t = (CommonTree)s.downup(t);\n System.out.println(\"Simplified tree: \"+t.toStringTree());\n","type":"text"}]},{"type":"paragraph","content":[{"text":"Output:","type":"text"}]},{"type":"codeBlock","content":[{"text":"\n$ cat t1\nx = 4 * [0, 5*0, 3]\n$ java Test < t1\nOriginal tree: (= x (* 4 (VEC 0 (* 5 0) 3)))\n(* 4 (VEC 0 (* 5 0) 3)) -> (VEC (* 4 0) (* 4 (* 5 0)) (* 4 3))\n(* 4 0) -> 0\n(* 5 0) -> 0\n(* 4 0) -> 0\nSimplified tree: (= x (VEC 0 0 (* 4 3)))\n$ \n","type":"text"}]},{"type":"paragraph","content":[{"text":"Now for stuff that needs to repeatedly get applied to subtrees.","type":"text"}]},{"type":"codeBlock","content":[{"text":"\ntree grammar Reduce;\noptions {\n tokenVocab=VecMath; // use tokens from VecMath.g\n ASTLabelType=CommonTree; // we're using CommonTree nodes\n output=AST; // build ASTs from input AST\n filter=true; // tree pattern matching, rewrited mode\n}\n\n/** Rewrite: x+x to be 2*x, 2*x to be x<<1, x< ^(MULT[\"*\"] INT[\"2\"] $j)\n | ^('*' x=INT {$x.int==2}? y=.) -> ^(SHIFT[\"<<\"] $y INT[\"1\"])\n | ^(SHIFT ^(SHIFT e=. n=INT) m=INT)\n -> ^(SHIFT[\"<<\"] $e INT[String.valueOf($n.int+$m.int)])\n ;\n","type":"text"}]},{"type":"paragraph","content":[{"text":"Test code:","type":"text"}]},{"type":"codeBlock","content":[{"text":"\n CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);\n Reduce red = new Reduce(nodes);\n t = (CommonTree)red.downup(t);\n","type":"text"}]},{"type":"paragraph","content":[{"text":"Running:","type":"text"}]},{"type":"codeBlock","content":[{"text":"\n$ cat t2\nx = 2*(3+3)\n$ java Test2 < t2\nOriginal tree: (= x (* 2 (+ 3 3)))\n(+ 3 3) -> (* 2 3)\n(* 2 3) -> (<< 3 1)\n(* 2 (<< 3 1)) -> (<< (<< 3 1) 1)\n(<< (<< 3 1) 1) -> (<< 3 2)\nSimplified tree: (= x (<< 3 2))\n$ \n","type":"text"}]},{"type":"paragraph","content":[{"text":"I'm replacing multiply with shift left by 1 and then combining shifts.","type":"text"}]}],"version":1}