nfatodfaconverter.java

antlr最新版本V3源代码

	 *
	 *  If nondeterministicAlts is null then turn off all configs 'cept those
	 *  associated with the minimum alt.
	 *
	 *  Return the min alt found.
	 */
	protected int resolveByPickingMinAlt(DFAState d, Set nondeterministicAlts) {
		int min = Integer.MAX_VALUE;
		if ( nondeterministicAlts!=null ) {
			min = getMinAlt(nondeterministicAlts);
		}
		else {
			// else walk the actual configurations to find the min
			min = getMinAlt(d);
		}

		turnOffOtherAlts(d, min, nondeterministicAlts);

		return min;
	}

	/** Resolve state d by choosing exit alt, which is same value as the
	 *  number of alternatives.  Return that exit alt.
	 */
	protected int resolveByPickingExitAlt(DFAState d, Set nondeterministicAlts) {
		int exitAlt = dfa.getNumberOfAlts();
		turnOffOtherAlts(d, exitAlt, nondeterministicAlts);
		return exitAlt;
	}

	/** turn off all states associated with alts other than the good one
	 *  (as long as they are one of the nondeterministic ones)
	 */
	protected static void turnOffOtherAlts(DFAState d, int min, Set nondeterministicAlts) {
		Iterator iter = d.nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			if ( configuration.alt!=min ) {
				if ( nondeterministicAlts==null ||
					 nondeterministicAlts.contains(Utils.integer(configuration.alt)) )
				{
					configuration.resolved = true;
				}
			}
		}
	}

	protected static int getMinAlt(DFAState d) {
		int min = Integer.MAX_VALUE;
		Iterator iter = d.nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			if ( configuration.alt<min ) {
				min = configuration.alt;
			}
		}
		return min;
	}

	protected static int getMinAlt(Set nondeterministicAlts) {
		int min = Integer.MAX_VALUE;
		Iterator iter = nondeterministicAlts.iterator();
		while (iter.hasNext()) {
			Integer altI = (Integer) iter.next();
			int alt = altI.intValue();
			if ( alt < min ) {
				min = alt;
			}
		}
		return min;
	}

	/** See if a set of nondeterministic alternatives can be disambiguated
	 *  with the semantic predicate contexts of the alternatives.
	 *
	 *  Without semantic predicates, syntactic conflicts are resolved
	 *  by simply choosing the first viable alternative.  In the
	 *  presence of semantic predicates, you can resolve the issue by
	 *  evaluating boolean expressions at run time.  During analysis,
	 *  this amounts to suppressing grammar error messages to the
	 *  developer.  NFA configurations are always marked as "to be
	 *  resolved with predicates" so that
	 *  DFA.findNewDFAStatesAndAddDFATransitions() will know to ignore
	 *  these configurations and add predicate transitions to the DFA
	 *  after adding token/char labels.
	 *
	 *  During analysis, we can simply make sure that for n
	 *  ambiguously predicted alternatives there are at least n-1
	 *  unique predicate sets.  The nth alternative can be predicted
	 *  with "not" the "or" of all other predicates.  NFA configurations without
	 *  predicates are assumed to have the default predicate of
	 *  "true" from a user point of view.  When true is combined via || with
	 *  another predicate, the predicate is a tautology and must be removed
	 *  from consideration for disambiguation:
	 *
	 *  a : b | B ; // hoisting p1||true out of rule b, yields no predicate
	 *  b : {p1}? B | B ;
	 *
	 *  This is done down in getPredicatesPerNonDeterministicAlt().
	 */
	protected boolean tryToResolveWithSemanticPredicates(DFAState d,
														 Set nondeterministicAlts)
	{
		Map altToPredMap =
				getPredicatesPerNonDeterministicAlt(d, nondeterministicAlts);

		if ( altToPredMap.size()==0 ) {
			return false;
		}

		//System.out.println("nondeterministic alts with predicates: "+altToPredMap);
		dfa.probe.reportAltPredicateContext(d, altToPredMap);

		if ( nondeterministicAlts.size()-altToPredMap.size()>1 ) {
			// too few predicates to resolve; just return
			// TODO: actually do we need to gen error here?
			return false;
		}

		// Handle case where 1 predicate is missing
		// Case 1. Semantic predicates
		// If the missing pred is on nth alt, !(union of other preds)==true
		// so we can avoid that computation.  If naked alt is ith, then must
		// test it with !(union) since semantic predicated alts are order
		// independent
		// Case 2: Syntactic predicates
		// The naked alt is always assumed to be true as the order of
		// alts is the order of precedence.  The naked alt will be a tautology
		// anyway as it's !(union of other preds).  This implies
		// that there is no such thing as noviable alt for synpred edges
		// emanating from a DFA state.
		if ( altToPredMap.size()==nondeterministicAlts.size()-1 ) {
			// if there are n-1 predicates for n nondeterministic alts, can fix
			org.antlr.misc.BitSet ndSet = org.antlr.misc.BitSet.of(nondeterministicAlts);
			org.antlr.misc.BitSet predSet = org.antlr.misc.BitSet.of(altToPredMap);
			int nakedAlt = ndSet.subtract(predSet).getSingleElement();
			SemanticContext nakedAltPred = null;
			if ( nakedAlt == max(nondeterministicAlts) ) {
				// the naked alt is the last nondet alt and will be the default clause
				nakedAltPred = new SemanticContext.TruePredicate();
			}
			else {
				// pretend naked alternative is covered with !(union other preds)
				// unless it's a synpred since those have precedence same
				// as alt order
				SemanticContext unionOfPredicatesFromAllAlts =
					getUnionOfPredicates(altToPredMap);
				//System.out.println("all predicates "+unionOfPredicatesFromAllAlts);
				if ( unionOfPredicatesFromAllAlts.isSyntacticPredicate() ) {
					nakedAltPred = new SemanticContext.TruePredicate();
				}
				else {
					nakedAltPred =
						SemanticContext.not(unionOfPredicatesFromAllAlts);
				}
			}

			//System.out.println("covering naked alt="+nakedAlt+" with "+nakedAltPred);

			altToPredMap.put(Utils.integer(nakedAlt), nakedAltPred);
			// set all config with alt=nakedAlt to have the computed predicate
			Iterator iter = d.nfaConfigurations.iterator();
			NFAConfiguration configuration;
			while (iter.hasNext()) {
				configuration = (NFAConfiguration) iter.next();
				if ( configuration.alt == nakedAlt ) {
					configuration.semanticContext = nakedAltPred;
				}
			}
		}

		if ( altToPredMap.size()==nondeterministicAlts.size() ) {
			// RESOLVE CONFLICT by picking one NFA configuration for each alt
			// and setting its resolvedWithPredicate flag
			// First, prevent a recursion warning on this state due to
			// pred resolution
			if ( d.abortedDueToRecursionOverflow ) {
				d.dfa.probe.removeRecursiveOverflowState(d);
			}
			Iterator iter = d.nfaConfigurations.iterator();
			NFAConfiguration configuration;
			while (iter.hasNext()) {
				configuration = (NFAConfiguration) iter.next();
				SemanticContext semCtx = (SemanticContext)
						altToPredMap.get(Utils.integer(configuration.alt));
				if ( semCtx!=null ) {
					// resolve (first found) with pred
					// and remove alt from problem list
					configuration.resolveWithPredicate = true;
					configuration.semanticContext = semCtx; // reset to combined
					altToPredMap.remove(Utils.integer(configuration.alt));
					// notify grammar that we've used the preds contained in semCtx
					if ( semCtx.isSyntacticPredicate() ) {
						dfa.nfa.grammar.synPredUsedInDFA(dfa, semCtx);
					}
				}
				else if ( nondeterministicAlts.contains(Utils.integer(configuration.alt)) ) {
					// resolve all configurations for nondeterministic alts
					// for which there is no predicate context by turning it off
					configuration.resolved = true;
				}
			}
			return true;
		}

		return false;  // couldn't fix the problem with predicates
	}

	/** Return a mapping from nondeterministc alt to combined list of predicates.
	 *  If both (s|i|semCtx1) and (t|i|semCtx2) exist, then the proper predicate
	 *  for alt i is semCtx1||semCtx2 because you have arrived at this single
	 *  DFA state via two NFA paths, both of which have semantic predicates.
	 *  We ignore deterministic alts because syntax alone is sufficient
	 *  to predict those.  Do not include their predicates.
	 *
	 *  Alts with no predicate are assumed to have {true}? pred.
	 *
	 *  When combining via || with "true", all predicates are removed from
	 *  consideration since the expression will always be true and hence
	 *  not tell us how to resolve anything.  So, if any NFA configuration
	 *  in this DFA state does not have a semantic context, the alt cannot
	 *  be resolved with a predicate.
	 */
	protected Map getPredicatesPerNonDeterministicAlt(DFAState d,
													  Set nondeterministicAlts)
	{
		// map alt to combined SemanticContext
		Map altToPredicateContextMap = new HashMap();
		// init the alt to predicate set map
		Map altToSetOfContextsMap = new HashMap();
		for (Iterator it = nondeterministicAlts.iterator(); it.hasNext();) {
			Integer altI = (Integer) it.next();
			altToSetOfContextsMap.put(altI, new HashSet());
		}
		Set altToIncompletePredicateContextSet = new HashSet();
		Iterator iter = d.nfaConfigurations.iterator();
		NFAConfiguration configuration;
		// for each configuration, create a unique set of predicates
		// Also, track the alts with at least one uncovered configuration
		// (one w/o a predicate); tracks tautologies like p1||true
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			Integer altI = Utils.integer(configuration.alt);
			// if alt is nondeterministic, combine its predicates
			if ( nondeterministicAlts.contains(altI) ) {
				// if there is a predicate for this NFA configuration, OR in
				if ( configuration.semanticContext !=
					 SemanticContext.EMPTY_SEMANTIC_CONTEXT )
				{
					/*
					SemanticContext altsExistingPred =(SemanticContext)
							altToPredicateContextMap.get(Utils.integer(configuration.alt));
					if ( altsExistingPred!=null ) {
						// must merge all predicates from configs with same alt
						SemanticContext combinedContext =
								SemanticContext.or(
										altsExistingPred,
										configuration.semanticContext);
						System.out.println(altsExistingPred+" OR "+
										   configuration.semanticContext+
										   "="+combinedContext);
						altToPredicateContextMap.put(
								Utils.integer(configuration.alt),
								combinedContext
						);
					}
					else {
						// not seen before, just add it
						altToPredicateContextMap.put(
								Utils.integer(configuration.alt),
								configuration.semanticContext
						);
					}
					*/
					Set predSet = (Set)altToSetOfContextsMap.get(altI);
					predSet.add(configuration.semanticContext);
				}
				else {
					// if no predicate, but it's part of nondeterministic alt
					// then at least one path exists not covered by a predicate.
					// must remove predicate for this alt; track incomplete alts
					altToIncompletePredicateContextSet.add(altI);
				}
			}
		}

		// For each alt, OR together all unique predicates associated with
		// all configurations
		// Also, track the list of incompletely covered alts: those alts
		// with at least 1 predicate and at least one configuration w/o a
		// predicate. We want this in order to report to the decision probe.
		List incompletelyCoveredAlts = new ArrayList();
		for (Iterator it = nondeterministicAlts.iterator(); it.hasNext();) {
			Integer altI = (Integer) it.next();
			Set predSet = (Set)altToSetOfContextsMap.get(altI);
			if ( altToIncompletePredicateContextSet.contains(altI) ) {
				SemanticContext insufficientPred =(SemanticContext)
						altToPredicateContextMap.get(altI);
				if ( predSet.size()>0 ) {
					incompletelyCoveredAlts.add(altI);
				}
				continue;
			}
			SemanticContext combinedContext = null;
			for (Iterator itrSet = predSet.iterator(); itrSet.hasNext();) {
				SemanticContext ctx = (SemanticContext) itrSet.next();
				combinedContext =
						SemanticContext.or(combinedContext,ctx);
			}
			altToPredicateContextMap.put(altI, combinedContext);
		}

		// remove any predicates from incompletely covered alts
		/*
		iter = altToIncompletePredicateContextSet.iterator();
		List incompletelyCoveredAlts = new ArrayList();
		while (iter.hasNext()) {
			Integer alt = (Integer) iter.next();
			SemanticContext insufficientPred =(Semanti