1 /* 2 [The "BSD license"] 3 Copyright (c) 2005-2009 Terence Parr 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without 7 modification, are permitted provided that the following conditions 8 are met: 9 1. Redistributions of source code must retain the above copyright 10 notice, this list of conditions and the following disclaimer. 11 2. Redistributions in binary form must reproduce the above copyright 12 notice, this list of conditions and the following disclaimer in the 13 documentation and/or other materials provided with the distribution. 14 3. The name of the author may not be used to endorse or promote products 15 derived from this software without specific prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 /* Java Stuff 30 package org.antlr.runtime.tree; 31 32 import org.antlr.runtime.RecognizerSharedState; 33 import org.antlr.runtime.RecognitionException; 34 import org.antlr.runtime.TokenStream; 35 */ 36 37 /** 38 Cut-n-paste from material I'm not using in the book anymore (edit later 39 to make sense): 40 41 Now, how are we going to test these tree patterns against every 42 subtree in our original tree? In what order should we visit nodes? 43 For this application, it turns out we need a simple ``apply once'' 44 rule application strategy and a ``down then up'' tree traversal 45 strategy. Let's look at rule application first. 46 47 As we visit each node, we need to see if any of our patterns match. If 48 a pattern matches, we execute the associated tree rewrite and move on 49 to the next node. In other words, we only look for a single rule 50 application opportunity (we'll see below that we sometimes need to 51 repeatedly apply rules). The following method applies a rule in a @cl 52 TreeParser (derived from a tree grammar) to a tree: 53 54 here is where weReferenced code/walking/patterns/TreePatternMatcher.java 55 56 It uses reflection to lookup the appropriate rule within the generated 57 tree parser class (@cl Simplify in this case). Most of the time, the 58 rule will not match the tree. To avoid issuing syntax errors and 59 attempting error recovery, it bumps up the backtracking level. Upon 60 failure, the invoked rule immediately returns. If you don't plan on 61 using this technique in your own ANTLR-based application, don't sweat 62 the details. This method boils down to ``call a rule to match a tree, 63 executing any embedded actions and rewrite rules.'' 64 65 At this point, we know how to define tree grammar rules and how to 66 apply them to a particular subtree. The final piece of the tree 67 pattern matcher is the actual tree traversal. We have to get the 68 correct node visitation order. In particular, we need to perform the 69 scalar-vector multiply transformation on the way down (preorder) and 70 we need to reduce multiply-by-zero subtrees on the way up (postorder). 71 72 To implement a top-down visitor, we do a depth first walk of the tree, 73 executing an action in the preorder position. To get a bottom-up 74 visitor, we execute an action in the postorder position. ANTLR 75 provides a standard @cl TreeVisitor class with a depth first search @v 76 visit method. That method executes either a @m pre or @m post method 77 or both. In our case, we need to call @m applyOnce in both. On the way 78 down, we'll look for @r vmult patterns. On the way up, 79 we'll look for @r mult0 patterns. 80 */ 81 82 /* Java Stuff 83 public class TreeFilter extends TreeParser { 84 public interface fptr { 85 public void rule() throws RecognitionException; 86 } 87 88 protected TokenStream originalTokenStream; 89 protected TreeAdaptor originalAdaptor; 90 91 public TreeFilter(TreeNodeStream input) { 92 this(input, new RecognizerSharedState()); 93 } 94 public TreeFilter(TreeNodeStream input, RecognizerSharedState state) { 95 super(input, state); 96 originalAdaptor = input.getTreeAdaptor(); 97 originalTokenStream = input.getTokenStream(); 98 } 99 100 public void applyOnce(Object t, fptr whichRule) { 101 if ( t==null ) return; 102 try { 103 // share TreeParser object but not parsing-related state 104 state = new RecognizerSharedState(); 105 input = new CommonTreeNodeStream(originalAdaptor, t); 106 ((CommonTreeNodeStream)input).setTokenStream(originalTokenStream); 107 setBacktrackingLevel(1); 108 whichRule.rule(); 109 setBacktrackingLevel(0); 110 } 111 catch (RecognitionException e) { ; } 112 } 113 114 public void downup(Object t) { 115 TreeVisitor v = new TreeVisitor(new CommonTreeAdaptor()); 116 TreeVisitorAction actions = new TreeVisitorAction() { 117 public Object pre(Object t) { applyOnce(t, topdown_fptr); return t; } 118 public Object post(Object t) { applyOnce(t, bottomup_fptr); return t; } 119 }; 120 v.visit(t, actions); 121 } 122 123 fptr topdown_fptr = new fptr() { 124 public void rule() throws RecognitionException { 125 topdown(); 126 } 127 }; 128 129 fptr bottomup_fptr = new fptr() { 130 public void rule() throws RecognitionException { 131 bottomup(); 132 } 133 }; 134 135 // methods the downup strategy uses to do the up and down rules. 136 // to override, just define tree grammar rule topdown and turn on 137 // filter=true. 138 public void topdown() throws RecognitionException {;} 139 public void bottomup() throws RecognitionException {;} 140 } 141 */ 142 143 #import "RecognizerSharedState.h" 144 #import "TokenStream.h" 145 #import "TreeAdaptor.h" 146 #import "TreeNodeStream.h" 147 #import "TreeParser.h" 148 #import "TreeVisitor.h" 149 #import "TreeVisitorAction.h" 150 151 @class TreeFilter; 152 153 @interface fptr : NSObject { 154 SEL whichRule; 155 TreeFilter *treeFilter; 156 } 157 158 @property (assign) SEL whichRule; 159 @property (assign) TreeFilter *treeFilter; 160 161 + (fptr *) newfptr:(TreeFilter *)aTreeFilter Rule:(SEL) aRule; 162 163 - (fptr *) init:(TreeFilter *)aTreeFilter Rule:(SEL)aRule; 164 165 - (void) rule; 166 167 @end 168 169 @interface TreeFilter : TreeParser { 170 171 id<TokenStream> originalTokenStream; 172 id<TreeAdaptor> originalAdaptor; 173 fptr *topdown_fptr; 174 fptr *bottomup_fptr; 175 176 } 177 178 + (id) newTreeFilter:(id<TreeNodeStream>)input; 179 180 + (id) newTreeFilter:(id<TreeNodeStream>)input State:(RecognizerSharedState *)state; 181 182 - (id) initWithStream:(id<TreeNodeStream>)anInput State:(RecognizerSharedState *)aState; 183 184 - (void) applyOnce:(id<BaseTree>)t rule:(fptr *)whichRule; 185 186 - (void) downup:(id<BaseTree>)t; 187 188 - (void) settopdown_fptr; 189 - (void) setbottomdown_fptr; 190 191 // methods the downup strategy uses to do the up and down rules. 192 // to override, just define tree grammar rule topdown and turn on 193 // filter=true. 194 - (void) topdown; 195 - (void) bottomup; 196 197 @property (retain) id<TokenStream> originalTokenStream; 198 @property (retain) id<TreeAdaptor> originalAdaptor; 199 @property (retain, setter=settopdown_fptr:) fptr *topdown_fptr; 200 @property (retain, setter=setbottomdown_fptr:) fptr *bottomup_fptr; 201 202 @end 203 // end TreeFilter.h 204