Package jflex

Class DFA

  • public final class DFA
extends java.lang.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 <=> the state state is a final state.
      (package private) boolean lookaheadUsed
      True iff this DFA contains general lookahead
      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 numLexStates
      The number of lexical states (2*numLexStates <= entryState.length)
      (package private) int numStates
      The number of states in this DFA
      private static 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) java.util.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

      All Methods Instance Methods Concrete Methods 
      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 java.lang.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.
      java.lang.String toString()
      Returns a string representation of the DFA.
      java.lang.String toString​(int[] a)
      Returns a representation of this DFA.
      (package private) void writeDot​(java.io.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 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.

      • 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 <= entryState.length)

      • usedActions

        java.util.Map<Action,​Action> usedActions
        all actions that are used in this DFA

      • lookaheadUsed

        boolean lookaheadUsed
        True iff this DFA contains general lookahead

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

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

      • writeDot

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

      • dotFormat

        private java.lang.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 < 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