Package jflex.dfa
Class DFA
java.lang.Object
jflex.dfa.DFA
- Direct Known Subclasses:
DeprecatedDfa
Deterministic finite automata representation in JFlex. Contains minimization algorithm.
- Version:
- JFlex 1.8.2
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Action[]
action[state]
is the action that is to be carried out in statestate
,null
if there is no action.(package private) static final boolean
(package private) int[]
entryState[i]
is the start-state of lexical state i or lookahead DFA i.(package private) boolean[]
isFinal[state] == true
if the statestate
is a final state.private boolean
True iff this DFA contains general lookaheadprivate boolean
Whether the DFA is minimized.static final int
The code for "no target state" in the transition table.private final int
The maximum number of input charactersprivate final int
The number of lexical states (2*numLexStates invalid input: '<'= entryState.length)private int
The number of states in this DFAprivate static final int
The initial number of states(package private) int[][]
table[current_state][character]
is the next state forcurrent_state
with inputcharacter
,NO_TARGET
if there is no transition for this input incurrent_state
all actions that are used in this DFA -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionaction
(int i) void
addTransition
(int start, int input, int dest) addTransition.void
checkActions
(LexScan scanner, LexParse parser) Checks that all actions can actually be matched in this DFA.private String
Returns a gnu representation of the DFA.private void
ensureStateCapacity
(int newNumStates) int
entryState
(int i) boolean
int
hashCode()
boolean
isFinal
(int i) boolean
boolean
void
minimize()
Implementation of Hopcroft's O(n log n) minimization algorithm, follows description by D.int
numInput()
int
int
private void
printBlocks
(int[] b, int[] b_f, int[] b_b, int last) private void
printInvDelta
(int[][] inv_delta, int[] inv_delta_set) Prints the inverse of transition table.private void
printL
(int[] l_f, int[] l_b, int anchor) void
Sets the action.void
setEntryState
(int eState, int trueState) Sets the state of the entry.void
setFinal
(int state, boolean isFinalState) setFinal.int
table
(int i, int j) private static boolean
tableEquals
(int[][] a, int[][] b) toString()
toString
(int[] a) Returns a representation of this DFA.void
Writes a dot-file representing this DFA.
-
Field Details
-
STATES
private static final int STATESThe initial number of states- See Also:
-
NO_TARGET
public static final int NO_TARGETThe code for "no target state" in the transition table.- See Also:
-
DFA_DEBUG
static final boolean DFA_DEBUG- See Also:
-
table
int[][] tabletable[current_state][character]
is the next state forcurrent_state
with inputcharacter
,NO_TARGET
if there is no transition for this input incurrent_state
-
isFinal
boolean[] isFinalisFinal[state] == true
if the statestate
is a final state. -
numInput
private final int numInputThe maximum number of input characters -
numLexStates
private final int numLexStatesThe number of lexical states (2*numLexStates invalid input: '<'= entryState.length) -
numStates
private int numStatesThe number of states in this DFA -
entryState
int[] entryStateentryState[i]
is the start-state of lexical state i or lookahead DFA i. -
action
action[state]
is the action that is to be carried out in statestate
,null
if there is no action. -
usedActions
all actions that are used in this DFA -
lookaheadUsed
private boolean lookaheadUsedTrue iff this DFA contains general lookahead -
minimized
private boolean minimizedWhether the DFA is minimized.
-
-
Constructor Details
-
DFA
public DFA(int numEntryStates, int numInputs, int numLexStates) Constructor for a deterministic finite automata. -
DFA
DFA(int numEntryStates, int numInputs, int numLexStates, int numStates)
-
-
Method Details
-
setEntryState
public void setEntryState(int eState, int trueState) Sets the state of the entry.- Parameters:
eState
- entry state.trueState
- whether it is the current state.
-
ensureStateCapacity
private void ensureStateCapacity(int newNumStates) -
setAction
Sets the action.- Parameters:
state
- a int.stateAction
- aAction
object.
-
setFinal
public void setFinal(int state, boolean isFinalState) setFinal.- Parameters:
state
- a int.isFinalState
- a boolean.
-
addTransition
public void addTransition(int start, int input, int dest) addTransition.- Parameters:
start
- a int.input
- a int.dest
- a int.
-
lookaheadUsed
public boolean lookaheadUsed() -
toString
-
hashCode
public int hashCode() -
equals
-
tableEquals
private static boolean tableEquals(int[][] a, int[][] b) -
writeDot
Writes a dot-file representing this DFA.- Parameters:
file
- output file.
-
dotFormat
Returns a gnu representation of the DFA.- Returns:
- a representation in the dot format.
-
checkActions
Checks that all actions can actually be matched in this DFA. -
minimize
public void minimize()Implementation of Hopcroft's O(n log n) minimization algorithm, follows description by D. Gries.Time:
O(n log n)
Space:O(c n), size < 4*(5*c*n + 13*n + 3*c) byte
-
isMinimized
public boolean isMinimized() -
toString
Returns a representation of this DFA. -
printBlocks
private void printBlocks(int[] b, int[] b_f, int[] b_b, int last) -
printL
private void printL(int[] l_f, int[] l_b, int anchor) -
printInvDelta
private void printInvDelta(int[][] inv_delta, int[] inv_delta_set) Prints the inverse of transition table.- Parameters:
inv_delta
- an array of int.inv_delta_set
- an array of int.
-
numInput
public int numInput() -
numStates
public int numStates() -
numLexStates
public int numLexStates() -
entryState
public int entryState(int i) -
isFinal
public boolean isFinal(int i) -
table
public int table(int i, int j) -
action
-