1 /* 2 * [The "BSD license"] 3 * Copyright (c) 2010 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 package org.antlr.analysis; 29 30 /** A tree node for tracking the call chains for NFAs that invoke 31 * other NFAs. These trees only have to point upwards to their parents 32 * so we can walk back up the tree (i.e., pop stuff off the stack). We 33 * never walk from stack down down through the children. 34 * 35 * Each alt predicted in a decision has its own context tree, 36 * representing all possible return nodes. The initial stack has 37 * EOF ("$") in it. So, for m alternative productions, the lookahead 38 * DFA will have m NFAContext trees. 39 * 40 * To "push" a new context, just do "new NFAContext(context-parent, state)" 41 * which will add itself to the parent. The root is NFAContext(null, null). 42 * 43 * The complete context for an NFA configuration is the set of invoking states 44 * on the path from this node thru the parent pointers to the root. 45 */ 46 public class NFAContext { 47 /** This is similar to Bermudez's m constant in his LAR(m) where 48 * you bound the stack so your states don't explode. The main difference 49 * is that I bound only recursion on the stack, not the simple stack size. 50 * This looser constraint will let the conversion roam further to find 51 * lookahead to resolve a decision. 52 * 53 * Bermudez's m operates differently as it is his LR stack depth 54 * I'm pretty sure it therefore includes all stack symbols. Here I 55 * restrict the size of an NFA configuration to be finite because a 56 * stack component may mention the same NFA invocation state at 57 * most m times. Hence, the number of DFA states will not grow forever. 58 * With recursive rules like 59 * 60 * e : '(' e ')' | INT ; 61 * 62 * you could chase your tail forever if somebody said "s : e '.' | e ';' ;" 63 * This constant prevents new states from being created after a stack gets 64 * "too big". Actually (12/14/2007) I realize that this example is 65 * trapped by the non-LL(*) detector for recursion in > 1 alt. Here is 66 * an example that trips stack overflow: 67 * 68 * s : a Y | A A A A A X ; // force recursion past m=4 69 * a : A a | Q; 70 * 71 * If that were: 72 * 73 * s : a Y | A+ X ; 74 * 75 * it could loop forever. 76 * 77 * Imagine doing a depth-first search on the e DFA...as you chase an input 78 * sequence you can recurse to same rule such as e above. You'd have a 79 * chain of ((((. When you get do some point, you have to give up. The 80 * states in the chain will have longer and longer NFA config stacks. 81 * Must limit size. 82 * 83 * max=0 implies you cannot ever jump to another rule during closure. 84 * max=1 implies you can make as many calls as you want--you just 85 * can't ever visit a state that is on your rule invocation stack. 86 * I.e., you cannot ever recurse. 87 * max=2 implies you are able to recurse once (i.e., call a rule twice 88 * from the same place). 89 * 90 * This tracks recursion to a rule specific to an invocation site! 91 * It does not detect multiple calls to a rule from different rule 92 * invocation states. We are guaranteed to terminate because the 93 * stack can only grow as big as the number of NFA states * max. 94 * 95 * I noticed that the Java grammar didn't work with max=1, but did with 96 * max=4. Let's set to 4. Recursion is sometimes needed to resolve some 97 * fixed lookahead decisions. 98 */ 99 public static int MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK = 4; 100 101 public NFAContext parent; 102 103 /** The NFA state that invoked another rule's start state is recorded 104 * on the rule invocation context stack. 105 */ 106 public NFAState invokingState; 107 108 /** Computing the hashCode is very expensive and closureBusy() 109 * uses it to track when it's seen a state|ctx before to avoid 110 * infinite loops. As we add new contexts, record the hash code 111 * as this.invokingState + parent.cachedHashCode. Avoids walking 112 * up the tree for every hashCode(). Note that this caching works 113 * because a context is a monotonically growing tree of context nodes 114 * and nothing on the stack is ever modified...ctx just grows 115 * or shrinks. 116 */ 117 protected int cachedHashCode; 118 NFAContext(NFAContext parent, NFAState invokingState)119 public NFAContext(NFAContext parent, NFAState invokingState) { 120 this.parent = parent; 121 this.invokingState = invokingState; 122 if ( invokingState!=null ) { 123 this.cachedHashCode = invokingState.stateNumber; 124 } 125 if ( parent!=null ) { 126 this.cachedHashCode += parent.cachedHashCode; 127 } 128 } 129 130 /** Two contexts are equals() if both have 131 * same call stack; walk upwards to the root. 132 * Recall that the root sentinel node has no invokingStates and no parent. 133 * Note that you may be comparing contexts in different alt trees. 134 * 135 * The hashCode is now cheap as it's computed once upon each context 136 * push on the stack. Use it to make equals() more efficient. 137 */ equals(Object o)138 public boolean equals(Object o) { 139 NFAContext other = ((NFAContext)o); 140 if ( this.cachedHashCode != other.cachedHashCode ) { 141 return false; // can't be same if hash is different 142 } 143 if ( this==other ) { 144 return true; 145 } 146 // System.out.println("comparing "+this+" with "+other); 147 NFAContext sp = this; 148 while ( sp.parent!=null && other.parent!=null ) { 149 if ( sp.invokingState != other.invokingState ) { 150 return false; 151 } 152 sp = sp.parent; 153 other = other.parent; 154 } 155 if ( !(sp.parent==null && other.parent==null) ) { 156 return false; // both pointers must be at their roots after walk 157 } 158 return true; 159 } 160 161 /** Two contexts conflict() if they are equals() or one is a stack suffix 162 * of the other. For example, contexts [21 12 $] and [21 9 $] do not 163 * conflict, but [21 $] and [21 12 $] do conflict. Note that I should 164 * probably not show the $ in this case. There is a dummy node for each 165 * stack that just means empty; $ is a marker that's all. 166 * 167 * This is used in relation to checking conflicts associated with a 168 * single NFA state's configurations within a single DFA state. 169 * If there are configurations s and t within a DFA state such that 170 * s.state=t.state && s.alt != t.alt && s.ctx conflicts t.ctx then 171 * the DFA state predicts more than a single alt--it's nondeterministic. 172 * Two contexts conflict if they are the same or if one is a suffix 173 * of the other. 174 * 175 * When comparing contexts, if one context has a stack and the other 176 * does not then they should be considered the same context. The only 177 * way for an NFA state p to have an empty context and a nonempty context 178 * is the case when closure falls off end of rule without a call stack 179 * and re-enters the rule with a context. This resolves the issue I 180 * discussed with Sriram Srinivasan Feb 28, 2005 about not terminating 181 * fast enough upon nondeterminism. 182 */ conflictsWith(NFAContext other)183 public boolean conflictsWith(NFAContext other) { 184 return this.suffix(other); // || this.equals(other); 185 } 186 187 /** [$] suffix any context 188 * [21 $] suffix [21 12 $] 189 * [21 12 $] suffix [21 $] 190 * [21 18 $] suffix [21 18 12 9 $] 191 * [21 18 12 9 $] suffix [21 18 $] 192 * [21 12 $] not suffix [21 9 $] 193 * 194 * Example "[21 $] suffix [21 12 $]" means: rule r invoked current rule 195 * from state 21. Rule s invoked rule r from state 12 which then invoked 196 * current rule also via state 21. While the context prior to state 21 197 * is different, the fact that both contexts emanate from state 21 implies 198 * that they are now going to track perfectly together. Once they 199 * converged on state 21, there is no way they can separate. In other 200 * words, the prior stack state is not consulted when computing where to 201 * go in the closure operation. ?$ and ??$ are considered the same stack. 202 * If ? is popped off then $ and ?$ remain; they are now an empty and 203 * nonempty context comparison. So, if one stack is a suffix of 204 * another, then it will still degenerate to the simple empty stack 205 * comparison case. 206 */ suffix(NFAContext other)207 protected boolean suffix(NFAContext other) { 208 NFAContext sp = this; 209 // if one of the contexts is empty, it never enters loop and returns true 210 while ( sp.parent!=null && other.parent!=null ) { 211 if ( sp.invokingState != other.invokingState ) { 212 return false; 213 } 214 sp = sp.parent; 215 other = other.parent; 216 } 217 //System.out.println("suffix"); 218 return true; 219 } 220 221 /** Walk upwards to the root of the call stack context looking 222 * for a particular invoking state. 223 public boolean contains(int state) { 224 NFAContext sp = this; 225 int n = 0; // track recursive invocations of state 226 System.out.println("this.context is "+sp); 227 while ( sp.parent!=null ) { 228 if ( sp.invokingState.stateNumber == state ) { 229 return true; 230 } 231 sp = sp.parent; 232 } 233 return false; 234 } 235 */ 236 237 /** Given an NFA state number, how many times has the NFA-to-DFA 238 * conversion pushed that state on the stack? In other words, 239 * the NFA state must be a rule invocation state and this method 240 * tells you how many times you've been to this state. If none, 241 * then you have not called the target rule from this state before 242 * (though another NFA state could have called that target rule). 243 * If n=1, then you've been to this state before during this 244 * DFA construction and are going to invoke that rule again. 245 * 246 * Note that many NFA states can invoke rule r, but we ignore recursion 247 * unless you hit the same rule invocation state again. 248 */ recursionDepthEmanatingFromState(int state)249 public int recursionDepthEmanatingFromState(int state) { 250 NFAContext sp = this; 251 int n = 0; // track recursive invocations of target from this state 252 //System.out.println("this.context is "+sp); 253 while ( sp.parent!=null ) { 254 if ( sp.invokingState.stateNumber == state ) { 255 n++; 256 } 257 sp = sp.parent; 258 } 259 return n; 260 } 261 hashCode()262 public int hashCode() { 263 return cachedHashCode; 264 /* 265 int h = 0; 266 NFAContext sp = this; 267 while ( sp.parent!=null ) { 268 h += sp.invokingState.getStateNumber(); 269 sp = sp.parent; 270 } 271 return h; 272 */ 273 } 274 275 /** A context is empty if there is no parent; meaning nobody pushed 276 * anything on the call stack. 277 */ isEmpty()278 public boolean isEmpty() { 279 return parent==null; 280 } 281 toString()282 public String toString() { 283 StringBuffer buf = new StringBuffer(); 284 NFAContext sp = this; 285 buf.append("["); 286 while ( sp.parent!=null ) { 287 buf.append(sp.invokingState.stateNumber); 288 buf.append(" "); 289 sp = sp.parent; 290 } 291 buf.append("$]"); 292 return buf.toString(); 293 } 294 } 295