decisionprobe.java

antlr最新版本V3源代码

		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));
	}

	public Set getNondeterministicStatesResolvedWithSemanticPredicate() {
		return statesResolvedWithSemanticPredicatesSet;
	}

	/** Return a list of alts whose predicate context was insufficient to
	 *  resolve a nondeterminism for state d.
	 */
    public List getIncompletelyCoveredAlts(DFAState d) {
		return (List)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);
		}

		if ( analysisAborted() ) {
			// only report early termination errors if !backtracking
			if ( !dfa.getAutoBacktrackMode() ) {
				ErrorManager.analysisAborted(this);
			}
			// now just return...if we bailed out, don't spew other messages
			return;
		}

		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();
				// 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 ) {
						ErrorManager.nondeterminism(this,d);
					}
				}
				List insufficientAlts = getIncompletelyCoveredAlts(d);
				if ( insufficientAlts!=null && insufficientAlts.size()>0 ) {
					ErrorManager.insufficientPredicates(this,insufficientAlts);
				}
			}
		}

		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 unreachableAlts = dfa.getUnreachableAlts();
			if ( unreachableAlts!=null && unreachableAlts.size()>0 ) {
				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 = blockAST.getChild(lastAlt.intValue());
		}
		else {
			lastAltAST = 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 =
			stateToRecursiveOverflowConfigurationsMap.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,
								stateToRecursiveOverflowConfigurationsMap,
								altToTargetToCallSitesMap, // output param
								altToDFAState);            // output param
		//System.out.println("altToTargetToCallSitesMap="+altToTargetToCallSitesMap);

		// 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);
		}

		/* All  recursion determines now before analysis
		// LEFT RECURSION
		// TODO: hideous cut/paste of code; try to refactor

		Set dfaStatesWithLeftRecursionProblems =
			stateToLeftRecursiveConfigurationsMap.keySet();
		Set dfaStatesUnaliased =
			getUnaliasedDFAStateSet(dfaStatesWithLeftRecursionProblems);

		// 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>>
		altToTargetToCallSitesMap = new HashMap();
		// track a single problem DFA state for each alt
		altToDFAState = new HashMap();
		computeAltToProblemMaps(dfaStatesUnaliased,
								stateToLeftRecursiveConfigurationsMap,
								altToTargetToCallSitesMap, // output param
								altToDFAState);            // output param

		// walk each alt with recursion overflow problems and generate error
		alts = altToTargetToCallSitesMap.keySet();
		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();
			ErrorManager.leftRecursion(this,
									   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).getEnclosingRule();
				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 reportEarlyTermination() {