decisionprobe.java

antlr最新版本V3源代码

		terminated = true;
		dfa.nfa.grammar.setOfDFAWhoseConversionTerminatedEarly.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);
		nonLLStarDecision = true;
		altsWithProblem.addAll(dfa.recursiveAltSet.toList());
	}

	public void reportRecursiveOverflow(DFAState d,
										NFAConfiguration recursiveNFAConfiguration)
	{
		// track the state number rather than the state as d will change
		// out from underneath us; hash wouldn't return any value
		Integer stateI = Utils.integer(d.stateNumber);
		List configs = (List)stateToRecursiveOverflowConfigurationsMap.get(stateI);
		if ( configs==null ) {
			configs = new ArrayList();
			configs.add(recursiveNFAConfiguration);
			stateToRecursiveOverflowConfigurationsMap.put(stateI, configs);
		}
		else {
			configs.add(recursiveNFAConfiguration);
		}
	}

	public void reportLeftRecursion(DFAState d,
									NFAConfiguration leftRecursiveNFAConfiguration)
	{
		// track the state number rather than the state as d will change
		// out from underneath us; hash wouldn't return any value
		Integer stateI = Utils.integer(d.stateNumber);
		List configs = (List)stateToLeftRecursiveConfigurationsMap.get(stateI);
		if ( configs==null ) {
			configs = new ArrayList();
			configs.add(leftRecursiveNFAConfiguration);
			stateToLeftRecursiveConfigurationsMap.put(stateI, configs);
		}
		else {
			configs.add(leftRecursiveNFAConfiguration);
		}
	}

	public void reportNondeterminism(DFAState d, Set 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 nondeterministicAlts) {
		stateToSyntacticallyAmbiguousTokensRuleAltsMap.put(d,nondeterministicAlts);
	}

	public void reportNondeterminismResolvedWithSemanticPredicate(DFAState 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,
											  List alts)
	{
		stateToIncompletelyCoveredAltsMap.put(d, alts);
	}

	// 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, REACHABLE_YES);
			return true;
		}

		DFAState s = startState;
		// avoid infinite loops
		stateReachable.put(s, 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 = (Integer)stateReachable.get(edgeTarget);
			if ( targetStatus==REACHABLE_BUSY ) { // avoid cycles; they say nothing
				continue;
			}
			if ( targetStatus==REACHABLE_YES ) { // return success!
				stateReachable.put(s, 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, REACHABLE_YES);
				return true;
			}
		}

		stateReachable.put(s, REACHABLE_NO);
		return false; // no path to targetState found.
	}

	protected Set getDFAPathStatesToTarget(DFAState targetState) {
		Set dfaStates = new HashSet();
		stateReachable = new HashMap();
		boolean reaches = reachesState(dfa.startState, targetState, dfaStates);
		return dfaStates;
	}

    /** Given a set of DFA states, return a set of NFA states associated
	 *  with alt collected from all DFA states.  If alt==0 then collect
	 *  all NFA states regardless of alt.
	protected Set getNFAStatesFromDFAStatesForAlt(Set dfaStates, int alt) {
		Set nfaStates = new LinkedHashSet();
		for (Iterator it = dfaStates.iterator(); it.hasNext();) {
			DFAState d = (DFAState) it.next();
			Set configs = d.getNFAConfigurations();
			for (Iterator configIter = configs.iterator(); configIter.hasNext();) {
				NFAConfiguration c = (NFAConfiguration) configIter.next();
				if ( alt==0 || c.alt==alt ) {
					nfaStates.add(Utils.integer(c.state));
				}
			}
		}
		return nfaStates;
	}
	 */

	/** 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 labels)
	{
		statesVisitedDuringSampleSequence.add(startState);

		// 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) )
			{
				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() ) {
				// 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.getEnclosingRule();
	}
}