public final class DFA
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
(package private) Action[] |
action
action[state] is the action that is to be carried out in state state ,
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 state state is a final state. |
(package private) boolean |
lookaheadUsed
True iff this DFA contains general lookahead
|
static 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 DFA
|
private static int |
STATES
The initial number of states
|
(package private) int[][] |
table
table[current_state][character] is the next state for
current_state with input
character , NO_TARGET if there is no transition for this input in
current_state |
(package private) java.util.Map<Action,Action> |
usedActions
all actions that are used in this DFA
|
Constructor and Description |
---|
DFA(int numEntryStates,
int numInp,
int numLexStates)
Constructor for a deterministic finite automata.
|
Modifier and Type | Method and 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.
|
private static final int STATES
public static final int NO_TARGET
int[][] table
current_state
with input
character
, NO_TARGET
if there is no transition for this input in
current_state
boolean[] isFinal
isFinal[state] == true
<=> the state state
is a final state.Action[] action
action[state]
is the action that is to be carried out in state state
,
null
if there is no action.int[] entryState
int numStates
int numInput
int numLexStates
boolean lookaheadUsed
public DFA(int numEntryStates, int numInp, int numLexStates)
public void setEntryState(int eState, int trueState)
eState
- entry state.trueState
- whether it is the current state.private void ensureStateCapacity(int newNumStates)
public void setAction(int state, Action stateAction)
state
- a int.stateAction
- a Action
object.public void setFinal(int state, boolean isFinalState)
state
- a int.isFinalState
- a boolean.public void addTransition(int start, int input, int dest)
start
- a int.input
- a int.dest
- a int.public java.lang.String toString()
toString
in class java.lang.Object
void writeDot(java.io.File file)
file
- output file.private java.lang.String dotFormat()
public void checkActions(LexScan scanner, LexParse parser)
public void minimize()
Time: O(n log n) Space: O(c n), size < 4*(5*c*n + 13*n + 3*c) byte
public java.lang.String toString(int[] a)
a
- an array of int.String
object.public void printBlocks(int[] b, int[] b_f, int[] b_b, int last)
b
- an array of int.b_f
- an array of int.b_b
- an array of int.last
- a int.public void printL(int[] l_f, int[] l_b, int anchor)
l_f
- an array of int.l_b
- an array of int.anchor
- a int.public boolean[][] old_minimize()
public void printInvDelta(int[][] inv_delta, int[] inv_delta_set)
inv_delta
- an array of int.inv_delta_set
- an array of int.public void printTable(boolean[][] equiv)
equiv
- Equivalence table