dfastate.java

antlr最新版本V3源代码

        // walk the existing list looking for the collision
        for (int i=0; i<n; i++) {
            Label rl = (Label)reachableLabels.get(i);
            /*
            if ( label.equals(rl) ) {
                // OPTIMIZATION:
                // exact label already here, just return; previous addition
                // would have made everything unique/disjoint
                return;
            }
            */
            IntSet s_i = rl.getSet();
            IntSet intersection = s_i.and(t);
            /*
			System.out.println("comparing ["+i+"]: "+label.toString(dfa.nfa.grammar)+" & "+
                    rl.toString(dfa.nfa.grammar)+"="+
                    intersection.toString(dfa.nfa.grammar));
            */
			if ( intersection.isNil() ) {
                continue;
            }

            // For any (s_i, t) with s_i&t!=nil replace with (s_i-t, s_i&t)
            // (ignoring s_i-t if nil; don't put in list)

            // Replace existing s_i with intersection since we
            // know that will always be a non nil character class
            reachableLabels.set(i, new Label(intersection));

            // Compute s_i-t to see what is in current set and not in incoming
            IntSet existingMinusNewElements = s_i.subtract(t);
			//System.out.println(s_i+"-"+t+"="+existingMinusNewElements);
            if ( !existingMinusNewElements.isNil() ) {
                // found a new character class, add to the end (doesn't affect
                // outer loop duration due to n computation a priori.
                Label newLabel = new Label(existingMinusNewElements);
                reachableLabels.add(newLabel);
            }

			/*
            System.out.println("after collision, " +
                    "reachableLabels="+reachableLabels.toString());
					*/

            // anything left to add to the reachableLabels?
            remainder = t.subtract(s_i);
            if ( remainder.isNil() ) {
                break; // nothing left to add to set.  done!
            }

            t = remainder;
        }
        if ( !remainder.isNil() ) {
			/*
			System.out.println("before add remainder to state "+dfa.decisionNumber+"."+stateNumber+": " +
					"reachableLabels="+reachableLabels.toString());
			System.out.println("remainder state "+dfa.decisionNumber+"."+stateNumber+": "+remainder.toString(dfa.nfa.grammar));
            */
			Label newLabel = new Label(remainder);
            reachableLabels.add(newLabel);
        }
		/*
		System.out.println("#END of add to state "+dfa.decisionNumber+"."+stateNumber+": " +
				"reachableLabels="+reachableLabels.toString());
				*/
    }

    public OrderedHashSet getReachableLabels() {
        return reachableLabels;
    }

    public Set getNFAConfigurations() {
        return this.nfaConfigurations;
    }

    public void setNFAConfigurations(Set configs) {
        this.nfaConfigurations = configs;
    }

    /** A decent hash for a DFA state is the sum of the NFA state/alt pairs.
     *  This is used when we add DFAState objects to the DFA.states Map and
     *  when we compare DFA states.  Computed in addNFAConfiguration()
     */
    public int hashCode() {
        return cachedHashCode;
    }

    /** Two DFAStates are equal if their NFA configuration sets are the
	 *  same. This method is used to see if a DFA state already exists.
	 *
     *  Because the number of alternatives and number of NFA configurations are
     *  finite, there is a finite number of DFA states that can be processed.
     *  This is necessary to show that the algorithm terminates.
	 *
	 *  Cannot test the state numbers here because in DFA.addState we need
	 *  to know if any other state exists that has this exact set of NFA
	 *  configurations.  The DFAState state number is irrelevant.
     */
    public boolean equals(Object o) {
        DFAState other = (DFAState)o;
        if ( o==null ) {
            return false;
        }
        if ( this.hashCode()!=other.hashCode() ) {
            return false;
        }
		// if not same number of NFA configuraitons, cannot be same state
		if ( this.nfaConfigurations.size() != other.nfaConfigurations.size() ) {
			return false;
		}

		// compare set of NFA configurations in this set with other
        Iterator iter = this.nfaConfigurations.iterator();
        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 ) {