LeftRecursionDetector.java 文件源码

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