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 Gruverimport org.antlr.grammar.v3.ANTLRParser; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.MultiMap; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.Utils; 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.runtime.Token; 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.ErrorManager; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.Grammar; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.GrammarAST; 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.*; 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Collection of information about what is wrong with a decision as 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * discovered while building the DFA predictor. 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The information is collected during NFA->DFA conversion and, while 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * some of this is available elsewhere, it is nice to have it all tracked 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in one spot so a great error message can be easily had. I also like 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the fact that this object tracks it all for later perusing to make an 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * excellent error message instead of lots of imprecise on-the-fly warnings 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (during conversion). 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A decision normally only has one problem; e.g., some input sequence 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * can be matched by multiple alternatives. Unfortunately, some decisions 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * such as 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : ( A | B ) | ( A | B ) | A ; 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * have multiple problems. So in general, you should approach a decision 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as having multiple flaws each one uniquely identified by a DFAState. 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * For example, statesWithSyntacticallyAmbiguousAltsSet tracks the set of 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * all DFAStates where ANTLR has discovered a problem. Recall that a decision 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is represented internall with a DFA comprised of multiple states, each of 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * which could potentially have problems. 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Because of this, you need to iterate over this list of DFA states. You'll 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * note that most of the informational methods like 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * getSampleNonDeterministicInputSequence() require a DFAState. This state 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * will be one of the iterated states from stateToSyntacticallyAmbiguousAltsSet. 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This class is not thread safe due to shared use of visited maps etc... 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Only one thread should really need to access one DecisionProbe anyway. 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class DecisionProbe { 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public DFA dfa; 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Track all DFA states with nondeterministic alternatives. 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * By reaching the same DFA state, a path through the NFA for some input 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is able to reach the same NFA state by starting at more than one 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alternative's left edge. Though, later, we may find that predicates 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * resolve the issue, but track info anyway. 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Note that from the DFA state, you can ask for 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * which alts are nondeterministic. 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set<DFAState> statesWithSyntacticallyAmbiguousAltsSet = new HashSet<DFAState>(); 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Track just like stateToSyntacticallyAmbiguousAltsMap, but only 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for nondeterminisms that arise in the Tokens rule such as keyword vs 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ID rule. The state maps to the list of Tokens rule alts that are 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in conflict. 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Map<DFAState, Set<Integer>> stateToSyntacticallyAmbiguousTokensRuleAltsMap = 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new HashMap<DFAState, Set<Integer>>(); 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Was a syntactic ambiguity resolved with predicates? Any DFA 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * state that predicts more than one alternative, must be resolved 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with predicates or it should be reported to the user. 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set<DFAState> statesResolvedWithSemanticPredicatesSet = new HashSet<DFAState>(); 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Track the predicates for each alt per DFA state; 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * more than one DFA state might have syntactically ambig alt prediction. 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Maps DFA state to another map, mapping alt number to a 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * SemanticContext (pred(s) to execute to resolve syntactic ambiguity). 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Map<DFAState, Map<Integer,SemanticContext>> stateToAltSetWithSemanticPredicatesMap = 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new HashMap<DFAState, Map<Integer,SemanticContext>>(); 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Tracks alts insufficiently covered. 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * For example, p1||true gets reduced to true and so leaves 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * whole alt uncovered. This maps DFA state to the set of alts 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Map<DFAState,Map<Integer, Set<Token>>> stateToIncompletelyCoveredAltsMap = 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new HashMap<DFAState,Map<Integer, Set<Token>>>(); 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The set of states w/o emanating edges and w/o resolving sem preds. */ 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set<DFAState> danglingStates = new HashSet<DFAState>(); 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The overall list of alts within the decision that have at least one 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * conflicting input sequence. 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set<Integer> altsWithProblem = new HashSet<Integer>(); 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** If decision with > 1 alt has recursion in > 1 alt, it's (likely) nonregular 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * lookahead. The decision cannot be made with a DFA. 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the alts are stored in altsWithProblem. 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean nonLLStarDecision = false; 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Recursion is limited to a particular depth. If that limit is exceeded 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the proposed new NFAConfiguration is recorded for the associated DFA state. 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected MultiMap<Integer, NFAConfiguration> stateToRecursionOverflowConfigurationsMap = 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new MultiMap<Integer, NFAConfiguration>(); 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Map<Integer, List<NFAConfiguration>> stateToRecursionOverflowConfigurationsMap = 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new HashMap<Integer, List<NFAConfiguration>>(); 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Left recursion discovered. The proposed new NFAConfiguration 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is recorded for the associated DFA state. 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Map<Integer,List<NFAConfiguration>> stateToLeftRecursiveConfigurationsMap = 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new HashMap<Integer,List<NFAConfiguration>>(); 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Did ANTLR have to terminate early on the analysis of this decision? */ 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected boolean timedOut = false; 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Used to find paths through syntactically ambiguous DFA. If we've 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * seen statement number before, what did we learn? 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Map<Integer, Integer> stateReachable; 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final Integer REACHABLE_BUSY = Utils.integer(-1); 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final Integer REACHABLE_NO = Utils.integer(0); 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static final Integer REACHABLE_YES = Utils.integer(1); 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Used while finding a path through an NFA whose edge labels match 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * an input sequence. Tracks the input position 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * we were at the last time at this node. If same input position, then 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * we'd have reached same state without consuming input...probably an 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * infinite loop. Stop. Set<String>. The strings look like 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * stateNumber_labelIndex. 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set<String> statesVisitedAtInputDepth; 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set<Integer> statesVisitedDuringSampleSequence; 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static boolean verbose = false; 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public DecisionProbe(DFA dfa) { 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.dfa = dfa; 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // I N F O R M A T I O N A B O U T D E C I S I O N 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a string like "3:22: ( A {;} | B )" that describes this 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * decision. 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String getDescription() { 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfa.getNFADecisionStartState().getDescription(); 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isReduced() { 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfa.isReduced(); 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isCyclic() { 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfa.isCyclic(); 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** If no states are dead-ends, no alts are unreachable, there are 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * no nondeterminisms unresolved by syn preds, all is ok with decision. 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isDeterministic() { 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( danglingStates.size()==0 && 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesWithSyntacticallyAmbiguousAltsSet.size()==0 && 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.getUnreachableAlts().size()==0 ) 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( statesWithSyntacticallyAmbiguousAltsSet.size()>0 ) { 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator it = 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesWithSyntacticallyAmbiguousAltsSet.iterator(); 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( it.hasNext() ) { 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState d = (DFAState) it.next(); 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !statesResolvedWithSemanticPredicatesSet.contains(d) ) { 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no syntactically ambig alts were left unresolved by predicates 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Did the analysis complete it's work? */ 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// public boolean analysisTimedOut() { 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// return timedOut; 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// } 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Took too long to analyze a DFA */ 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean analysisOverflowed() { 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return stateToRecursionOverflowConfigurationsMap.size()>0; 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Found recursion in > 1 alt */ 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean isNonLLStarDecision() { 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return nonLLStarDecision; 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** How many states does the DFA predictor have? */ 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int getNumberOfStates() { 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfa.getNumberOfStates(); 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Get a list of all unreachable alternatives for this decision. There 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * may be multiple alternatives with ambiguous input sequences, but this 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is the overall list of unreachable alternatives (either due to 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * conflict resolution or alts w/o accept states). 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public List<Integer> getUnreachableAlts() { 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfa.getUnreachableAlts(); 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** return set of states w/o emanating edges and w/o resolving sem preds. 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * These states come about because the analysis algorithm had to 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * terminate early to avoid infinite recursion for example (due to 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * left recursion perhaps). 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Set getDanglingStates() { 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return danglingStates; 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Set getNonDeterministicAlts() { 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return altsWithProblem; 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return the sorted list of alts that conflict within a single state. 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Note that predicates may resolve the conflict. 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public List getNonDeterministicAltsForState(DFAState targetState) { 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set nondetAlts = targetState.getNonDeterministicAlts(); 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nondetAlts==null ) { 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List sorted = new LinkedList(); 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sorted.addAll(nondetAlts); 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Collections.sort(sorted); // make sure it's 1, 2, ... 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return sorted; 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return all DFA states in this DFA that have NFA configurations that 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * conflict. You must report a problem for each state in this set 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * because each state represents a different input sequence. 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Set getDFAStatesWithSyntacticallyAmbiguousAlts() { 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return statesWithSyntacticallyAmbiguousAltsSet; 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Which alts were specifically turned off to resolve nondeterminisms? 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This is different than the unreachable alts. Disabled doesn't mean that 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the alternative is totally unreachable necessarily, it just means 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that for this DFA state, that alt is disabled. There may be other 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * accept states for that alt that make an alt reachable. 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Set getDisabledAlternatives(DFAState d) { 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return d.getDisabledAlternatives(); 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** If a recursion overflow is resolve with predicates, then we need 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to shut off the warning that would be generated. 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void removeRecursiveOverflowState(DFAState d) { 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer stateI = Utils.integer(d.stateNumber); 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToRecursionOverflowConfigurationsMap.remove(stateI); 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a List<Label> indicating an input sequence that can be matched 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from the start state of the DFA to the targetState (which is known 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to have a problem). 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public List<Label> getSampleNonDeterministicInputSequence(DFAState targetState) { 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set dfaStates = getDFAPathStatesToTarget(targetState); 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedDuringSampleSequence = new HashSet<Integer>(); 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<Label> labels = new ArrayList<Label>(); // may access ith element; use array 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( dfa==null || dfa.startState==null ) { 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labels; 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getSampleInputSequenceUsingStateSet(dfa.startState, 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver targetState, 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfaStates, 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels); 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labels; 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given List<Label>, return a String with a useful representation 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of the associated input string. One could show something different 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for lexers and parsers, for example. 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String getInputSequenceDisplay(List labels) { 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Grammar g = dfa.nfa.grammar; 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = labels.iterator(); it.hasNext();) { 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label label = (Label) it.next(); 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(label.toString(g)); 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( it.hasNext() && g.type!=Grammar.LEXER ) { 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(' '); 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given an alternative associated with a nondeterministic DFA state, 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * find the path of NFA states associated with the labels sequence. 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Useful tracing where in the NFA, a single input sequence can be 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * matched. For different alts, you should get different NFA paths. 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The first NFA state for all NFA paths will be the same: the starting 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NFA state of the first nondeterministic alt. Imagine (A|B|A|A): 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 5->9-A->o 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6->10-B->o 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 7->11-A->o 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 8->12-A->o 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * There are 3 nondeterministic alts. The paths should be: 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 5 9 ... 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 5 6 7 11 ... 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 5 6 7 8 12 ... 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The NFA path matching the sample input sequence (labels) is computed 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * using states 9, 11, and 12 rather than 5, 7, 8 because state 5, for 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * example can get to all ambig paths. Must isolate for each alt (hence, 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the extra state beginning each alt in my NFA structures). Here, 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * firstAlt=1. 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public List getNFAPathStatesForAlt(int firstAlt, 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt, 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List labels) 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState nfaStart = dfa.getNFADecisionStartState(); 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List path = new LinkedList(); 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // first add all NFA states leading up to altStart state 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int a=firstAlt; a<=alt; a++) { 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState s = 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.getNFAStateForAltOfDecision(nfaStart,a); 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver path.add(s); 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add first state of actual alt 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState altStart = dfa.nfa.grammar.getNFAStateForAltOfDecision(nfaStart,alt); 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState isolatedAltStart = (NFAState)altStart.transition[0].target; 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver path.add(isolatedAltStart); 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add the actual path now 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedAtInputDepth = new HashSet(); 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getNFAPath(isolatedAltStart, 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 0, 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels, 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver path); 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return path; 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Each state in the DFA represents a different input sequence for an 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt of the decision. Given a DFA state, what is the semantic 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicate context for a particular alt. 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public SemanticContext getSemanticContextForAlt(DFAState d, int alt) { 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map altToPredMap = (Map)stateToAltSetWithSemanticPredicatesMap.get(d); 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( altToPredMap==null ) { 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return (SemanticContext)altToPredMap.get(Utils.integer(alt)); 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** At least one alt refs a sem or syn pred */ 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public boolean hasPredicate() { 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return stateToAltSetWithSemanticPredicatesMap.size()>0; 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Set getNondeterministicStatesResolvedWithSemanticPredicate() { 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return statesResolvedWithSemanticPredicatesSet; 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a list of alts whose predicate context was insufficient to 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * resolve a nondeterminism for state d. 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public Map<Integer, Set<Token>> getIncompletelyCoveredAlts(DFAState d) { 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return stateToIncompletelyCoveredAltsMap.get(d); 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void issueWarnings() { 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // NONREGULAR DUE TO RECURSION > 1 ALTS 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Issue this before aborted analysis, which might also occur 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if we take too long to terminate 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nonLLStarDecision && !dfa.getAutoBacktrackMode() ) { 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ErrorManager.nonLLStarDecision(this); 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver issueRecursionWarnings(); 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // generate a separate message for each problem state in DFA 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set resolvedStates = getNondeterministicStatesResolvedWithSemanticPredicate(); 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set problemStates = getDFAStatesWithSyntacticallyAmbiguousAlts(); 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( problemStates.size()>0 ) { 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator it = 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver problemStates.iterator(); 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( it.hasNext() && !dfa.nfa.grammar.NFAToDFAConversionExternallyAborted() ) { 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState d = (DFAState) it.next(); 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map<Integer, Set<Token>> insufficientAltToLocations = getIncompletelyCoveredAlts(d); 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( insufficientAltToLocations!=null && insufficientAltToLocations.size()>0 ) { 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ErrorManager.insufficientPredicates(this,d,insufficientAltToLocations); 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't report problem if resolved 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( resolvedStates==null || !resolvedStates.contains(d) ) { 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // first strip last alt from disableAlts if it's wildcard 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // then don't print error if no more disable alts 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set disabledAlts = getDisabledAlternatives(d); 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stripWildCardAlts(disabledAlts); 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( disabledAlts.size()>0 ) { 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // nondeterminism; same input predicts multiple alts. 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // but don't emit error if greedy=true explicitly set 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean explicitlyGreedy = false; 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver GrammarAST blockAST = 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.dfa.nfa.grammar.getDecisionBlockAST(d.dfa.decisionNumber); 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( blockAST!=null ) { 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String greedyS = (String)blockAST.getBlockOption("greedy"); 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( greedyS!=null && greedyS.equals("true") ) explicitlyGreedy = true; 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !explicitlyGreedy) ErrorManager.nondeterminism(this,d); 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set danglingStates = getDanglingStates(); 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( danglingStates.size()>0 ) { 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.err.println("no emanating edges for states: "+danglingStates); 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = danglingStates.iterator(); it.hasNext();) { 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState d = (DFAState) it.next(); 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ErrorManager.danglingState(this,d); 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !nonLLStarDecision ) { 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<Integer> unreachableAlts = dfa.getUnreachableAlts(); 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( unreachableAlts!=null && unreachableAlts.size()>0 ) { 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // give different msg if it's an empty Tokens rule from delegate 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean isInheritedTokensRule = false; 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( dfa.isTokensRuleDecision() ) { 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Integer altI : unreachableAlts) { 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver GrammarAST decAST = dfa.getDecisionASTNode(); 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver GrammarAST altAST = (GrammarAST)decAST.getChild(altI-1); 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver GrammarAST delegatedTokensAlt = 477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (GrammarAST)altAST.getFirstChildWithType(ANTLRParser.DOT); 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( delegatedTokensAlt !=null ) { 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver isInheritedTokensRule = true; 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ErrorManager.grammarWarning(ErrorManager.MSG_IMPORTED_TOKENS_RULE_EMPTY, 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar, 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver null, 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.name, 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver delegatedTokensAlt.getChild(0).getText()); 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( isInheritedTokensRule ) { 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ErrorManager.unreachableAlts(this,unreachableAlts); 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Get the last disabled alt number and check in the grammar to see 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if that alt is a simple wildcard. If so, treat like an else clause 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and don't emit the error. Strip out the last alt if it's wildcard. 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void stripWildCardAlts(Set disabledAlts) { 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List sortedDisableAlts = new ArrayList(disabledAlts); 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Collections.sort(sortedDisableAlts); 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer lastAlt = 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (Integer)sortedDisableAlts.get(sortedDisableAlts.size()-1); 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver GrammarAST blockAST = 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.getDecisionBlockAST(dfa.decisionNumber); 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("block with error = "+blockAST.toStringTree()); 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver GrammarAST lastAltAST = null; 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( blockAST.getChild(0).getType()==ANTLRParser.OPTIONS ) { 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if options, skip first child: ( options { ( = greedy false ) ) 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lastAltAST = (GrammarAST)blockAST.getChild(lastAlt.intValue()); 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lastAltAST = (GrammarAST)blockAST.getChild(lastAlt.intValue()-1); 516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("last alt is "+lastAltAST.toStringTree()); 518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if last alt looks like ( ALT . <end-of-alt> ) then wildcard 519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Avoid looking at optional blocks etc... that have last alt 520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // as the EOB: 521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // ( BLOCK ( ALT 'else' statement <end-of-alt> ) <end-of-block> ) 522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( lastAltAST.getType()!=ANTLRParser.EOB && 523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lastAltAST.getChild(0).getType()== ANTLRParser.WILDCARD && 524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver lastAltAST.getChild(1).getType()== ANTLRParser.EOA ) 525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("wildcard"); 527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver disabledAlts.remove(lastAlt); 528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void issueRecursionWarnings() { 532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // RECURSION OVERFLOW 533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set dfaStatesWithRecursionProblems = 534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToRecursionOverflowConfigurationsMap.keySet(); 535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // now walk truly unique (unaliased) list of dfa states with inf recur 536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Goal: create a map from alt to map<target,List<callsites>> 537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Map<Map<String target, List<NFAState call sites>> 538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map altToTargetToCallSitesMap = new HashMap(); 539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // track a single problem DFA state for each alt 540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map altToDFAState = new HashMap(); 541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver computeAltToProblemMaps(dfaStatesWithRecursionProblems, 542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToRecursionOverflowConfigurationsMap, 543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToTargetToCallSitesMap, // output param 544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToDFAState); // output param 545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk each alt with recursion overflow problems and generate error 547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set alts = altToTargetToCallSitesMap.keySet(); 548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List sortedAlts = new ArrayList(alts); 549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Collections.sort(sortedAlts); 550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator altsIt = sortedAlts.iterator(); altsIt.hasNext();) { 551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer altI = (Integer) altsIt.next(); 552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map targetToCallSiteMap = 553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (Map)altToTargetToCallSitesMap.get(altI); 554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set targetRules = targetToCallSiteMap.keySet(); 555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Collection callSiteStates = targetToCallSiteMap.values(); 556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState sampleBadState = (DFAState)altToDFAState.get(altI); 557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ErrorManager.recursionOverflow(this, 558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sampleBadState, 559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altI.intValue(), 560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver targetRules, 561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver callSiteStates); 562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private void computeAltToProblemMaps(Set dfaStatesUnaliased, 566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map configurationsMap, 567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map altToTargetToCallSitesMap, 568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map altToDFAState) 569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = dfaStatesUnaliased.iterator(); it.hasNext();) { 571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer stateI = (Integer) it.next(); 572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk this DFA's config list 573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List configs = (List)configurationsMap.get(stateI); 574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < configs.size(); i++) { 575324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration c = (NFAConfiguration) configs.get(i); 576324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState ruleInvocationState = dfa.nfa.getState(c.state); 577324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition0 = ruleInvocationState.transition[0]; 578324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver RuleClosureTransition ref = (RuleClosureTransition)transition0; 579324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String targetRule = ((NFAState) ref.target).enclosingRule.name; 580324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer altI = Utils.integer(c.alt); 581324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map targetToCallSiteMap = 582324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (Map)altToTargetToCallSitesMap.get(altI); 583324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( targetToCallSiteMap==null ) { 584324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver targetToCallSiteMap = new HashMap(); 585324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToTargetToCallSitesMap.put(altI, targetToCallSiteMap); 586324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 587324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set callSites = 588324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (HashSet)targetToCallSiteMap.get(targetRule); 589324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( callSites==null ) { 590324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver callSites = new HashSet(); 591324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver targetToCallSiteMap.put(targetRule, callSites); 592324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 593324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver callSites.add(ruleInvocationState); 594324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // track one problem DFA state per alt 595324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( altToDFAState.get(altI)==null ) { 596324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState sampleBadState = dfa.getState(stateI.intValue()); 597324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToDFAState.put(altI, sampleBadState); 598324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 599324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 600324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 601324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 602324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 603324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private Set getUnaliasedDFAStateSet(Set dfaStatesWithRecursionProblems) { 604324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set dfaStatesUnaliased = new HashSet(); 605324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = dfaStatesWithRecursionProblems.iterator(); it.hasNext();) { 606324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer stateI = (Integer) it.next(); 607324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState d = dfa.getState(stateI.intValue()); 608324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfaStatesUnaliased.add(Utils.integer(d.stateNumber)); 609324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 610324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfaStatesUnaliased; 611324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 612324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 613324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 614324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // T R A C K I N G M E T H O D S 615324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 616324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Report the fact that DFA state d is not a state resolved with 617324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicates and yet it has no emanating edges. Usually this 618324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is a result of the closure/reach operations being unable to proceed 619324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 620324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportDanglingState(DFAState d) { 621324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver danglingStates.add(d); 622324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 623324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 624324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// public void reportAnalysisTimeout() { 625324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// timedOut = true; 626324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// dfa.nfa.grammar.setOfDFAWhoseAnalysisTimedOut.add(dfa); 627324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// } 628324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 629324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Report that at least 2 alts have recursive constructs. There is 630324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * no way to build a DFA so we terminated. 631324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 632324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportNonLLStarDecision(DFA dfa) { 633324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 634324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("non-LL(*) DFA "+dfa.decisionNumber+", alts: "+ 635324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.recursiveAltSet.toList()); 636324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 637324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nonLLStarDecision = true; 638324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.numNonLLStar++; 639324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altsWithProblem.addAll(dfa.recursiveAltSet.toList()); 640324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 641324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 642324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportRecursionOverflow(DFAState d, 643324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration recursionNFAConfiguration) 644324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 645324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // track the state number rather than the state as d will change 646324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // out from underneath us; hash wouldn't return any value 647324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 648324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // left-recursion is detected in start state. Since we can't 649324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // call resolveNondeterminism() on the start state (it would 650324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // not look k=1 to get min single token lookahead), we must 651324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // prevent errors derived from this state. Avoid start state 652324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d.stateNumber > 0 ) { 653324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer stateI = Utils.integer(d.stateNumber); 654324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToRecursionOverflowConfigurationsMap.map(stateI, recursionNFAConfiguration); 655324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 656324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 657324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 658324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportNondeterminism(DFAState d, Set<Integer> nondeterministicAlts) { 659324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altsWithProblem.addAll(nondeterministicAlts); // track overall list 660324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesWithSyntacticallyAmbiguousAltsSet.add(d); 661324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.setOfNondeterministicDecisionNumbers.add( 662324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Utils.integer(dfa.getDecisionNumber()) 663324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ); 664324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 665324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 666324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Currently the analysis reports issues between token definitions, but 667324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * we don't print out warnings in favor of just picking the first token 668324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * definition found in the grammar ala lex/flex. 669324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 670324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportLexerRuleNondeterminism(DFAState d, Set<Integer> nondeterministicAlts) { 671324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToSyntacticallyAmbiguousTokensRuleAltsMap.put(d,nondeterministicAlts); 672324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 673324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 674324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportNondeterminismResolvedWithSemanticPredicate(DFAState d) { 675324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // First, prevent a recursion warning on this state due to 676324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // pred resolution 677324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d.abortedDueToRecursionOverflow ) { 678324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.dfa.probe.removeRecursiveOverflowState(d); 679324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 680324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesResolvedWithSemanticPredicatesSet.add(d); 681324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("resolved with pred: "+d); 682324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.setOfNondeterministicDecisionNumbersResolvedWithPredicates.add( 683324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Utils.integer(dfa.getDecisionNumber()) 684324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ); 685324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 686324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 687324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Report the list of predicates found for each alternative; copy 688324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the list because this set gets altered later by the method 689324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * tryToResolveWithSemanticPredicates() while flagging NFA configurations 690324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in d as resolved. 691324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 692324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportAltPredicateContext(DFAState d, Map altPredicateContext) { 693324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map copy = new HashMap(); 694324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver copy.putAll(altPredicateContext); 695324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToAltSetWithSemanticPredicatesMap.put(d,copy); 696324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 697324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 698324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reportIncompletelyCoveredAlts(DFAState d, 699324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map<Integer, Set<Token>> altToLocationsReachableWithoutPredicate) 700324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 701324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToIncompletelyCoveredAltsMap.put(d, altToLocationsReachableWithoutPredicate); 702324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 703324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 704324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // S U P P O R T 705324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 706324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given a start state and a target state, return true if start can reach 707324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * target state. Also, compute the set of DFA states 708324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that are on a path from start to target; return in states parameter. 709324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 710324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected boolean reachesState(DFAState startState, 711324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState targetState, 712324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set states) { 713324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( startState==targetState ) { 714324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver states.add(targetState); 715324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("found target DFA state "+targetState.getStateNumber()); 716324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateReachable.put(startState.stateNumber, REACHABLE_YES); 717324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 718324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 719324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 720324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState s = startState; 721324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // avoid infinite loops 722324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateReachable.put(s.stateNumber, REACHABLE_BUSY); 723324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 724324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // look for a path to targetState among transitions for this state 725324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // stop when you find the first one; I'm pretty sure there is 726324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // at most one path to any DFA state with conflicting predictions 727324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=0; i<s.getNumberOfTransitions(); i++) { 728324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition t = s.transition(i); 729324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState edgeTarget = (DFAState)t.target; 730324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer targetStatus = stateReachable.get(edgeTarget.stateNumber); 731324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( targetStatus==REACHABLE_BUSY ) { // avoid cycles; they say nothing 732324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 733324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 734324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( targetStatus==REACHABLE_YES ) { // return success! 735324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateReachable.put(s.stateNumber, REACHABLE_YES); 736324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 737324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 738324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( targetStatus==REACHABLE_NO ) { // try another transition 739324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 740324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 741324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if null, target must be REACHABLE_UNKNOWN (i.e., unvisited) 742324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( reachesState(edgeTarget, targetState, states) ) { 743324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver states.add(s); 744324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateReachable.put(s.stateNumber, REACHABLE_YES); 745324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 746324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 747324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 748324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 749324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateReachable.put(s.stateNumber, REACHABLE_NO); 750324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; // no path to targetState found. 751324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 752324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 753324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Set getDFAPathStatesToTarget(DFAState targetState) { 754324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set dfaStates = new HashSet(); 755324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateReachable = new HashMap(); 756324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( dfa==null || dfa.startState==null ) { 757324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfaStates; 758324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 759324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean reaches = reachesState(dfa.startState, targetState, dfaStates); 760324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return dfaStates; 761324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 762324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 763324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given a start state and a final state, find a list of edge labels 764324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * between the two ignoring epsilon. Limit your scan to a set of states 765324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * passed in. This is used to show a sample input sequence that is 766324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * nondeterministic with respect to this decision. Return List<Label> as 767324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a parameter. The incoming states set must be all states that lead 768324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from startState to targetState and no others so this algorithm doesn't 769324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * take a path that eventually leads to a state other than targetState. 770324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Don't follow loops, leading to short (possibly shortest) path. 771324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 772324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void getSampleInputSequenceUsingStateSet(State startState, 773324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver State targetState, 774324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set states, 775324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<Label> labels) 776324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 777324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedDuringSampleSequence.add(startState.stateNumber); 778324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 779324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // pick the first edge in states as the one to traverse 780324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=0; i<startState.getNumberOfTransitions(); i++) { 781324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition t = startState.transition(i); 782324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState edgeTarget = (DFAState)t.target; 783324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( states.contains(edgeTarget) && 784324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver !statesVisitedDuringSampleSequence.contains(edgeTarget.stateNumber) ) 785324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 786324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels.add(t.label); // traverse edge and track label 787324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( edgeTarget!=targetState ) { 788324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // get more labels if not at target 789324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getSampleInputSequenceUsingStateSet(edgeTarget, 790324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver targetState, 791324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver states, 792324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels); 793324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 794324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // done with this DFA state as we've found a good path to target 795324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 796324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 797324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 798324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels.add(new Label(Label.EPSILON)); // indicate no input found 799324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // this happens on a : {p1}? a | A ; 800324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //ErrorManager.error(ErrorManager.MSG_CANNOT_COMPUTE_SAMPLE_INPUT_SEQ); 801324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 802324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 803324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given a sample input sequence, you usually would like to know the 804324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * path taken through the NFA. Return the list of NFA states visited 805324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * while matching a list of labels. This cannot use the usual 806324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * interpreter, which does a deterministic walk. We need to be able to 807324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * take paths that are turned off during nondeterminism resolution. So, 808324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * just do a depth-first walk traversing edges labeled with the current 809324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * label. Return true if a path was found emanating from state s. 810324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 811324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected boolean getNFAPath(NFAState s, // starting where? 812324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int labelIndex, // 0..labels.size()-1 813324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List labels, // input sequence 814324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List path) // output list of NFA states 815324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 816324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // track a visit to state s at input index labelIndex if not seen 817324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String thisStateKey = getStateLabelIndexKey(s.stateNumber,labelIndex); 818324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( statesVisitedAtInputDepth.contains(thisStateKey) ) { 819324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 820324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("### already visited "+s.stateNumber+" previously at index "+ 821324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelIndex); 822324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 823324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 824324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 825324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedAtInputDepth.add(thisStateKey); 826324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 827324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 828324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("enter state "+s.stateNumber+" visited states: "+ 829324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedAtInputDepth); 830324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 831324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 832324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // pick the first edge whose target is in states and whose 833324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // label is labels[labelIndex] 834324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=0; i<s.getNumberOfTransitions(); i++) { 835324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition t = s.transition[i]; 836324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState edgeTarget = (NFAState)t.target; 837324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label label = (Label)labels.get(labelIndex); 838324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 839324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println(s.stateNumber+"-"+ 840324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.label.toString(dfa.nfa.grammar)+"->"+ 841324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver edgeTarget.stateNumber+" =="+ 842324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label.toString(dfa.nfa.grammar)+"?"); 843324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 844324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t.label.isEpsilon() || t.label.isSemanticPredicate() ) { 845324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // nondeterministically backtrack down epsilon edges 846324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver path.add(edgeTarget); 847324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean found = 848324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getNFAPath(edgeTarget, labelIndex, labels, path); 849324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( found ) { 850324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedAtInputDepth.remove(thisStateKey); 851324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; // return to "calling" state 852324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 853324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver path.remove(path.size()-1); // remove; didn't work out 854324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; // look at the next edge 855324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 856324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t.label.matches(label) ) { 857324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver path.add(edgeTarget); 858324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 859324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("found label "+ 860324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.label.toString(dfa.nfa.grammar)+ 861324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " at state "+s.stateNumber+"; labelIndex="+labelIndex); 862324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 863324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( labelIndex==labels.size()-1 ) { 864324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // found last label; done! 865324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedAtInputDepth.remove(thisStateKey); 866324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 867324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 868324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // otherwise try to match remaining input 869324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean found = 870324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getNFAPath(edgeTarget, labelIndex+1, labels, path); 871324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( found ) { 872324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedAtInputDepth.remove(thisStateKey); 873324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 874324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 875324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 876324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("backtrack; path from "+s.stateNumber+"->"+ 877324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.label.toString(dfa.nfa.grammar)+" didn't work"); 878324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 879324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver path.remove(path.size()-1); // remove; didn't work out 880324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; // keep looking for a path for labels 881324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 882324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 883324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("no epsilon or matching edge; removing "+thisStateKey); 884324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no edge was found matching label; is ok, some state will have it 885324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver statesVisitedAtInputDepth.remove(thisStateKey); 886324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 887324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 888324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 889324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected String getStateLabelIndexKey(int s, int i) { 890324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuffer buf = new StringBuffer(); 891324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(s); 892324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append('_'); 893324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.append(i); 894324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.toString(); 895324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 896324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 897324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** From an alt number associated with artificial Tokens rule, return 898324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the name of the token that is associated with that alt. 899324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 900324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public String getTokenNameForTokensRuleAlt(int alt) { 901324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState decisionState = dfa.getNFADecisionStartState(); 902324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState altState = 903324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.getNFAStateForAltOfDecision(decisionState,alt); 904324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState decisionLeft = (NFAState)altState.transition[0].target; 905324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver RuleClosureTransition ruleCallEdge = 906324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (RuleClosureTransition)decisionLeft.transition[0]; 907324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState ruleStartState = (NFAState)ruleCallEdge.target; 908324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("alt = "+decisionLeft.getEnclosingRule()); 909324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ruleStartState.enclosingRule.name; 910324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 911324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 912324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void reset() { 913324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver stateToRecursionOverflowConfigurationsMap.clear(); 914324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 915324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 916