nfatodfaconverter.java

antlr最新版本V3源代码

			int depth = context.recursionDepthEmanatingFromState(p.stateNumber);
			// Detect recursion by more than a single alt, which indicates
			// that the decision's lookahead language is non-regular; terminate
			if ( depth == 1 && d.dfa.getUserMaxLookahead()==0 ) { // k=* only
			//if ( depth >= NFAContext.MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK ) {
				d.dfa.recursiveAltSet.add(alt); // indicate that this alt is recursive
				if ( d.dfa.recursiveAltSet.size()>1 ) {
					//System.out.println("recursive alts: "+d.dfa.recursiveAltSet.toString());
					d.abortedDueToMultipleRecursiveAlts = true;
					return;
				}
				/*
				System.out.println("alt "+alt+" in rule "+p.enclosingRule+" dec "+d.dfa.decisionNumber+
					" ctx: "+context);
				System.out.println("d="+d);
				*/
			}
			// Detect an attempt to recurse too high
			// if this context has hit the max recursions for p.stateNumber,
			// don't allow it to enter p.stateNumber again
			if ( depth >= NFAContext.MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK ) {
				/*
				System.out.println("OVF state "+d);
				System.out.println("proposed "+proposedNFAConfiguration);
				*/
				d.dfa.probe.reportRecursiveOverflow(d, proposedNFAConfiguration);
				d.abortedDueToRecursionOverflow = true;
				return;
			}

			// otherwise, it's cool to (re)enter target of this rule ref
			RuleClosureTransition ref = (RuleClosureTransition)transition0;
			// first create a new context and push onto call tree,
			// recording the fact that we are invoking a rule and
			// from which state (case 2 below will get the following state
			// via the RuleClosureTransition emanating from the invoking state
			// pushed on the stack).
			// Reset the context to reflect the fact we invoked rule
			NFAContext newContext = new NFAContext(context, p);
			// System.out.print("invoking rule "+nfa.getGrammar().getRuleName(ref.getRuleIndex()));
			// System.out.println(" context="+context);
			// traverse epsilon edge to new rule
			NFAState ruleTarget = (NFAState)ref.target;
			closure(ruleTarget, alt, newContext, semanticContext, d, collectPredicates);
		}
		// Case 2: end of rule state, context (i.e., an invoker) exists
		else if ( p.isAcceptState() && context.parent!=null ) {
			NFAState whichStateInvokedRule = context.invokingState;
			RuleClosureTransition edgeToRule =
				(RuleClosureTransition)whichStateInvokedRule.transition(0);
			NFAState continueState = edgeToRule.getFollowState();
			NFAContext newContext = context.parent; // "pop" invoking state
			closure(continueState, alt, newContext, semanticContext, d, collectPredicates);
		}
		/*
		11/27/2005: I tried adding this but it highlighted that
		lexer rules needed to be called from Tokens not just ref'd directly
		so their contexts are different for F : I '.' ;  I : '0' ;  otherwise
		we get an ambiguity.  The context of state following '0' has same
		NFA state with [6 $] and [$] hence they conflict.  We need to get
		the other stack call in there.
		else if ( dfa.nfa.grammar.type == Grammar.LEXER &&
			      p.isAcceptState() &&
			context.invokingState.enclosingRule.equals("Tokens") )
		{
			// hit the end of a lexer rule when no one has invoked that rule
			// (this will be the case if Tokens rule analysis reaches the
			// stop state of a token in its alt list).
			// Must not follow the FOLLOW links; must return
			return;
		}
		*/
		// Case 3: end of rule state, nobody invoked this rule (no context)
		//    Fall thru to be handled by case 4 automagically.
		// Case 4: ordinary NFA->DFA conversion case: simple epsilon transition
		else {
			// recurse down any epsilon transitions
			if ( transition0!=null && transition0.isEpsilon() ) {
				closure((NFAState)transition0.target,
						alt,
						context,
						semanticContext,
						d,
						collectPredicates);
			}
			else if ( transition0!=null && transition0.isSemanticPredicate() ) {
				// continue closure here too, but add the sem pred to ctx
				SemanticContext newSemanticContext = semanticContext;
				if ( collectPredicates ) {
					// AND the previous semantic context with new pred
					SemanticContext labelContext =
						transition0.label.getSemanticContext();
					// do not hoist syn preds from other rules; only get if in
					// starting state's rule (i.e., context is empty)
					int walkAlt =
						dfa.decisionNFAStartState.translateDisplayAltToWalkAlt(dfa, alt);
					NFAState altLeftEdge =
						dfa.nfa.grammar.getNFAStateForAltOfDecision(dfa.decisionNFAStartState,walkAlt);
					/*
					System.out.println("state "+p.stateNumber+" alt "+alt+" walkAlt "+walkAlt+" trans to "+transition0.target);
					System.out.println("DFA start state "+dfa.decisionNFAStartState.stateNumber);
					System.out.println("alt left edge "+altLeftEdge.stateNumber+
						", epsilon target "+
						altLeftEdge.transition(0).target.stateNumber);
					*/
					if ( !labelContext.isSyntacticPredicate() ||
						 p==altLeftEdge.transition(0).target )
					{
						//System.out.println("&"+labelContext+" enclosingRule="+p.enclosingRule);
						newSemanticContext =
							SemanticContext.and(semanticContext, labelContext);
					}
				}
				closure((NFAState)transition0.target,
						alt,
						context,
						newSemanticContext,
						d,
						collectPredicates);
			}
			Transition transition1 = p.transition(1);
			if ( transition1!=null && transition1.isEpsilon() ) {
				closure((NFAState)transition1.target,
						alt,
						context,
						semanticContext,
						d,
						collectPredicates);
			}
		}

		// don't remove "busy" flag as we want to prevent all
		// references to same config of state|alt|ctx|semCtx even
		// if resulting from another NFA state
	}

	/** A closure operation should abort if that computation has already
	 *  been done or a computation with a conflicting context has already
	 *  been done.  If proposed NFA config's state and alt are the same
	 *  there is potentially a problem.  If the stack context is identical
	 *  then clearly the exact same computation is proposed.  If a context
	 *  is a suffix of the other, then again the computation is in an
	 *  identical context.  ?$ and ??$ are considered the same stack.
	 *  We have to walk configurations linearly doing the comparison instead
	 *  of a set for exact matches.
	 *
	 *  We cannot use a set hash table for this lookup as contexts that are
	 *  suffixes could be !equal() but their hashCode()s would be different;
	 *  that's a problem for a HashSet.  This costs a lot actually, it
	 *  takes about 490ms vs 355ms for Java grammar's analysis phase when
	 *  I moved away from hash lookup.  Argh!  Still it's small.  For newbie
	 *  generated grammars though this really speeds things up because it
	 *  avoids chasing its tail during closure operations on highly left-
	 *  recursive grammars.
	 *
	 *  Ok, backing this out to use exact match again for speed.  We will
	 *  always detect the conflict later when checking for context suffixes...
	 *  I was just trying to prevent unnecessary closures for random crap
	 *  submitted by newbies.  Instead now I check for left-recursive stuff
	 *  and terminate before analysis obviates the need to do this more
	 *  expensive computation.
	 *
	 *  If the semantic context is different, then allow new computation.
	 */
	public static boolean closureIsBusy(DFAState d,
										NFAConfiguration proposedNFAConfiguration)
	{
		// Check epsilon cycle (same state, same alt, same context)
		return d.closureBusy.contains(proposedNFAConfiguration);
		/*
		// Uncomment to get all conflicts not just exact context matches
		for (int i = 0; i < d.closureBusy.size(); i++) {
			NFAConfiguration c = (NFAConfiguration) d.closureBusy.get(i);
			if ( proposedNFAConfiguration.state==c.state &&
				 proposedNFAConfiguration.alt==c.alt &&
				 proposedNFAConfiguration.semanticContext.equals(c.semanticContext) &&
				 proposedNFAConfiguration.context.suffix(c.context) )
			{
				// if computing closure of start state, we tried to
				// recompute a closure, must be left recursion.  We got back
				// to the same computation.  After having consumed no input,
				// we're back.  Only track rule invocation states
				if ( (dfa.startState==null ||
					  d.stateNumber==dfa.startState.stateNumber) &&
					 p.transition(0) instanceof RuleClosureTransition )
				{
					d.dfa.probe.reportLeftRecursion(d, proposedNFAConfiguration);
				}
				return true;
			}
		}
		return false;
		*/
	}

	/** Given the set of NFA states in DFA state d, find all NFA states
	 *  reachable traversing label arcs.  By definition, there can be
	 *  only one DFA state reachable by an atom from DFA state d so we must
	 *  find and merge all NFA states reachable via label.  Return a new
	 *  DFAState that has all of those NFA states with their context (i.e.,
	 *  which alt do they predict and where to return to if they fall off
	 *  end of a rule).
	 *
	 *  Because we cannot jump to another rule nor fall off the end of a rule
	 *  via a non-epsilon transition, NFA states reachable from d have the
	 *  same configuration as the NFA state in d.  So if NFA state 7 in d's
	 *  configurations can reach NFA state 13 then 13 will be added to the
	 *  new DFAState (labelDFATarget) with the same configuration as state
	 *  7 had.
	 *
	 *  This method does not see EOT transitions off the end of token rule
	 *  accept states if the rule was invoked by somebody.
	 */
	public DFAState reach(DFAState d, Label label) {
		DFAState labelDFATarget = dfa.newState();
		// for each NFA state in d, add in target states for label
		int intLabel = label.getAtom();
		IntSet setLabel = label.getSet();
		Iterator iter = d.getNFAConfigurations().iterator();
		while ( iter.hasNext() ) {
			NFAConfiguration c = (NFAConfiguration)iter.next();
			if ( c.resolved || c.resolveWithPredicate ) {
				continue; // the conflict resolver indicates we must leave alone
			}
			NFAState p = dfa.nfa.getState(c.state);
			// by design of the grammar->NFA conversion, only transition 0
			// may have a non-epsilon edge.
			Transition edge = p.transition(0);
			if ( edge==null || !c.singleAtomTransitionEmanating ) {
				continue;
			}
			Label edgeLabel = edge.label;

			// SPECIAL CASE
			// if it's an EOT transition on end of lexer rule, but context
			// stack is not empty, then don't see the EOT; the closure
			// will have added in the proper states following the reference
			// to this rule in the invoking rule.  In other words, if
			// somebody called this rule, don't see the EOT emanating from
			// this accept state.
			if ( c.context.parent!=null &&
				 edgeLabel.isAtom() &&
				 edgeLabel.getAtom()==Label.EOT )
			{
				continue;
			}

			// Labels not unique at this point (not until addReachableLabels)
			// so try simple int label match before general set intersection
			//System.out.println("comparing "+edgeLabel+" with "+label);
			boolean matched =
				(!label.isSet()&&edgeLabel.getAtom()==intLabel)||
				(!edgeLabel.getSet().and(setLabel).isNil());
			if ( matched ) {
				// found a transition with label;
				// add NFA target to (potentially) new DFA state
                labelDFATarget.addNFAConfiguration(
					(NFAState)edge.target,
					c.alt,
					c.context,
					c.semanticContext);
			}
		}
        if ( labelDFATarget.getNFAConfigurations().size()==0 ) {
            // kill; it's empty
            dfa.setState(labelDFATarget.stateNumber, null);
            labelDFATarget = null;
        }
        return labelDFATarget;
	}

	/** Walk the configurations of this DFA state d looking for the
	 *  configuration, c, that has a transition on EOT.  State d should
	 *  be converted to an accept state predicting the c.alt.  Blast
	 *  d's current configuration set and make it just have config c.
	 *
	 *  TODO: can there be more than one config with EOT transition?
	 *  That would mean that two NFA configurations could reach the
	 *  end of the token with possibly different predicted alts.
	 *  Seems like that would be rare or impossible.  Perhaps convert
	 *  this routine to find all such configs and give error if >1.
	 */
	protected void convertToEOTAcceptState(DFAState d) {
		Label eot = new Label(Label.EOT);
		Iterator iter = d.getNFAConfigurations().iterator();
		while ( iter.hasNext() ) {
			NFAConfiguration c =
					(NFAConfiguration)iter.next();
			if ( c.resolved || c.resolveWithPredicate ) {
				continue; // the conflict resolver indicates we must leave alone
			}
			NFAState p = dfa.nfa.getState(c.state);
			Transition edge = p.transition(0);
			Label edgeLabel = edge.label;
			if ( edgeLabel.equals(eot) ) {
				//System.out.println("config with EOT: "+c);
				d.setAcceptState(true);
				//System.out.println("d goes from "+d);
				d.getNFAConfigurations().clear();
				d.addNFAConfiguration(p,c.alt,c.context,c.semanticContext);
				//System.out.println("to "+d);
				return; // assume only one EOT transition
			}
		}
	}

	/** Add a new DFA state to the DFA if not already present.
     *  If the DFA state uniquely predicts a single alternative, it
     *  becomes a stop state; don't add to work list.  Further, if
     *  there exists an NFA state predicted by > 1 different alternatives
     *  and with the same syn and sem context, the DFA is nondeterministic for
     *  at least one input sequence reaching that NFA state.
     */
    protected DFAState addDFAStateToWorkList(DFAState d) {
        DFAState existingState = dfa.addState(d);
		if ( d != existingState ) {
			// already there...use/return the existing DFA state.
			// But also set the states[d.stateNumber] to the existing
			// DFA state because the closureIsBusy must report
			// infinite recursion on a state before it knows
			// whether or not the state will already be
			// found after closure on it finishes.  It could be
			// refer to a state that will ultimately not make it
			// into the reachable state space and the error