Package jflex.dfa

Class DFA

java.lang.Object
jflex.dfa.DFA
Direct Known Subclasses:
DeprecatedDfa
public class DFA extends 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 state state, null if there is no action.
    (package private) static final 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 state state is a final state.
    private boolean
    lookaheadUsed
    True iff this DFA contains general lookahead
    private boolean
    minimized
    Whether the DFA is minimized.
    static final int
    NO_TARGET
    The code for "no target state" in the transition table.
    private final int
    numInput
    The maximum number of input characters
    private final int
    numLexStates
    The number of lexical states (2*numLexStates invalid input: '<'= entryState.length)
    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
    private final Map<Action,Action>
    usedActions
    all actions that are used in this DFA

  • Constructor Summary

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

  • Method Summary

    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 String
    dotFormat()
    Returns a gnu representation of the DFA.
    private void
    ensureStateCapacity(int newNumStates)
     
    int
    entryState(int i)
     
    boolean
    equals(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)
     
    String
    toString()
     
    String
    toString(int[] a)
    Returns a representation of this DFA.
    void
    writeDot(File file)
    Writes a dot-file representing this DFA.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, 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:

    • DFA_DEBUG

      static final boolean DFA_DEBUG
      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 if the state state 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 invalid input: '<'= 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 state state, null if there is no action.

    • usedActions

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

  • Constructor Details

    • DFA

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

    • DFA

      DFA(int numEntryStates, int numInputs, int numLexStates, int numStates)

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

    • lookaheadUsed

      public boolean lookaheadUsed()

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(@Nullable Object obj)
      Overrides:
      equals in class Object

    • tableEquals

      private static boolean tableEquals(int[][] a, int[][] b)

    • writeDot

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

    • 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 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)