JFlex
Class DFA

java.lang.Object
  JFlex.DFA

public final class DFA
extends java.lang.Object

DFA representation in JFlex. Contains minimization algorithm.

Version:

JFlex 1.4.1, $Revision: 2.7 $, $Date: 2004/11/06 23:03:31 $

Author:

Gerwin Klein

Field Summary

(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) boolean[]	isFinal isFinal[state] == true <=> the state state is a final state.
(package private) boolean[]	isLookEnd isLookEnd[state] == true <=> the state state is a final state of a lookahead expression.
(package private) boolean[]	isPushback isPushback[state] == true <=> the state state is a final state of an expression that can only be matched when followed by a certain lookaead.
(package private) int[]	lexState lexState[i] is the start-state of lexical state i
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	numStates The number of states in this DFA
(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.Hashtable	usedActions all actions that are used in this DFA

Constructor Summary

DFA(int numLexStates, int numInp)

Method Summary

void	addTransition(int start, char input, int dest)
void	checkActions(LexScan scanner, LexParse parser)
java.lang.String	dotFormat()
void	minimize() Implementation of Hopcroft's O(n log n) minimization algorithm, follows description by D.
boolean[][]	old_minimize()
void	printBlocks(int[] b, int[] b_f, int[] b_b, int last)
void	printInvDelta(int[][] inv_delta, int[] inv_delta_set)
void	printL(int[] l_f, int[] l_b, int anchor)
void	printTable(boolean[][] equiv)
void	setAction(int state, Action stateAction)
void	setFinal(int state, boolean isFinalState)
void	setLexState(int lState, int trueState)
void	setPushback(int state, boolean isPushbackState)
java.lang.String	toString()
java.lang.String	toString(int[] a)
void	writeDot(java.io.File file)

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

table

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

isFinal

boolean[] isFinal

isFinal[state] == true <=> the state state is a final state.

isPushback

boolean[] isPushback

isPushback[state] == true <=> the state state is a final state of an expression that can only be matched when followed by a certain lookaead.

isLookEnd

boolean[] isLookEnd

isLookEnd[state] == true <=> the state state is a final state of a lookahead expression.

action

Action[] action

action[state] is the action that is to be carried out in state state, null if there is no action.

lexState

int[] lexState

lexState[i] is the start-state of lexical state i

numStates

int numStates

The number of states in this DFA

numInput

int numInput

The current maximum number of input characters

usedActions

java.util.Hashtable usedActions

all actions that are used in this DFA

Constructor Detail

DFA

public DFA(int numLexStates,
           int numInp)

Method Detail

setLexState

public void setLexState(int lState,
                        int trueState)

setAction

public void setAction(int state,
                      Action stateAction)

setFinal

public void setFinal(int state,
                     boolean isFinalState)

setPushback

public void setPushback(int state,
                        boolean isPushbackState)

addTransition

public void addTransition(int start,
                          char input,
                          int dest)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

writeDot

public void writeDot(java.io.File file)

dotFormat

public java.lang.String dotFormat()

checkActions

public void checkActions(LexScan scanner,
                         LexParse parser)

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)

printBlocks

public void printBlocks(int[] b,
                        int[] b_f,
                        int[] b_b,
                        int last)

printL

public void printL(int[] l_f,
                   int[] l_b,
                   int anchor)

old_minimize

public boolean[][] old_minimize()

printInvDelta

public void printInvDelta(int[][] inv_delta,
                          int[] inv_delta_set)

printTable

public void printTable(boolean[][] equiv)