|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.antlr.analysis.DecisionProbe
public class DecisionProbe
Collection of information about what is wrong with a decision as discovered while building the DFA predictor. The information is collected during NFA->DFA conversion and, while some of this is available elsewhere, it is nice to have it all tracked in one spot so a great error message can be easily had. I also like the fact that this object tracks it all for later perusing to make an excellent error message instead of lots of imprecise on-the-fly warnings (during conversion). A decision normally only has one problem; e.g., some input sequence can be matched by multiple alternatives. Unfortunately, some decisions such as a : ( A | B ) | ( A | B ) | A ; have multiple problems. So in general, you should approach a decision as having multiple flaws each one uniquely identified by a DFAState. For example, statesWithSyntacticallyAmbiguousAltsSet tracks the set of all DFAStates where ANTLR has discovered a problem. Recall that a decision is represented internall with a DFA comprised of multiple states, each of which could potentially have problems. Because of this, you need to iterate over this list of DFA states. You'll note that most of the informational methods like getSampleNonDeterministicInputSequence() require a DFAState. This state will be one of the iterated states from stateToSyntacticallyAmbiguousAltsSet. This class is not thread safe due to shared use of visited maps etc... Only one thread should really need to access one DecisionProbe anyway.
Field Summary | |
---|---|
protected java.util.Set<java.lang.Integer> |
altsWithProblem
The overall list of alts within the decision that have at least one conflicting input sequence. |
protected java.util.Set<DFAState> |
danglingStates
The set of states w/o emanating edges and w/o resolving sem preds. |
DFA |
dfa
|
protected boolean |
nonLLStarDecision
If decision with > 1 alt has recursion in > 1 alt, it's nonregular lookahead. |
static java.lang.Integer |
REACHABLE_BUSY
|
static java.lang.Integer |
REACHABLE_NO
|
static java.lang.Integer |
REACHABLE_YES
|
protected java.util.Map<java.lang.Integer,java.lang.Integer> |
stateReachable
Used to find paths through syntactically ambiguous DFA. |
protected java.util.Set<DFAState> |
statesResolvedWithSemanticPredicatesSet
Was a syntactic ambiguity resolved with predicates? Any DFA state that predicts more than one alternative, must be resolved with predicates or it should be reported to the user. |
protected java.util.Set<java.lang.String> |
statesVisitedAtInputDepth
Used while finding a path through an NFA whose edge labels match an input sequence. |
protected java.util.Set<java.lang.Integer> |
statesVisitedDuringSampleSequence
|
protected java.util.Set<DFAState> |
statesWithSyntacticallyAmbiguousAltsSet
Track all DFA states with nondeterministic alternatives. |
protected java.util.Map<DFAState,java.util.Map<java.lang.Integer,SemanticContext>> |
stateToAltSetWithSemanticPredicatesMap
Track the predicates for each alt per DFA state; more than one DFA state might have syntactically ambig alt prediction. |
protected java.util.Map<DFAState,java.util.Map<java.lang.Integer,java.util.Set<antlr.Token>>> |
stateToIncompletelyCoveredAltsMap
Tracks alts insufficiently covered. |
protected MultiMap<java.lang.Integer,NFAConfiguration> |
stateToRecursionOverflowConfigurationsMap
Recursion is limited to a particular depth. |
protected java.util.Map<DFAState,java.util.Set<java.lang.Integer>> |
stateToSyntacticallyAmbiguousTokensRuleAltsMap
Track just like stateToSyntacticallyAmbiguousAltsMap, but only for nondeterminisms that arise in the Tokens rule such as keyword vs ID rule. |
protected boolean |
timedOut
Did ANTLR have to terminate early on the analysis of this decision? |
static boolean |
verbose
|
Constructor Summary | |
---|---|
DecisionProbe(DFA dfa)
|
Method Summary | |
---|---|
boolean |
analysisOverflowed()
Took too long to analyze a DFA |
boolean |
analysisTimedOut()
Did the analysis complete it's work? |
java.util.Set |
getDanglingStates()
return set of states w/o emanating edges and w/o resolving sem preds. |
java.lang.String |
getDescription()
Return a string like "3:22: ( A {;} | B )" that describes this decision. |
protected java.util.Set |
getDFAPathStatesToTarget(DFAState targetState)
|
java.util.Set |
getDFAStatesWithSyntacticallyAmbiguousAlts()
Return all DFA states in this DFA that have NFA configurations that conflict. |
java.util.Set |
getDisabledAlternatives(DFAState d)
Which alts were specifically turned off to resolve nondeterminisms? This is different than the unreachable alts. |
java.util.Map<java.lang.Integer,java.util.Set<antlr.Token>> |
getIncompletelyCoveredAlts(DFAState d)
Return a list of alts whose predicate context was insufficient to resolve a nondeterminism for state d. |
java.lang.String |
getInputSequenceDisplay(java.util.List labels)
Given List |
protected boolean |
getNFAPath(NFAState s,
int labelIndex,
java.util.List labels,
java.util.List path)
Given a sample input sequence, you usually would like to know the path taken through the NFA. |
java.util.List |
getNFAPathStatesForAlt(int firstAlt,
int alt,
java.util.List labels)
Given an alternative associated with a nondeterministic DFA state, find the path of NFA states associated with the labels sequence. |
java.util.Set |
getNonDeterministicAlts()
|
java.util.List |
getNonDeterministicAltsForState(DFAState targetState)
Return the sorted list of alts that conflict within a single state. |
java.util.Set |
getNondeterministicStatesResolvedWithSemanticPredicate()
|
int |
getNumberOfStates()
How many states does the DFA predictor have? |
protected void |
getSampleInputSequenceUsingStateSet(State startState,
State targetState,
java.util.Set states,
java.util.List<Label> labels)
Given a start state and a final state, find a list of edge labels between the two ignoring epsilon. |
java.util.List<Label> |
getSampleNonDeterministicInputSequence(DFAState targetState)
Return a List |
SemanticContext |
getSemanticContextForAlt(DFAState d,
int alt)
Each state in the DFA represents a different input sequence for an alt of the decision. |
protected java.lang.String |
getStateLabelIndexKey(int s,
int i)
|
java.lang.String |
getTokenNameForTokensRuleAlt(int alt)
From an alt number associated with artificial Tokens rule, return the name of the token that is associated with that alt. |
java.util.List<java.lang.Integer> |
getUnreachableAlts()
Get a list of all unreachable alternatives for this decision. |
boolean |
hasPredicate()
At least one alt refs a sem or syn pred |
boolean |
isCyclic()
|
boolean |
isDeterministic()
If no states are dead-ends, no alts are unreachable, there are no nondeterminisms unresolved by syn preds, all is ok with decision. |
boolean |
isNonLLStarDecision()
Found recursion in > 1 alt |
boolean |
isReduced()
|
protected void |
issueRecursionWarnings()
|
void |
issueWarnings()
|
protected boolean |
reachesState(DFAState startState,
DFAState targetState,
java.util.Set states)
Given a start state and a target state, return true if start can reach target state. |
void |
removeRecursiveOverflowState(DFAState d)
If a recursion overflow is resolve with predicates, then we need to shut off the warning that would be generated. |
void |
reportAltPredicateContext(DFAState d,
java.util.Map altPredicateContext)
Report the list of predicates found for each alternative; copy the list because this set gets altered later by the method tryToResolveWithSemanticPredicates() while flagging NFA configurations in d as resolved. |
void |
reportAnalysisTimeout()
|
void |
reportDanglingState(DFAState d)
Report the fact that DFA state d is not a state resolved with predicates and yet it has no emanating edges. |
void |
reportIncompletelyCoveredAlts(DFAState d,
java.util.Map<java.lang.Integer,java.util.Set<antlr.Token>> altToLocationsReachableWithoutPredicate)
|
void |
reportLexerRuleNondeterminism(DFAState d,
java.util.Set<java.lang.Integer> nondeterministicAlts)
Currently the analysis reports issues between token definitions, but we don't print out warnings in favor of just picking the first token definition found in the grammar ala lex/flex. |
void |
reportNondeterminism(DFAState d,
java.util.Set<java.lang.Integer> nondeterministicAlts)
|
void |
reportNondeterminismResolvedWithSemanticPredicate(DFAState d)
|
void |
reportNonLLStarDecision(DFA dfa)
Report that at least 2 alts have recursive constructs. |
void |
reportRecursionOverflow(DFAState d,
NFAConfiguration recursionNFAConfiguration)
|
void |
reset()
|
protected void |
stripWildCardAlts(java.util.Set disabledAlts)
Get the last disabled alt number and check in the grammar to see if that alt is a simple wildcard. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
public DFA dfa
protected java.util.Set<DFAState> statesWithSyntacticallyAmbiguousAltsSet
protected java.util.Map<DFAState,java.util.Set<java.lang.Integer>> stateToSyntacticallyAmbiguousTokensRuleAltsMap
protected java.util.Set<DFAState> statesResolvedWithSemanticPredicatesSet
protected java.util.Map<DFAState,java.util.Map<java.lang.Integer,SemanticContext>> stateToAltSetWithSemanticPredicatesMap
protected java.util.Map<DFAState,java.util.Map<java.lang.Integer,java.util.Set<antlr.Token>>> stateToIncompletelyCoveredAltsMap
protected java.util.Set<DFAState> danglingStates
protected java.util.Set<java.lang.Integer> altsWithProblem
protected boolean nonLLStarDecision
protected MultiMap<java.lang.Integer,NFAConfiguration> stateToRecursionOverflowConfigurationsMap
protected boolean timedOut
protected java.util.Map<java.lang.Integer,java.lang.Integer> stateReachable
public static final java.lang.Integer REACHABLE_BUSY
public static final java.lang.Integer REACHABLE_NO
public static final java.lang.Integer REACHABLE_YES
protected java.util.Set<java.lang.String> statesVisitedAtInputDepth
protected java.util.Set<java.lang.Integer> statesVisitedDuringSampleSequence
public static boolean verbose
Constructor Detail |
---|
public DecisionProbe(DFA dfa)
Method Detail |
---|
public java.lang.String getDescription()
public boolean isReduced()
public boolean isCyclic()
public boolean isDeterministic()
public boolean analysisTimedOut()
public boolean analysisOverflowed()
public boolean isNonLLStarDecision()
public int getNumberOfStates()
public java.util.List<java.lang.Integer> getUnreachableAlts()
public java.util.Set getDanglingStates()
public java.util.Set getNonDeterministicAlts()
public java.util.List getNonDeterministicAltsForState(DFAState targetState)
public java.util.Set getDFAStatesWithSyntacticallyAmbiguousAlts()
public java.util.Set getDisabledAlternatives(DFAState d)
public void removeRecursiveOverflowState(DFAState d)
public java.util.List<Label> getSampleNonDeterministicInputSequence(DFAState targetState)
public java.lang.String getInputSequenceDisplay(java.util.List labels)
public java.util.List getNFAPathStatesForAlt(int firstAlt, int alt, java.util.List labels)
public SemanticContext getSemanticContextForAlt(DFAState d, int alt)
public boolean hasPredicate()
public java.util.Set getNondeterministicStatesResolvedWithSemanticPredicate()
public java.util.Map<java.lang.Integer,java.util.Set<antlr.Token>> getIncompletelyCoveredAlts(DFAState d)
public void issueWarnings()
protected void stripWildCardAlts(java.util.Set disabledAlts)
protected void issueRecursionWarnings()
public void reportDanglingState(DFAState d)
public void reportAnalysisTimeout()
public void reportNonLLStarDecision(DFA dfa)
public void reportRecursionOverflow(DFAState d, NFAConfiguration recursionNFAConfiguration)
public void reportNondeterminism(DFAState d, java.util.Set<java.lang.Integer> nondeterministicAlts)
public void reportLexerRuleNondeterminism(DFAState d, java.util.Set<java.lang.Integer> nondeterministicAlts)
public void reportNondeterminismResolvedWithSemanticPredicate(DFAState d)
public void reportAltPredicateContext(DFAState d, java.util.Map altPredicateContext)
public void reportIncompletelyCoveredAlts(DFAState d, java.util.Map<java.lang.Integer,java.util.Set<antlr.Token>> altToLocationsReachableWithoutPredicate)
protected boolean reachesState(DFAState startState, DFAState targetState, java.util.Set states)
protected java.util.Set getDFAPathStatesToTarget(DFAState targetState)
protected void getSampleInputSequenceUsingStateSet(State startState, State targetState, java.util.Set states, java.util.List<Label> labels)
protected boolean getNFAPath(NFAState s, int labelIndex, java.util.List labels, java.util.List path)
protected java.lang.String getStateLabelIndexKey(int s, int i)
public java.lang.String getTokenNameForTokensRuleAlt(int alt)
public void reset()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |