Package jflex

Class DFA

java.lang.Object
jflex.DFA
public final class DFA extends Object
Deterministic finite automata representation in JFlex. Contains minimization algorithm.
Version:
JFlex 1.7.0

  • Field Summary

    Fields
    Modifier and Type
    Field
    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 invalid input: '<'=> the state state is a final state.
    (package private) boolean
    lookaheadUsed
    True iff this DFA contains general lookahead
    static final 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 invalid input: '<'= entryState.length)
    (package private) int
    numStates
    The number of states in this DFA
    private static final 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) Map<Action,Action>
    usedActions
    all actions that are used in this DFA

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    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 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.
    String
    toString()
    Returns a string representation of the DFA.
    String
    toString(int[] a)
    Returns a representation of this DFA.
    (package private) void
    writeDot(File file)
    Writes a dot-file representing this DFA.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • STATES

      private static final int STATES
      The initial number of states
      See Also:

    • NO_TARGET

      public static final int NO_TARGET
      The code for "no target state" in the transition table.
      See Also:

    • 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 invalid input: '<'=> the state state is a final state.

    • action

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

    • entryState

      int[] entryState
      entryState[i] is the start-state of lexical state i or lookahead DFA i

    • numStates

      int numStates
      The number of states in this DFA

    • numInput

      int numInput
      The current maximum number of input characters

    • numLexStates

      int numLexStates
      The number of lexical states (2*numLexStates invalid input: '<'= entryState.length)

    • usedActions

      Map<Action,Action> usedActions
      all actions that are used in this DFA

    • lookaheadUsed

      boolean lookaheadUsed
      True iff this DFA contains general lookahead

  • Constructor Details

    • DFA

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

  • Method Details

    • 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 - 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 String toString()
      Returns a string representation of the DFA.
      Overrides:
      toString in class Object

    • writeDot

      void writeDot(File file)
      Writes a dot-file representing this DFA.
      Parameters:
      file - output file.

    • dotFormat

      private 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.
      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 invalid input: '<' 4*(5*c*n + 13*n + 3*c) byte

    • toString

      public 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