org.antlr.analysis
Class DFA

java.lang.Object
  extended by org.antlr.analysis.DFA

public class DFA
extends java.lang.Object

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).


Field Summary
 java.util.Vector accept
           
protected  DFAState[] altToAcceptState
          We only want one accept state per predicted alt; track here
protected  long conversionStartTime
          Track absolute time of the conversion so we can have a failsafe: if it takes too long, then terminate.
protected  boolean cyclic
          Are there any loops in this DFA? Computed by doesStateReachAcceptState()
 NFAState decisionNFAStartState
          From what NFAState did we create the DFA?
 int decisionNumber
          This DFA is being built for which decision?
 java.lang.String description
          The printable grammar fragment associated with this DFA
protected  int edgeTransitionClass
          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.
 java.util.Map edgeTransitionClassMap
          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.
 java.util.Vector eof
           
 java.util.Vector eot
           
 java.util.Vector max
           
protected  int max_k
          While building the DFA, track max lookahead depth if not cyclic
static int MAX_STATE_TRANSITIONS_FOR_TABLE
          How many edges can each DFA state have before a "special" state is created that uses IF expressions instead of a table?
static int MAX_STATES_PER_ALT_IN_DFA
          Prevent explosion of DFA states during conversion.
static int MAX_TIME_PER_DFA_CREATION
          Set to 0 to not terminate early
 java.util.Vector min
           
protected  int nAlts
           
 NFA nfa
          Which NFA are we converting (well, which piece of the NFA)?
protected  NFAToDFAConverter nfaConverter
           
protected  int numberOfStates
          count only new states not states that were rejected as already present
 DecisionProbe probe
          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.
static int REACHABLE_BUSY
           
static int REACHABLE_NO
           
static int REACHABLE_UNKNOWN
           
static int REACHABLE_YES
           
protected  IntSet recursiveAltSet
          Track whether an alt discovers recursion for each alt during NFA to DFA conversion; >1 alt with recursion implies nonregular.
protected  boolean reduced
          Is this DFA reduced? I.e., can all states lead to an accept state?
 java.util.Vector special
           
 java.util.List specialStates
          List of special DFAState objects
 java.util.List specialStateSTs
          List of ST for special states.
 DFAState startState
          What's the start state for this DFA?
protected  int stateCounter
          Unique state numbers
protected  java.util.Vector states
          Maps the state number to the actual DFAState.
 java.util.Vector transition
           
 java.util.Vector transitionEdgeTables
          just the Vector indicating which unique edge table is at position i.
protected  int uniqueCompressedSpecialStateNum
           
protected  java.util.Map uniqueStates
          A set of all uniquely-numbered DFA states.
protected  java.util.List unreachableAlts
          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.
protected  int user_k
          User specified max fixed lookahead.
 
Constructor Summary
DFA(int decisionNumber, NFAState decisionStartState)
           
 
Method Summary
protected  DFAState addState(DFAState d)
          Add a new DFA state to this DFA if not already present.
 boolean analysisAborted()
           
 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)
           
 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.
static java.lang.String encodeIntAsCharEscape(int v)
           
 DFAState getAcceptState(int alt)
           
 boolean getAutoBacktrackMode()
           
 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...
 int getDecisionNumber()
           
 java.lang.String getDescription()
           
 java.util.List getJavaCompressedAccept()
           
 java.util.List getJavaCompressedEOF()
           
 java.util.List getJavaCompressedEOT()
           
 java.util.List getJavaCompressedMax()
           
 java.util.List getJavaCompressedMin()
           
 java.util.List getJavaCompressedSpecial()
           
 java.util.List getJavaCompressedTransition()
           
 int getMaxLookaheadDepth()
          Return k if decision is LL(k) for some k else return max int
 int getMaxStateNumber()
          What is the max state number ever created? This may be beyond getNumberOfStates().
 NFAState getNFADecisionStartState()
           
 int getNumberOfAlts()
           
 int getNumberOfStates()
           
 java.util.List getRunLengthEncoding(java.util.List data)
          Compress the incoming data list so that runs of same number are encoded as number,value pair sequences.
 DFAState getState(int stateNumber)
           
 java.util.Map getUniqueStates()
           
 java.util.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.
 int getUserMaxLookahead()
          The user may specify a max, acyclic lookahead for any decision.
protected  void initAltRelatedInfo()
           
 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.
 boolean isGreedy()
           
 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".
 boolean isTokensRuleDecision()
          Is this DFA derived from the NFA for the Tokens rule?
 DFAState newState()
           
 int predict(IntStream input)
           
 void removeState(DFAState d)
           
 void resetStateNumbersToBeContiguous()
          Walk all states and reset their numbers to be a contiguous sequence of integers starting from 0.
 void setAcceptState(int alt, DFAState acceptState)
           
 void setState(int stateNumber, DFAState d)
           
 void setUserMaxLookahead(int k)
           
 java.lang.String toString()
           
 void verify()
          Once this DFA has been built, need to verify that: 1.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

REACHABLE_UNKNOWN

public static final int REACHABLE_UNKNOWN
See Also:
Constant Field Values

REACHABLE_BUSY

public static final int REACHABLE_BUSY
See Also:
Constant Field Values

REACHABLE_NO

public static final int REACHABLE_NO
See Also:
Constant Field Values

REACHABLE_YES

public static final int REACHABLE_YES
See Also:
Constant Field Values

MAX_STATES_PER_ALT_IN_DFA

public static final int MAX_STATES_PER_ALT_IN_DFA
Prevent explosion of DFA states during conversion. The max number of states per alt in a single decision's DFA.

See Also:
Constant Field Values

MAX_TIME_PER_DFA_CREATION

public static int MAX_TIME_PER_DFA_CREATION
Set to 0 to not terminate early


MAX_STATE_TRANSITIONS_FOR_TABLE

public static int MAX_STATE_TRANSITIONS_FOR_TABLE
How many edges can each DFA state have before a "special" state is created that uses IF expressions instead of a table?


startState

public DFAState startState
What's the start state for this DFA?


decisionNumber

public int decisionNumber
This DFA is being built for which decision?


decisionNFAStartState

public NFAState decisionNFAStartState
From what NFAState did we create the DFA?


description

public java.lang.String description
The printable grammar fragment associated with this DFA


uniqueStates

protected java.util.Map uniqueStates
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.


states

protected java.util.Vector states
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.


stateCounter

protected int stateCounter
Unique state numbers


numberOfStates

protected int numberOfStates
count only new states not states that were rejected as already present


user_k

protected int user_k
User specified max fixed lookahead. If 0, nothing specified. -1 implies we have not looked at the options table yet to set k.


max_k

protected int max_k
While building the DFA, track max lookahead depth if not cyclic


reduced

protected boolean reduced
Is this DFA reduced? I.e., can all states lead to an accept state?


cyclic

protected boolean cyclic
Are there any loops in this DFA? Computed by doesStateReachAcceptState()


unreachableAlts

protected java.util.List unreachableAlts
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.


nAlts

protected int nAlts

altToAcceptState

protected DFAState[] altToAcceptState
We only want one accept state per predicted alt; track here


recursiveAltSet

protected IntSet recursiveAltSet
Track whether an alt discovers recursion for each alt during NFA to DFA conversion; >1 alt with recursion implies nonregular.


nfa

public NFA nfa
Which NFA are we converting (well, which piece of the NFA)?


nfaConverter

protected NFAToDFAConverter nfaConverter

probe

public DecisionProbe probe
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.


conversionStartTime

protected long conversionStartTime
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.


edgeTransitionClassMap

public java.util.Map edgeTransitionClassMap
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, ... };


edgeTransitionClass

protected int edgeTransitionClass
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.


specialStates

public java.util.List specialStates
List of special DFAState objects


specialStateSTs

public java.util.List specialStateSTs
List of ST for special states.


accept

public java.util.Vector accept

eot

public java.util.Vector eot

eof

public java.util.Vector eof

min

public java.util.Vector min

max

public java.util.Vector max

special

public java.util.Vector special

transition

public java.util.Vector transition

transitionEdgeTables

public java.util.Vector transitionEdgeTables
just the Vector indicating which unique edge table is at position i.


uniqueCompressedSpecialStateNum

protected int uniqueCompressedSpecialStateNum
Constructor Detail

DFA

public DFA(int decisionNumber,
           NFAState decisionStartState)
Method Detail

resetStateNumbersToBeContiguous

public void resetStateNumbersToBeContiguous()
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.


getJavaCompressedAccept

public java.util.List getJavaCompressedAccept()

getJavaCompressedEOT

public java.util.List getJavaCompressedEOT()

getJavaCompressedEOF

public java.util.List getJavaCompressedEOF()

getJavaCompressedMin

public java.util.List getJavaCompressedMin()

getJavaCompressedMax

public java.util.List getJavaCompressedMax()

getJavaCompressedSpecial

public java.util.List getJavaCompressedSpecial()

getJavaCompressedTransition

public java.util.List getJavaCompressedTransition()

getRunLengthEncoding

public java.util.List getRunLengthEncoding(java.util.List data)
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 ? for 16bit. Hideous and specific to Java, but it is the only target bad enough to need it.


createStateTables

public void createStateTables(CodeGenerator generator)

createMinMaxTables

protected void createMinMaxTables(DFAState s)

createTransitionTableEntryForState

protected void createTransitionTableEntryForState(DFAState s)

createEOTAndEOFTables

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.


createSpecialTable

protected void createSpecialTable(DFAState s)

encodeIntAsCharEscape

public static java.lang.String encodeIntAsCharEscape(int v)

predict

public int predict(IntStream input)

addState

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. 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.


removeState

public void removeState(DFAState d)

getUniqueStates

public java.util.Map getUniqueStates()

getMaxStateNumber

public int getMaxStateNumber()
What is the max state number ever created? This may be beyond getNumberOfStates().


getState

public DFAState getState(int stateNumber)

setState

public void setState(int stateNumber,
                     DFAState d)

isReduced

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". Also tracks list of alts with no accept state in the DFA. Must call verify() first before this makes sense.


isCyclic

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. In the presence of cycles, we need to build a general DFA and interpret it to distinguish between alternatives.


canInlineDecision

public boolean canInlineDecision()

isTokensRuleDecision

public boolean isTokensRuleDecision()
Is this DFA derived from the NFA for the Tokens rule?


getUserMaxLookahead

public int getUserMaxLookahead()
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.


getAutoBacktrackMode

public boolean getAutoBacktrackMode()

setUserMaxLookahead

public void setUserMaxLookahead(int k)

getMaxLookaheadDepth

public int getMaxLookaheadDepth()
Return k if decision is LL(k) for some k else return max int


getUnreachableAlts

public java.util.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. Must call verify() first before this makes sense.


verify

public void verify()
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


doesStateReachAcceptState

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. 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


getNFADecisionStartState

public NFAState getNFADecisionStartState()

getAcceptState

public DFAState getAcceptState(int alt)

setAcceptState

public void setAcceptState(int alt,
                           DFAState acceptState)

getDescription

public java.lang.String getDescription()

getDecisionNumber

public int getDecisionNumber()

getDecisionASTNode

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...


isGreedy

public boolean isGreedy()

newState

public DFAState newState()

getNumberOfStates

public int getNumberOfStates()

getNumberOfAlts

public int getNumberOfAlts()

analysisAborted

public boolean analysisAborted()

initAltRelatedInfo

protected void initAltRelatedInfo()

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object