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

Author:

Gerwin Klein

Field Summary

Fields

Modifier and Type	Field and Description
static int	NO_TARGET The code for "no target state" in the transition table.

Constructor Summary

Constructors

Constructor and Description
DFA(int numEntryStates, int numInp, int numLexStates) Constructor for a deterministic finite automata.

Method Summary

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.
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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

NO_TARGET

public static final int NO_TARGET

The code for "no target state" in the transition table.

See Also:

Constant Field Values

Constructor Detail

DFA

public DFA(int numEntryStates,
           int numInp,
           int numLexStates)

Constructor for a deterministic finite automata.

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.

setAction

public void setAction(int state,
                      Action stateAction)

Sets the action.

Parameters:

state - a int.

stateAction - a Action 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 class java.lang.Object

checkActions

public void checkActions(LexScan scanner,
                         LexParse parser)

Checks that all actions can actually be matched in this DFA.

Parameters:

scanner - a LexScan.

parser - a LexParse.

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