1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD license"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2010 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.analysis; 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** A tree node for tracking the call chains for NFAs that invoke 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * other NFAs. These trees only have to point upwards to their parents 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * so we can walk back up the tree (i.e., pop stuff off the stack). We 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * never walk from stack down down through the children. 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Each alt predicted in a decision has its own context tree, 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * representing all possible return nodes. The initial stack has 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * EOF ("$") in it. So, for m alternative productions, the lookahead 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DFA will have m NFAContext trees. 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * To "push" a new context, just do "new NFAContext(context-parent, state)" 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * which will add itself to the parent. The root is NFAContext(null, null). 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The complete context for an NFA configuration is the set of invoking states 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * on the path from this node thru the parent pointers to the root. 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class NFAContext { 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** This is similar to Bermudez's m constant in his LAR(m) where 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * you bound the stack so your states don't explode. The main difference 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is that I bound only recursion on the stack, not the simple stack size. 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This looser constraint will let the conversion roam further to find 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * lookahead to resolve a decision. 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Bermudez's m operates differently as it is his LR stack depth 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * I'm pretty sure it therefore includes all stack symbols. Here I 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * restrict the size of an NFA configuration to be finite because a 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * stack component may mention the same NFA invocation state at 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * most m times. Hence, the number of DFA states will not grow forever. 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * With recursive rules like 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * e : '(' e ')' | INT ; 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * you could chase your tail forever if somebody said "s : e '.' | e ';' ;" 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This constant prevents new states from being created after a stack gets 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * "too big". Actually (12/14/2007) I realize that this example is 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * trapped by the non-LL(*) detector for recursion in > 1 alt. Here is 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * an example that trips stack overflow: 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * s : a Y | A A A A A X ; // force recursion past m=4 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : A a | Q; 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If that were: 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * s : a Y | A+ X ; 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * it could loop forever. 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Imagine doing a depth-first search on the e DFA...as you chase an input 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * sequence you can recurse to same rule such as e above. You'd have a 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * chain of ((((. When you get do some point, you have to give up. The 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * states in the chain will have longer and longer NFA config stacks. 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Must limit size. 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * max=0 implies you cannot ever jump to another rule during closure. 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * max=1 implies you can make as many calls as you want--you just 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * can't ever visit a state that is on your rule invocation stack. 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * I.e., you cannot ever recurse. 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * max=2 implies you are able to recurse once (i.e., call a rule twice 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from the same place). 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This tracks recursion to a rule specific to an invocation site! 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * It does not detect multiple calls to a rule from different rule 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * invocation states. We are guaranteed to terminate because the 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * stack can only grow as big as the number of NFA states * max. 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * I noticed that the Java grammar didn't work with max=1, but did with 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * max=4. Let's set to 4. Recursion is sometimes needed to resolve some 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * fixed lookahead decisions. 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static int MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK = 4; 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public NFAContext parent; 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The NFA state that invoked another rule's start state is recorded 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * on the rule invocation context stack. 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public NFAState invokingState; 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Computing the hashCode is very expensive and closureBusy() 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * uses it to track when it's seen a state|ctx before to avoid 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * infinite loops. As we add new contexts, record the hash code 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as this.invokingState + parent.cachedHashCode. Avoids walking 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * up the tree for every hashCode(). Note that this caching works 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * because a context is a monotonically growing tree of context nodes 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and nothing on the stack is ever modified...ctx just grows 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * or shrinks. 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int cachedHashCode; 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public NFAContext(NFAContext parent, NFAState invokingState) { 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.parent = parent; 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.invokingState = invokingState; 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( invokingState!=null ) { 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.cachedHashCode = invokingState.stateNumber; 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( parent!=null ) { 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.cachedHashCode += parent.cachedHashCode; 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Two contexts are equals() if both have 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * same call stack; walk upwards to the root. 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Recall that the root sentinel node has no invokingStates and no parent. 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Note that you may be comparing contexts in different alt trees. 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The hashCode is now cheap as it's computed once upon each context 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * push on the stack. Use it to make equals() more efficient. 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean equals(Object o) { 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext other = ((NFAContext)o); 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this.cachedHashCode != other.cachedHashCode ) { 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; // can't be same if hash is different 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this==other ) { 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // System.out.println("comparing "+this+" with "+other); 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext sp = this; 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( sp.parent!=null && other.parent!=null ) { 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( sp.invokingState != other.invokingState ) { 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sp = sp.parent; 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver other = other.parent; 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !(sp.parent==null && other.parent==null) ) { 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; // both pointers must be at their roots after walk 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Two contexts conflict() if they are equals() or one is a stack suffix 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of the other. For example, contexts [21 12 $] and [21 9 $] do not 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * conflict, but [21 $] and [21 12 $] do conflict. Note that I should 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * probably not show the $ in this case. There is a dummy node for each 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * stack that just means empty; $ is a marker that's all. 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This is used in relation to checking conflicts associated with a 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * single NFA state's configurations within a single DFA state. 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If there are configurations s and t within a DFA state such that 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * s.state=t.state && s.alt != t.alt && s.ctx conflicts t.ctx then 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the DFA state predicts more than a single alt--it's nondeterministic. 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Two contexts conflict if they are the same or if one is a suffix 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of the other. 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * When comparing contexts, if one context has a stack and the other 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * does not then they should be considered the same context. The only 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * way for an NFA state p to have an empty context and a nonempty context 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is the case when closure falls off end of rule without a call stack 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and re-enters the rule with a context. This resolves the issue I 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * discussed with Sriram Srinivasan Feb 28, 2005 about not terminating 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * fast enough upon nondeterminism. 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean conflictsWith(NFAContext other) { 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.suffix(other); // || this.equals(other); 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** [$] suffix any context 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [21 $] suffix [21 12 $] 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [21 12 $] suffix [21 $] 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [21 18 $] suffix [21 18 12 9 $] 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [21 18 12 9 $] suffix [21 18 $] 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [21 12 $] not suffix [21 9 $] 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Example "[21 $] suffix [21 12 $]" means: rule r invoked current rule 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from state 21. Rule s invoked rule r from state 12 which then invoked 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * current rule also via state 21. While the context prior to state 21 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is different, the fact that both contexts emanate from state 21 implies 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that they are now going to track perfectly together. Once they 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * converged on state 21, there is no way they can separate. In other 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * words, the prior stack state is not consulted when computing where to 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * go in the closure operation. ?$ and ??$ are considered the same stack. 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If ? is popped off then $ and ?$ remain; they are now an empty and 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * nonempty context comparison. So, if one stack is a suffix of 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * another, then it will still degenerate to the simple empty stack 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * comparison case. 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected boolean suffix(NFAContext other) { 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext sp = this; 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if one of the contexts is empty, it never enters loop and returns true 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( sp.parent!=null && other.parent!=null ) { 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( sp.invokingState != other.invokingState ) { 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sp = sp.parent; 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver other = other.parent; 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("suffix"); 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Walk upwards to the root of the call stack context looking 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for a particular invoking state. 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean contains(int state) { 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext sp = this; 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = 0; // track recursive invocations of state 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("this.context is "+sp); 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( sp.parent!=null ) { 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( sp.invokingState.stateNumber == state ) { 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sp = sp.parent; 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given an NFA state number, how many times has the NFA-to-DFA 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * conversion pushed that state on the stack? In other words, 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the NFA state must be a rule invocation state and this method 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * tells you how many times you've been to this state. If none, 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * then you have not called the target rule from this state before 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (though another NFA state could have called that target rule). 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If n=1, then you've been to this state before during this 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DFA construction and are going to invoke that rule again. 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Note that many NFA states can invoke rule r, but we ignore recursion 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * unless you hit the same rule invocation state again. 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int recursionDepthEmanatingFromState(int state) { 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext sp = this; 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = 0; // track recursive invocations of target from this state 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("this.context is "+sp); 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( sp.parent!=null ) { 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( sp.invokingState.stateNumber == state ) { 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n++; 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sp = sp.parent; 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return n; 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int hashCode() { 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return cachedHashCode; 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int h = 0; 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext sp = this; 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( sp.parent!=null ) { 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver h += sp.invokingState.getStateNumber(); 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sp = sp.parent; 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return h; 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** A context is empty if there is no parent; meaning nobody pushed 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * anything on the call stack. 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isEmpty() { 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return parent==null; 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String toString() { 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext sp = this; 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append("["); 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( sp.parent!=null ) { 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(sp.invokingState.stateNumber); 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(" "); 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sp = sp.parent; 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append("$]"); 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 295