dfastate.java

antlr最新版本V3源代码

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

	public Set getSyntacticPredicatesInNFAConfigurations() {
		Set synpreds = new HashSet();
		Iterator iter = nfaConfigurations.iterator();
		NFAConfiguration configuration;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			SemanticContext gatedPredExpr =
				configuration.semanticContext.getGatedPredicateContext();
			// if this is a manual syn pred (gated and syn pred), add
			if ( gatedPredExpr!=null &&
				 configuration.semanticContext.isSyntacticPredicate() )
			{
				synpreds.add(configuration.semanticContext);
			}
		}
		if ( synpreds.size()==0 ) {
			return null;
		}
		return synpreds;
	}

	/** 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).
	 *
	 *  For syntactic predicates, we only want to generate predicate
	 *  evaluations as it transitions to an accept state; waste to
	 *  do it earlier.  So, only add gated preds derived from manually-
	 *  specified syntactic predicates if this is an accept state.
	 *
	 *  Also, since configurations w/o gated predicates are like true
	 *  gated predicates, finding a configuration whose alt has no gated
	 *  predicate implies we should evaluate the predicate to true. This
	 *  means the whole edge has to be ungated. Consider:
	 *
	 *	 X : ('a' | {p}?=> 'a')
	 *	   | 'a' 'b'
	 *	   ;
	 *
	 *  Here, you 'a' gets you from s0 to s1 but you can't test p because
	 *  plain 'a' is ok.  It's also ok for starting alt 2.  Hence, you can't
	 *  test p.  Even on the edge going to accept state for alt 1 of X, you
	 *  can't test p.  You can get to the same place with and w/o the context.
	 *  Therefore, it is never ok to test p in this situation. 
	 *
	 *  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;
		while (iter.hasNext()) {
			configuration = (NFAConfiguration) iter.next();
			SemanticContext gatedPredExpr =
				configuration.semanticContext.getGatedPredicateContext();
			if ( gatedPredExpr==null ) {
				// if we ever find a configuration w/o a gated predicate
				// (even if it's a nongated predicate), we cannot gate
				// the indident edges.
				return null;
			}
			else if ( acceptState || !configuration.semanticContext.isSyntacticPredicate() ) {
				// at this point we have a gated predicate and, due to elseif,
				// we know it's an accept and not a syn pred.  In this case,
				// it's safe to add the gated predicate to the union.  We
				// only want to add syn preds if it's an accept state.  Other
				// gated preds can be used with edges leading to accept states.
				if ( unionOfPredicatesFromAllAlts==null ) {
					unionOfPredicatesFromAllAlts = gatedPredExpr;
				}
				else {
					unionOfPredicatesFromAllAlts =
						SemanticContext.or(unionOfPredicatesFromAllAlts,gatedPredExpr);
				}
			}
		}
		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;
		}
	}

}