nfafactory.java

antlr最新版本V3源代码

		NFAState startOfAlt = newState(); // must have this no matter what
		transitionBetweenStates(startOfAlt, set.left, Label.EPSILON);

		return new StateCluster(startOfAlt,set.right);
	}

	/** From A|B|..|Z alternative block build
     *
     *  o->o-A->o->o (last NFAState is blockEndNFAState pointed to by all alts)
     *  |          ^
     *  o->o-B->o--|
     *  |          |
     *  ...        |
     *  |          |
     *  o->o-Z->o--|
     *
     *  So every alternative gets begin NFAState connected by epsilon
     *  and every alt right side points at a block end NFAState.  There is a
     *  new NFAState in the NFAState in the StateCluster for each alt plus one for the
     *  end NFAState.
     *
     *  Special case: only one alternative: don't make a block with alt
     *  begin/end.
     *
     *  Special case: if just a list of tokens/chars/sets, then collapse
     *  to a single edge'd o-set->o graph.
     *
     *  Set alt number (1..n) in the left-Transition NFAState.
     */
    public StateCluster build_AlternativeBlock(List alternativeStateClusters)
    {
        StateCluster result = null;
        if ( alternativeStateClusters==null || alternativeStateClusters.size()==0 ) {
            return null;
        }

		// single alt case
		if ( alternativeStateClusters.size()==1 ) {
			// single alt, no decision, just return only alt state cluster
			StateCluster g = (StateCluster)alternativeStateClusters.get(0);
			NFAState startOfAlt = newState(); // must have this no matter what
			transitionBetweenStates(startOfAlt, g.left, Label.EPSILON);

			//System.out.println("### opt saved start/stop end in (...)");
			return new StateCluster(startOfAlt,g.right);
		}

		// even if we can collapse for lookahead purposes, we will still
        // need to predict the alts of this subrule in case there are actions
        // etc...  This is the decision that is pointed to from the AST node
        // (always)
        NFAState prevAlternative = null; // tracks prev so we can link to next alt
        NFAState firstAlt = null;
        NFAState blockEndNFAState = newState();
        blockEndNFAState.setDescription("end block");
        int altNum = 1;
        for (Iterator iter = alternativeStateClusters.iterator(); iter.hasNext();) {
            StateCluster g = (StateCluster) iter.next();
            // add begin NFAState for this alt connected by epsilon
            NFAState left = newState();
            left.setDescription("alt "+altNum+" of ()");
			transitionBetweenStates(left, g.left, Label.EPSILON);
			transitionBetweenStates(g.right, blockEndNFAState, Label.EPSILON);
			// Are we the first alternative?
			if ( firstAlt==null ) {
				firstAlt = left; // track extreme left node of StateCluster
			}
			else {
				// if not first alternative, must link to this alt from previous
				transitionBetweenStates(prevAlternative, left, Label.EPSILON);
			}
			prevAlternative = left;
			altNum++;
		}

		// return StateCluster pointing representing entire block
		// Points to first alt NFAState on left, block end on right
		result = new StateCluster(firstAlt, blockEndNFAState);

		firstAlt.decisionStateType = NFAState.BLOCK_START;

		// set EOB markers for Jean
		firstAlt.endOfBlockStateNumber = blockEndNFAState.stateNumber;

		return result;
    }

    /** From (A)? build either:
     *
	 *  o--A->o
	 *  |     ^
	 *  o---->|
     *
     *  or, if A is a block, just add an empty alt to the end of the block
     */
    public StateCluster build_Aoptional(StateCluster A) {
        StateCluster g = null;
        int n = nfa.grammar.getNumberOfAltsForDecisionNFA(A.left);
        if ( n==1 ) {
            // no decision, just wrap in an optional path
			//NFAState decisionState = newState();
			NFAState decisionState = A.left; // resuse left edge
			decisionState.setDescription("only alt of ()? block");
			NFAState emptyAlt = newState();
            emptyAlt.setDescription("epsilon path of ()? block");
            NFAState blockEndNFAState = null;
			blockEndNFAState = newState();
			transitionBetweenStates(A.right, blockEndNFAState, Label.EPSILON);
			blockEndNFAState.setDescription("end ()? block");
            //transitionBetweenStates(decisionState, A.left, Label.EPSILON);
            transitionBetweenStates(decisionState, emptyAlt, Label.EPSILON);
            transitionBetweenStates(emptyAlt, blockEndNFAState, Label.EPSILON);

			// set EOB markers for Jean
			decisionState.endOfBlockStateNumber = blockEndNFAState.stateNumber;
			blockEndNFAState.decisionStateType = NFAState.RIGHT_EDGE_OF_BLOCK;

            g = new StateCluster(decisionState, blockEndNFAState);
        }
        else {
            // a decision block, add an empty alt
            NFAState lastRealAlt =
                    nfa.grammar.getNFAStateForAltOfDecision(A.left, n);
            NFAState emptyAlt = newState();
            emptyAlt.setDescription("epsilon path of ()? block");
            transitionBetweenStates(lastRealAlt, emptyAlt, Label.EPSILON);
            transitionBetweenStates(emptyAlt, A.right, Label.EPSILON);

			// set EOB markers for Jean (I think this is redundant here)
			A.left.endOfBlockStateNumber = A.right.stateNumber;
			A.right.decisionStateType = NFAState.RIGHT_EDGE_OF_BLOCK;

            g = A; // return same block, but now with optional last path
        }
		g.left.decisionStateType = NFAState.OPTIONAL_BLOCK_START;

        return g;
    }

    /** From (A)+ build
	 *
     *     |---|    (Transition 2 from A.right points at alt 1)
	 *     v   |    (follow of loop is Transition 1)
     *  o->o-A-o->o
     *
     *  Meaning that the last NFAState in A points back to A's left Transition NFAState
     *  and we add a new begin/end NFAState.  A can be single alternative or
     *  multiple.
	 *
	 *  During analysis we'll call the follow link (transition 1) alt n+1 for
	 *  an n-alt A block.
     */
    public StateCluster build_Aplus(StateCluster A) {
        NFAState left = newState();
        NFAState blockEndNFAState = newState();
		blockEndNFAState.decisionStateType = NFAState.RIGHT_EDGE_OF_BLOCK;

		// don't reuse A.right as loopback if it's right edge of another block
		if ( A.right.decisionStateType == NFAState.RIGHT_EDGE_OF_BLOCK ) {
			// nested A* so make another tail node to be the loop back
			// instead of the usual A.right which is the EOB for inner loop
			NFAState extraRightEdge = newState();
			transitionBetweenStates(A.right, extraRightEdge, Label.EPSILON);
			A.right = extraRightEdge;
		}

        transitionBetweenStates(A.right, blockEndNFAState, Label.EPSILON); // follow is Transition 1
		// turn A's block end into a loopback (acts like alt 2)
		transitionBetweenStates(A.right, A.left, Label.EPSILON); // loop back Transition 2
		transitionBetweenStates(left, A.left, Label.EPSILON);
		
		A.right.decisionStateType = NFAState.LOOPBACK;
		A.left.decisionStateType = NFAState.BLOCK_START;

		// set EOB markers for Jean
		A.left.endOfBlockStateNumber = A.right.stateNumber;

        StateCluster g = new StateCluster(left, blockEndNFAState);
        return g;
    }

    /** From (A)* build
     *
	 *     |---|
	 *     v   |
	 *  o->o-A-o--o (Transition 2 from block end points at alt 1; follow is Transition 1)
     *  |         ^
     *  o---------| (optional branch is 2nd alt of optional block containing A+)
     *
     *  Meaning that the last (end) NFAState in A points back to A's
     *  left side NFAState and we add 3 new NFAStates (the
     *  optional branch is built just like an optional subrule).
     *  See the Aplus() method for more on the loop back Transition.
	 *  The new node on right edge is set to RIGHT_EDGE_OF_CLOSURE so we
	 *  can detect nested (A*)* loops and insert an extra node.  Previously,
	 *  two blocks shared same EOB node.
     *
     *  There are 2 or 3 decision points in a A*.  If A is not a block (i.e.,
     *  it only has one alt), then there are two decisions: the optional bypass
     *  and then loopback.  If A is a block of alts, then there are three
     *  decisions: bypass, loopback, and A's decision point.
     *
     *  Note that the optional bypass must be outside the loop as (A|B)* is
     *  not the same thing as (A|B|)+.
     *
     *  This is an accurate NFA representation of the meaning of (A)*, but
     *  for generating code, I don't need a DFA for the optional branch by
     *  virtue of how I generate code.  The exit-loopback-branch decision
     *  is sufficient to let me make an appropriate enter, exit, loop
     *  determination.  See codegen.g
     */
    public StateCluster build_Astar(StateCluster A) {
		NFAState bypassDecisionState = newState();
		bypassDecisionState.setDescription("enter loop path of ()* block");
        NFAState optionalAlt = newState();
        optionalAlt.setDescription("epsilon path of ()* block");
        NFAState blockEndNFAState = newState();
		blockEndNFAState.decisionStateType = NFAState.RIGHT_EDGE_OF_BLOCK;

		// don't reuse A.right as loopback if it's right edge of another block
		if ( A.right.decisionStateType == NFAState.RIGHT_EDGE_OF_BLOCK ) {
			// nested A* so make another tail node to be the loop back
			// instead of the usual A.right which is the EOB for inner loop
			NFAState extraRightEdge = newState();
			transitionBetweenStates(A.right, extraRightEdge, Label.EPSILON);
			A.right = extraRightEdge;
		}

		// convert A's end block to loopback
		A.right.setDescription("()* loopback");
		// Transition 1 to actual block of stuff
        transitionBetweenStates(bypassDecisionState, A.left, Label.EPSILON);
        // Transition 2 optional to bypass
        transitionBetweenStates(bypassDecisionState, optionalAlt, Label.EPSILON);
		transitionBetweenStates(optionalAlt, blockEndNFAState, Label.EPSILON);
        // Transition 1 of end block exits
        transitionBetweenStates(A.right, blockEndNFAState, Label.EPSILON);
        // Transition 2 of end block loops
        transitionBetweenStates(A.right, A.left, Label.EPSILON);

		bypassDecisionState.decisionStateType = NFAState.BYPASS;
		A.left.decisionStateType = NFAState.BLOCK_START;
		A.right.decisionStateType = NFAState.LOOPBACK;

		// set EOB markers for Jean
		A.left.endOfBlockStateNumber = A.right.stateNumber;
		bypassDecisionState.endOfBlockStateNumber = blockEndNFAState.stateNumber;

        StateCluster g = new StateCluster(bypassDecisionState, blockEndNFAState);
        return g;
    }

    /** Build an NFA predictor for special rule called Tokens manually that
     *  predicts which token will succeed.  The refs to the rules are not
     *  RuleRefTransitions as I want DFA conversion to stop at the EOT
     *  transition on the end of each token, rather than return to Tokens rule.
     *  If I used normal build_alternativeBlock for this, the RuleRefTransitions
     *  would save return address when jumping away from Tokens rule.
     *
     *  All I do here is build n new states for n rules with an epsilon
     *  edge to the rule start states and then to the next state in the
     *  list:
     *
     *   o->(A)  (a state links to start of A and to next in list)
     *   |
     *   o->(B)
     *   |
     *   ...
     *   |
     *   o->(Z)
	 *
	 *  This is the NFA created for the artificial rule created in
	 *  Grammar.addArtificialMatchTokensRule().
	 *
	 *  11/28/2005: removed so we can use normal rule construction for Tokens.
    public NFAState build_ArtificialMatchTokensRuleNFA() {
        int altNum = 1;
        NFAState firstAlt = null; // the start state for the "rule"
        NFAState prevAlternative = null;
        Iterator iter = nfa.grammar.getRules().iterator();
		// TODO: add a single decision node/state for good description
        while (iter.hasNext()) {
			Rule r = (Rule) iter.next();
            String ruleName = r.name;
			String modifier = nfa.grammar.getRuleModifier(ruleName);
            if ( ruleName.equals(Grammar.ARTIFICIAL_TOKENS_RULENAME) ||
				 (modifier!=null &&
				  modifier.equals(Grammar.FRAGMENT_RULE_MODIFIER)) )
			{
                continue; // don't loop to yourself or do nontoken rules
            }
            NFAState ruleStartState = nfa.grammar.getRuleStartState(ruleName);
            NFAState left = newState();
            left.setDescription("alt "+altNum+" of artificial rule "+Grammar.ARTIFICIAL_TOKENS_RULENAME);
            transitionBetweenStates(left, ruleStartState, Label.EPSILON);
            // Are we the first alternative?
            if ( firstAlt==null ) {
                firstAlt = left; // track extreme top left node as rule start
            }
            else {
                // if not first alternative, must link to this alt from previous
                transitionBetweenStates(prevAlternative, left, Label.EPSILON);
            }
            prevAlternative = left;
            altNum++;
        }
		firstAlt.decisionStateType = NFAState.BLOCK_START;

        return firstAlt;
    }
	 */

    /** Build an atom with all possible values in its label */
    public StateCluster build_Wildcard() {
        NFAState left = newState();
        NFAState right = newState();
        Label label = new Label(nfa.grammar.getTokenTypes()); // char or tokens
        Transition e = new Transition(label,right);
        left.addTransition(e);
        StateCluster g = new StateCluster(left, right);
        return g;
    }

    /** Given a collapsed block of alts (a set of atoms), pull out
     *  the set and return it.
     */
    protected IntSet getCollapsedBlockAsSet(State blk) {
        State s0 = blk;
        if ( s0!=null && s0.transition(0)!=null ) {
            State s1 = s0.transition(0).target;
            if ( s1!=null && s1.transition(0)!=null ) {
                Label label = s1.transition(0).label;
                if ( label.isSet() ) {
                    return label.getSet();
                }
            }
        }
        return null;
    }

	private void transitionBetweenStates(NFAState a, NFAState b, int label) {
		Transition e = new Transition(label,b);
		a.addTransition(e);
	}
}