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.
stateToAltSetWithSemanticPredicatesMap Track the predicates for each alt per DFA state;
more than one DFA state might have syntactically ambig alt prediction.
stateToIncompletelyCoveredAltsMap Map> Tracks alts insufficiently covered.
For example, p1||true gets reduced to true and so leaves
whole alt uncovered.
stateToSyntacticallyAmbiguousTokensRuleAltsMap Track just like stateToSyntacticallyAmbiguousAltsMap, but only
for nondeterminisms that arise in the Tokens rule such as keyword vs
ID rule.
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.
statesWithSyntacticallyAmbiguousAltsSet Track all DFA states with nondeterministic alternatives.
By reaching the same DFA state, a path through the NFA for some input
is able to reach the same NFA state by starting at more than one
alternative's left edge.
getNFAPath(NFAState s, int labelIndex, List labels, List path) Given a sample input sequence, you usually would like to know the
path taken through the NFA.
getNFAPathStatesForAlt(int firstAlt, int alt, List labels) Given an alternative associated with a nondeterministic DFA state,
find the path of NFA states associated with the labels sequence.
Useful tracing where in the NFA, a single input sequence can be
matched.
getTokenNameForTokensRuleAlt(int alt) From an alt number associated with artificial Tokens rule, return
the name of the token that is associated with that alt.
reachesState(DFAState startState, DFAState targetState, Set states) Given a start state and a target state, return true if start can reach
target state.
public void
removeRecursiveOverflowState(DFAState d) If a recursion overflow is resolve with predicates, then we need
to shut off the warning that would be generated.
public void
reportAltPredicateContext(DFAState d, 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.
public 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.
reportLexerRuleNondeterminism(DFAState d, Set 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.
If decision with > 1 alt has recursion in > 1 alt, it's nonregular
lookahead. The decision cannot be made with a DFA.
the alts are stored in altsWithProblem.
Track the predicates for each alt per DFA state;
more than one DFA state might have syntactically ambig alt prediction.
This is Map>; that is, it
maps DFA state to another map, mapping alt number to a
SemanticContext (pred(s) to execute to resolve syntactic ambiguity).
Map> Tracks alts insufficiently covered.
For example, p1||true gets reduced to true and so leaves
whole alt uncovered. This maps DFA state to the set of alts
Recursion is limited to a particular depth. If that limit is exceeded
the proposed new NFAConfiguration is recorded for the associated DFA state.
Map>.
Track just like stateToSyntacticallyAmbiguousAltsMap, but only
for nondeterminisms that arise in the Tokens rule such as keyword vs
ID rule. The state maps to the list of Tokens rule alts that are
in conflict.
Map>
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.
Set
Used while finding a path through an NFA whose edge labels match
an input sequence. Tracks the input position
we were at the last time at this node. If same input position, then
we'd have reached same state without consuming input...probably an
infinite loop. Stop. Set. The strings look like
stateNumber_labelIndex.
Track all DFA states with nondeterministic alternatives.
By reaching the same DFA state, a path through the NFA for some input
is able to reach the same NFA state by starting at more than one
alternative's left edge. Though, later, we may find that predicates
resolve the issue, but track info anyway.
Set. Note that from the DFA state, you can ask for
which alts are nondeterministic.
Return all DFA states in this DFA that have NFA configurations that
conflict. You must report a problem for each state in this set
because each state represents a different input sequence.
return set of states w/o emanating edges and w/o resolving sem preds.
These states come about because the analysis algorithm had to
terminate early to avoid infinite recursion for example (due to
left recursion perhaps).
Which alts were specifically turned off to resolve nondeterminisms?
This is different than the unreachable alts. Disabled doesn't mean that
the alternative is totally unreachable necessarily, it just means
that for this DFA state, that alt is disabled. There may be other
accept states for that alt that make an alt reachable.
Given a sample input sequence, you usually would like to know the
path taken through the NFA. Return the list of NFA states visited
while matching a list of labels. This cannot use the usual
interpreter, which does a deterministic walk. We need to be able to
take paths that are turned off during nondeterminism resolution. So,
just do a depth-first walk traversing edges labeled with the current
label. Return true if a path was found emanating from state s.
getNFAPathStatesForAlt
publicList getNFAPathStatesForAlt(int firstAlt, int alt, List labels)(Code)
Given an alternative associated with a nondeterministic DFA state,
find the path of NFA states associated with the labels sequence.
Useful tracing where in the NFA, a single input sequence can be
matched. For different alts, you should get different NFA paths.
The first NFA state for all NFA paths will be the same: the starting
NFA state of the first nondeterministic alt. Imagine (A|B|A|A):
5->9-A->o
|
6->10-B->o
|
7->11-A->o
|
8->12-A->o
There are 3 nondeterministic alts. The paths should be:
5 9 ...
5 6 7 11 ...
5 6 7 8 12 ...
The NFA path matching the sample input sequence (labels) is computed
using states 9, 11, and 12 rather than 5, 7, 8 because state 5, for
example can get to all ambig paths. Must isolate for each alt (hence,
the extra state beginning each alt in my NFA structures). Here,
firstAlt=1.
protected void getSampleInputSequenceUsingStateSet(State startState, State targetState, Set states, List labels)(Code)
Given a start state and a final state, find a list of edge labels
between the two ignoring epsilon. Limit your scan to a set of states
passed in. This is used to show a sample input sequence that is
nondeterministic with respect to this decision. Return List
Each state in the DFA represents a different input sequence for an
alt of the decision. Given a DFA state, what is the semantic
predicate context for a particular alt.
getStateLabelIndexKey
protectedString getStateLabelIndexKey(int s, int i)(Code)
Get a list of all unreachable alternatives for this decision. There
may be multiple alternatives with ambiguous input sequences, but this
is the overall list of unreachable alternatives (either due to
conflict resolution or alts w/o accept states).
Given a start state and a target state, return true if start can reach
target state. Also, compute the set of DFA states
that are on a path from start to target; return in states parameter.
removeRecursiveOverflowState
public void removeRecursiveOverflowState(DFAState d)(Code)
If a recursion overflow is resolve with predicates, then we need
to shut off the warning that would be generated.
reportAltPredicateContext
public void reportAltPredicateContext(DFAState d, Map altPredicateContext)(Code)
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.
Report the fact that DFA state d is not a state resolved with
predicates and yet it has no emanating edges. Usually this
is a result of the closure/reach operations being unable to proceed
public void reportLexerRuleNondeterminism(DFAState d, Set nondeterministicAlts)(Code)
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.
reportNonLLStarDecision
public void reportNonLLStarDecision(DFA dfa)(Code)
Report that at least 2 alts have recursive constructs. There is
no way to build a DFA so we terminated.
reportNondeterminism
public void reportNondeterminism(DFAState d, Set nondeterministicAlts)(Code)
reportNondeterminismResolvedWithSemanticPredicate
public void reportNondeterminismResolvedWithSemanticPredicate(DFAState d)(Code)
Get the last disabled alt number and check in the grammar to see
if that alt is a simple wildcard. If so, treat like an else clause
and don't emit the error. Strip out the last alt if it's wildcard.
