Package jflex.dfa

Class DFA

  • Direct Known Subclasses:
    DeprecatedDfa

    public class DFA
    extends java.lang.Object
    Deterministic finite automata representation in JFlex. Contains minimization algorithm.
    Version:
    JFlex 1.8.2
    • 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 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 int NO_TARGET
      The code for "no target state" in the transition table.
      private int numInput
      The maximum number of input characters
      private int numLexStates
      The number of lexical states (2*numLexStates <= entryState.length)
      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
      private java.util.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

      All Methods Static Methods Instance Methods Concrete Methods 
      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 java.lang.String dotFormat()
      Returns a gnu representation of the DFA.
      private void ensureStateCapacity​(int newNumStates)  
      int entryState​(int i)  
      boolean equals​(java.lang.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)  
      java.lang.String toString()  
      java.lang.String toString​(int[] a)
      Returns a representation of this DFA.
      void writeDot​(java.io.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 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 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 <= 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 java.util.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 Detail

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

        public boolean lookaheadUsed()
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • equals

        public boolean equals​(java.lang.Object obj)
        Overrides:
        equals in class java.lang.Object
      • tableEquals

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

        public 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.
      • 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 java.lang.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)