org.antlr.v4.analysis

Class LeftRecursionDetector

java.lang.Object

org.antlr.v4.analysis.LeftRecursionDetector

public class LeftRecursionDetector
extends java.lang.Object

Field Summary

Fields

Modifier and Type	Field and Description
ATN	atn
(package private) Grammar	g
java.util.List<java.util.Set<Rule>>	listOfRecursiveCycles Holds a list of cycles (sets of rule names).
(package private) java.util.Set<RuleStartState>	rulesVisitedPerRuleCheck Which rule start states have we visited while looking for a single left-recursion check?

Constructor Summary

Constructors

Constructor and Description
LeftRecursionDetector(Grammar g, ATN atn)

Method Summary

Modifier and Type	Method and Description
protected void	addRulesToCycle(Rule enclosingRule, Rule targetRule) enclosingRule calls targetRule.
void	check()
boolean	check(Rule enclosingRule, ATNState s, java.util.Set<ATNState> visitedStates) From state s, look for any transition to a rule that is currently being traced.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

g

Grammar g

atn

public ATN atn

listOfRecursiveCycles

public java.util.List<java.util.Set<Rule>> listOfRecursiveCycles

Holds a list of cycles (sets of rule names).

rulesVisitedPerRuleCheck

java.util.Set<RuleStartState> rulesVisitedPerRuleCheck

Which rule start states have we visited while looking for a single left-recursion check?

Constructor Detail

LeftRecursionDetector

public LeftRecursionDetector(Grammar g,
                             ATN atn)

Method Detail

check

public void check()

check

public boolean check(Rule enclosingRule,
                     ATNState s,
                     java.util.Set<ATNState> visitedStates)

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.

addRulesToCycle

protected void addRulesToCycle(Rule enclosingRule,
                               Rule targetRule)

enclosingRule calls targetRule. Find the cycle containing the target and add the caller. Find the cycle containing the caller and add the target. If no cycles contain either, then create a new cycle.