JFlex

Class DFA


public final class DFA
extends java.lang.Object

DFA representation in JFlex. Contains minimization algorithm.

Field Summary

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

Constructor Summary

DFA(int numEntryStates, int numInp, int numLexStates)

Method Summary

void
addTransition(int start, char input, int dest)
void
checkActions(LexScan scanner, LexParse parser)
Check that all actions can actually be matched in this DFA.
String
dotFormat()
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)
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
setEntryState(int eState, int trueState)
void
setFinal(int state, boolean isFinalState)
String
toString()
String
toString(int[] a)
void
writeDot(File file)

Field Details

NO_TARGET

public static final int NO_TARGET
The code for "no target state" in the transition table.
Field Value:
-1

Constructor Details

DFA

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

Method Details

addTransition

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

checkActions

public void checkActions(LexScan scanner,
                         LexParse parser)
Check that all actions can actually be matched in this DFA.

dotFormat

public String dotFormat()

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 <324*(5*c*n + 13*n + 3*c) byte

old_minimize

public boolean[][] old_minimize()
Much simpler, but slower and less memory efficient minimization algorithm.
Returns:
the equivalence relation on states.

printBlocks

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

printInvDelta

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

printL

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

printTable

public void printTable(boolean[][] equiv)

setAction

public void setAction(int state,
                      Action stateAction)

setEntryState

public void setEntryState(int eState,
                          int trueState)

setFinal

public void setFinal(int state,
                     boolean isFinalState)

toString

public String toString()

toString

public String toString(int[] a)

writeDot

public void writeDot(File file)