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.misc.OrderedHashSet; 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.misc.Utils; 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.runtime.Token; 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport org.antlr.tool.ErrorManager; 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverimport java.util.*; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Code that embodies the NFA conversion to DFA. A new object is needed 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * per DFA (also required for thread safety if multiple conversions 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * launched). 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class NFAToDFAConverter { 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** A list of DFA states we still need to process during NFA conversion */ 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected List work = new LinkedList(); 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** While converting NFA, we must track states that 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * reference other rule's NFAs so we know what to do 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * at the end of a rule. We need to know what context invoked 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this rule so we can know where to continue looking for NFA 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * states. I'm tracking a context tree (record of rule invocation 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * stack trace) for each alternative that could be predicted. 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected NFAContext[] contextTrees; 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** We are converting which DFA? */ 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected DFA dfa; 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static boolean debug = false; 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Should ANTLR launch multiple threads to convert NFAs to DFAs? 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * With a 2-CPU box, I note that it's about the same single or 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * multithreaded. Both CPU meters are going even when single-threaded 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * so I assume the GC is killing us. Could be the compiler. When I 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * run java -Xint mode, I get about 15% speed improvement with multiple 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * threads. 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static boolean SINGLE_THREADED_NFA_CONVERSION = true; 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected boolean computingStartState = false; 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public NFAToDFAConverter(DFA dfa) { 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.dfa = dfa; 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int nAlts = dfa.getNumberOfAlts(); 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver initContextTrees(nAlts); 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void convert() { 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //dfa.conversionStartTime = System.currentTimeMillis(); 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // create the DFA start state 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.startState = computeStartState(); 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // while more DFA states to check, process them 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( work.size()>0 && 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver !dfa.nfa.grammar.NFAToDFAConversionExternallyAborted() ) 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState d = (DFAState) work.get(0); 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( dfa.nfa.grammar.composite.watchNFAConversion ) { 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("convert DFA state "+d.stateNumber+ 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " ("+d.nfaConfigurations.size()+" nfa states)"); 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int k = dfa.getUserMaxLookahead(); 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( k>0 && k==d.getLookaheadDepth() ) { 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // we've hit max lookahead, make this a stop state 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("stop state @k="+k+" (terminated early)"); 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<Label> sampleInputLabels = d.dfa.probe.getSampleNonDeterministicInputSequence(d); 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String input = d.dfa.probe.getInputSequenceDisplay(sampleInputLabels); 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("sample input: "+input); 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver resolveNonDeterminisms(d); 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Check to see if we need to add any semantic predicate transitions 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d.isResolvedWithPredicates() ) { 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver addPredicateTransitions(d); 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.setAcceptState(true); // must convert to accept state at k 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver findNewDFAStatesAndAddDFATransitions(d); 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver work.remove(0); // done with it; remove from work list 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Find all manual syn preds (gated). These are not discovered 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // in tryToResolveWithSemanticPredicates because they are implicitly 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // added to every edge by code gen, DOT generation etc... 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.findAllGatedSynPredsUsedInDFAAcceptStates(); 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** From this first NFA state of a decision, create a DFA. 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Walk each alt in decision and compute closure from the start of that 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * rule, making sure that the closure does not include other alts within 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that same decision. The idea is to associate a specific alt number 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with the starting closure so we can trace the alt number for all states 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this. At a stop state in the DFA, we can return this alt 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * number, indicating which alt is predicted. 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If this DFA is derived from an loop back NFA state, then the first 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * transition is actually the exit branch of the loop. Rather than make 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this alternative one, let's make this alt n+1 where n is the number of 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alts in this block. This is nice to keep the alts of the block 1..n; 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * helps with error messages. 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * I handle nongreedy in findNewDFAStatesAndAddDFATransitions 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * when nongreedy and EOT transition. Make state with EOT emanating 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from it the accept state. 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected DFAState computeStartState() { 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState alt = dfa.decisionNFAStartState; 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState startState = dfa.newState(); 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver computingStartState = true; 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int i = 0; 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int altNum = 1; 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( alt!=null ) { 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // find the set of NFA states reachable without consuming 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // any input symbols for each alt. Keep adding to same 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // overall closure that will represent the DFA start state, 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // but track the alt number 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext initialContext = contextTrees[i]; 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if first alt is derived from loopback/exit branch of loop, 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make alt=n+1 for n alts instead of 1 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( i==0 && 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.getNFADecisionStartState().decisionStateType==NFAState.LOOPBACK ) 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numAltsIncludingExitBranch = dfa.nfa.grammar 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver .getNumberOfAltsForDecisionNFA(dfa.decisionNFAStartState); 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altNum = numAltsIncludingExitBranch; 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure((NFAState)alt.transition[0].target, 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altNum, 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver initialContext, 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.EMPTY_SEMANTIC_CONTEXT, 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver startState, 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver true 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ); 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altNum = 1; // make next alt the first 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure((NFAState)alt.transition[0].target, 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altNum, 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver initialContext, 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.EMPTY_SEMANTIC_CONTEXT, 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver startState, 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver true 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ); 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altNum++; 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // move to next alternative 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( alt.transition[1] ==null ) { 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver break; 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver alt = (NFAState)alt.transition[1].target; 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // now DFA start state has the complete closure for the decision 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // but we have tracked which alt is associated with which 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // NFA states. 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.addState(startState); // make sure dfa knows about this state 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver work.add(startState); 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver computingStartState = false; 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return startState; 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** From this node, add a d--a-->t transition for all 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * labels 'a' where t is a DFA node created 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from the set of NFA states reachable from any NFA 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * state in DFA state d. 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void findNewDFAStatesAndAddDFATransitions(DFAState d) { 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("work on DFA state "+d); 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver OrderedHashSet labels = d.getReachableLabels(); 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("reachable labels="+labels); 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("|reachable|/|nfaconfigs|="+ 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels.size()+"/"+d.getNFAConfigurations().size()+"="+ 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labels.size()/(float)d.getNFAConfigurations().size()); 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // normally EOT is the "default" clause and decisions just 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // choose that last clause when nothing else matches. DFA conversion 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // continues searching for a unique sequence that predicts the 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // various alts or until it finds EOT. So this rule 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // DUH : ('x'|'y')* "xy!"; 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // does not need a greedy indicator. The following rule works fine too 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // A : ('x')+ ; 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // When the follow branch could match what is in the loop, by default, 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the nondeterminism is resolved in favor of the loop. You don't 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // get a warning because the only way to get this condition is if 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the DFA conversion hits the end of the token. In that case, 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // we're not *sure* what will happen next, but it could be anything. 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Anyway, EOT is the default case which means it will never be matched 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // as resolution goes to the lowest alt number. Exit branches are 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // always alt n+1 for n alts in a block. 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // When a loop is nongreedy and we find an EOT transition, the DFA 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // state should become an accept state, predicting exit of loop. It's 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // just reversing the resolution of ambiguity. 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: should this be done in the resolveAmbig method? 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label EOTLabel = new Label(Label.EOT); 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean containsEOT = labels!=null && labels.contains(EOTLabel); 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !dfa.isGreedy() && containsEOT ) { 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver convertToEOTAcceptState(d); 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; // no more work to do on this accept state 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if in filter mode for lexer, want to match shortest not longest 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // string so if we see an EOT edge emanating from this state, then 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // convert this state to an accept state. This only counts for 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // The Tokens rule as all other decisions must continue to look for 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // longest match. 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // [Taking back out a few days later on Jan 17, 2006. This could 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // be an option for the future, but this was wrong soluion for 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // filtering.] 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( dfa.nfa.grammar.type==Grammar.LEXER && containsEOT ) { 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String filterOption = (String)dfa.nfa.grammar.getOption("filter"); 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean filterMode = filterOption!=null && filterOption.equals("true"); 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( filterMode && d.dfa.isTokensRuleDecision() ) { 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState t = reach(d, EOTLabel); 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t.getNFAConfigurations().size()>0 ) { 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver convertToEOTAcceptState(d); 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("state "+d+" has EOT target "+t.stateNumber); 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numberOfEdgesEmanating = 0; 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map targetToLabelMap = new HashMap(); 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for each label that could possibly emanate from NFAStates of d 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numLabels = 0; 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( labels!=null ) { 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numLabels = labels.size(); 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i=0; i<numLabels; i++) { 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label label = (Label)labels.get(i); 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState t = reach(d, label); 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("DFA state after reach "+label+" "+d+"-" + 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label.toString(dfa.nfa.grammar)+"->"+t); 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t==null ) { 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // nothing was reached by label due to conflict resolution 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // EOT also seems to be in here occasionally probably due 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // to an end-of-rule state seeing it even though we'll pop 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // an invoking state off the state; don't bother to conflict 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // as this labels set is a covering approximation only. 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("dfa.k="+dfa.getUserMaxLookahead()); 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t.getUniqueAlt()==NFA.INVALID_ALT_NUMBER ) { 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Only compute closure if a unique alt number is not known. 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // If a unique alternative is mentioned among all NFA 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // configurations then there is no possibility of needing to look 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // beyond this state; also no possibility of a nondeterminism. 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // This optimization May 22, 2006 just dropped -Xint time 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for analysis of Java grammar from 11.5s to 2s! Wow. 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure(t); // add any NFA states reachable via epsilon 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("DFA state after closure "+d+"-"+ 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label.toString(dfa.nfa.grammar)+ 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver "->"+t); 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add if not in DFA yet and then make d-label->t 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState targetState = addDFAStateToWorkList(t); 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numberOfEdgesEmanating += 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver addTransition(d, label, targetState, targetToLabelMap); 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // lookahead of target must be one larger than d's k 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // We are possibly setting the depth of a pre-existing state 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // that is equal to one we just computed...not sure if that's 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // ok. 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver targetState.setLookaheadDepth(d.getLookaheadDepth() + 1); 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("DFA after reach / closures:\n"+dfa); 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !d.isResolvedWithPredicates() && numberOfEdgesEmanating==0 ) { 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("dangling DFA state "+d+"\nAfter reach / closures:\n"+dfa); 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: can fixed lookahead hit a dangling state case? 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: yes, with left recursion 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.err.println("dangling state alts: "+d.getAltSet()); 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.probe.reportDanglingState(d); 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // turn off all configurations except for those associated with 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // min alt number; somebody has to win else some input will not 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // predict any alt. 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int minAlt = resolveByPickingMinAlt(d, null); 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // force it to be an accept state 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't call convertToAcceptState() which merges stop states. 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // other states point at us; don't want them pointing to dead states 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.setAcceptState(true); // might be adding new accept state for alt 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.setAcceptState(minAlt, d); 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //convertToAcceptState(d, minAlt); // force it to be an accept state 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Check to see if we need to add any semantic predicate transitions 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // might have both token and predicated edges from d 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d.isResolvedWithPredicates() ) { 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver addPredicateTransitions(d); 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Add a transition from state d to targetState with label in normal case. 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if COLLAPSE_ALL_INCIDENT_EDGES, however, try to merge all edges from 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * d to targetState; this means merging their labels. Another optimization 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is to reduce to a single EOT edge any set of edges from d to targetState 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * where there exists an EOT state. EOT is like the wildcard so don't 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * bother to test any other edges. Example: 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NUM_INT 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * : '1'..'9' ('0'..'9')* ('l'|'L')? 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | '0' ('x'|'X') ('0'..'9'|'a'..'f'|'A'..'F')+ ('l'|'L')? 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | '0' ('0'..'7')* ('l'|'L')? 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ; 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The normal decision to predict alts 1, 2, 3 is: 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if ( (input.LA(1)>='1' && input.LA(1)<='9') ) { 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=1; 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * else if ( input.LA(1)=='0' ) { 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if ( input.LA(2)=='X'||input.LA(2)=='x' ) { 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=2; 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * else if ( (input.LA(2)>='0' && input.LA(2)<='7') ) { 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=3; 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * else if ( input.LA(2)=='L'||input.LA(2)=='l' ) { 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=3; 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * else { 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=3; 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * else error 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Clearly, alt 3 is predicted with extra work since it tests 0..7 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and [lL] before finally realizing that any character is actually 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ok at k=2. 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A better decision is as follows: 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if ( (input.LA(1)>='1' && input.LA(1)<='9') ) { 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=1; 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * else if ( input.LA(1)=='0' ) { 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if ( input.LA(2)=='X'||input.LA(2)=='x' ) { 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=2; 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * else { 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt7=3; 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * } 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The DFA originally has 3 edges going to the state the predicts alt 3, 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * but upon seeing the EOT edge (the "else"-clause), this method 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * replaces the old merged label (which would have (0..7|l|L)) with EOT. 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The code generator then leaves alt 3 predicted with a simple else- 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * clause. :) 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The only time the EOT optimization makes no sense is in the Tokens 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * rule. We want EOT to truly mean you have matched an entire token 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * so don't bother actually rewinding to execute that rule unless there 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are actions in that rule. For now, since I am not preventing 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * backtracking from Tokens rule, I will simply allow the optimization. 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected static int addTransition(DFAState d, 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label label, 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState targetState, 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map targetToLabelMap) 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println(d.stateNumber+"-"+label.toString(dfa.nfa.grammar)+"->"+targetState.stateNumber); 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = 0; 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( DFAOptimizer.COLLAPSE_ALL_PARALLEL_EDGES ) { 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // track which targets we've hit 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer tI = Utils.integer(targetState.stateNumber); 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition oldTransition = (Transition)targetToLabelMap.get(tI); 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( oldTransition!=null ) { 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("extra transition to "+tI+" upon "+label.toString(dfa.nfa.grammar)); 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // already seen state d to target transition, just add label 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // to old label unless EOT 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( label.getAtom()==Label.EOT ) { 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // merge with EOT means old edge can go away 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver oldTransition.label = new Label(Label.EOT); 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't add anything to EOT, it's essentially the wildcard 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( oldTransition.label.getAtom()!=Label.EOT ) { 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // ok, not EOT, add in this label to old label 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver oldTransition.label.add(label); 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("label updated to be "+oldTransition.label.toString(dfa.nfa.grammar)); 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make a transition from d to t upon 'a' 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n = 1; 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver label = (Label)label.clone(); // clone in case we alter later 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int transitionIndex = d.addTransition(targetState, label); 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition trans = d.getTransition(transitionIndex); 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // track target/transition pairs 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver targetToLabelMap.put(tI, trans); 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver n = 1; 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.addTransition(targetState, label); 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return n; 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** For all NFA states (configurations) merged in d, 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * compute the epsilon closure; that is, find all NFA states reachable 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from the NFA states in d via purely epsilon transitions. 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void closure(DFAState d) { 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("closure("+d+")"); 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<NFAConfiguration> configs = new ArrayList<NFAConfiguration>(); 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Because we are adding to the configurations in closure 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // must clone initial list so we know when to stop doing closure 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configs.addAll(d.nfaConfigurations); 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for each NFA configuration in d (abort if we detect non-LL(*) state) 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = configs.size(); 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration c = (NFAConfiguration)configs.get(i); 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( c.singleAtomTransitionEmanating ) { 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; // ignore NFA states w/o epsilon transitions 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("go do reach for NFA state "+c.state); 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // figure out reachable NFA states from each of d's nfa states 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // via epsilon transitions. 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Fill configsInClosure rather than altering d configs inline 477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure(dfa.nfa.getState(c.state), 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.alt, 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.context, 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.semanticContext, 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d, 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver false); 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("after closure d="+d); 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.closureBusy = null; // wack all that memory used during closure 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Where can we get from NFA state p traversing only epsilon transitions? 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Add new NFA states + context to DFA state d. Also add semantic 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicates to semantic context if collectPredicates is set. We only 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * collect predicates at hoisting depth 0, meaning before any token/char 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * have been recognized. This corresponds, during analysis, to the 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * initial DFA start state construction closure() invocation. 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * There are four cases of interest (the last being the usual transition): 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Traverse an edge that takes us to the start state of another 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * rule, r. We must push this state so that if the DFA 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * conversion hits the end of rule r, then it knows to continue 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the conversion at state following state that "invoked" r. By 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * construction, there is a single transition emanating from a rule 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ref node. 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Reach an NFA state associated with the end of a rule, r, in the 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * grammar from which it was built. We must add an implicit (i.e., 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * don't actually add an epsilon transition) epsilon transition 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from r's end state to the NFA state following the NFA state 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that transitioned to rule r's start state. Because there are 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * many states that could reach r, the context for a rule invocation 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is part of a call tree not a simple stack. When we fall off end 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of rule, "pop" a state off the call tree and add that state's 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * "following" node to d's NFA configuration list. The context 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for this new addition will be the new "stack top" in the call tree. 514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. Like case 2, we reach an NFA state associated with the end of a 516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * rule, r, in the grammar from which NFA was built. In this case, 517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * however, we realize that during this NFA->DFA conversion, no state 518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * invoked the current rule's NFA. There is no choice but to add 519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * all NFA states that follow references to r's start state. This is 520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * analogous to computing the FOLLOW(r) in the LL(k) world. By 521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * construction, even rule stop state has a chain of nodes emanating 522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from it that points to every possible following node. This case 523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is conveniently handled then by the 4th case. 524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 4. Normal case. If p can reach another NFA state q, then add 526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * q to d's configuration list, copying p's context for q's context. 527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If there is a semantic predicate on the transition, then AND it 528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with any existing semantic context. 529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Current state p is always added to d's configuration list as it's part 531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of the closure as well. 532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * When is a closure operation in a cycle condition? While it is 534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * very possible to have the same NFA state mentioned twice 535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * within the same DFA state, there are two situations that 536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * would lead to nontermination of closure operation: 537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * o Whenever closure reaches a configuration where the same state 539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with same or a suffix context already exists. This catches 540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the IF-THEN-ELSE tail recursion cycle and things like 541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : A a | B ; 543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the context will be $ (empty stack). 545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * We have to check 547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * larger context stacks because of (...)+ loops. For 548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * example, the context of a (...)+ can be nonempty if the 549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * surrounding rule is invoked by another rule: 550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : b A | X ; 552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * b : (B|)+ ; // nondeterministic by the way 553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The context of the (B|)+ loop is "invoked from item 555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : . b A ;" and then the empty alt of the loop can reach back 556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to itself. The context stack will have one "return 557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * address" element and so we must check for same state, same 558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * context for arbitrary context stacks. 559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Idea: If we've seen this configuration before during closure, stop. 561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * We also need to avoid reaching same state with conflicting context. 562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Ultimately analysis would stop and we'd find the conflict, but we 563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * should stop the computation. Previously I only checked for 564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * exact config. Need to check for same state, suffix context 565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * not just exact context. 566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * o Whenever closure reaches a configuration where state p 568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is present in its own context stack. This means that 569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * p is a rule invocation state and the target rule has 570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * been called before. NFAContext.MAX_RECURSIVE_INVOCATIONS 571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (See the comment there also) determines how many times 572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * it's possible to recurse; clearly we cannot recurse forever. 573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Some grammars such as the following actually require at 574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * least one recursive call to correctly compute the lookahead: 575324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 576324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : L ID R 577324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | b 578324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ; 579324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * b : ID 580324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | L a R 581324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ; 582324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 583324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Input L ID R is ambiguous but to figure this out, ANTLR 584324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * needs to go a->b->a->b to find the L ID sequence. 585324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 586324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Do not allow closure to add a configuration that would 587324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * allow too much recursion. 588324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 589324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This case also catches infinite left recursion. 590324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 591324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void closure(NFAState p, 592324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt, 593324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext context, 594324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext semanticContext, 595324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState d, 596324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean collectPredicates) 597324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 598324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ){ 599324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("closure at "+p.enclosingRule.name+" state "+p.stateNumber+"|"+ 600324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver alt+" filling DFA state "+d.stateNumber+" with context "+context 601324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ); 602324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 603324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 604324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// if ( DFA.MAX_TIME_PER_DFA_CREATION>0 && 605324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// System.currentTimeMillis() - d.dfa.conversionStartTime >= 606324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// DFA.MAX_TIME_PER_DFA_CREATION ) 607324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// { 608324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// // bail way out; we've blown up somehow 609324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// throw new AnalysisTimeoutException(d.dfa); 610324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// } 611324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 612324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration proposedNFAConfiguration = 613324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new NFAConfiguration(p.stateNumber, 614324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver alt, 615324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver context, 616324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver semanticContext); 617324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 618324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Avoid infinite recursion 619324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( closureIsBusy(d, proposedNFAConfiguration) ) { 620324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 621324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("avoid visiting exact closure computation NFA config: "+ 622324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver proposedNFAConfiguration+" in "+p.enclosingRule.name); 623324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("state is "+d.dfa.decisionNumber+"."+d.stateNumber); 624324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 625324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 626324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 627324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 628324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // set closure to be busy for this NFA configuration 629324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.closureBusy.add(proposedNFAConfiguration); 630324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 631324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // p itself is always in closure 632324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.addNFAConfiguration(p, proposedNFAConfiguration); 633324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 634324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Case 1: are we a reference to another rule? 635324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition0 = p.transition[0]; 636324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0 instanceof RuleClosureTransition ) { 637324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int depth = context.recursionDepthEmanatingFromState(p.stateNumber); 638324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Detect recursion by more than a single alt, which indicates 639324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // that the decision's lookahead language is potentially non-regular; terminate 640324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( depth == 1 && d.dfa.getUserMaxLookahead()==0 ) { // k=* only 641324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.dfa.recursiveAltSet.add(alt); // indicate that this alt is recursive 642324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d.dfa.recursiveAltSet.size()>1 ) { 643324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("recursive alts: "+d.dfa.recursiveAltSet.toString()); 644324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.abortedDueToMultipleRecursiveAlts = true; 645324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new NonLLStarDecisionException(d.dfa); 646324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 647324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 648324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("alt "+alt+" in rule "+p.enclosingRule+" dec "+d.dfa.decisionNumber+ 649324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " ctx: "+context); 650324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("d="+d); 651324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 652324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 653324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Detect an attempt to recurse too high 654324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if this context has hit the max recursions for p.stateNumber, 655324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't allow it to enter p.stateNumber again 656324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( depth >= NFAContext.MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK ) { 657324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 658324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("OVF state "+d); 659324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("proposed "+proposedNFAConfiguration); 660324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 661324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.abortedDueToRecursionOverflow = true; 662324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.dfa.probe.reportRecursionOverflow(d, proposedNFAConfiguration); 663324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 664324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("analysis overflow in closure("+d.stateNumber+")"); 665324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 666324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 667324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 668324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 669324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // otherwise, it's cool to (re)enter target of this rule ref 670324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver RuleClosureTransition ref = (RuleClosureTransition)transition0; 671324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // first create a new context and push onto call tree, 672324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // recording the fact that we are invoking a rule and 673324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // from which state (case 2 below will get the following state 674324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // via the RuleClosureTransition emanating from the invoking state 675324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // pushed on the stack). 676324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Reset the context to reflect the fact we invoked rule 677324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext newContext = new NFAContext(context, p); 678324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("invoking rule "+ref.rule.name); 679324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // System.out.println(" context="+context); 680324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // traverse epsilon edge to new rule 681324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState ruleTarget = (NFAState)ref.target; 682324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure(ruleTarget, alt, newContext, semanticContext, d, collectPredicates); 683324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 684324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Case 2: end of rule state, context (i.e., an invoker) exists 685324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( p.isAcceptState() && context.parent!=null ) { 686324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState whichStateInvokedRule = context.invokingState; 687324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver RuleClosureTransition edgeToRule = 688324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (RuleClosureTransition)whichStateInvokedRule.transition[0]; 689324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState continueState = edgeToRule.followState; 690324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAContext newContext = context.parent; // "pop" invoking state 691324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure(continueState, alt, newContext, semanticContext, d, collectPredicates); 692324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 693324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Case 3: end of rule state, nobody invoked this rule (no context) 694324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Fall thru to be handled by case 4 automagically. 695324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Case 4: ordinary NFA->DFA conversion case: simple epsilon transition 696324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 697324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // recurse down any epsilon transitions 698324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0!=null && transition0.isEpsilon() ) { 699324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean collectPredicatesAfterAction = collectPredicates; 700324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition0.isAction() && collectPredicates ) { 701324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver collectPredicatesAfterAction = false; 702324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 703324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( computingStartState ) { 704324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("found action during prediction closure "+((ActionLabel)transition0.label).actionAST.token); 705324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 706324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 707324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 708324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure((NFAState)transition0.target, 709324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver alt, 710324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver context, 711324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver semanticContext, 712324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d, 713324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver collectPredicatesAfterAction 714324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ); 715324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 716324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( transition0!=null && transition0.isSemanticPredicate() ) { 717324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext labelContext = transition0.label.getSemanticContext(); 718324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( computingStartState ) { 719324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( collectPredicates ) { 720324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // only indicate we can see a predicate if we're collecting preds 721324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Could be computing start state & seen an action before this. 722324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.predicateVisible = true; 723324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 724324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 725324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // this state has a pred, but we can't see it. 726324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.hasPredicateBlockedByAction = true; 727324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // System.out.println("found pred during prediction but blocked by action found previously"); 728324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 729324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 730324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // continue closure here too, but add the sem pred to ctx 731324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext newSemanticContext = semanticContext; 732324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( collectPredicates ) { 733324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // AND the previous semantic context with new pred 734324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // do not hoist syn preds from other rules; only get if in 735324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // starting state's rule (i.e., context is empty) 736324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int walkAlt = 737324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.decisionNFAStartState.translateDisplayAltToWalkAlt(alt); 738324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState altLeftEdge = 739324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.getNFAStateForAltOfDecision(dfa.decisionNFAStartState,walkAlt); 740324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 741324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("state "+p.stateNumber+" alt "+alt+" walkAlt "+walkAlt+" trans to "+transition0.target); 742324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("DFA start state "+dfa.decisionNFAStartState.stateNumber); 743324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("alt left edge "+altLeftEdge.stateNumber+ 744324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ", epsilon target "+ 745324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altLeftEdge.transition(0).target.stateNumber); 746324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 747324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !labelContext.isSyntacticPredicate() || 748324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver p==altLeftEdge.transition[0].target ) 749324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 750324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("&"+labelContext+" enclosingRule="+p.enclosingRule); 751324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newSemanticContext = 752324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.and(semanticContext, labelContext); 753324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 754324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 755324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure((NFAState)transition0.target, 756324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver alt, 757324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver context, 758324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newSemanticContext, 759324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d, 760324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver collectPredicates); 761324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 762324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition transition1 = p.transition[1]; 763324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( transition1!=null && transition1.isEpsilon() ) { 764324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver closure((NFAState)transition1.target, 765324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver alt, 766324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver context, 767324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver semanticContext, 768324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d, 769324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver collectPredicates); 770324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 771324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 772324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 773324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // don't remove "busy" flag as we want to prevent all 774324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // references to same config of state|alt|ctx|semCtx even 775324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if resulting from another NFA state 776324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 777324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 778324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** A closure operation should abort if that computation has already 779324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * been done or a computation with a conflicting context has already 780324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * been done. If proposed NFA config's state and alt are the same 781324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * there is potentially a problem. If the stack context is identical 782324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * then clearly the exact same computation is proposed. If a context 783324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is a suffix of the other, then again the computation is in an 784324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * identical context. ?$ and ??$ are considered the same stack. 785324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * We could walk configurations linearly doing the comparison instead 786324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of a set for exact matches but it's much slower because you can't 787324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * do a Set lookup. I use exact match as ANTLR 788324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * always detect the conflict later when checking for context suffixes... 789324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * I check for left-recursive stuff and terminate before analysis to 790324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * avoid need to do this more expensive computation. 791324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 792324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 12-31-2007: I had to use the loop again rather than simple 793324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * closureBusy.contains(proposedNFAConfiguration) lookup. The 794324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * semantic context should not be considered when determining if 795324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a closure operation is busy. I saw a FOLLOW closure operation 796324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * spin until time out because the predicate context kept increasing 797324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in size even though it's same boolean value. This seems faster also 798324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * because I'm not doing String.equals on the preds all the time. 799324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 800324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 05-05-2008: Hmm...well, i think it was a mistake to remove the sem 801324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ctx check below...adding back in. Coincides with report of ANTLR 802324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * getting super slow: http://www.antlr.org:8888/browse/ANTLR-235 803324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This could be because it doesn't properly compute then resolve 804324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a predicate expression. Seems to fix unit test: 805324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TestSemanticPredicates.testSemanticContextPreventsEarlyTerminationOfClosure() 806324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Changing back to Set from List. Changed a large grammar from 8 minutes 807324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to 11 seconds. Cool. Closing ANTLR-235. 808324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 809324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static boolean closureIsBusy(DFAState d, 810324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration proposedNFAConfiguration) 811324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 812324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return d.closureBusy.contains(proposedNFAConfiguration); 813324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 814324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = d.closureBusy.size(); 815324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Check epsilon cycle (same state, same alt, same context) 816324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 817324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration c = (NFAConfiguration) d.closureBusy.get(i); 818324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( proposedNFAConfiguration.state==c.state && 819324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver proposedNFAConfiguration.alt==c.alt && 820324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver proposedNFAConfiguration.semanticContext.equals(c.semanticContext) && 821324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver proposedNFAConfiguration.context.suffix(c.context) ) 822324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 823324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 824324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 825324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 826324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 827324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 828324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 829324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 830324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Given the set of NFA states in DFA state d, find all NFA states 831324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * reachable traversing label arcs. By definition, there can be 832324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * only one DFA state reachable by an atom from DFA state d so we must 833324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * find and merge all NFA states reachable via label. Return a new 834324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DFAState that has all of those NFA states with their context (i.e., 835324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * which alt do they predict and where to return to if they fall off 836324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * end of a rule). 837324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 838324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Because we cannot jump to another rule nor fall off the end of a rule 839324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * via a non-epsilon transition, NFA states reachable from d have the 840324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * same configuration as the NFA state in d. So if NFA state 7 in d's 841324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * configurations can reach NFA state 13 then 13 will be added to the 842324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * new DFAState (labelDFATarget) with the same configuration as state 843324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 7 had. 844324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 845324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This method does not see EOT transitions off the end of token rule 846324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * accept states if the rule was invoked by somebody. 847324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 848324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public DFAState reach(DFAState d, Label label) { 849324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("reach "+label.toString(dfa.nfa.grammar)+" from "+d.stateNumber); 850324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState labelDFATarget = dfa.newState(); 851324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 852324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for each NFA state in d with a labeled edge, 853324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add in target states for label 854324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("size(d.state="+d.stateNumber+")="+d.nfaConfigurations.size()); 855324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("size(labeled edge states)="+d.configurationsWithLabeledEdges.size()); 856324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<NFAConfiguration> configs = d.configurationsWithLabeledEdges; 857324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = configs.size(); 858324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 859324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration c = configs.get(i); 860324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( c.resolved || c.resolveWithPredicate ) { 861324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; // the conflict resolver indicates we must leave alone 862324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 863324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState p = dfa.nfa.getState(c.state); 864324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // by design of the grammar->NFA conversion, only transition 0 865324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // may have a non-epsilon edge. 866324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition edge = p.transition[0]; 867324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( edge==null || !c.singleAtomTransitionEmanating ) { 868324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 869324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 870324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label edgeLabel = edge.label; 871324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 872324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // SPECIAL CASE 873324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if it's an EOT transition on end of lexer rule, but context 874324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // stack is not empty, then don't see the EOT; the closure 875324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // will have added in the proper states following the reference 876324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // to this rule in the invoking rule. In other words, if 877324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // somebody called this rule, don't see the EOT emanating from 878324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // this accept state. 879324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( c.context.parent!=null && edgeLabel.label==Label.EOT ) { 880324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 881324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 882324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 883324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Labels not unique at this point (not until addReachableLabels) 884324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // so try simple int label match before general set intersection 885324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("comparing "+edgeLabel+" with "+label); 886324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( Label.intersect(label, edgeLabel) ) { 887324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // found a transition with label; 888324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add NFA target to (potentially) new DFA state 889324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration newC = labelDFATarget.addNFAConfiguration( 890324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (NFAState)edge.target, 891324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.alt, 892324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.context, 893324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.semanticContext); 894324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 895324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 896324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( labelDFATarget.nfaConfigurations.size()==0 ) { 897324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // kill; it's empty 898324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.setState(labelDFATarget.stateNumber, null); 899324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver labelDFATarget = null; 900324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 901324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return labelDFATarget; 902324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 903324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 904324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Walk the configurations of this DFA state d looking for the 905324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * configuration, c, that has a transition on EOT. State d should 906324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * be converted to an accept state predicting the c.alt. Blast 907324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * d's current configuration set and make it just have config c. 908324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 909324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO: can there be more than one config with EOT transition? 910324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * That would mean that two NFA configurations could reach the 911324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * end of the token with possibly different predicted alts. 912324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Seems like that would be rare or impossible. Perhaps convert 913324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this routine to find all such configs and give error if >1. 914324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 915324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void convertToEOTAcceptState(DFAState d) { 916324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label eot = new Label(Label.EOT); 917324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = d.nfaConfigurations.size(); 918324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 919324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration c = (NFAConfiguration)d.nfaConfigurations.get(i); 920324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( c.resolved || c.resolveWithPredicate ) { 921324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; // the conflict resolver indicates we must leave alone 922324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 923324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState p = dfa.nfa.getState(c.state); 924324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Transition edge = p.transition[0]; 925324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Label edgeLabel = edge.label; 926324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( edgeLabel.equals(eot) ) { 927324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("config with EOT: "+c); 928324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.setAcceptState(true); 929324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("d goes from "+d); 930324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.nfaConfigurations.clear(); 931324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.addNFAConfiguration(p,c.alt,c.context,c.semanticContext); 932324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("to "+d); 933324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; // assume only one EOT transition 934324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 935324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 936324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 937324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 938324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Add a new DFA state to the DFA if not already present. 939324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If the DFA state uniquely predicts a single alternative, it 940324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * becomes a stop state; don't add to work list. Further, if 941324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * there exists an NFA state predicted by > 1 different alternatives 942324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and with the same syn and sem context, the DFA is nondeterministic for 943324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * at least one input sequence reaching that NFA state. 944324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 945324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected DFAState addDFAStateToWorkList(DFAState d) { 946324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState existingState = dfa.addState(d); 947324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d != existingState ) { 948324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // already there...use/return the existing DFA state. 949324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // But also set the states[d.stateNumber] to the existing 950324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // DFA state because the closureIsBusy must report 951324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // infinite recursion on a state before it knows 952324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // whether or not the state will already be 953324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // found after closure on it finishes. It could be 954324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // referring to a state that will ultimately not make it 955324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // into the reachable state space and the error 956324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // reporting must be able to compute the path from 957324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // start to the error state with infinite recursion 958324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.setState(d.stateNumber, existingState); 959324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return existingState; 960324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 961324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 962324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if not there, then examine new state. 963324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 964324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // resolve syntactic conflicts by choosing a single alt or 965324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // by using semantic predicates if present. 966324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver resolveNonDeterminisms(d); 967324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 968324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // If deterministic, don't add this state; it's an accept state 969324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Just return as a valid DFA state 970324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt = d.getUniquelyPredictedAlt(); 971324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( alt!=NFA.INVALID_ALT_NUMBER ) { // uniquely predicts an alt? 972324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d = convertToAcceptState(d, alt); 973324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 974324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("convert to accept; DFA "+d.dfa.decisionNumber+" state "+d.stateNumber+" uniquely predicts alt "+ 975324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.getUniquelyPredictedAlt()); 976324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 977324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 978324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 979324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // unresolved, add to work list to continue NFA conversion 980324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver work.add(d); 981324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 982324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return d; 983324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 984324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 985324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected DFAState convertToAcceptState(DFAState d, int alt) { 986324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // only merge stop states if they are deterministic and no 987324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // recursion problems and only if they have the same gated pred 988324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // context! 989324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Later, the error reporting may want to trace the path from 990324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the start state to the nondet state 991324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( DFAOptimizer.MERGE_STOP_STATES && 992324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.getNonDeterministicAlts()==null && 993324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver !d.abortedDueToRecursionOverflow && 994324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver !d.abortedDueToMultipleRecursiveAlts ) 995324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 996324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // check to see if we already have an accept state for this alt 997324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // [must do this after we resolve nondeterminisms in general] 998324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState acceptStateForAlt = dfa.getAcceptState(alt); 999324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( acceptStateForAlt!=null ) { 1000324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // we already have an accept state for alt; 1001324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Are their gate sem pred contexts the same? 1002324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // For now we assume a braindead version: both must not 1003324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // have gated preds or share exactly same single gated pred. 1004324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // The equals() method is only defined on Predicate contexts not 1005324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // OR etc... 1006324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext gatedPreds = d.getGatedPredicatesInNFAConfigurations(); 1007324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext existingStateGatedPreds = 1008324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver acceptStateForAlt.getGatedPredicatesInNFAConfigurations(); 1009324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( (gatedPreds==null && existingStateGatedPreds==null) || 1010324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ((gatedPreds!=null && existingStateGatedPreds!=null) && 1011324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver gatedPreds.equals(existingStateGatedPreds)) ) 1012324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 1013324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // make this d.statenumber point at old DFA state 1014324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.setState(d.stateNumber, acceptStateForAlt); 1015324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.removeState(d); // remove this state from unique DFA state set 1016324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d = acceptStateForAlt; // use old accept state; throw this one out 1017324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return d; 1018324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1019324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // else consider it a new accept state; fall through. 1020324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1021324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1022324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.setAcceptState(true); // new accept state for alt 1023324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.setAcceptState(alt, d); 1024324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return d; 1025324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1026324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1027324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** If > 1 NFA configurations within this DFA state have identical 1028324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NFA state and context, but differ in their predicted 1029324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * TODO update for new context suffix stuff 3-9-2005 1030324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alternative then a single input sequence predicts multiple alts. 1031324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The NFA decision is therefore syntactically indistinguishable 1032324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from the left edge upon at least one input sequence. We may 1033324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * terminate the NFA to DFA conversion for these paths since no 1034324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * paths emanating from those NFA states can possibly separate 1035324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * these conjoined twins once interwined to make things 1036324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * deterministic (unless there are semantic predicates; see below). 1037324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1038324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Upon a nondeterministic set of NFA configurations, we should 1039324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * report a problem to the grammar designer and resolve the issue 1040324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * by aribitrarily picking the first alternative (this usually 1041324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ends up producing the most natural behavior). Pick the lowest 1042324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alt number and just turn off all NFA configurations 1043324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * associated with the other alts. Rather than remove conflicting 1044324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NFA configurations, I set the "resolved" bit so that future 1045324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * computations will ignore them. In this way, we maintain the 1046324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * complete DFA state with all its configurations, but prevent 1047324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * future DFA conversion operations from pursuing undesirable 1048324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * paths. Remember that we want to terminate DFA conversion as 1049324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * soon as we know the decision is deterministic *or* 1050324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * nondeterministic. 1051324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1052324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [BTW, I have convinced myself that there can be at most one 1053324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * set of nondeterministic configurations in a DFA state. Only NFA 1054324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * configurations arising from the same input sequence can appear 1055324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in a DFA state. There is no way to have another complete set 1056324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of nondeterministic NFA configurations without another input 1057324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * sequence, which would reach a different DFA state. Therefore, 1058324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the two nondeterministic NFA configuration sets cannot collide 1059324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in the same DFA state.] 1060324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1061324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Consider DFA state {(s|1),(s|2),(s|3),(t|3),(v|4)} where (s|a) 1062324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is state 's' and alternative 'a'. Here, configuration set 1063324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * {(s|1),(s|2),(s|3)} predicts 3 different alts. Configurations 1064324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (s|2) and (s|3) are "resolved", leaving {(s|1),(t|3),(v|4)} as 1065324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * items that must still be considered by the DFA conversion 1066324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * algorithm in DFA.findNewDFAStatesAndAddDFATransitions(). 1067324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1068324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Consider the following grammar where alts 1 and 2 are no 1069324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * problem because of the 2nd lookahead symbol. Alts 3 and 4 are 1070324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * identical and will therefore reach the rule end NFA state but 1071324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicting 2 different alts (no amount of future lookahead 1072324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * will render them deterministic/separable): 1073324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1074324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : A B 1075324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | A C 1076324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | A 1077324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | A 1078324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ; 1079324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1080324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Here is a (slightly reduced) NFA of this grammar: 1081324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1082324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (1)-A->(2)-B->(end)-EOF->(8) 1083324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | ^ 1084324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (2)-A->(3)-C----| 1085324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | ^ 1086324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (4)-A->(5)------| 1087324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | ^ 1088324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (6)-A->(7)------| 1089324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1090324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * where (n) is NFA state n. To begin DFA conversion, the start 1091324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * state is created: 1092324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1093324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * {(1|1),(2|2),(4|3),(6|4)} 1094324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1095324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Upon A, all NFA configurations lead to new NFA states yielding 1096324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * new DFA state: 1097324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1098324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * {(2|1),(3|2),(5|3),(7|4),(end|3),(end|4)} 1099324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * where the configurations with state end in them are added 1101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * during the epsilon closure operation. State end predicts both 1102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alts 3 and 4. An error is reported, the latter configuration is 1103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * flagged as resolved leaving the DFA state as: 1104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * {(2|1),(3|2),(5|3),(7|4|resolved),(end|3),(end|4|resolved)} 1106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * As NFA configurations are added to a DFA state during its 1108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * construction, the reachable set of labels is computed. Here 1109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * reachable is {B,C,EOF} because there is at least one NFA state 1110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in the DFA state that can transition upon those symbols. 1111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The final DFA looks like: 1113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * {(1|1),(2|2),(4|3),(6|4)} 1115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | 1116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * v 1117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * {(2|1),(3|2),(5|3),(7|4),(end|3),(end|4)} -B-> (end|1) 1118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | | 1119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * C ----EOF-> (8,3) 1120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * | 1121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * v 1122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (end|2) 1123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Upon AB, alt 1 is predicted. Upon AC, alt 2 is predicted. 1125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Upon A EOF, alt 3 is predicted. Alt 4 is not a viable 1126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * alternative. 1127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The algorithm is essentially to walk all the configurations 1129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * looking for a conflict of the form (s|i) and (s|j) for i!=j. 1130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Use a hash table to track state+context pairs for collisions 1131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * so that we have O(n) to walk the n configurations looking for 1132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a conflict. Upon every conflict, track the alt number so 1133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * we have a list of all nondeterministically predicted alts. Also 1134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * track the minimum alt. Next go back over the configurations, setting 1135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the "resolved" bit for any that have an alt that is a member of 1136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the nondeterministic set. This will effectively remove any alts 1137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * but the one we want from future consideration. 1138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * See resolveWithSemanticPredicates() 1140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * AMBIGUOUS TOKENS 1142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * With keywords and ID tokens, there is an inherit ambiguity in that 1144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * "int" can be matched by ID also. Each lexer rule has an EOT 1145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * transition emanating from it which is used whenever the end of 1146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a rule is reached and another token rule did not invoke it. EOT 1147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is the only thing that can be seen next. If two rules are identical 1148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * like "int" and "int" then the 2nd def is unreachable and you'll get 1149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a warning. We prevent a warning though for the keyword/ID issue as 1150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ID is still reachable. This can be a bit weird. '+' rule then a 1151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * '+'|'+=' rule will fail to match '+' for the 2nd rule. 1152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If all NFA states in this DFA state are targets of EOT transitions, 1154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (and there is more than one state plus no unique alt is predicted) 1155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * then DFA conversion will leave this state as a dead state as nothing 1156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * can be reached from this state. To resolve the ambiguity, just do 1157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * what flex and friends do: pick the first rule (alt in this case) to 1158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * win. This means you should put keywords before the ID rule. 1159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If the DFA state has only one NFA state then there is no issue: 1160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * it uniquely predicts one alt. :) Problem 1161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * states will look like this during conversion: 1162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DFA 1:{9|1, 19|2, 14|3, 20|2, 23|2, 24|2, ...}-<EOT>->5:{41|3, 42|2} 1164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Worse, when you have two identical literal rules, you will see 3 alts 1166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in the EOT state (one for ID and one each for the identical rules). 1167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void resolveNonDeterminisms(DFAState d) { 1169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 1170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("resolveNonDeterminisms "+d.toString()); 1171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean conflictingLexerRules = false; 1173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set nondeterministicAlts = d.getNonDeterministicAlts(); 1174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug && nondeterministicAlts!=null ) { 1175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("nondet alts="+nondeterministicAlts); 1176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // CHECK FOR AMBIGUOUS EOT (if |allAlts|>1 and EOT state, resolve) 1179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // grab any config to see if EOT state; any other configs must 1180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // transition on EOT to get to this DFA state as well so all 1181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // states in d must be targets of EOT. These are the end states 1182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // created in NFAFactory.build_EOFState 1183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration anyConfig = d.nfaConfigurations.get(0); 1184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState anyState = dfa.nfa.getState(anyConfig.state); 1185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if d is target of EOT and more than one predicted alt 1187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // indicate that d is nondeterministic on all alts otherwise 1188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // it looks like state has no problem 1189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( anyState.isEOTTargetState() ) { 1190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set allAlts = d.getAltSet(); 1191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // is more than 1 alt predicted? 1192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( allAlts!=null && allAlts.size()>1 ) { 1193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nondeterministicAlts = allAlts; 1194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // track Tokens rule issues differently than other decisions 1195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d.dfa.isTokensRuleDecision() ) { 1196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.probe.reportLexerRuleNondeterminism(d,allAlts); 1197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("Tokens rule DFA state "+d+" nondeterministic"); 1198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver conflictingLexerRules = true; 1199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if no problems return unless we aborted work on d to avoid inf recursion 1204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !d.abortedDueToRecursionOverflow && nondeterministicAlts==null ) { 1205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; // no problems, return 1206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if we're not a conflicting lexer rule and we didn't abort, report ambig 1209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // We should get a report for abort so don't give another 1210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !d.abortedDueToRecursionOverflow && !conflictingLexerRules ) { 1211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: with k=x option set, this is called twice for same state 1212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.probe.reportNondeterminism(d, nondeterministicAlts); 1213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: how to turn off when it's only the FOLLOW that is 1214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // conflicting. This used to shut off even alts i,j < n 1215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // conflict warnings. :( 1216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // ATTEMPT TO RESOLVE WITH SEMANTIC PREDICATES 1219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver boolean resolved = 1220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tryToResolveWithSemanticPredicates(d, nondeterministicAlts); 1221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( resolved ) { 1222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( debug ) { 1223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("resolved DFA state "+d.stateNumber+" with pred"); 1224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.resolvedWithPredicates = true; 1226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.probe.reportNondeterminismResolvedWithSemanticPredicate(d); 1227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 1228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // RESOLVE SYNTACTIC CONFLICT BY REMOVING ALL BUT ONE ALT 1231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver resolveByChoosingFirstAlt(d, nondeterministicAlts); 1232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("state "+d.stateNumber+" resolved to alt "+winningAlt); 1234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int resolveByChoosingFirstAlt(DFAState d, Set nondeterministicAlts) { 1237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int winningAlt = 0; 1238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( dfa.isGreedy() ) { 1239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver winningAlt = resolveByPickingMinAlt(d,nondeterministicAlts); 1240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // If nongreedy, the exit alt shout win, but only if it's 1243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // involved in the nondeterminism! 1244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 1245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("resolving exit alt for decision="+ 1246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.decisionNumber+" state="+d); 1247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("nondet="+nondeterministicAlts); 1248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("exit alt "+exitAlt); 1249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int exitAlt = dfa.getNumberOfAlts(); 1251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nondeterministicAlts.contains(Utils.integer(exitAlt)) ) { 1252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if nongreedy and exit alt is one of those nondeterministic alts 1253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // predicted, resolve in favor of what follows block 1254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver winningAlt = resolveByPickingExitAlt(d,nondeterministicAlts); 1255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver winningAlt = resolveByPickingMinAlt(d,nondeterministicAlts); 1258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return winningAlt; 1261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Turn off all configurations associated with the 1264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * set of incoming nondeterministic alts except the min alt number. 1265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * There may be many alts among the configurations but only turn off 1266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the ones with problems (other than the min alt of course). 1267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If nondeterministicAlts is null then turn off all configs 'cept those 1269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * associated with the minimum alt. 1270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Return the min alt found. 1272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int resolveByPickingMinAlt(DFAState d, Set nondeterministicAlts) { 1274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int min = Integer.MAX_VALUE; 1275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nondeterministicAlts!=null ) { 1276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver min = getMinAlt(nondeterministicAlts); 1277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver min = d.minAltInConfigurations; 1280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver turnOffOtherAlts(d, min, nondeterministicAlts); 1283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return min; 1285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Resolve state d by choosing exit alt, which is same value as the 1288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * number of alternatives. Return that exit alt. 1289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected int resolveByPickingExitAlt(DFAState d, Set nondeterministicAlts) { 1291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int exitAlt = dfa.getNumberOfAlts(); 1292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver turnOffOtherAlts(d, exitAlt, nondeterministicAlts); 1293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return exitAlt; 1294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** turn off all states associated with alts other than the good one 1297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (as long as they are one of the nondeterministic ones) 1298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected static void turnOffOtherAlts(DFAState d, int min, Set<Integer> nondeterministicAlts) { 1300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = d.nfaConfigurations.size(); 1301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 1302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration configuration = (NFAConfiguration)d.nfaConfigurations.get(i); 1303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( configuration.alt!=min ) { 1304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nondeterministicAlts==null || 1305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nondeterministicAlts.contains(Utils.integer(configuration.alt)) ) 1306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 1307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configuration.resolved = true; 1308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected static int getMinAlt(Set<Integer> nondeterministicAlts) { 1314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int min = Integer.MAX_VALUE; 1315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Integer altI : nondeterministicAlts) { 1316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt = altI.intValue(); 1317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( alt < min ) { 1318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver min = alt; 1319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return min; 1322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** See if a set of nondeterministic alternatives can be disambiguated 1325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with the semantic predicate contexts of the alternatives. 1326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Without semantic predicates, syntactic conflicts are resolved 1328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * by simply choosing the first viable alternative. In the 1329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * presence of semantic predicates, you can resolve the issue by 1330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * evaluating boolean expressions at run time. During analysis, 1331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * this amounts to suppressing grammar error messages to the 1332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * developer. NFA configurations are always marked as "to be 1333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * resolved with predicates" so that 1334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DFA.findNewDFAStatesAndAddDFATransitions() will know to ignore 1335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * these configurations and add predicate transitions to the DFA 1336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * after adding token/char labels. 1337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * During analysis, we can simply make sure that for n 1339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * ambiguously predicted alternatives there are at least n-1 1340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * unique predicate sets. The nth alternative can be predicted 1341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * with "not" the "or" of all other predicates. NFA configurations without 1342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * predicates are assumed to have the default predicate of 1343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * "true" from a user point of view. When true is combined via || with 1344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * another predicate, the predicate is a tautology and must be removed 1345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * from consideration for disambiguation: 1346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a : b | B ; // hoisting p1||true out of rule b, yields no predicate 1348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * b : {p1}? B | B ; 1349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This is done down in getPredicatesPerNonDeterministicAlt(). 1351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected boolean tryToResolveWithSemanticPredicates(DFAState d, 1353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set nondeterministicAlts) 1354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 1355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map<Integer, SemanticContext> altToPredMap = 1356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getPredicatesPerNonDeterministicAlt(d, nondeterministicAlts); 1357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( altToPredMap.size()==0 ) { 1359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 1360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("nondeterministic alts with predicates: "+altToPredMap); 1363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.probe.reportAltPredicateContext(d, altToPredMap); 1364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nondeterministicAlts.size()-altToPredMap.size()>1 ) { 1366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // too few predicates to resolve; just return 1367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 1368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Handle case where 1 predicate is missing 1371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Case 1. Semantic predicates 1372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // If the missing pred is on nth alt, !(union of other preds)==true 1373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // so we can avoid that computation. If naked alt is ith, then must 1374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // test it with !(union) since semantic predicated alts are order 1375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // independent 1376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Case 2: Syntactic predicates 1377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // The naked alt is always assumed to be true as the order of 1378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // alts is the order of precedence. The naked alt will be a tautology 1379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // anyway as it's !(union of other preds). This implies 1380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // that there is no such thing as noviable alt for synpred edges 1381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // emanating from a DFA state. 1382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( altToPredMap.size()==nondeterministicAlts.size()-1 ) { 1383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if there are n-1 predicates for n nondeterministic alts, can fix 1384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver org.antlr.misc.BitSet ndSet = org.antlr.misc.BitSet.of(nondeterministicAlts); 1385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver org.antlr.misc.BitSet predSet = org.antlr.misc.BitSet.of(altToPredMap); 1386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int nakedAlt = ndSet.subtract(predSet).getSingleElement(); 1387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext nakedAltPred = null; 1388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nakedAlt == max(nondeterministicAlts) ) { 1389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the naked alt is the last nondet alt and will be the default clause 1390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nakedAltPred = new SemanticContext.TruePredicate(); 1391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // pretend naked alternative is covered with !(union other preds) 1394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // unless one of preds from other alts is a manually specified synpred 1395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // since those have precedence same as alt order. Missing synpred 1396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // is true so that alt wins (or is at least attempted). 1397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Note: can't miss any preds on alts (can't be here) if auto backtrack 1398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // since it prefixes all. 1399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // In LL(*) paper, i'll just have algorithm emit warning about uncovered 1400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // pred 1401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext unionOfPredicatesFromAllAlts = 1402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver getUnionOfPredicates(altToPredMap); 1403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("all predicates "+unionOfPredicatesFromAllAlts); 1404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( unionOfPredicatesFromAllAlts.isSyntacticPredicate() ) { 1405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nakedAltPred = new SemanticContext.TruePredicate(); 1406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nakedAltPred = 1409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.not(unionOfPredicatesFromAllAlts); 1410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("covering naked alt="+nakedAlt+" with "+nakedAltPred); 1414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToPredMap.put(Utils.integer(nakedAlt), nakedAltPred); 1416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // set all config with alt=nakedAlt to have the computed predicate 1417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = d.nfaConfigurations.size(); 1418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { // TODO: I don't think we need to do this; altToPredMap has it 1419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //7/27/10 theok, I removed it and it still seems to work with everything; leave in anyway just in case 1420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration configuration = (NFAConfiguration)d.nfaConfigurations.get(i); 1421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( configuration.alt == nakedAlt ) { 1422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configuration.semanticContext = nakedAltPred; 1423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( altToPredMap.size()==nondeterministicAlts.size() ) { 1428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // RESOLVE CONFLICT by picking one NFA configuration for each alt 1429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // and setting its resolvedWithPredicate flag 1430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // First, prevent a recursion warning on this state due to 1431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // pred resolution 1432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( d.abortedDueToRecursionOverflow ) { 1433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.dfa.probe.removeRecursiveOverflowState(d); 1434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = d.nfaConfigurations.size(); 1436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("pred map="+altToPredMap); 1437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 1438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration configuration = (NFAConfiguration)d.nfaConfigurations.get(i); 1439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext semCtx = (SemanticContext) 1440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToPredMap.get(Utils.integer(configuration.alt)); 1441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( semCtx!=null ) { 1442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // resolve (first found) with pred 1443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // and remove alt from problem list 1444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("c="+configuration); 1445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configuration.resolveWithPredicate = true; 1446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // altToPredMap has preds from all alts; store into "annointed" config 1447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configuration.semanticContext = semCtx; // reset to combined 1448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToPredMap.remove(Utils.integer(configuration.alt)); 1449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // notify grammar that we've used the preds contained in semCtx 1451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( semCtx.isSyntacticPredicate() ) { 1452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.nfa.grammar.synPredUsedInDFA(dfa, semCtx); 1453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( nondeterministicAlts.contains(Utils.integer(configuration.alt)) ) { 1456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // resolve all configurations for nondeterministic alts 1457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for which there is no predicate context by turning it off 1458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configuration.resolved = true; 1459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return true; 1462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; // couldn't fix the problem with predicates 1465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a mapping from nondeterministc alt to combined list of predicates. 1468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If both (s|i|semCtx1) and (t|i|semCtx2) exist, then the proper predicate 1469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for alt i is semCtx1||semCtx2 because you have arrived at this single 1470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DFA state via two NFA paths, both of which have semantic predicates. 1471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * We ignore deterministic alts because syntax alone is sufficient 1472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to predict those. Do not include their predicates. 1473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Alts with no predicate are assumed to have {true}? pred. 1475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * When combining via || with "true", all predicates are removed from 1477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * consideration since the expression will always be true and hence 1478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * not tell us how to resolve anything. So, if any NFA configuration 1479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in this DFA state does not have a semantic context, the alt cannot 1480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * be resolved with a predicate. 1481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If nonnull, incidentEdgeLabel tells us what NFA transition label 1483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * we did a reach on to compute state d. d may have insufficient 1484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * preds, so we really want this for the error message. 1485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Map<Integer, SemanticContext> getPredicatesPerNonDeterministicAlt(DFAState d, 1487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set nondeterministicAlts) 1488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 1489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // map alt to combined SemanticContext 1490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map<Integer, SemanticContext> altToPredicateContextMap = 1491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new HashMap<Integer, SemanticContext>(); 1492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // init the alt to predicate set map 1493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map<Integer, OrderedHashSet<SemanticContext>> altToSetOfContextsMap = 1494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new HashMap<Integer, OrderedHashSet<SemanticContext>>(); 1495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = nondeterministicAlts.iterator(); it.hasNext();) { 1496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer altI = (Integer) it.next(); 1497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToSetOfContextsMap.put(altI, new OrderedHashSet<SemanticContext>()); 1498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 1501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<Label> sampleInputLabels = d.dfa.probe.getSampleNonDeterministicInputSequence(d); 1502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String input = d.dfa.probe.getInputSequenceDisplay(sampleInputLabels); 1503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("sample input: "+input); 1504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for each configuration, create a unique set of predicates 1507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Also, track the alts with at least one uncovered configuration 1508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // (one w/o a predicate); tracks tautologies like p1||true 1509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Map<Integer, Set<Token>> altToLocationsReachableWithoutPredicate = new HashMap<Integer, Set<Token>>(); 1510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<Integer> nondetAltsWithUncoveredConfiguration = new HashSet<Integer>(); 1511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("configs="+d.nfaConfigurations); 1512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("configs with preds?"+d.atLeastOneConfigurationHasAPredicate); 1513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("configs with preds="+d.configurationsWithPredicateEdges); 1514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = d.nfaConfigurations.size(); 1515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 1516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration configuration = (NFAConfiguration)d.nfaConfigurations.get(i); 1517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer altI = Utils.integer(configuration.alt); 1518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if alt is nondeterministic, combine its predicates 1519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nondeterministicAlts.contains(altI) ) { 1520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if there is a predicate for this NFA configuration, OR in 1521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( configuration.semanticContext != 1522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.EMPTY_SEMANTIC_CONTEXT ) 1523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 1524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<SemanticContext> predSet = altToSetOfContextsMap.get(altI); 1525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predSet.add(configuration.semanticContext); 1526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if no predicate, but it's part of nondeterministic alt 1529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // then at least one path exists not covered by a predicate. 1530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // must remove predicate for this alt; track incomplete alts 1531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nondetAltsWithUncoveredConfiguration.add(altI); 1532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 1533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState s = dfa.nfa.getState(configuration.state); 1534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("###\ndec "+dfa.decisionNumber+" alt "+configuration.alt+ 1535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " enclosing rule for nfa state not covered "+ 1536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver s.enclosingRule); 1537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s.associatedASTNode!=null ) { 1538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("token="+s.associatedASTNode.token); 1539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("nfa state="+s); 1541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s.incidentEdgeLabel!=null && Label.intersect(incidentEdgeLabel, s.incidentEdgeLabel) ) { 1543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<Token> locations = altToLocationsReachableWithoutPredicate.get(altI); 1544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( locations==null ) { 1545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver locations = new HashSet<Token>(); 1546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToLocationsReachableWithoutPredicate.put(altI, locations); 1547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver locations.add(s.associatedASTNode.token); 1549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // For each alt, OR together all unique predicates associated with 1556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // all configurations 1557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Also, track the list of incompletely covered alts: those alts 1558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // with at least 1 predicate and at least one configuration w/o a 1559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // predicate. We want this in order to report to the decision probe. 1560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<Integer> incompletelyCoveredAlts = new ArrayList<Integer>(); 1561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = nondeterministicAlts.iterator(); it.hasNext();) { 1562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer altI = (Integer) it.next(); 1563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<SemanticContext> contextsForThisAlt = altToSetOfContextsMap.get(altI); 1564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nondetAltsWithUncoveredConfiguration.contains(altI) ) { // >= 1 config has no ctx 1565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( contextsForThisAlt.size()>0 ) { // && at least one pred 1566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver incompletelyCoveredAlts.add(altI); // this alt incompleted covered 1567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; // don't include at least 1 config has no ctx 1569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext combinedContext = null; 1571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator itrSet = contextsForThisAlt.iterator(); itrSet.hasNext();) { 1572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext ctx = (SemanticContext) itrSet.next(); 1573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver combinedContext = 1574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.or(combinedContext,ctx); 1575324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1576324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToPredicateContextMap.put(altI, combinedContext); 1577324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1578324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1579324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( incompletelyCoveredAlts.size()>0 ) { 1580324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 1581324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("prob in dec "+dfa.decisionNumber+" state="+d); 1582324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver FASerializer serializer = new FASerializer(dfa.nfa.grammar); 1583324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver String result = serializer.serialize(dfa.startState); 1584324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("dfa: "+result); 1585324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("incomplete alts: "+incompletelyCoveredAlts); 1586324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("nondet="+nondeterministicAlts); 1587324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("nondetAltsWithUncoveredConfiguration="+ nondetAltsWithUncoveredConfiguration); 1588324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("altToCtxMap="+altToSetOfContextsMap); 1589324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("altToPredicateContextMap="+altToPredicateContextMap); 1590324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1591324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 1592324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration configuration = (NFAConfiguration)d.nfaConfigurations.get(i); 1593324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer altI = Utils.integer(configuration.alt); 1594324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( incompletelyCoveredAlts.contains(altI) && 1595324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configuration.semanticContext == SemanticContext.EMPTY_SEMANTIC_CONTEXT ) 1596324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 1597324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAState s = dfa.nfa.getState(configuration.state); 1598324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 1599324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.print("nondet config w/o context "+configuration+ 1600324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " incident "+(s.incidentEdgeLabel!=null?s.incidentEdgeLabel.toString(dfa.nfa.grammar):null)); 1601324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s.associatedASTNode!=null ) { 1602324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.print(" token="+s.associatedASTNode.token); 1603324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1604324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else System.out.println(); 1605324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1606324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // We want to report getting to an NFA state with an 1607324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // incoming label, unless it's EOF, w/o a predicate. 1608324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s.incidentEdgeLabel!=null && s.incidentEdgeLabel.label != Label.EOF ) { 1609324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s.associatedASTNode==null || s.associatedASTNode.token==null ) { 1610324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ErrorManager.internalError("no AST/token for nonepsilon target w/o predicate"); 1611324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1612324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1613324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Set<Token> locations = altToLocationsReachableWithoutPredicate.get(altI); 1614324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( locations==null ) { 1615324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver locations = new HashSet<Token>(); 1616324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToLocationsReachableWithoutPredicate.put(altI, locations); 1617324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1618324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver locations.add(s.associatedASTNode.token); 1619324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1620324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1621324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1622324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1623324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.probe.reportIncompletelyCoveredAlts(d, 1624324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver altToLocationsReachableWithoutPredicate); 1625324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1626324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1627324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return altToPredicateContextMap; 1628324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1629324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1630324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** OR together all predicates from the alts. Note that the predicate 1631324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * for an alt could itself be a combination of predicates. 1632324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1633324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected static SemanticContext getUnionOfPredicates(Map altToPredMap) { 1634324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Iterator iter; 1635324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext unionOfPredicatesFromAllAlts = null; 1636324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver iter = altToPredMap.values().iterator(); 1637324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( iter.hasNext() ) { 1638324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext semCtx = (SemanticContext)iter.next(); 1639324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( unionOfPredicatesFromAllAlts==null ) { 1640324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver unionOfPredicatesFromAllAlts = semCtx; 1641324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1642324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 1643324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver unionOfPredicatesFromAllAlts = 1644324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SemanticContext.or(unionOfPredicatesFromAllAlts,semCtx); 1645324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1646324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1647324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return unionOfPredicatesFromAllAlts; 1648324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1649324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1650324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** for each NFA config in d, look for "predicate required" sign set 1651324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * during nondeterminism resolution. 1652324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1653324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Add the predicate edges sorted by the alternative number; I'm fairly 1654324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * sure that I could walk the configs backwards so they are added to 1655324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the predDFATarget in the right order, but it's best to make sure. 1656324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Predicates succeed in the order they are specifed. Alt i wins 1657324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * over alt i+1 if both predicates are true. 1658324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 1659324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void addPredicateTransitions(DFAState d) { 1660324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List configsWithPreds = new ArrayList(); 1661324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // get a list of all configs with predicates 1662324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numConfigs = d.nfaConfigurations.size(); 1663324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < numConfigs; i++) { 1664324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration c = (NFAConfiguration)d.nfaConfigurations.get(i); 1665324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( c.resolveWithPredicate ) { 1666324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver configsWithPreds.add(c); 1667324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1668324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1669324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Sort ascending according to alt; alt i has higher precedence than i+1 1670324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Collections.sort(configsWithPreds, 1671324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver new Comparator() { 1672324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public int compare(Object a, Object b) { 1673324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration ca = (NFAConfiguration)a; 1674324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration cb = (NFAConfiguration)b; 1675324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( ca.alt < cb.alt ) return -1; 1676324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( ca.alt > cb.alt ) return 1; 1677324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 1678324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1679324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver }); 1680324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List predConfigsSortedByAlt = configsWithPreds; 1681324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Now, we can add edges emanating from d for these preds in right order 1682324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < predConfigsSortedByAlt.size(); i++) { 1683324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NFAConfiguration c = (NFAConfiguration)predConfigsSortedByAlt.get(i); 1684324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState predDFATarget = d.dfa.getAcceptState(c.alt); 1685324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( predDFATarget==null ) { 1686324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predDFATarget = dfa.newState(); // create if not there. 1687324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // create a new DFA state that is a target of the predicate from d 1688324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predDFATarget.addNFAConfiguration(dfa.nfa.getState(c.state), 1689324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.alt, 1690324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.context, 1691324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.semanticContext); 1692324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predDFATarget.setAcceptState(true); 1693324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.setAcceptState(c.alt, predDFATarget); 1694324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DFAState existingState = dfa.addState(predDFATarget); 1695324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( predDFATarget != existingState ) { 1696324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // already there...use/return the existing DFA state that 1697324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // is a target of this predicate. Make this state number 1698324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // point at the existing state 1699324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver dfa.setState(predDFATarget.stateNumber, existingState); 1700324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver predDFATarget = existingState; 1701324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1702324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1703324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add a transition to pred target from d 1704324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver d.addTransition(predDFATarget, new PredicateLabel(c.semanticContext)); 1705324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1706324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1707324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1708324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected void initContextTrees(int numberOfAlts) { 1709324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver contextTrees = new NFAContext[numberOfAlts]; 1710324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < contextTrees.length; i++) { 1711324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int alt = i+1; 1712324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // add a dummy root node so that an NFA configuration can 1713324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // always point at an NFAContext. If a context refers to this 1714324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // node then it implies there is no call stack for 1715324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // that configuration 1716324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver contextTrees[i] = new NFAContext(null, null); 1717324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1718324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1719324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1720324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public static int max(Set s) { 1721324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( s==null ) { 1722324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Integer.MIN_VALUE; 1723324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1724324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int i = 0; 1725324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int m = 0; 1726324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (Iterator it = s.iterator(); it.hasNext();) { 1727324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver i++; 1728324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Integer I = (Integer) it.next(); 1729324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( i==1 ) { // init m with first value 1730324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver m = I.intValue(); 1731324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver continue; 1732324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1733324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( I.intValue()>m ) { 1734324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver m = I.intValue(); 1735324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1736324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1737324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return m; 1738324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1739324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 1740