Package jflex
Class DFA
java.lang.Object
jflex.DFA
Deterministic finite automata representation in JFlex. Contains minimization algorithm.
- Version:
- JFlex 1.7.0
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) Action[]
action[state]
is the action that is to be carried out in statestate
,null
if there is no action.(package private) int[]
entryState[i] is the start-state of lexical state i or lookahead DFA i(package private) boolean[]
isFinal[state] == true
invalid input: '<'=> the statestate
is a final state.(package private) boolean
True iff this DFA contains general lookaheadstatic final int
The code for "no target state" in the transition table.(package private) int
The current maximum number of input characters(package private) int
The number of lexical states (2*numLexStates invalid input: '<'= entryState.length)(package 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
ConstructorsConstructorDescriptionDFA
(int numEntryStates, int numInp, int numLexStates) Constructor for a deterministic finite automata. -
Method Summary
Modifier and TypeMethodDescriptionvoid
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) void
minimize()
Implementation of Hopcroft's O(n log n) minimization algorithm, follows description by D.boolean[][]
Much simpler, but slower and less memory efficient minimization algorithm.void
printBlocks
(int[] b, int[] b_f, int[] b_b, int last) printBlocks.void
printInvDelta
(int[][] inv_delta, int[] inv_delta_set) Prints the inverse of transition table.void
printL
(int[] l_f, int[] l_b, int anchor) printL.void
printTable
(boolean[][] equiv) Prints the equivalence table.void
Sets the action.void
setEntryState
(int eState, int trueState) Sets the state of the entry.void
setFinal
(int state, boolean isFinalState) setFinal.toString()
Returns a string representation of the DFA.toString
(int[] a) Returns a representation of this DFA.(package private) 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:
-
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
invalid input: '<'=> the statestate
is a final state. -
action
Action[] actionaction[state]
is the action that is to be carried out in statestate
,null
if there is no action. -
entryState
int[] entryStateentryState[i] is the start-state of lexical state i or lookahead DFA i -
numStates
int numStatesThe number of states in this DFA -
numInput
int numInputThe current maximum number of input characters -
numLexStates
int numLexStatesThe number of lexical states (2*numLexStates invalid input: '<'= entryState.length) -
usedActions
all actions that are used in this DFA -
lookaheadUsed
boolean lookaheadUsedTrue iff this DFA contains general lookahead
-
-
Constructor Details
-
DFA
public DFA(int numEntryStates, int numInp, int numLexStates) Constructor for a deterministic finite automata.
-
-
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.
-
toString
Returns a string representation of the DFA. -
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 invalid input: '<' 4*(5*c*n + 13*n + 3*c) byte
-
toString
Returns a representation of this DFA.- Parameters:
a
- an array of int.- Returns:
- a
String
object.
-
printBlocks
public void printBlocks(int[] b, int[] b_f, int[] b_b, int last) printBlocks.- Parameters:
b
- an array of int.b_f
- an array of int.b_b
- an array of int.last
- a int.
-
printL
public void printL(int[] l_f, int[] l_b, int anchor) printL.- Parameters:
l_f
- an array of int.l_b
- an array of int.anchor
- a int.
-
old_minimize
public boolean[][] old_minimize()Much simpler, but slower and less memory efficient minimization algorithm.- Returns:
- the equivalence relation on states.
-
printInvDelta
public 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.
-
printTable
public void printTable(boolean[][] equiv) Prints the equivalence table.- Parameters:
equiv
- Equivalence table
-