Package jflex
Class DFA
- java.lang.Object
-
- jflex.DFA
-
public final class DFA extends java.lang.Object
Deterministic finite automata representation in JFlex. Contains minimization algorithm.- Version:
- JFlex 1.7.0
-
-
Field Summary
Fields Modifier and Type Field Description (package private) Action[]
action
action[state]
is the action that is to be carried out in statestate
,null
if there is no action.(package private) int[]
entryState
entryState[i] is the start-state of lexical state i or lookahead DFA i(package private) boolean[]
isFinal
isFinal[state] == true
<=> the statestate
is a final state.(package private) boolean
lookaheadUsed
True iff this DFA contains general lookaheadstatic int
NO_TARGET
The code for "no target state" in the transition table.(package private) int
numInput
The current maximum number of input characters(package private) int
numLexStates
The number of lexical states (2*numLexStates <= entryState.length)(package private) int
numStates
The number of states in this DFAprivate static int
STATES
The initial number of states(package private) int[][]
table
table[current_state][character] is the next state forcurrent_state
with inputcharacter
,NO_TARGET
if there is no transition for this input incurrent_state
(package private) java.util.Map<Action,Action>
usedActions
all actions that are used in this DFA
-
Constructor Summary
Constructors Constructor Description DFA(int numEntryStates, int numInp, int numLexStates)
Constructor for a deterministic finite automata.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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 java.lang.String
dotFormat()
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[][]
old_minimize()
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
setAction(int state, Action stateAction)
Sets the action.void
setEntryState(int eState, int trueState)
Sets the state of the entry.void
setFinal(int state, boolean isFinalState)
setFinal.java.lang.String
toString()
Returns a string representation of the DFA.java.lang.String
toString(int[] a)
Returns a representation of this DFA.(package private) void
writeDot(java.io.File file)
Writes a dot-file representing this DFA.
-
-
-
Field Detail
-
STATES
private static final int STATES
The initial number of states- See Also:
- Constant Field Values
-
NO_TARGET
public static final int NO_TARGET
The code for "no target state" in the transition table.- See Also:
- Constant Field Values
-
table
int[][] table
table[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[] isFinal
isFinal[state] == true
<=> the statestate
is a final state.
-
action
Action[] action
action[state]
is the action that is to be carried out in statestate
,null
if there is no action.
-
entryState
int[] entryState
entryState[i] is the start-state of lexical state i or lookahead DFA i
-
numStates
int numStates
The number of states in this DFA
-
numInput
int numInput
The current maximum number of input characters
-
numLexStates
int numLexStates
The number of lexical states (2*numLexStates <= entryState.length)
-
lookaheadUsed
boolean lookaheadUsed
True iff this DFA contains general lookahead
-
-
Method Detail
-
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
public void setAction(int state, Action stateAction)
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
public java.lang.String toString()
Returns a string representation of the DFA.- Overrides:
toString
in classjava.lang.Object
-
writeDot
void writeDot(java.io.File file)
Writes a dot-file representing this DFA.- Parameters:
file
- output file.
-
dotFormat
private java.lang.String dotFormat()
Returns a gnu representation of the DFA.- Returns:
- a representation in the dot format.
-
checkActions
public void checkActions(LexScan scanner, LexParse parser)
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
-
toString
public java.lang.String toString(int[] a)
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
-
-