| /* |
| * [The "BSD license"] |
| * Copyright (c) 2010 Terence Parr |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| package org.antlr.analysis; |
| |
| import org.antlr.grammar.v3.ANTLRParser; |
| import org.antlr.misc.MultiMap; |
| import org.antlr.misc.Utils; |
| import org.antlr.runtime.Token; |
| import org.antlr.tool.ErrorManager; |
| import org.antlr.tool.Grammar; |
| import org.antlr.tool.GrammarAST; |
| |
| import java.util.*; |
| |
| /** Collection of information about what is wrong with a decision as |
| * discovered while building the DFA predictor. |
| * |
| * The information is collected during NFA->DFA conversion and, while |
| * some of this is available elsewhere, it is nice to have it all tracked |
| * in one spot so a great error message can be easily had. I also like |
| * the fact that this object tracks it all for later perusing to make an |
| * excellent error message instead of lots of imprecise on-the-fly warnings |
| * (during conversion). |
| * |
| * A decision normally only has one problem; e.g., some input sequence |
| * can be matched by multiple alternatives. Unfortunately, some decisions |
| * such as |
| * |
| * a : ( A | B ) | ( A | B ) | A ; |
| * |
| * have multiple problems. So in general, you should approach a decision |
| * as having multiple flaws each one uniquely identified by a DFAState. |
| * For example, statesWithSyntacticallyAmbiguousAltsSet tracks the set of |
| * all DFAStates where ANTLR has discovered a problem. Recall that a decision |
| * is represented internall with a DFA comprised of multiple states, each of |
| * which could potentially have problems. |
| * |
| * Because of this, you need to iterate over this list of DFA states. You'll |
| * note that most of the informational methods like |
| * getSampleNonDeterministicInputSequence() require a DFAState. This state |
| * will be one of the iterated states from stateToSyntacticallyAmbiguousAltsSet. |
| * |
| * This class is not thread safe due to shared use of visited maps etc... |
| * Only one thread should really need to access one DecisionProbe anyway. |
| */ |
| public class DecisionProbe { |
| public DFA dfa; |
| |
| /** Track all DFA states with nondeterministic alternatives. |
| * By reaching the same DFA state, a path through the NFA for some input |
| * is able to reach the same NFA state by starting at more than one |
| * alternative's left edge. Though, later, we may find that predicates |
| * resolve the issue, but track info anyway. |
| * Note that from the DFA state, you can ask for |
| * which alts are nondeterministic. |
| */ |
| protected Set<DFAState> statesWithSyntacticallyAmbiguousAltsSet = new HashSet<DFAState>(); |
| |
| /** Track just like stateToSyntacticallyAmbiguousAltsMap, but only |
| * for nondeterminisms that arise in the Tokens rule such as keyword vs |
| * ID rule. The state maps to the list of Tokens rule alts that are |
| * in conflict. |
| */ |
| protected Map<DFAState, Set<Integer>> stateToSyntacticallyAmbiguousTokensRuleAltsMap = |
| new HashMap<DFAState, Set<Integer>>(); |
| |
| /** Was a syntactic ambiguity resolved with predicates? Any DFA |
| * state that predicts more than one alternative, must be resolved |
| * with predicates or it should be reported to the user. |
| */ |
| protected Set<DFAState> statesResolvedWithSemanticPredicatesSet = new HashSet<DFAState>(); |
| |
| /** Track the predicates for each alt per DFA state; |
| * more than one DFA state might have syntactically ambig alt prediction. |
| * Maps DFA state to another map, mapping alt number to a |
| * SemanticContext (pred(s) to execute to resolve syntactic ambiguity). |
| */ |
| protected Map<DFAState, Map<Integer,SemanticContext>> stateToAltSetWithSemanticPredicatesMap = |
| new HashMap<DFAState, Map<Integer,SemanticContext>>(); |
| |
| /** Tracks alts insufficiently covered. |
| * For example, p1||true gets reduced to true and so leaves |
| * whole alt uncovered. This maps DFA state to the set of alts |
| */ |
| protected Map<DFAState,Map<Integer, Set<Token>>> stateToIncompletelyCoveredAltsMap = |
| new HashMap<DFAState,Map<Integer, Set<Token>>>(); |
| |
| /** The set of states w/o emanating edges and w/o resolving sem preds. */ |
| protected Set<DFAState> danglingStates = new HashSet<DFAState>(); |
| |
| /** The overall list of alts within the decision that have at least one |
| * conflicting input sequence. |
| */ |
| protected Set<Integer> altsWithProblem = new HashSet<Integer>(); |
| |
| /** If decision with > 1 alt has recursion in > 1 alt, it's (likely) nonregular |
| * lookahead. The decision cannot be made with a DFA. |
| * the alts are stored in altsWithProblem. |
| */ |
| public boolean nonLLStarDecision = false; |
| |
| /** Recursion is limited to a particular depth. If that limit is exceeded |
| * the proposed new NFAConfiguration is recorded for the associated DFA state. |
| */ |
| protected MultiMap<Integer, NFAConfiguration> stateToRecursionOverflowConfigurationsMap = |
| new MultiMap<Integer, NFAConfiguration>(); |
| /* |
| protected Map<Integer, List<NFAConfiguration>> stateToRecursionOverflowConfigurationsMap = |
| new HashMap<Integer, List<NFAConfiguration>>(); |
| */ |
| |
| /** Left recursion discovered. The proposed new NFAConfiguration |
| * is recorded for the associated DFA state. |
| protected Map<Integer,List<NFAConfiguration>> stateToLeftRecursiveConfigurationsMap = |
| new HashMap<Integer,List<NFAConfiguration>>(); |
| */ |
| |
| /** Did ANTLR have to terminate early on the analysis of this decision? */ |
| protected boolean timedOut = false; |
| |
| /** Used to find paths through syntactically ambiguous DFA. If we've |
| * seen statement number before, what did we learn? |
| */ |
| protected Map<Integer, Integer> stateReachable; |
| |
| public static final Integer REACHABLE_BUSY = Utils.integer(-1); |
| public static final Integer REACHABLE_NO = Utils.integer(0); |
| public static final Integer REACHABLE_YES = Utils.integer(1); |
| |
| /** Used while finding a path through an NFA whose edge labels match |
| * an input sequence. Tracks the input position |
| * we were at the last time at this node. If same input position, then |
| * we'd have reached same state without consuming input...probably an |
| * infinite loop. Stop. Set<String>. The strings look like |
| * stateNumber_labelIndex. |
| */ |
| protected Set<String> statesVisitedAtInputDepth; |
| |
| protected Set<Integer> statesVisitedDuringSampleSequence; |
| |
| public static boolean verbose = false; |
| |
| public DecisionProbe(DFA dfa) { |
| this.dfa = dfa; |
| } |
| |
| // I N F O R M A T I O N A B O U T D E C I S I O N |
| |
| /** Return a string like "3:22: ( A {;} | B )" that describes this |
| * decision. |
| */ |
| public String getDescription() { |
| return dfa.getNFADecisionStartState().getDescription(); |
| } |
| |
| public boolean isReduced() { |
| return dfa.isReduced(); |
| } |
| |
| public boolean isCyclic() { |
| return dfa.isCyclic(); |
| } |
| |
| /** If no states are dead-ends, no alts are unreachable, there are |
| * no nondeterminisms unresolved by syn preds, all is ok with decision. |
| */ |
| public boolean isDeterministic() { |
| if ( danglingStates.size()==0 && |
| statesWithSyntacticallyAmbiguousAltsSet.size()==0 && |
| dfa.getUnreachableAlts().size()==0 ) |
| { |
| return true; |
| } |
| |
| if ( statesWithSyntacticallyAmbiguousAltsSet.size()>0 ) { |
| Iterator it = |
| statesWithSyntacticallyAmbiguousAltsSet.iterator(); |
| while ( it.hasNext() ) { |
| DFAState d = (DFAState) it.next(); |
| if ( !statesResolvedWithSemanticPredicatesSet.contains(d) ) { |
| return false; |
| } |
| } |
| // no syntactically ambig alts were left unresolved by predicates |
| return true; |
| } |
| return false; |
| } |
| |
| /** Did the analysis complete it's work? */ |
| // public boolean analysisTimedOut() { |
| // return timedOut; |
| // } |
| |
| /** Took too long to analyze a DFA */ |
| public boolean analysisOverflowed() { |
| return stateToRecursionOverflowConfigurationsMap.size()>0; |
| } |
| |
| /** Found recursion in > 1 alt */ |
| public boolean isNonLLStarDecision() { |
| return nonLLStarDecision; |
| } |
| |
| /** How many states does the DFA predictor have? */ |
| public int getNumberOfStates() { |
| return dfa.getNumberOfStates(); |
| } |
| |
| /** Get a list of all unreachable alternatives for this decision. There |
| * may be multiple alternatives with ambiguous input sequences, but this |
| * is the overall list of unreachable alternatives (either due to |
| * conflict resolution or alts w/o accept states). |
| */ |
| public List<Integer> getUnreachableAlts() { |
| return dfa.getUnreachableAlts(); |
| } |
| |
| /** return set of states w/o emanating edges and w/o resolving sem preds. |
| * These states come about because the analysis algorithm had to |
| * terminate early to avoid infinite recursion for example (due to |
| * left recursion perhaps). |
| */ |
| public Set getDanglingStates() { |
| return danglingStates; |
| } |
| |
| public Set getNonDeterministicAlts() { |
| return altsWithProblem; |
| } |
| |
| /** Return the sorted list of alts that conflict within a single state. |
| * Note that predicates may resolve the conflict. |
| */ |
| public List getNonDeterministicAltsForState(DFAState targetState) { |
| Set nondetAlts = targetState.getNonDeterministicAlts(); |
| if ( nondetAlts==null ) { |
| return null; |
| } |
| List sorted = new LinkedList(); |
| sorted.addAll(nondetAlts); |
| Collections.sort(sorted); // make sure it's 1, 2, ... |
| return sorted; |
| } |
| |
| /** Return all DFA states in this DFA that have NFA configurations that |
| * conflict. You must report a problem for each state in this set |
| * because each state represents a different input sequence. |
| */ |
| public Set getDFAStatesWithSyntacticallyAmbiguousAlts() { |
| return statesWithSyntacticallyAmbiguousAltsSet; |
| } |
| |
| /** Which alts were specifically turned off to resolve nondeterminisms? |
| * This is different than the unreachable alts. Disabled doesn't mean that |
| * the alternative is totally unreachable necessarily, it just means |
| * that for this DFA state, that alt is disabled. There may be other |
| * accept states for that alt that make an alt reachable. |
| */ |
| public Set getDisabledAlternatives(DFAState d) { |
| return d.getDisabledAlternatives(); |
| } |
| |
| /** If a recursion overflow is resolve with predicates, then we need |
| * to shut off the warning that would be generated. |
| */ |
| public void removeRecursiveOverflowState(DFAState d) { |
| Integer stateI = Utils.integer(d.stateNumber); |
| stateToRecursionOverflowConfigurationsMap.remove(stateI); |
| } |
| |
| /** Return a List<Label> indicating an input sequence that can be matched |
| * from the start state of the DFA to the targetState (which is known |
| * to have a problem). |
| */ |
| public List<Label> getSampleNonDeterministicInputSequence(DFAState targetState) { |
| Set dfaStates = getDFAPathStatesToTarget(targetState); |
| statesVisitedDuringSampleSequence = new HashSet<Integer>(); |
| List<Label> labels = new ArrayList<Label>(); // may access ith element; use array |
| if ( dfa==null || dfa.startState==null ) { |
| return labels; |
| } |
| getSampleInputSequenceUsingStateSet(dfa.startState, |
| targetState, |
| dfaStates, |
| labels); |
| return labels; |
| } |
| |
| /** Given List<Label>, return a String with a useful representation |
| * of the associated input string. One could show something different |
| * for lexers and parsers, for example. |
| */ |
| public String getInputSequenceDisplay(List labels) { |
| Grammar g = dfa.nfa.grammar; |
| StringBuffer buf = new StringBuffer(); |
| for (Iterator it = labels.iterator(); it.hasNext();) { |
| Label label = (Label) it.next(); |
| buf.append(label.toString(g)); |
| if ( it.hasNext() && g.type!=Grammar.LEXER ) { |
| buf.append(' '); |
| } |
| } |
| return buf.toString(); |
| } |
| |
| /** Given an alternative associated with a nondeterministic DFA state, |
| * find the path of NFA states associated with the labels sequence. |
| * Useful tracing where in the NFA, a single input sequence can be |
| * matched. For different alts, you should get different NFA paths. |
| * |
| * The first NFA state for all NFA paths will be the same: the starting |
| * NFA state of the first nondeterministic alt. Imagine (A|B|A|A): |
| * |
| * 5->9-A->o |
| * | |
| * 6->10-B->o |
| * | |
| * 7->11-A->o |
| * | |
| * 8->12-A->o |
| * |
| * There are 3 nondeterministic alts. The paths should be: |
| * 5 9 ... |
| * 5 6 7 11 ... |
| * 5 6 7 8 12 ... |
| * |
| * The NFA path matching the sample input sequence (labels) is computed |
| * using states 9, 11, and 12 rather than 5, 7, 8 because state 5, for |
| * example can get to all ambig paths. Must isolate for each alt (hence, |
| * the extra state beginning each alt in my NFA structures). Here, |
| * firstAlt=1. |
| */ |
| public List getNFAPathStatesForAlt(int firstAlt, |
| int alt, |
| List labels) |
| { |
| NFAState nfaStart = dfa.getNFADecisionStartState(); |
| List path = new LinkedList(); |
| // first add all NFA states leading up to altStart state |
| for (int a=firstAlt; a<=alt; a++) { |
| NFAState s = |
| dfa.nfa.grammar.getNFAStateForAltOfDecision(nfaStart,a); |
| path.add(s); |
| } |
| |
| // add first state of actual alt |
| NFAState altStart = dfa.nfa.grammar.getNFAStateForAltOfDecision(nfaStart,alt); |
| NFAState isolatedAltStart = (NFAState)altStart.transition[0].target; |
| path.add(isolatedAltStart); |
| |
| // add the actual path now |
| statesVisitedAtInputDepth = new HashSet(); |
| getNFAPath(isolatedAltStart, |
| 0, |
| labels, |
| path); |
| return path; |
| } |
| |
| /** Each state in the DFA represents a different input sequence for an |
| * alt of the decision. Given a DFA state, what is the semantic |
| * predicate context for a particular alt. |
| */ |
| public SemanticContext getSemanticContextForAlt(DFAState d, int alt) { |
| Map altToPredMap = (Map)stateToAltSetWithSemanticPredicatesMap.get(d); |
| if ( altToPredMap==null ) { |
| return null; |
| } |
| return (SemanticContext)altToPredMap.get(Utils.integer(alt)); |
| } |
| |
| /** At least one alt refs a sem or syn pred */ |
| public boolean hasPredicate() { |
| return stateToAltSetWithSemanticPredicatesMap.size()>0; |
| } |
| |
| public Set getNondeterministicStatesResolvedWithSemanticPredicate() { |
| return statesResolvedWithSemanticPredicatesSet; |
| } |
| |
| /** Return a list of alts whose predicate context was insufficient to |
| * resolve a nondeterminism for state d. |
| */ |
| public Map<Integer, Set<Token>> getIncompletelyCoveredAlts(DFAState d) { |
| return stateToIncompletelyCoveredAltsMap.get(d); |
| } |
| |
| public void issueWarnings() { |
| // NONREGULAR DUE TO RECURSION > 1 ALTS |
| // Issue this before aborted analysis, which might also occur |
| // if we take too long to terminate |
| if ( nonLLStarDecision && !dfa.getAutoBacktrackMode() ) { |
| ErrorManager.nonLLStarDecision(this); |
| } |
| |
| issueRecursionWarnings(); |
| |
| // generate a separate message for each problem state in DFA |
| Set resolvedStates = getNondeterministicStatesResolvedWithSemanticPredicate(); |
| Set problemStates = getDFAStatesWithSyntacticallyAmbiguousAlts(); |
| if ( problemStates.size()>0 ) { |
| Iterator it = |
| problemStates.iterator(); |
| while ( it.hasNext() && !dfa.nfa.grammar.NFAToDFAConversionExternallyAborted() ) { |
| DFAState d = (DFAState) it.next(); |
| Map<Integer, Set<Token>> insufficientAltToLocations = getIncompletelyCoveredAlts(d); |
| if ( insufficientAltToLocations!=null && insufficientAltToLocations.size()>0 ) { |
| ErrorManager.insufficientPredicates(this,d,insufficientAltToLocations); |
| } |
| // don't report problem if resolved |
| if ( resolvedStates==null || !resolvedStates.contains(d) ) { |
| // first strip last alt from disableAlts if it's wildcard |
| // then don't print error if no more disable alts |
| Set disabledAlts = getDisabledAlternatives(d); |
| stripWildCardAlts(disabledAlts); |
| if ( disabledAlts.size()>0 ) { |
| // nondeterminism; same input predicts multiple alts. |
| // but don't emit error if greedy=true explicitly set |
| boolean explicitlyGreedy = false; |
| GrammarAST blockAST = |
| d.dfa.nfa.grammar.getDecisionBlockAST(d.dfa.decisionNumber); |
| if ( blockAST!=null ) { |
| String greedyS = (String)blockAST.getBlockOption("greedy"); |
| if ( greedyS!=null && greedyS.equals("true") ) explicitlyGreedy = true; |
| } |
| if ( !explicitlyGreedy) ErrorManager.nondeterminism(this,d); |
| } |
| } |
| } |
| } |
| |
| Set danglingStates = getDanglingStates(); |
| if ( danglingStates.size()>0 ) { |
| //System.err.println("no emanating edges for states: "+danglingStates); |
| for (Iterator it = danglingStates.iterator(); it.hasNext();) { |
| DFAState d = (DFAState) it.next(); |
| ErrorManager.danglingState(this,d); |
| } |
| } |
| |
| if ( !nonLLStarDecision ) { |
| List<Integer> unreachableAlts = dfa.getUnreachableAlts(); |
| if ( unreachableAlts!=null && unreachableAlts.size()>0 ) { |
| // give different msg if it's an empty Tokens rule from delegate |
| boolean isInheritedTokensRule = false; |
| if ( dfa.isTokensRuleDecision() ) { |
| for (Integer altI : unreachableAlts) { |
| GrammarAST decAST = dfa.getDecisionASTNode(); |
| GrammarAST altAST = (GrammarAST)decAST.getChild(altI-1); |
| GrammarAST delegatedTokensAlt = |
| (GrammarAST)altAST.getFirstChildWithType(ANTLRParser.DOT); |
| if ( delegatedTokensAlt !=null ) { |
| isInheritedTokensRule = true; |
| ErrorManager.grammarWarning(ErrorManager.MSG_IMPORTED_TOKENS_RULE_EMPTY, |
| dfa.nfa.grammar, |
| null, |
| dfa.nfa.grammar.name, |
| delegatedTokensAlt.getChild(0).getText()); |
| } |
| } |
| } |
| if ( isInheritedTokensRule ) { |
| } |
| else { |
| ErrorManager.unreachableAlts(this,unreachableAlts); |
| } |
| } |
| } |
| } |
| |
| /** Get the last disabled alt number and check in the grammar to see |
| * if that alt is a simple wildcard. If so, treat like an else clause |
| * and don't emit the error. Strip out the last alt if it's wildcard. |
| */ |
| protected void stripWildCardAlts(Set disabledAlts) { |
| List sortedDisableAlts = new ArrayList(disabledAlts); |
| Collections.sort(sortedDisableAlts); |
| Integer lastAlt = |
| (Integer)sortedDisableAlts.get(sortedDisableAlts.size()-1); |
| GrammarAST blockAST = |
| dfa.nfa.grammar.getDecisionBlockAST(dfa.decisionNumber); |
| //System.out.println("block with error = "+blockAST.toStringTree()); |
| GrammarAST lastAltAST = null; |
| if ( blockAST.getChild(0).getType()==ANTLRParser.OPTIONS ) { |
| // if options, skip first child: ( options { ( = greedy false ) ) |
| lastAltAST = (GrammarAST)blockAST.getChild(lastAlt.intValue()); |
| } |
| else { |
| lastAltAST = (GrammarAST)blockAST.getChild(lastAlt.intValue()-1); |
| } |
| //System.out.println("last alt is "+lastAltAST.toStringTree()); |
| // if last alt looks like ( ALT . <end-of-alt> ) then wildcard |
| // Avoid looking at optional blocks etc... that have last alt |
| // as the EOB: |
| // ( BLOCK ( ALT 'else' statement <end-of-alt> ) <end-of-block> ) |
| if ( lastAltAST.getType()!=ANTLRParser.EOB && |
| lastAltAST.getChild(0).getType()== ANTLRParser.WILDCARD && |
| lastAltAST.getChild(1).getType()== ANTLRParser.EOA ) |
| { |
| //System.out.println("wildcard"); |
| disabledAlts.remove(lastAlt); |
| } |
| } |
| |
| protected void issueRecursionWarnings() { |
| // RECURSION OVERFLOW |
| Set dfaStatesWithRecursionProblems = |
| stateToRecursionOverflowConfigurationsMap.keySet(); |
| // now walk truly unique (unaliased) list of dfa states with inf recur |
| // Goal: create a map from alt to map<target,List<callsites>> |
| // Map<Map<String target, List<NFAState call sites>> |
| Map altToTargetToCallSitesMap = new HashMap(); |
| // track a single problem DFA state for each alt |
| Map altToDFAState = new HashMap(); |
| computeAltToProblemMaps(dfaStatesWithRecursionProblems, |
| stateToRecursionOverflowConfigurationsMap, |
| altToTargetToCallSitesMap, // output param |
| altToDFAState); // output param |
| |
| // walk each alt with recursion overflow problems and generate error |
| Set alts = altToTargetToCallSitesMap.keySet(); |
| List sortedAlts = new ArrayList(alts); |
| Collections.sort(sortedAlts); |
| for (Iterator altsIt = sortedAlts.iterator(); altsIt.hasNext();) { |
| Integer altI = (Integer) altsIt.next(); |
| Map targetToCallSiteMap = |
| (Map)altToTargetToCallSitesMap.get(altI); |
| Set targetRules = targetToCallSiteMap.keySet(); |
| Collection callSiteStates = targetToCallSiteMap.values(); |
| DFAState sampleBadState = (DFAState)altToDFAState.get(altI); |
| ErrorManager.recursionOverflow(this, |
| sampleBadState, |
| altI.intValue(), |
| targetRules, |
| callSiteStates); |
| } |
| } |
| |
| private void computeAltToProblemMaps(Set dfaStatesUnaliased, |
| Map configurationsMap, |
| Map altToTargetToCallSitesMap, |
| Map altToDFAState) |
| { |
| for (Iterator it = dfaStatesUnaliased.iterator(); it.hasNext();) { |
| Integer stateI = (Integer) it.next(); |
| // walk this DFA's config list |
| List configs = (List)configurationsMap.get(stateI); |
| for (int i = 0; i < configs.size(); i++) { |
| NFAConfiguration c = (NFAConfiguration) configs.get(i); |
| NFAState ruleInvocationState = dfa.nfa.getState(c.state); |
| Transition transition0 = ruleInvocationState.transition[0]; |
| RuleClosureTransition ref = (RuleClosureTransition)transition0; |
| String targetRule = ((NFAState) ref.target).enclosingRule.name; |
| Integer altI = Utils.integer(c.alt); |
| Map targetToCallSiteMap = |
| (Map)altToTargetToCallSitesMap.get(altI); |
| if ( targetToCallSiteMap==null ) { |
| targetToCallSiteMap = new HashMap(); |
| altToTargetToCallSitesMap.put(altI, targetToCallSiteMap); |
| } |
| Set callSites = |
| (HashSet)targetToCallSiteMap.get(targetRule); |
| if ( callSites==null ) { |
| callSites = new HashSet(); |
| targetToCallSiteMap.put(targetRule, callSites); |
| } |
| callSites.add(ruleInvocationState); |
| // track one problem DFA state per alt |
| if ( altToDFAState.get(altI)==null ) { |
| DFAState sampleBadState = dfa.getState(stateI.intValue()); |
| altToDFAState.put(altI, sampleBadState); |
| } |
| } |
| } |
| } |
| |
| private Set getUnaliasedDFAStateSet(Set dfaStatesWithRecursionProblems) { |
| Set dfaStatesUnaliased = new HashSet(); |
| for (Iterator it = dfaStatesWithRecursionProblems.iterator(); it.hasNext();) { |
| Integer stateI = (Integer) it.next(); |
| DFAState d = dfa.getState(stateI.intValue()); |
| dfaStatesUnaliased.add(Utils.integer(d.stateNumber)); |
| } |
| return dfaStatesUnaliased; |
| } |
| |
| |
| // T R A C K I N G M E T H O D S |
| |
| /** Report the fact that DFA state d is not a state resolved with |
| * predicates and yet it has no emanating edges. Usually this |
| * is a result of the closure/reach operations being unable to proceed |
| */ |
| public void reportDanglingState(DFAState d) { |
| danglingStates.add(d); |
| } |
| |
| // public void reportAnalysisTimeout() { |
| // timedOut = true; |
| // dfa.nfa.grammar.setOfDFAWhoseAnalysisTimedOut.add(dfa); |
| // } |
| |
| /** Report that at least 2 alts have recursive constructs. There is |
| * no way to build a DFA so we terminated. |
| */ |
| public void reportNonLLStarDecision(DFA dfa) { |
| /* |
| System.out.println("non-LL(*) DFA "+dfa.decisionNumber+", alts: "+ |
| dfa.recursiveAltSet.toList()); |
| */ |
| nonLLStarDecision = true; |
| dfa.nfa.grammar.numNonLLStar++; |
| altsWithProblem.addAll(dfa.recursiveAltSet.toList()); |
| } |
| |
| public void reportRecursionOverflow(DFAState d, |
| NFAConfiguration recursionNFAConfiguration) |
| { |
| // track the state number rather than the state as d will change |
| // out from underneath us; hash wouldn't return any value |
| |
| // left-recursion is detected in start state. Since we can't |
| // call resolveNondeterminism() on the start state (it would |
| // not look k=1 to get min single token lookahead), we must |
| // prevent errors derived from this state. Avoid start state |
| if ( d.stateNumber > 0 ) { |
| Integer stateI = Utils.integer(d.stateNumber); |
| stateToRecursionOverflowConfigurationsMap.map(stateI, recursionNFAConfiguration); |
| } |
| } |
| |
| public void reportNondeterminism(DFAState d, Set<Integer> nondeterministicAlts) { |
| altsWithProblem.addAll(nondeterministicAlts); // track overall list |
| statesWithSyntacticallyAmbiguousAltsSet.add(d); |
| dfa.nfa.grammar.setOfNondeterministicDecisionNumbers.add( |
| Utils.integer(dfa.getDecisionNumber()) |
| ); |
| } |
| |
| /** Currently the analysis reports issues between token definitions, but |
| * we don't print out warnings in favor of just picking the first token |
| * definition found in the grammar ala lex/flex. |
| */ |
| public void reportLexerRuleNondeterminism(DFAState d, Set<Integer> nondeterministicAlts) { |
| stateToSyntacticallyAmbiguousTokensRuleAltsMap.put(d,nondeterministicAlts); |
| } |
| |
| public void reportNondeterminismResolvedWithSemanticPredicate(DFAState d) { |
| // First, prevent a recursion warning on this state due to |
| // pred resolution |
| if ( d.abortedDueToRecursionOverflow ) { |
| d.dfa.probe.removeRecursiveOverflowState(d); |
| } |
| statesResolvedWithSemanticPredicatesSet.add(d); |
| //System.out.println("resolved with pred: "+d); |
| dfa.nfa.grammar.setOfNondeterministicDecisionNumbersResolvedWithPredicates.add( |
| Utils.integer(dfa.getDecisionNumber()) |
| ); |
| } |
| |
| /** Report the list of predicates found for each alternative; copy |
| * the list because this set gets altered later by the method |
| * tryToResolveWithSemanticPredicates() while flagging NFA configurations |
| * in d as resolved. |
| */ |
| public void reportAltPredicateContext(DFAState d, Map altPredicateContext) { |
| Map copy = new HashMap(); |
| copy.putAll(altPredicateContext); |
| stateToAltSetWithSemanticPredicatesMap.put(d,copy); |
| } |
| |
| public void reportIncompletelyCoveredAlts(DFAState d, |
| Map<Integer, Set<Token>> altToLocationsReachableWithoutPredicate) |
| { |
| stateToIncompletelyCoveredAltsMap.put(d, altToLocationsReachableWithoutPredicate); |
| } |
| |
| // S U P P O R T |
| |
| /** Given a start state and a target state, return true if start can reach |
| * target state. Also, compute the set of DFA states |
| * that are on a path from start to target; return in states parameter. |
| */ |
| protected boolean reachesState(DFAState startState, |
| DFAState targetState, |
| Set states) { |
| if ( startState==targetState ) { |
| states.add(targetState); |
| //System.out.println("found target DFA state "+targetState.getStateNumber()); |
| stateReachable.put(startState.stateNumber, REACHABLE_YES); |
| return true; |
| } |
| |
| DFAState s = startState; |
| // avoid infinite loops |
| stateReachable.put(s.stateNumber, REACHABLE_BUSY); |
| |
| // look for a path to targetState among transitions for this state |
| // stop when you find the first one; I'm pretty sure there is |
| // at most one path to any DFA state with conflicting predictions |
| for (int i=0; i<s.getNumberOfTransitions(); i++) { |
| Transition t = s.transition(i); |
| DFAState edgeTarget = (DFAState)t.target; |
| Integer targetStatus = stateReachable.get(edgeTarget.stateNumber); |
| if ( targetStatus==REACHABLE_BUSY ) { // avoid cycles; they say nothing |
| continue; |
| } |
| if ( targetStatus==REACHABLE_YES ) { // return success! |
| stateReachable.put(s.stateNumber, REACHABLE_YES); |
| return true; |
| } |
| if ( targetStatus==REACHABLE_NO ) { // try another transition |
| continue; |
| } |
| // if null, target must be REACHABLE_UNKNOWN (i.e., unvisited) |
| if ( reachesState(edgeTarget, targetState, states) ) { |
| states.add(s); |
| stateReachable.put(s.stateNumber, REACHABLE_YES); |
| return true; |
| } |
| } |
| |
| stateReachable.put(s.stateNumber, REACHABLE_NO); |
| return false; // no path to targetState found. |
| } |
| |
| protected Set getDFAPathStatesToTarget(DFAState targetState) { |
| Set dfaStates = new HashSet(); |
| stateReachable = new HashMap(); |
| if ( dfa==null || dfa.startState==null ) { |
| return dfaStates; |
| } |
| boolean reaches = reachesState(dfa.startState, targetState, dfaStates); |
| return dfaStates; |
| } |
| |
| /** Given a start state and a final state, find a list of edge labels |
| * between the two ignoring epsilon. Limit your scan to a set of states |
| * passed in. This is used to show a sample input sequence that is |
| * nondeterministic with respect to this decision. Return List<Label> as |
| * a parameter. The incoming states set must be all states that lead |
| * from startState to targetState and no others so this algorithm doesn't |
| * take a path that eventually leads to a state other than targetState. |
| * Don't follow loops, leading to short (possibly shortest) path. |
| */ |
| protected void getSampleInputSequenceUsingStateSet(State startState, |
| State targetState, |
| Set states, |
| List<Label> labels) |
| { |
| statesVisitedDuringSampleSequence.add(startState.stateNumber); |
| |
| // pick the first edge in states as the one to traverse |
| for (int i=0; i<startState.getNumberOfTransitions(); i++) { |
| Transition t = startState.transition(i); |
| DFAState edgeTarget = (DFAState)t.target; |
| if ( states.contains(edgeTarget) && |
| !statesVisitedDuringSampleSequence.contains(edgeTarget.stateNumber) ) |
| { |
| labels.add(t.label); // traverse edge and track label |
| if ( edgeTarget!=targetState ) { |
| // get more labels if not at target |
| getSampleInputSequenceUsingStateSet(edgeTarget, |
| targetState, |
| states, |
| labels); |
| } |
| // done with this DFA state as we've found a good path to target |
| return; |
| } |
| } |
| labels.add(new Label(Label.EPSILON)); // indicate no input found |
| // this happens on a : {p1}? a | A ; |
| //ErrorManager.error(ErrorManager.MSG_CANNOT_COMPUTE_SAMPLE_INPUT_SEQ); |
| } |
| |
| /** Given a sample input sequence, you usually would like to know the |
| * path taken through the NFA. Return the list of NFA states visited |
| * while matching a list of labels. This cannot use the usual |
| * interpreter, which does a deterministic walk. We need to be able to |
| * take paths that are turned off during nondeterminism resolution. So, |
| * just do a depth-first walk traversing edges labeled with the current |
| * label. Return true if a path was found emanating from state s. |
| */ |
| protected boolean getNFAPath(NFAState s, // starting where? |
| int labelIndex, // 0..labels.size()-1 |
| List labels, // input sequence |
| List path) // output list of NFA states |
| { |
| // track a visit to state s at input index labelIndex if not seen |
| String thisStateKey = getStateLabelIndexKey(s.stateNumber,labelIndex); |
| if ( statesVisitedAtInputDepth.contains(thisStateKey) ) { |
| /* |
| System.out.println("### already visited "+s.stateNumber+" previously at index "+ |
| labelIndex); |
| */ |
| return false; |
| } |
| statesVisitedAtInputDepth.add(thisStateKey); |
| |
| /* |
| System.out.println("enter state "+s.stateNumber+" visited states: "+ |
| statesVisitedAtInputDepth); |
| */ |
| |
| // pick the first edge whose target is in states and whose |
| // label is labels[labelIndex] |
| for (int i=0; i<s.getNumberOfTransitions(); i++) { |
| Transition t = s.transition[i]; |
| NFAState edgeTarget = (NFAState)t.target; |
| Label label = (Label)labels.get(labelIndex); |
| /* |
| System.out.println(s.stateNumber+"-"+ |
| t.label.toString(dfa.nfa.grammar)+"->"+ |
| edgeTarget.stateNumber+" =="+ |
| label.toString(dfa.nfa.grammar)+"?"); |
| */ |
| if ( t.label.isEpsilon() || t.label.isSemanticPredicate() ) { |
| // nondeterministically backtrack down epsilon edges |
| path.add(edgeTarget); |
| boolean found = |
| getNFAPath(edgeTarget, labelIndex, labels, path); |
| if ( found ) { |
| statesVisitedAtInputDepth.remove(thisStateKey); |
| return true; // return to "calling" state |
| } |
| path.remove(path.size()-1); // remove; didn't work out |
| continue; // look at the next edge |
| } |
| if ( t.label.matches(label) ) { |
| path.add(edgeTarget); |
| /* |
| System.out.println("found label "+ |
| t.label.toString(dfa.nfa.grammar)+ |
| " at state "+s.stateNumber+"; labelIndex="+labelIndex); |
| */ |
| if ( labelIndex==labels.size()-1 ) { |
| // found last label; done! |
| statesVisitedAtInputDepth.remove(thisStateKey); |
| return true; |
| } |
| // otherwise try to match remaining input |
| boolean found = |
| getNFAPath(edgeTarget, labelIndex+1, labels, path); |
| if ( found ) { |
| statesVisitedAtInputDepth.remove(thisStateKey); |
| return true; |
| } |
| /* |
| System.out.println("backtrack; path from "+s.stateNumber+"->"+ |
| t.label.toString(dfa.nfa.grammar)+" didn't work"); |
| */ |
| path.remove(path.size()-1); // remove; didn't work out |
| continue; // keep looking for a path for labels |
| } |
| } |
| //System.out.println("no epsilon or matching edge; removing "+thisStateKey); |
| // no edge was found matching label; is ok, some state will have it |
| statesVisitedAtInputDepth.remove(thisStateKey); |
| return false; |
| } |
| |
| protected String getStateLabelIndexKey(int s, int i) { |
| StringBuffer buf = new StringBuffer(); |
| buf.append(s); |
| buf.append('_'); |
| buf.append(i); |
| return buf.toString(); |
| } |
| |
| /** From an alt number associated with artificial Tokens rule, return |
| * the name of the token that is associated with that alt. |
| */ |
| public String getTokenNameForTokensRuleAlt(int alt) { |
| NFAState decisionState = dfa.getNFADecisionStartState(); |
| NFAState altState = |
| dfa.nfa.grammar.getNFAStateForAltOfDecision(decisionState,alt); |
| NFAState decisionLeft = (NFAState)altState.transition[0].target; |
| RuleClosureTransition ruleCallEdge = |
| (RuleClosureTransition)decisionLeft.transition[0]; |
| NFAState ruleStartState = (NFAState)ruleCallEdge.target; |
| //System.out.println("alt = "+decisionLeft.getEnclosingRule()); |
| return ruleStartState.enclosingRule.name; |
| } |
| |
| public void reset() { |
| stateToRecursionOverflowConfigurationsMap.clear(); |
| } |
| } |