Modifier and Type | Field and Description |
---|---|
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?
|
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.
|
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.
|
Vector |
eof |
Vector |
eot |
protected CodeGenerator |
generator
Which generator to use if we're building state tables
|
boolean |
hasPredicateBlockedByAction |
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_TIME_PER_DFA_CREATION
Set to 0 to not terminate early (time in ms)
|
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
|
boolean |
predicateVisible
Track whether this DFA has at least one sem/syn pred encountered
during a closure operation.
|
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 |
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?
|
Vector |
special |
List |
specialStates
List of special DFAState objects
|
List |
specialStateSTs
List of ST for special states.
|
DFAState |
startState
What's the start state for this DFA?
|
protected int |
stateCounter
Unique state numbers per DFA
|
protected Vector<DFAState> |
states
Maps the state number to the actual DFAState.
|
Vector |
transition |
Vector |
transitionEdgeTables
just the Vector
|
protected int |
uniqueCompressedSpecialStateNum |
protected Map<DFAState,DFAState> |
uniqueStates
A set of all uniquely-numbered DFA states.
|
protected List<Integer> |
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.
|
Modifier | Constructor and Description |
---|---|
protected |
DFA() |
|
DFA(int decisionNumber,
NFAState decisionStartState) |
Modifier and Type | Method and Description |
---|---|
protected DFAState |
addState(DFAState d)
Add a new DFA state to this DFA if not already present.
|
boolean |
analysisTimedOut() |
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.
|
void |
findAllGatedSynPredsUsedInDFAAcceptStates()
Walk all accept states and find the manually-specified synpreds.
|
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() |
String |
getDescription() |
List |
getJavaCompressedAccept() |
List |
getJavaCompressedEOF() |
List |
getJavaCompressedEOT() |
List |
getJavaCompressedMax() |
List |
getJavaCompressedMin() |
List |
getJavaCompressedSpecial() |
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() |
String |
getReasonForFailure() |
List |
getRunLengthEncoding(List data)
Compress the incoming data list so that runs of same number are
encoded as number,value pair sequences.
|
DFAState |
getState(int stateNumber) |
Map<DFAState,DFAState> |
getUniqueStates() |
List<Integer> |
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() |
boolean |
okToRetryDFAWithK1()
If this DFA failed to finish during construction, we might be
able to retry with k=1 but we need to know whether it will
potentially succeed.
|
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) |
String |
toString() |
void |
verify()
Once this DFA has been built, need to verify that:
1.
|
public static final int REACHABLE_UNKNOWN
public static final int REACHABLE_BUSY
public static final int REACHABLE_NO
public static final int REACHABLE_YES
public static int MAX_TIME_PER_DFA_CREATION
public static int MAX_STATE_TRANSITIONS_FOR_TABLE
public DFAState startState
public int decisionNumber
public NFAState decisionNFAStartState
public String description
protected Map<DFAState,DFAState> uniqueStates
protected Vector<DFAState> states
protected int stateCounter
protected int numberOfStates
protected int user_k
protected int max_k
protected boolean reduced
protected boolean cyclic
public boolean predicateVisible
public boolean hasPredicateBlockedByAction
protected List<Integer> unreachableAlts
protected int nAlts
protected DFAState[] altToAcceptState
public IntSet recursiveAltSet
public NFA nfa
protected NFAToDFAConverter nfaConverter
public DecisionProbe probe
protected long conversionStartTime
public Map edgeTransitionClassMap
protected int edgeTransitionClass
public List specialStates
public List specialStateSTs
public Vector accept
public Vector eot
public Vector eof
public Vector min
public Vector max
public Vector special
public Vector transition
public Vector transitionEdgeTables
protected int uniqueCompressedSpecialStateNum
protected CodeGenerator generator
protected DFA()
public DFA(int decisionNumber, NFAState decisionStartState)
public void resetStateNumbersToBeContiguous()
public List getJavaCompressedAccept()
public List getJavaCompressedEOT()
public List getJavaCompressedEOF()
public List getJavaCompressedMin()
public List getJavaCompressedMax()
public List getJavaCompressedSpecial()
public List getJavaCompressedTransition()
public List getRunLengthEncoding(List data)
public void createStateTables(CodeGenerator generator)
protected void createMinMaxTables(DFAState s)
protected void createTransitionTableEntryForState(DFAState s)
protected void createEOTAndEOFTables(DFAState s)
protected void createSpecialTable(DFAState s)
public int predict(IntStream input)
protected DFAState addState(DFAState d)
public void removeState(DFAState d)
public int getMaxStateNumber()
public DFAState getState(int stateNumber)
public void setState(int stateNumber, DFAState d)
public boolean isReduced()
public boolean isCyclic()
public boolean canInlineDecision()
public boolean isTokensRuleDecision()
public int getUserMaxLookahead()
public boolean getAutoBacktrackMode()
public void setUserMaxLookahead(int k)
public int getMaxLookaheadDepth()
public List<Integer> getUnreachableAlts()
public void verify()
protected boolean doesStateReachAcceptState(DFAState d)
public void findAllGatedSynPredsUsedInDFAAcceptStates()
public NFAState getNFADecisionStartState()
public DFAState getAcceptState(int alt)
public void setAcceptState(int alt, DFAState acceptState)
public String getDescription()
public int getDecisionNumber()
public boolean okToRetryDFAWithK1()
public String getReasonForFailure()
public GrammarAST getDecisionASTNode()
public boolean isGreedy()
public DFAState newState()
public int getNumberOfStates()
public int getNumberOfAlts()
public boolean analysisTimedOut()
protected void initAltRelatedInfo()
Copyright © 2020. All rights reserved.