| java.lang.Object
 org.antlr.analysis.DFA
| DFA | | public class DFA (Code) | | A DFA (converted from a grammar's NFA).
DFAs are used as prediction machine for alternative blocks in all kinds
of recognizers (lexers, parsers, tree walkers).
|
| Constructor Summary | |
| public | DFA(int decisionNumber, NFAState decisionStartState)
|
| Method Summary | |
| protected DFAState | addState(DFAState d)
Add a new DFA state to this DFA if not already present.
To force an acyclic, fixed maximum depth DFA, just always
return the incoming state. | | public boolean | analysisAborted()
| | public boolean | canInlineDecision()
| | protected void | createEOTAndEOFTables(DFAState s)
Set up the EOT and EOF tables; we cannot put -1 min/max values so
we need another way to test that in the DFA transition function. | | protected void | createMinMaxTables(DFAState s)
| | protected void | createSpecialTable(DFAState s)
| | public void | createStateTables(CodeGenerator generator)
| | protected void | createTransitionTableEntryForState(DFAState s)
| | protected boolean | doesStateReachAcceptState(DFAState d)
figure out if this state eventually reaches an accept state and
modify the instance variable 'reduced' to indicate if we find
at least one state that cannot reach an accept state. | | public static String | encodeIntAsCharEscape(int v)
| | public DFAState | getAcceptState(int alt)
| | public boolean | getAutoBacktrackMode()
| | public GrammarAST | getDecisionASTNode()
What GrammarAST node (derived from the grammar) is this DFA
associated with? It will point to the start of a block or
the loop back of a (...)+ block etc... | | public int | getDecisionNumber()
| | public String | getDescription()
| | public List | getJavaCompressedAccept()
| | public List | getJavaCompressedEOF()
| | public List | getJavaCompressedEOT()
| | public List | getJavaCompressedMax()
| | public List | getJavaCompressedMin()
| | public List | getJavaCompressedSpecial()
| | public List | getJavaCompressedTransition()
| | public int | getMaxLookaheadDepth()
| | public int | getMaxStateNumber()
What is the max state number ever created? This may be beyond
getNumberOfStates(). | | public NFAState | getNFADecisionStartState()
| | public int | getNumberOfAlts()
| | public int | getNumberOfStates()
| | public List | getRunLengthEncoding(List data)
Compress the incoming data list so that runs of same number are
encoded as number,value pair sequences. | | public DFAState | getState(int stateNumber)
| | public Map | getUniqueStates()
| | public List | getUnreachableAlts()
Return a list of Integer alt numbers for which no lookahead could
be computed or for which no single DFA accept state predicts those
alts. | | public int | getUserMaxLookahead()
The user may specify a max, acyclic lookahead for any decision. | | protected void | initAltRelatedInfo()
| | public boolean | isCyclic()
Is this DFA cyclic? That is, are there any loops? If not, then
the DFA is essentially an LL(k) predictor for some fixed, max k value.
We can build a series of nested IF statements to match this. | | public boolean | isGreedy()
| | public boolean | isReduced()
Is the DFA reduced? I.e., does every state have a path to an accept
state? If not, don't delete as we need to generate an error indicating
which paths are "dead ends". | | public boolean | isTokensRuleDecision()
| | public DFAState | newState()
| | public int | predict(IntStream input)
| | public void | removeState(DFAState d)
| | public void | resetStateNumbersToBeContiguous()
Walk all states and reset their numbers to be a contiguous sequence
of integers starting from 0. | | public void | setAcceptState(int alt, DFAState acceptState)
| | public void | setState(int stateNumber, DFAState d)
| | public void | setUserMaxLookahead(int k)
| | public String | toString()
| | public void | verify()
Once this DFA has been built, need to verify that:
1. |
| MAX_STATES_PER_ALT_IN_DFA | | final public static int MAX_STATES_PER_ALT_IN_DFA(Code) | | Prevent explosion of DFA states during conversion. The max number
of states per alt in a single decision's DFA.
|
| MAX_STATE_TRANSITIONS_FOR_TABLE | | public static int MAX_STATE_TRANSITIONS_FOR_TABLE(Code) | | How many edges can each DFA state have before a "special" state
is created that uses IF expressions instead of a table?
|
| MAX_TIME_PER_DFA_CREATION | | public static int MAX_TIME_PER_DFA_CREATION(Code) | | Set to 0 to not terminate early
|
| REACHABLE_BUSY | | final public static int REACHABLE_BUSY(Code) | | |
| REACHABLE_NO | | final public static int REACHABLE_NO(Code) | | |
| REACHABLE_UNKNOWN | | final public static int REACHABLE_UNKNOWN(Code) | | |
| REACHABLE_YES | | final public static int REACHABLE_YES(Code) | | |
| altToAcceptState | | protected DFAState[] altToAcceptState(Code) | | We only want one accept state per predicted alt; track here
|
| conversionStartTime | | protected long conversionStartTime(Code) | | Track absolute time of the conversion so we can have a failsafe:
if it takes too long, then terminate. Assume bugs are in the
analysis engine.
|
| cyclic | | protected boolean cyclic(Code) | | Are there any loops in this DFA?
Computed by doesStateReachAcceptState()
|
| decisionNFAStartState | | public NFAState decisionNFAStartState(Code) | | From what NFAState did we create the DFA?
|
| decisionNumber | | public int decisionNumber(Code) | | This DFA is being built for which decision?
|
| description | | public String description(Code) | | The printable grammar fragment associated with this DFA
|
| edgeTransitionClass | | protected int edgeTransitionClass(Code) | | The unique edge transition class number; every time we see a new
set of edges emanating from a state, we number it so we can reuse
if it's every seen again for another state. For Java grammar,
some of the big edge transition tables are seen about 57 times.
|
| edgeTransitionClassMap | | public Map edgeTransitionClassMap(Code) | | Map an edge transition table to a unique set number; ordered so
we can push into the output template as an ordered list of sets
and then ref them from within the transition[][] table. Like this
for C# target:
public static readonly DFA30_transition0 =
new short[] { 46, 46, -1, 46, 46, -1, -1, -1, -1, -1, -1, -1,...};
public static readonly DFA30_transition1 =
new short[] { 21 };
public static readonly short[][] DFA30_transition = {
DFA30_transition0,
DFA30_transition0,
DFA30_transition1,
...
};
|
| max_k | | protected int max_k(Code) | | While building the DFA, track max lookahead depth if not cyclic
|
| nAlts | | protected int nAlts(Code) | | |
| nfa | | public NFA nfa(Code) | | Which NFA are we converting (well, which piece of the NFA)?
|
| numberOfStates | | protected int numberOfStates(Code) | | count only new states not states that were rejected as already present
|
| probe | | public DecisionProbe probe(Code) | | This probe tells you a lot about a decision and is useful even
when there is no error such as when a syntactic nondeterminism
is solved via semantic predicates. Perhaps a GUI would want
the ability to show that.
|
| recursiveAltSet | | protected IntSet recursiveAltSet(Code) | | Track whether an alt discovers recursion for each alt during
NFA to DFA conversion; >1 alt with recursion implies nonregular.
|
| reduced | | protected boolean reduced(Code) | | Is this DFA reduced? I.e., can all states lead to an accept state?
|
| specialStateSTs | | public List specialStateSTs(Code) | | List of ST for special states.
|
| specialStates | | public List specialStates(Code) | | List of special DFAState objects
|
| startState | | public DFAState startState(Code) | | What's the start state for this DFA?
|
| stateCounter | | protected int stateCounter(Code) | | Unique state numbers
|
| states | | protected Vector states(Code) | | Maps the state number to the actual DFAState. Use a Vector as it
grows automatically when I set the ith element. This contains all
states, but the states are not unique. s3 might be same as s1 so
s3 -> s1 in this table. This is how cycles occur. If fixed k,
then these states will all be unique as states[i] always points
at state i when no cycles exist.
This is managed in parallel with uniqueStates and simply provides
a way to go from state number to DFAState rather than via a
hash lookup.
|
| transitionEdgeTables | | public Vector transitionEdgeTables(Code) | | just the Vector indicating which unique edge table is at
position i.
|
| uniqueCompressedSpecialStateNum | | protected int uniqueCompressedSpecialStateNum(Code) | | |
| uniqueStates | | protected Map uniqueStates(Code) | | A set of all uniquely-numbered DFA states. Maps hash of DFAState
to the actual DFAState object. We use this to detect
existing DFA states. Map. Use Map so
we can get old state back (Set only allows you to see if it's there).
Not used during fixed k lookahead as it's a waste to fill it with
a dup of states array.
|
| unreachableAlts | | protected List unreachableAlts(Code) | | Each alt in an NFA derived from a grammar must have a DFA state that
predicts it lest the parser not know what to do. Nondeterminisms can
lead to this situation (assuming no semantic predicates can resolve
the problem) and when for some reason, I cannot compute the lookahead
(which might arise from an error in the algorithm or from
left-recursion etc...). This list starts out with all alts contained
and then in method doesStateReachAcceptState() I remove the alts I
know to be uniquely predicted.
|
| user_k | | protected int user_k(Code) | | User specified max fixed lookahead. If 0, nothing specified. -1
implies we have not looked at the options table yet to set k.
|
| addState | | protected DFAState addState(DFAState d)(Code) | | Add a new DFA state to this DFA if not already present.
To force an acyclic, fixed maximum depth DFA, just always
return the incoming state. By not reusing old states,
no cycles can be created. If we're doing fixed k lookahead
don't updated uniqueStates, just return incoming state, which
indicates it's a new state.
|
| analysisAborted | | public boolean analysisAborted()(Code) | | |
| canInlineDecision | | public boolean canInlineDecision()(Code) | | |
| createEOTAndEOFTables | | protected void createEOTAndEOFTables(DFAState s)(Code) | | Set up the EOT and EOF tables; we cannot put -1 min/max values so
we need another way to test that in the DFA transition function.
|
| createTransitionTableEntryForState | | protected void createTransitionTableEntryForState(DFAState s)(Code) | | |
| doesStateReachAcceptState | | protected boolean doesStateReachAcceptState(DFAState d)(Code) | | figure out if this state eventually reaches an accept state and
modify the instance variable 'reduced' to indicate if we find
at least one state that cannot reach an accept state. This implies
that the overall DFA is not reduced. This algorithm should be
linear in the number of DFA states.
The algorithm also tracks which alternatives have no accept state,
indicating a nondeterminism.
Also computes whether the DFA is cyclic.
TODO: I call getUniquelyPredicatedAlt too much; cache predicted alt
|
| encodeIntAsCharEscape | | public static String encodeIntAsCharEscape(int v)(Code) | | |
| getAutoBacktrackMode | | public boolean getAutoBacktrackMode()(Code) | | |
| getDecisionASTNode | | public GrammarAST getDecisionASTNode()(Code) | | What GrammarAST node (derived from the grammar) is this DFA
associated with? It will point to the start of a block or
the loop back of a (...)+ block etc...
|
| getDecisionNumber | | public int getDecisionNumber()(Code) | | |
| getJavaCompressedAccept | | public List getJavaCompressedAccept()(Code) | | |
| getJavaCompressedEOF | | public List getJavaCompressedEOF()(Code) | | |
| getJavaCompressedEOT | | public List getJavaCompressedEOT()(Code) | | |
| getJavaCompressedMax | | public List getJavaCompressedMax()(Code) | | |
| getJavaCompressedMin | | public List getJavaCompressedMin()(Code) | | |
| getJavaCompressedSpecial | | public List getJavaCompressedSpecial()(Code) | | |
| getJavaCompressedTransition | | public List getJavaCompressedTransition()(Code) | | |
| getMaxLookaheadDepth | | public int getMaxLookaheadDepth()(Code) | | Return k if decision is LL(k) for some k else return max int
|
| getMaxStateNumber | | public int getMaxStateNumber()(Code) | | What is the max state number ever created? This may be beyond
getNumberOfStates().
|
| getNFADecisionStartState | | public NFAState getNFADecisionStartState()(Code) | | |
| getNumberOfAlts | | public int getNumberOfAlts()(Code) | | |
| getNumberOfStates | | public int getNumberOfStates()(Code) | | |
| getRunLengthEncoding | | public List getRunLengthEncoding(List data)(Code) | | Compress the incoming data list so that runs of same number are
encoded as number,value pair sequences. 3 -1 -1 -1 28 is encoded
as 1 3 3 -1 1 28. I am pretty sure this is the lossless compression
that GIF files use. Transition tables are heavily compressed by
this technique. I got the idea from JFlex http://jflex.de/
Return List where each string is either \xyz for 8bit char
and \uFFFF for 16bit. Hideous and specific to Java, but it is the
only target bad enough to need it.
|
| getUniqueStates | | public Map getUniqueStates()(Code) | | |
| getUnreachableAlts | | public List getUnreachableAlts()(Code) | | Return a list of Integer alt numbers for which no lookahead could
be computed or for which no single DFA accept state predicts those
alts. Must call verify() first before this makes sense.
|
| getUserMaxLookahead | | public int getUserMaxLookahead()(Code) | | The user may specify a max, acyclic lookahead for any decision. No
DFA cycles are created when this value, k, is greater than 0.
If this decision has no k lookahead specified, then try the grammar.
|
| initAltRelatedInfo | | protected void initAltRelatedInfo()(Code) | | |
| isCyclic | | public boolean isCyclic()(Code) | | Is this DFA cyclic? That is, are there any loops? If not, then
the DFA is essentially an LL(k) predictor for some fixed, max k value.
We can build a series of nested IF statements to match this. In the
presence of cycles, we need to build a general DFA and interpret it
to distinguish between alternatives.
|
| isGreedy | | public boolean isGreedy()(Code) | | |
| isReduced | | public boolean isReduced()(Code) | | Is the DFA reduced? I.e., does every state have a path to an accept
state? If not, don't delete as we need to generate an error indicating
which paths are "dead ends". Also tracks list of alts with no accept
state in the DFA. Must call verify() first before this makes sense.
|
| isTokensRuleDecision | | public boolean isTokensRuleDecision()(Code) | | Is this DFA derived from the NFA for the Tokens rule?
|
| resetStateNumbersToBeContiguous | | public void resetStateNumbersToBeContiguous()(Code) | | Walk all states and reset their numbers to be a contiguous sequence
of integers starting from 0. Only cyclic DFA can have unused positions
in states list. State i might be identical to a previous state j and
will result in states[i] == states[j]. We don't want to waste a state
number on this. Useful mostly for code generation in tables.
At the start of this routine, states[i].stateNumber <= i by definition.
If states[50].stateNumber is 50 then a cycle during conversion may
try to add state 103, but we find that an identical DFA state, named
50, already exists, hence, states[103]==states[50] and both have
stateNumber 50 as they point at same object. Afterwards, the set
of state numbers from all states should represent a contiguous range
from 0..n-1 where n is the number of unique states.
|
| setAcceptState | | public void setAcceptState(int alt, DFAState acceptState)(Code) | | |
| setUserMaxLookahead | | public void setUserMaxLookahead(int k)(Code) | | |
| verify | | public void verify()(Code) | | Once this DFA has been built, need to verify that:
1. it's reduced
2. all alts have an accept state
Elsewhere, in the NFA converter, we need to verify that:
3. alts i and j have disjoint lookahead if no sem preds
4. if sem preds, nondeterministic alts must be sufficiently covered
|
|
|