dfastate.java

ANTLR(ANother Tool for Language Recognition)它是这样的一种工具

        while (iter.hasNext()) {
            NFAConfiguration myConfig = (NFAConfiguration) iter.next();
			if ( !other.nfaConfigurations.contains(myConfig) ) {
				return false;
			}
        }
        return true;
    }

    /** Walk each configuration and if they are all the same alt, return
     *  that alt else return NFA.INVALID_ALT_NUMBER.  Ignore resolved
     *  configurations, but don't ignore resolveWithPredicate configs
     *  because this state should not be an accept state.  We need to add
     *  this to the work list and then have semantic predicate edges
     *  emanating from it.
     */
    public int getUniquelyPredictedAlt() {
		if ( cachedUniquelyPredicatedAlt!=PREDICTED_ALT_UNSET ) {
			return cachedUniquelyPredicatedAlt;
		}
        int alt = NFA.INVALID_ALT_NUMBER;
        Iterator iter = nfaConfigurations.iterator();
        NFAConfiguration configuration;
        while (iter.hasNext()) {
            configuration = (NFAConfiguration) iter.next();
            // ignore anything we resolved; predicates will still result
            // in transitions out of this state, so must count those
            // configurations; i.e., don't ignore resolveWithPredicate configs
            if ( configuration.resolved ) {
                continue;
            }
            if ( alt==NFA.INVALID_ALT_NUMBER ) {
                alt = configuration.alt; // found first nonresolved alt
            }
            else if ( configuration.alt!=alt ) {
                return NFA.INVALID_ALT_NUMBER;
            }
        }
		this.cachedUniquelyPredicatedAlt = alt;
        return alt;
    }

	/** Return the uniquely mentioned alt from the NFA configurations;
	 *  Ignore the resolved bit etc...  Return INVALID_ALT_NUMBER
	 *  if there is more than one alt mentioned.
	 */ 
	public int getUniqueAlt() {
		int alt = NFA.INVALID_ALT_NUMBER;
		Iterator iter = nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			if ( alt==NFA.INVALID_ALT_NUMBER ) {
				alt = configuration.alt; // found first alt
			}
			else if ( configuration.alt!=alt ) {
				return NFA.INVALID_ALT_NUMBER;
			}
		}
		return alt;
	}

	/** When more than one alternative can match the same input, the first
	 *  alternative is chosen to resolve the conflict.  The other alts
	 *  are "turned off" by setting the "resolved" flag in the NFA
	 *  configurations.  Return the set of disabled alternatives.  For
	 *
	 *  a : A | A | A ;
	 *
	 *  this method returns {2,3} as disabled.  This does not mean that
	 *  the alternative is totally unreachable, it just means that for this
	 *  DFA state, that alt is disabled.  There may be other accept states
	 *  for that alt.
	 */
	public Set getDisabledAlternatives() {
		Set disabled = new LinkedHashSet();
		Iterator iter = nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			if ( configuration.resolved ) {
				disabled.add(Utils.integer(configuration.alt));
			}
		}
		return disabled;
	}

	/**
	public int getNumberOfEOTNFAStates() {
		int n = 0;
		Iterator iter = nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			NFAState s = dfa.nfa.getState(configuration.state);
			if ( s.isEOTState() ) {
				n++;
			}
		}
		return n;
	}
    */
	
	protected Set getNonDeterministicAlts() {
		int user_k = dfa.getUserMaxLookahead();
		if ( user_k>0 && user_k==k ) {
			// if fixed lookahead, then more than 1 alt is a nondeterminism
			// if we have hit the max lookahead
			return getAltSet();
		}
		else if ( abortedDueToMultipleRecursiveAlts || abortedDueToRecursionOverflow ) {
			// if we had to abort for non-LL(*) state assume all alts are a problem
			return getAltSet();
		}
		else {
			return getConflictingAlts();
		}
	}

    /** Walk each NFA configuration in this DFA state looking for a conflict
     *  where (s|i|ctx) and (s|j|ctx) exist, indicating that state s with
     *  context conflicting ctx predicts alts i and j.  Return an Integer set
	 *  of the alternative numbers that conflict.  Two contexts conflict if
	 *  they are equal or one is a stack suffix of the other or one is
	 *  the empty context.
	 *
     *  Use a hash table to record the lists of configs for each state
	 *  as they are encountered.  We need only consider states for which
	 *  there is more than one configuration.  The configurations' predicted
	 *  alt must be different or must have different contexts to avoid a
	 *  conflict.
	 *
	 *  Don't report conflicts for DFA states that have conflicting Tokens
	 *  rule NFA states; they will be resolved in favor of the first rule.
     */
    protected Set getConflictingAlts() {
		// TODO this is called multiple times: cache result?
		//System.out.println("getNondetAlts for DFA state "+stateNumber);
 		Set nondeterministicAlts = new HashSet();

		// If only 1 NFA conf then no way it can be nondeterministic;
		// save the overhead.  There are many o-a->o NFA transitions
		// and so we save a hash map and iterator creation for each
		// state.
		if ( nfaConfigurations.size()<=1 ) {
			return null;
		}

		// First get a list of configurations for each state.
		// Most of the time, each state will have one associated configuration
		Iterator iter = nfaConfigurations.iterator();
		Map stateToConfigListMap = new HashMap();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			Integer stateI = Utils.integer(configuration.state);
			List prevConfigs = (List)stateToConfigListMap.get(stateI);
			if ( prevConfigs==null ) {
				prevConfigs = new ArrayList();
				stateToConfigListMap.put(stateI, prevConfigs);
			}
			prevConfigs.add(configuration);
		}

		// potential conflicts are states with > 1 configuration and diff alts
		Set states = stateToConfigListMap.keySet();
		int numPotentialConflicts = 0;
		for (Iterator it = states.iterator(); it.hasNext();) {
			Integer stateI = (Integer) it.next();
			boolean thisStateHasPotentialProblem = false;
			List configsForState = (List)stateToConfigListMap.get(stateI);
			int alt=0;
			for (int i = 0; i < configsForState.size() && configsForState.size()>1 ; i++) {
				NFAConfiguration c = (NFAConfiguration) configsForState.get(i);
				if ( alt==0 ) {
					alt = c.alt;
				}
				else if ( c.alt!=alt ) {
					/*
					System.out.println("potential conflict in state "+stateI+
									   " configs: "+configsForState);
					*/
					// 11/28/2005: don't report closures that pinch back
					// together in Tokens rule.  We want to silently resolve
					// to the first token definition ala lex/flex by ignoring
					// these conflicts.
					if ( dfa.nfa.grammar.type!=Grammar.LEXER ||
						 !dfa.decisionNFAStartState.enclosingRule.equals(Grammar.ARTIFICIAL_TOKENS_RULENAME) )
					{
						numPotentialConflicts++;
						thisStateHasPotentialProblem = true;
					}
				}
			}
			if ( !thisStateHasPotentialProblem ) {
				// remove NFA state's configurations from
				// further checking; no issues with it
				// (can't remove as it's concurrent modification; set to null)
				stateToConfigListMap.put(stateI, null);
			}
		}

		// a fast check for potential issues; most states have none
		if ( numPotentialConflicts==0 ) {
			return null;
		}

		// we have a potential problem, so now go through config lists again
		// looking for different alts (only states with potential issues
		// are left in the states set).  Now we will check context.
		// For example, the list of configs for NFA state 3 in some DFA
		// state might be:
		//   [3|2|[28 18 $], 3|1|[28 $], 3|1, 3|2]
		// I want to create a map from context to alts looking for overlap:
		//   [28 18 $] -> 2
		//   [28 $] -> 1
		//   [$] -> 1,2
		// Indeed a conflict exists as same state 3, same context [$], predicts
		// alts 1 and 2.
		// walk each state with potential conflicting configurations
		for (Iterator it = states.iterator(); it.hasNext();) {
			Integer stateI = (Integer) it.next();
			List configsForState = (List)stateToConfigListMap.get(stateI);
			// compare each configuration pair s, t to ensure:
			// s.ctx different than t.ctx if s.alt != t.alt
			for (int i = 0; configsForState!=null && i < configsForState.size(); i++) {
				NFAConfiguration s = (NFAConfiguration) configsForState.get(i);
				for (int j = i+1; j < configsForState.size(); j++) {
					NFAConfiguration t = (NFAConfiguration)configsForState.get(j);
					// conflicts means s.ctx==t.ctx or s.ctx is a stack
					// suffix of t.ctx or vice versa (if alts differ).
					// Also a conflict if s.ctx or t.ctx is empty
					if ( s.alt != t.alt && s.context.conflictsWith(t.context) ) {
						nondeterministicAlts.add(Utils.integer(s.alt));
						nondeterministicAlts.add(Utils.integer(t.alt));
					}
				}
			}
		}

		if ( nondeterministicAlts.size()==0 ) {
			return null;
		}
        return nondeterministicAlts;
    }

	/** Get the set of all alts mentioned by all NFA configurations in this
	 *  DFA state.
	 */
	public Set getAltSet() {
		Set alts = new HashSet();
		Iterator iter = nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			alts.add(Utils.integer(configuration.alt));
		}
		if ( alts.size()==0 ) {
			return null;
		}
		return alts;
	}

	/** Get the set of all states mentioned by all NFA configurations in this
	 *  DFA state associated with alt.
	 */
	public Set getNFAStatesForAlt(int alt) {
		Set alts = new HashSet();
		Iterator iter = nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			if ( configuration.alt == alt ) {
				alts.add(Utils.integer(configuration.state));
			}
		}
		return alts;
	}

	/** For gated productions, we need a list of all predicates for the
	 *  target of an edge so we can gate the edge based upon the predicates
	 *  associated with taking that path (if any).
	 *
	 *  experimental 11/29/2005
	 *
	 *  TODO: cache this as it's called a lot; or at least set bit if >1 present in state
	public Set getGatedPredicatesInNFAConfigurations() {
		Set preds = new HashSet();
		Iterator iter = nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			if ( configuration.semanticContext.isGated() ) {
				preds.add(configuration.semanticContext);
			}
		}
		if ( preds.size()==0 ) {
			return null;
		}
		return preds;
	}
	 */

	/** For gated productions, we need an OR'd list of all predicates for the
	 *  target of an edge so we can gate the edge based upon the predicates
	 *  associated with taking that path (if any).
	 *
	 *  TODO: cache this as it's called a lot; or at least set bit if >1 present in state
	 */
	public SemanticContext getGatedPredicatesInNFAConfigurations() {
		Iterator iter = nfaConfigurations.iterator();
		SemanticContext unionOfPredicatesFromAllAlts = null;
		NFAConfiguration configuration;
		boolean foundTruePred = false;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			SemanticContext gatedPredExpr =
				configuration.semanticContext.getGatedPredicateContext();
			if ( gatedPredExpr==null ) {
				foundTruePred = true;
			}
			if ( gatedPredExpr!=null ) {
				if ( unionOfPredicatesFromAllAlts==null ) {
					unionOfPredicatesFromAllAlts = gatedPredExpr;
				}
				else {
					unionOfPredicatesFromAllAlts =
						SemanticContext.or(unionOfPredicatesFromAllAlts,gatedPredExpr);
				}
			}
		}
		if ( foundTruePred ) {
			return null;
		}
		if ( unionOfPredicatesFromAllAlts instanceof SemanticContext.TruePredicate ) {
			return null;
		}
		return unionOfPredicatesFromAllAlts;
	}

    /** Is an accept state reachable from this state? */
    public int getAcceptStateReachable() {
        return acceptStateReachable;
    }

    public void setAcceptStateReachable(int acceptStateReachable) {
        this.acceptStateReachable = acceptStateReachable;
    }

    public boolean isResolvedWithPredicates() {
        return resolvedWithPredicates;
    }

    /** Print all NFA states plus what alts they predict */
    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append(stateNumber+":{");
        Iterator iter = nfaConfigurations.iterator();
        int i = 1;
        while (iter.hasNext()) {
            NFAConfiguration configuration = (NFAConfiguration) iter.next();
            if ( i>1 ) {
                buf.append(", ");
            }
            buf.append(configuration);
            i++;
        }
        buf.append("}");
        return buf.toString();
    }

	public int getLookaheadDepth() {
		return k;
	}

	public void setLookaheadDepth(int k) {
		this.k = k;
		if ( k > dfa.max_k ) { // track max k for entire DFA
			dfa.max_k = k;
		}
	}

}