java类org.antlr.v4.runtime.atn.ATNState的实例源码

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

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

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);
    }

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

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);
}

@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);
    }
}

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());
}

@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);
    }
}

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);
}

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

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

@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);
                }
            }
        }
    }
}

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

@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);
}

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

@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);
}

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);
    }
}

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

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

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);
}

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

/**
 * From {@code (blk)+} build
 *
 * <pre>
 *   |---------|
 *   v         |
 *  [o-blk-o]-&gt;o-&gt;o
 * </pre>
 *
 * We add a decision for loop back node to the existing one at {@code blk}
 * start.
 */

@Override
public Handle plus(GrammarAST plusAST, Handle blk) {
    PlusBlockStartState blkStart = (PlusBlockStartState)blk.left;
    BlockEndState blkEnd = (BlockEndState)blk.right;
    preventEpsilonClosureBlocks.add(new Triple<Rule, ATNState, ATNState>(currentRule, blkStart, blkEnd));

    PlusLoopbackState loop = newState(PlusLoopbackState.class, plusAST);
    loop.nonGreedy = !((QuantifierAST)plusAST).isGreedy();
    atn.defineDecisionState(loop);
    LoopEndState end = newState(LoopEndState.class, plusAST);
    blkStart.loopBackState = loop;
    end.loopBackState = loop;

    plusAST.atnState = loop;
    epsilon(blkEnd, loop);      // blk can see loop back

    BlockAST blkAST = (BlockAST)plusAST.getChild(0);
    if ( ((QuantifierAST)plusAST).isGreedy() ) {
        if (expectNonGreedy(blkAST)) {
            g.tool.errMgr.grammarError(ErrorType.EXPECTED_NON_GREEDY_WILDCARD_BLOCK, g.fileName, plusAST.getToken(), plusAST.getToken().getText());
        }

        epsilon(loop, blkStart);    // loop back to start
        epsilon(loop, end);         // or exit
    }
    else {
        // if not greedy, priority to exit branch; make it first
        epsilon(loop, end);         // exit
        epsilon(loop, blkStart);    // loop back to start
    }

    return new Handle(blkStart, end);
}

/**
 * From {@code (blk)*} build {@code ( blk+ )?} with *two* decisions, one for
 * entry and one for choosing alts of {@code blk}.
 *
 * <pre>
 *   |-------------|
 *   v             |
 *   o--[o-blk-o]-&gt;o  o
 *   |                ^
 *   -----------------|
 * </pre>
 *
 * Note that the optional bypass must jump outside the loop as
 * {@code (A|B)*} is not the same thing as {@code (A|B|)+}.
 */

@Override
public Handle star(GrammarAST starAST, Handle elem) {
    StarBlockStartState blkStart = (StarBlockStartState)elem.left;
    BlockEndState blkEnd = (BlockEndState)elem.right;
    preventEpsilonClosureBlocks.add(new Triple<Rule, ATNState, ATNState>(currentRule, blkStart, blkEnd));

    StarLoopEntryState entry = newState(StarLoopEntryState.class, starAST);
    entry.nonGreedy = !((QuantifierAST)starAST).isGreedy();
    atn.defineDecisionState(entry);
    LoopEndState end = newState(LoopEndState.class, starAST);
    StarLoopbackState loop = newState(StarLoopbackState.class, starAST);
    entry.loopBackState = loop;
    end.loopBackState = loop;

    BlockAST blkAST = (BlockAST)starAST.getChild(0);
    if ( ((QuantifierAST)starAST).isGreedy() ) {
        if (expectNonGreedy(blkAST)) {
            g.tool.errMgr.grammarError(ErrorType.EXPECTED_NON_GREEDY_WILDCARD_BLOCK, g.fileName, starAST.getToken(), starAST.getToken().getText());
        }

        epsilon(entry, blkStart);   // loop enter edge (alt 1)
        epsilon(entry, end);        // bypass loop edge (alt 2)
    }
    else {
        // if not greedy, priority to exit branch; make it first
        epsilon(entry, end);        // bypass loop edge (alt 1)
        epsilon(entry, blkStart);   // loop enter edge (alt 2)
    }
    epsilon(blkEnd, loop);      // block end hits loop back
    epsilon(loop, entry);       // loop back to entry/exit decision

    starAST.atnState = entry;   // decision is to enter/exit; blk is its own decision
    return new Handle(entry, end);
}

/** Build an atom with all possible values in its label. */

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

public void addRuleFollowLinks() {
    for (ATNState p : atn.states) {
        if ( p!=null &&
             p.getStateType() == ATNState.BASIC && p.getNumberOfTransitions()==1 &&
             p.transition(0) instanceof RuleTransition )
        {
            RuleTransition rt = (RuleTransition) p.transition(0);
            addFollowLink(rt.ruleIndex, rt.followState);
        }
    }
}

/** Add an EOF transition to any rule end ATNState that points to nothing
    *  (i.e., for all those rules not invoked by another rule).  These
    *  are start symbols then.
 *
 *  Return the number of grammar entry points; i.e., how many rules are
 *  not invoked by another rule (they can only be invoked from outside).
 *  These are the start rules.
    */
public int addEOFTransitionToStartRules() {
    int n = 0;
    ATNState eofTarget = newState(null); // one unique EOF target for all rules
    for (Rule r : g.rules.values()) {
        ATNState stop = atn.ruleToStopState[r.index];
        if ( stop.getNumberOfTransitions()>0 ) continue;
        n++;
        Transition t = new AtomTransition(eofTarget, Token.EOF);
        stop.addTransition(t);
    }
    return n;
}

public void check() {
    for (RuleStartState start : atn.ruleToStartState) {
        //System.out.print("check "+start.rule.name);
        rulesVisitedPerRuleCheck.clear();
        rulesVisitedPerRuleCheck.add(start);
        //FASerializer ser = new FASerializer(atn.g, start);
        //System.out.print(":\n"+ser+"\n");

        check(g.getRule(start.ruleIndex), start, new HashSet<ATNState>());
    }
    //System.out.println("cycles="+listOfRecursiveCycles);
    if ( !listOfRecursiveCycles.isEmpty() ) {
        g.tool.errMgr.leftRecursionCycles(g.fileName, listOfRecursiveCycles);
    }
}

/** From state s, look for any transition to a rule that is currently
 *  being traced.  When tracing r, visitedPerRuleCheck has r
 *  initially.  If you reach a rule stop state, return but notify the
 *  invoking rule that the called rule is nullable. This implies that
 *  invoking rule must look at follow transition for that invoking state.
 *
 *  The visitedStates tracks visited states within a single rule so
 *  we can avoid epsilon-loop-induced infinite recursion here.  Keep
 *  filling the cycles in listOfRecursiveCycles and also, as a
 *  side-effect, set leftRecursiveRules.
 */
public boolean check(Rule enclosingRule, ATNState s, Set<ATNState> visitedStates) {
    if ( s instanceof RuleStopState) return true;
    if ( visitedStates.contains(s) ) return false;
    visitedStates.add(s);

    //System.out.println("visit "+s);
    int n = s.getNumberOfTransitions();
    boolean stateReachesStopState = false;
    for (int i=0; i<n; i++) {
        Transition t = s.transition(i);
        if ( t instanceof RuleTransition ) {
            RuleTransition rt = (RuleTransition) t;
            Rule r = g.getRule(rt.ruleIndex);
            if ( rulesVisitedPerRuleCheck.contains((RuleStartState)t.target) ) {
                addRulesToCycle(enclosingRule, r);
            }
            else {
                // must visit if not already visited; mark target, pop when done
                rulesVisitedPerRuleCheck.add((RuleStartState)t.target);
                // send new visitedStates set per rule invocation
                boolean nullable = check(r, t.target, new HashSet<ATNState>());
                // we're back from visiting that rule
                rulesVisitedPerRuleCheck.remove((RuleStartState)t.target);
                if ( nullable ) {
                    stateReachesStopState |= check(enclosingRule, rt.followState, visitedStates);
                }
            }
        }
        else if ( t.isEpsilon() ) {
            stateReachesStopState |= check(enclosingRule, t.target, visitedStates);
        }
        // else ignore non-epsilon transitions
    }
    return stateReachesStopState;
}

private static Transition createSetTransition(ATNState target, IntervalSet set) {
    if (set.getIntervals().size() == 1) {
        Interval interval = set.getIntervals().get(0);
        if (interval.a == interval.b) {
            return new AtomTransition(target, interval.a);
        } else {
            return new RangeTransition(target, interval.a, interval.b);
        }
    } else {
        return new SetTransition(target, set);
    }
}

private static Transition createSetTransition(ATNState target, IntervalSet set) {
    if (set.getIntervals().size() == 1) {
        Interval interval = set.getIntervals().get(0);
        if (interval.a == interval.b) {
            return new AtomTransition(target, interval.a);
        } else {
            return new RangeTransition(target, interval.a, interval.b);
        }
    } else {
        return new SetTransition(target, set);
    }
}