|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.antlr.analysis.State
org.antlr.analysis.DFAState
public class DFAState
A DFA state represents a set of possible NFA configurations. As Aho, Sethi, Ullman p. 117 says "The DFA uses its state to keep track of all possible states the NFA can be in after reading each input symbol. That is to say, after reading input a1a2..an, the DFA is in a state that represents the subset T of the states of the NFA that are reachable from the NFA's start state along some path labeled a1a2..an." In conventional NFA->DFA conversion, therefore, the subset T would be a bitset representing the set of states the NFA could be in. We need to track the alt predicted by each state as well, however. More importantly, we need to maintain a stack of states, tracking the closure operations as they jump from rule to rule, emulating rule invocations (method calls). Recall that NFAs do not normally have a stack like a pushdown-machine so I have to add one to simulate the proper lookahead sequences for the underlying LL grammar from which the NFA was derived. I use a list of NFAConfiguration objects. An NFAConfiguration is both a state (ala normal conversion) and an NFAContext describing the chain of rules (if any) followed to arrive at that state. There is also the semantic context, which is the "set" of predicates found on the path to this configuration. A DFA state may have multiple references to a particular state, but with different NFAContexts (with same or different alts) meaning that state was reached via a different set of rule invocations.
Field Summary | |
---|---|
protected boolean |
abortedDueToMultipleRecursiveAlts
If we detect recursion on more than one alt, decision is non-LL(*), but try to isolate it to only those states whose closure operations detect recursion. |
protected boolean |
abortedDueToRecursionOverflow
If a closure operation finds that we tried to invoke the same rule too many times (stack would grow beyond a threshold), it marks the state has aborted and notifies the DecisionProbe. |
protected int |
acceptStateReachable
The NFA->DFA algorithm may terminate leaving some states without a path to an accept state, implying that upon certain input, the decision is not deterministic--no decision about predicting a unique alternative can be made. |
protected int |
cachedHashCode
Build up the hash code for this state as NFA configurations are added as it's monotonically increasing list of configurations. |
protected int |
cachedUniquelyPredicatedAlt
|
protected java.util.Set |
closureBusy
Used to prevent the closure operation from looping to itself and hence looping forever. |
DFA |
dfa
We are part of what DFA? Use this ref to get access to the context trees for an alt. |
static int |
INITIAL_NUM_TRANSITIONS
|
protected int |
k
When doing an acyclic DFA, this is the number of lookahead symbols consumed to reach this state. |
protected java.util.Set |
nfaConfigurations
The set of NFA configurations (state,alt,context) for this DFA state |
static int |
PREDICTED_ALT_UNSET
|
protected OrderedHashSet |
reachableLabels
As this state is constructed (i.e., as NFA states are added), we can easily check for non-epsilon transitions because the only transition that could be a valid label is transition(0). |
protected boolean |
resolvedWithPredicates
Rather than recheck every NFA configuration in a DFA state (after resolving) in findNewDFAStatesAndAddDFATransitions just check this boolean. |
protected java.util.List |
transitions
Track the transitions emanating from this DFA state. |
Fields inherited from class org.antlr.analysis.State |
---|
acceptState, INVALID_STATE_NUMBER, stateNumber |
Constructor Summary | |
---|---|
DFAState(DFA dfa)
|
Method Summary | |
---|---|
void |
addNFAConfiguration(NFAState state,
int alt,
NFAContext context,
SemanticContext semanticContext)
|
void |
addNFAConfiguration(NFAState state,
NFAConfiguration c)
Add an NFA configuration to this DFA node. |
protected void |
addReachableLabel(Label label)
Add label uniquely and disjointly; intersection with another set or int/char forces breaking up the set(s). |
int |
addTransition(DFAState target,
Label label)
Add a transition from this state to target with label. |
void |
addTransition(Transition t)
|
boolean |
equals(java.lang.Object o)
Two DFAStates are equal if their NFA configuration sets are the same. |
int |
getAcceptStateReachable()
Is an accept state reachable from this state? |
java.util.Set |
getAltSet()
Get the set of all alts mentioned by all NFA configurations in this DFA state. |
protected java.util.Set |
getConflictingAlts()
Walk each NFA configuration in this DFA state looking for a conflict where (s|i|ctx) and (s|j|ctx) exist, indicating that state s with context conflicting ctx predicts alts i and j. |
java.util.Set |
getDisabledAlternatives()
When more than one alternative can match the same input, the first alternative is chosen to resolve the conflict. |
SemanticContext |
getGatedPredicatesInNFAConfigurations()
For gated productions, we need an OR'd list of all predicates for the target of an edge so we can gate the edge based upon the predicates associated with taking that path (if any). |
int |
getLookaheadDepth()
|
java.util.Set |
getNFAConfigurations()
|
java.util.Set |
getNFAStatesForAlt(int alt)
Get the set of all states mentioned by all NFA configurations in this DFA state associated with alt. |
protected java.util.Set |
getNonDeterministicAlts()
public int getNumberOfEOTNFAStates() { int n = 0; Iterator iter = nfaConfigurations.iterator(); NFAConfiguration configuration; while (iter.hasNext()) { configuration = (NFAConfiguration) iter.next(); NFAState s = dfa.nfa.getState(configuration.state); if ( s.isEOTState() ) { n++; } } return n; } |
int |
getNumberOfTransitions()
|
OrderedHashSet |
getReachableLabels()
|
java.util.Set |
getSyntacticPredicatesInNFAConfigurations()
For gated productions, we need a list of all predicates for the target of an edge so we can gate the edge based upon the predicates associated with taking that path (if any). |
Transition |
getTransition(int trans)
|
int |
getUniqueAlt()
Return the uniquely mentioned alt from the NFA configurations; Ignore the resolved bit etc... |
int |
getUniquelyPredictedAlt()
Walk each configuration and if they are all the same alt, return that alt else return NFA.INVALID_ALT_NUMBER. |
int |
hashCode()
A decent hash for a DFA state is the sum of the NFA state/alt pairs. |
boolean |
isResolvedWithPredicates()
|
void |
removeTransition(int trans)
|
void |
setAcceptStateReachable(int acceptStateReachable)
|
void |
setLookaheadDepth(int k)
|
void |
setNFAConfigurations(java.util.Set configs)
|
java.lang.String |
toString()
Print all NFA states plus what alts they predict |
Transition |
transition(int i)
|
Methods inherited from class org.antlr.analysis.State |
---|
isAcceptState, setAcceptState |
Methods inherited from class java.lang.Object |
---|
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public static final int INITIAL_NUM_TRANSITIONS
public static final int PREDICTED_ALT_UNSET
public DFA dfa
protected java.util.List transitions
protected int k
protected int acceptStateReachable
protected boolean resolvedWithPredicates
protected boolean abortedDueToRecursionOverflow
protected boolean abortedDueToMultipleRecursiveAlts
protected int cachedHashCode
protected int cachedUniquelyPredicatedAlt
protected java.util.Set nfaConfigurations
protected java.util.Set closureBusy
protected OrderedHashSet reachableLabels
Constructor Detail |
---|
public DFAState(DFA dfa)
Method Detail |
---|
public Transition transition(int i)
transition
in class State
public int getNumberOfTransitions()
getNumberOfTransitions
in class State
public void addTransition(Transition t)
addTransition
in class State
public int addTransition(DFAState target, Label label)
public Transition getTransition(int trans)
public void removeTransition(int trans)
public void addNFAConfiguration(NFAState state, NFAConfiguration c)
public void addNFAConfiguration(NFAState state, int alt, NFAContext context, SemanticContext semanticContext)
protected void addReachableLabel(Label label)
public OrderedHashSet getReachableLabels()
public java.util.Set getNFAConfigurations()
public void setNFAConfigurations(java.util.Set configs)
public int hashCode()
hashCode
in class java.lang.Object
public boolean equals(java.lang.Object o)
equals
in class java.lang.Object
public int getUniquelyPredictedAlt()
public int getUniqueAlt()
public java.util.Set getDisabledAlternatives()
protected java.util.Set getNonDeterministicAlts()
protected java.util.Set getConflictingAlts()
public java.util.Set getAltSet()
public java.util.Set getNFAStatesForAlt(int alt)
public java.util.Set getSyntacticPredicatesInNFAConfigurations()
public SemanticContext getGatedPredicatesInNFAConfigurations()
public int getAcceptStateReachable()
public void setAcceptStateReachable(int acceptStateReachable)
public boolean isResolvedWithPredicates()
public java.lang.String toString()
toString
in class java.lang.Object
public int getLookaheadDepth()
public void setLookaheadDepth(int k)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |