import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
protected String getStateLabel(ATNState s) {
	if ( s==null ) return "null";
	String stateLabel = "";

	if (s instanceof BlockStartState) {
		stateLabel += "→\\n";
	}
	else if (s instanceof BlockEndState) {
		stateLabel += "←\\n";
	}

	stateLabel += String.valueOf(s.stateNumber);

	if (s instanceof PlusBlockStartState || s instanceof PlusLoopbackState) {
		stateLabel += "+";
	}
	else if (s instanceof StarBlockStartState || s instanceof StarLoopEntryState || s instanceof StarLoopbackState) {
		stateLabel += "*";
	}

	if ( s instanceof DecisionState && ((DecisionState)s).decision>=0 ) {
		stateLabel = stateLabel+"\\nd="+((DecisionState)s).decision;
	}

	return stateLabel;
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
/** identify the ATN states where we need to set the outer alt number.
 *  For regular rules, that's the block at the target to rule start state.
 *  For left-recursive rules, we track the primary block, which looks just
 *  like a regular rule's outer block, and the star loop block (always
 *  there even if 1 alt).
 */
public BitSet findOuterMostDecisionStates() {
	BitSet track = new BitSet(atn.states.size());
	int numberOfDecisions = atn.getNumberOfDecisions();
	for (int i = 0; i < numberOfDecisions; i++) {
		DecisionState decisionState = atn.getDecisionState(i);
		RuleStartState startState = atn.ruleToStartState[decisionState.ruleIndex];
		// Look for StarLoopEntryState that is in any left recursive rule
		if ( decisionState instanceof StarLoopEntryState) {
			StarLoopEntryState loopEntry = (StarLoopEntryState)decisionState;
			if ( loopEntry.isPrecedenceDecision ) {
				// Recursive alts always result in a (...)* in the transformed
				// left recursive rule and that always has a BasicBlockStartState
				// even if just 1 recursive alt exists.
				ATNState blockStart = loopEntry.transition(0).target;
				// track the StarBlockStartState associated with the recursive alternatives
				track.set(blockStart.stateNumber);
			}
		}
		else if ( startState.transition(0).target == decisionState ) {
			// always track outermost block for any rule if it exists
			track.set(decisionState.stateNumber);
		}
	}
	return track;
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
private static void optimizeStates(ATN atn) {
//		System.out.println(atn.states);
		List<ATNState> compressed = new ArrayList<ATNState>();
		int i = 0; // new state number
		for (ATNState s : atn.states) {
			if ( s!=null ) {
				compressed.add(s);
				s.stateNumber = i; // reset state number as we shift to new position
				i++;
			}
		}
//		System.out.println(compressed);
//		System.out.println("ATN optimizer removed " + (atn.states.size() - compressed.size()) + " null states.");
		atn.states.clear();
		atn.states.addAll(compressed);
	}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
/** For a lexer, a string is a sequence of char to match.  That is,
 *  "fog" is treated as 'f' 'o' 'g' not as a single transition in
 *  the DFA.  Machine== o-'f'->o-'o'->o-'g'->o and has n+1 states
 *  for n characters.
 */
@Override
public Handle stringLiteral(TerminalAST stringLiteralAST) {
	String chars = stringLiteralAST.getText();
	chars = CharSupport.getStringFromGrammarStringLiteral(chars);
	int n = chars.length();
	ATNState left = newState(stringLiteralAST);
	ATNState prev = left;
	ATNState right = null;
	for (int i=0; i<n; i++) {
		right = newState(stringLiteralAST);
		prev.addTransition(new AtomTransition(right, chars.charAt(i)));
		prev = right;
	}
	stringLiteralAST.atnState = left;
	return new Handle(left, right);
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
public Handle _ruleRef(GrammarAST node) {
	Rule r = g.getRule(node.getText());
	if ( r==null ) {
		g.tool.errMgr.grammarError(ErrorType.INTERNAL_ERROR, g.fileName, node.getToken(), "Rule "+node.getText()+" undefined");
		return null;
	}
	RuleStartState start = atn.ruleToStartState[r.index];
	ATNState left = newState(node);
	ATNState right = newState(node);
	int precedence = 0;
	if (((GrammarASTWithOptions)node).getOptionString(LeftRecursiveRuleTransformer.PRECEDENCE_OPTION_NAME) != null) {
		precedence = Integer.parseInt(((GrammarASTWithOptions)node).getOptionString(LeftRecursiveRuleTransformer.PRECEDENCE_OPTION_NAME));
	}
	RuleTransition call = new RuleTransition(start, r.index, precedence, right);
	left.addTransition(call);

	node.atnState = left;
	return new Handle(left, right);
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
@Override
protected void visitState(ATNState p) {
    super.visitState(p);

    if (p.getNumberOfTransitions() > 1) {
        return;
    }

    Transition transition = p.transition(0);
    if (transition instanceof RuleTransition) {
        // rule transition created a new context
        associatedTransitions.put(_ctx, transition);
    }
    else if (!p.onlyHasEpsilonTransitions()) {
        // match transition created a new terminal or error node
        associatedTransitions.put(_ctx.getChild(_ctx.getChildCount() - 1), transition);
    }
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
public FailedPredicateException(@NotNull Parser recognizer,
								@Nullable String predicate,
								@Nullable String message)
{
	super(formatMessage(predicate, message), recognizer, recognizer.getInputStream(), recognizer._ctx);
	ATNState s = recognizer.getInterpreter().atn.states.get(recognizer.getState());

	AbstractPredicateTransition trans = (AbstractPredicateTransition)s.transition(0);
	if (trans instanceof PredicateTransition) {
		this.ruleIndex = ((PredicateTransition)trans).ruleIndex;
		this.predicateIndex = ((PredicateTransition)trans).predIndex;
	}
	else {
		this.ruleIndex = 0;
		this.predicateIndex = 0;
	}

	this.predicate = predicate;
	this.setOffendingToken(recognizer.getCurrentToken());
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
public String getDOT(ATNState startState, boolean isLexer) {
	Set<String> ruleNames = grammar.rules.keySet();
	String[] names = new String[ruleNames.size()+1];
	int i = 0;
	for (String s : ruleNames) names[i++] = s;
	return getDOT(startState, names, isLexer);
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
/** Override this method so that we can record which alternative
	 *  was taken at each decision point. For non-left recursive rules,
	 *  it's simple. Set decisionStatesThatSetOuterAltNumInContext
	 *  indicates which decision states should set the outer alternative number.
	 *
	 *  <p>Left recursive rules are much more complicated to deal with:
	 *  there is typically a decision for the primary alternatives and a
	 *  decision to choose between the recursive operator alternatives.
	 *  For example, the following left recursive rule has two primary and 2
	 *  recursive alternatives.</p>
	 *
		 e : e '*' e
		   | '-' INT
		   | e '+' e
		   | ID
		   ;

	 *  <p>ANTLR rewrites that rule to be</p>

		 e[int precedence]
			 : ('-' INT | ID)
			 ( {...}? '*' e[5]
			 | {...}? '+' e[3]
			 )*
			;

	 *
	 *  <p>So, there are two decisions associated with picking the outermost alt.
	 *  This complicates our tracking significantly. The outermost alternative number
	 *  is a function of the decision (ATN state) within a left recursive rule and the
	 *  predicted alternative coming back from adaptivePredict().
	 *
	 *  We use stateToAltsMap as a cache to avoid expensive calls to
	 *  getRecursiveOpAlts().
	 */
	@Override
	protected int visitDecisionState(DecisionState p) {
		int predictedAlt = super.visitDecisionState(p);
		if( p.getNumberOfTransitions() > 1) {
//			System.out.println("decision "+p.decision+": "+predictedAlt);
			if( p.decision == this.overrideDecision &&
				this._input.index() == this.overrideDecisionInputIndex )
			{
				overrideDecisionRoot = (GrammarInterpreterRuleContext)getContext();
			}
		}

		GrammarInterpreterRuleContext ctx = (GrammarInterpreterRuleContext)_ctx;
		if ( decisionStatesThatSetOuterAltNumInContext.get(p.stateNumber) ) {
			ctx.outerAltNum = predictedAlt;
			Rule r = g.getRule(p.ruleIndex);
			if ( atn.ruleToStartState[r.index].isLeftRecursiveRule ) {
				int[] alts = stateToAltsMap[p.stateNumber];
				LeftRecursiveRule lr = (LeftRecursiveRule) g.getRule(p.ruleIndex);
				if (p.getStateType() == ATNState.BLOCK_START) {
					if ( alts==null ) {
						alts = lr.getPrimaryAlts();
						stateToAltsMap[p.stateNumber] = alts; // cache it
					}
				}
				else if ( p.getStateType() == ATNState.STAR_BLOCK_START ) {
					if ( alts==null ) {
						alts = lr.getRecursiveOpAlts();
						stateToAltsMap[p.stateNumber] = alts; // cache it
					}
				}
				ctx.outerAltNum = alts[predictedAlt];
			}
		}

		return predictedAlt;
	}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
String getStateString(ATNState s) {
	int n = s.stateNumber;
	String stateStr = "s"+n;
	if ( s instanceof StarBlockStartState ) stateStr = "StarBlockStart_"+n;
	else if ( s instanceof PlusBlockStartState ) stateStr = "PlusBlockStart_"+n;
	else if ( s instanceof BlockStartState) stateStr = "BlockStart_"+n;
	else if ( s instanceof BlockEndState ) stateStr = "BlockEnd_"+n;
	else if ( s instanceof RuleStartState) stateStr = "RuleStart_"+g.getRule(s.ruleIndex).name+"_"+n;
	else if ( s instanceof RuleStopState ) stateStr = "RuleStop_"+g.getRule(s.ruleIndex).name+"_"+n;
	else if ( s instanceof PlusLoopbackState) stateStr = "PlusLoopBack_"+n;
	else if ( s instanceof StarLoopbackState) stateStr = "StarLoopBack_"+n;
	else if ( s instanceof StarLoopEntryState) stateStr = "StarLoopEntry_"+n;
	return stateStr;
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
@Override
public void visitState(ATNState p) {
	if (p.getStateType() == ATNState.BASIC && p.getNumberOfTransitions() == 1) {
		ATNState q = p.transition(0).target;
		if (p.transition(0) instanceof RuleTransition) {
			q = ((RuleTransition) p.transition(0)).followState;
		}
		if (q.getStateType() == ATNState.BASIC) {
			// we have p-x->q for x in {rule, action, pred, token, ...}
			// if edge out of q is single epsilon to block end
			// we can strip epsilon p-x->q-eps->r
			Transition trans = q.transition(0);
			if (q.getNumberOfTransitions() == 1 && trans instanceof EpsilonTransition) {
				ATNState r = trans.target;
				if (r instanceof BlockEndState || r instanceof PlusLoopbackState || r instanceof StarLoopbackState) {
					// skip over q
					if (p.transition(0) instanceof RuleTransition) {
						((RuleTransition) p.transition(0)).followState = r;
					} else {
						p.transition(0).target = r;
					}
					_atn.removeState(q);
				}
			}
		}
	}
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
protected Handle action(GrammarAST node, LexerAction lexerAction) {
	ATNState left = newState(node);
	ATNState right = newState(node);
	boolean isCtxDependent = false;
	int lexerActionIndex = getLexerActionIndex(lexerAction);
	ActionTransition a =
		new ActionTransition(right, currentRule.index, lexerActionIndex, isCtxDependent);
	left.addTransition(a);
	node.atnState = left;
	Handle h = new Handle(left, right);
	return h;
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
@Override
public Handle range(GrammarAST a, GrammarAST b) {
	ATNState left = newState(a);
	ATNState right = newState(b);
	int t1 = CharSupport.getCharValueFromGrammarCharLiteral(a.getText());
	int t2 = CharSupport.getCharValueFromGrammarCharLiteral(b.getText());
	left.addTransition(new  RangeTransition(right, t1, t2));
	a.atnState = left;
	b.atnState = left;
	return new Handle(left, right);
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
/** [Aa\t \u1234a-z\]\-] char sets */
@Override
public Handle charSetLiteral(GrammarAST charSetAST) {
	ATNState left = newState(charSetAST);
	ATNState right = newState(charSetAST);
	IntervalSet set = getSetFromCharSetLiteral(charSetAST);
	left.addTransition(new SetTransition(right, set));
	charSetAST.atnState = left;
	return new Handle(left, right);
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
@Override
public Handle tokenRef(TerminalAST node) {
	// Ref to EOF in lexer yields char transition on -1
	if ( node.getText().equals("EOF") ) {
		ATNState left = newState(node);
		ATNState right = newState(node);
		left.addTransition(new AtomTransition(right, IntStream.EOF));
		return new Handle(left, right);
	}
	return _ruleRef(node);
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
public void visit_(ATNState s, Set<Integer> visited) {
	if ( !visited.add(s.stateNumber) ) return;
	visited.add(s.stateNumber);

	visitState(s);
	int n = s.getNumberOfTransitions();
	for (int i=0; i<n; i++) {
		Transition t = s.transition(i);
		visit_(t.target, visited);
	}
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
/** From label {@code A} build graph {@code o-A->o}. */

	@Override
	public Handle tokenRef(TerminalAST node) {
		ATNState left = newState(node);
		ATNState right = newState(node);
		int ttype = g.getTokenType(node.getText());
		left.addTransition(new AtomTransition(right, ttype));
		node.atnState = left;
		return new Handle(left, right);
	}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
/** From an empty alternative build {@code o-e->o}. */

	@Override
	public Handle epsilon(GrammarAST node) {
		ATNState left = newState(node);
		ATNState right = newState(node);
		epsilon(left, right);
		node.atnState = left;
		return new Handle(left, right);
	}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
public Handle elemList(List<Handle> els) {
	int n = els.size();
	for (int i = 0; i < n - 1; i++) {	// hook up elements (visit all but last)
		Handle el = els.get(i);
		// if el is of form o-x->o for x in {rule, action, pred, token, ...}
		// and not last in alt
           Transition tr = null;
           if ( el.left.getNumberOfTransitions()==1 ) tr = el.left.transition(0);
           boolean isRuleTrans = tr instanceof RuleTransition;
           if ( el.left.getStateType() == ATNState.BASIC &&
			el.right.getStateType()== ATNState.BASIC &&
			tr!=null && (isRuleTrans && ((RuleTransition)tr).followState == el.right || tr.target == el.right) )
		{
			// we can avoid epsilon edge to next el
			if ( isRuleTrans ) ((RuleTransition)tr).followState = els.get(i+1).left;
               else tr.target = els.get(i+1).left;
			atn.removeState(el.right); // we skipped over this state
		}
		else { // need epsilon if previous block's right end node is complicated
			epsilon(el.right, els.get(i+1).left);
		}
	}
	Handle first = els.get(0);
	Handle last = els.get(n -1);
	if ( first==null || last==null ) {
		g.tool.errMgr.toolError(ErrorType.INTERNAL_ERROR, "element list has first|last == null");
	}
	return new Handle(first.left, last.right);
}
 

import org.antlr.v4.runtime.atn.ATNState; //导入依赖的package包/类
/**
 * From {@code (A)?} build either:
 *
 * <pre>
 *  o--A-&gt;o
 *  |     ^
 *  o----&gt;|
 * </pre>
 *
 * or, if {@code A} is a block, just add an empty alt to the end of the
 * block
 */

@Override
public Handle optional(GrammarAST optAST, Handle blk) {
	BlockStartState blkStart = (BlockStartState)blk.left;
	ATNState blkEnd = blk.right;
	preventEpsilonOptionalBlocks.add(new Triple<Rule, ATNState, ATNState>(currentRule, blkStart, blkEnd));

	boolean greedy = ((QuantifierAST)optAST).isGreedy();
	blkStart.nonGreedy = !greedy;
	epsilon(blkStart, blk.right, !greedy);

	optAST.atnState = blk.left;
	return blk;
}