Package jflex.dfa
Class DFA
- java.lang.Object
-
- jflex.dfa.DFA
-
- Direct Known Subclasses:
DeprecatedDfa
public class DFA extends java.lang.Object
Deterministic finite automata representation in JFlex. Contains minimization algorithm.- Version:
- JFlex 1.9.1
-
-
Field Summary
Fields Modifier and Type Field Description private Action[]
action
action[state]
is the action that is to be carried out in statestate
,null
if there is no action.(package private) static boolean
DFA_DEBUG
(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
if the statestate
is a final state.private boolean
lookaheadUsed
True iff this DFA contains general lookaheadprivate boolean
minimized
Whether the DFA is minimized.static int
NO_TARGET
The code for "no target state" in the transition table.private int
numInput
The maximum number of input charactersprivate int
numLexStates
The number of lexical states (2*numLexStates <= entryState.length)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
private java.util.Map<Action,Action>
usedActions
all actions that are used in this DFA
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Action
action(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 java.lang.String
dotFormat()
Returns a gnu representation of the DFA.private void
ensureStateCapacity(int newNumStates)
int
entryState(int i)
boolean
equals(java.lang.Object obj)
int
hashCode()
boolean
isFinal(int i)
boolean
isMinimized()
boolean
lookaheadUsed()
void
minimize()
Implementation of Hopcroft's O(n log n) minimization algorithm, follows description by D.int
numInput()
int
numLexStates()
int
numStates()
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
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.int
table(int i, int j)
private static boolean
tableEquals(int[][] a, int[][] b)
java.lang.String
toString()
java.lang.String
toString(int[] a)
Returns a representation of this DFA.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
-
DFA_DEBUG
static final boolean DFA_DEBUG
- 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
if the statestate
is a final state.
-
numInput
private final int numInput
The maximum number of input characters
-
numLexStates
private final int numLexStates
The number of lexical states (2*numLexStates <= entryState.length)
-
numStates
private int numStates
The number of states in this DFA
-
entryState
int[] entryState
entryState[i]
is the start-state of lexical state i or lookahead DFA i.
-
action
private Action[] action
action[state]
is the action that is to be carried out in statestate
,null
if there is no action.
-
usedActions
private final java.util.Map<Action,Action> usedActions
all actions that are used in this DFA
-
lookaheadUsed
private boolean lookaheadUsed
True iff this DFA contains general lookahead
-
minimized
private boolean minimized
Whether the DFA is minimized.
-
-
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.
-
lookaheadUsed
public boolean lookaheadUsed()
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
equals
public boolean equals(@Nullable java.lang.Object obj)
- Overrides:
equals
in classjava.lang.Object
-
tableEquals
private static boolean tableEquals(int[][] a, int[][] b)
-
writeDot
public 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
-
isMinimized
public boolean isMinimized()
-
toString
public java.lang.String toString(int[] a)
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
public Action action(int i)
-
-