Package jflex.core

Class NFA


  • public final class NFA
    extends java.lang.Object
    Non-deterministic finite automata representation in JFlex.

    Contains algorithms RegExp → NFA.

    Version:
    JFlex 1.8.2
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private Action[] action
      action[current_state]: the action associated with the state current_state (null, if there is no action for the state)
      private CharClasses classes  
      private StateSet[] epsilon
      epsilon[current_state] is the set of states that can be reached from current_state via epsilon edges
      private int estSize
      estimated size of the NFA (before actual construction)
      private boolean[] isFinal
      isFinal[state] == true <=> state is a final state of the NFA
      private int numInput
      the current maximum number of input characters
      private int numLexStates
      the number of lexical States.
      private int numStates
      the number of states in this NFA
      private RegExps regExps  
      private LexScan scanner  
      private StateSetEnumerator states  
      private StateSet[][] table
      table[current_state][next_char] is the set of states that can be reached from current_state with an input next_char
      private StateSet tempStateSet  
    • Constructor Summary

      Constructors 
      Constructor Description
      NFA​(int numInput, int estSize)
      Constructor for NFA.
      NFA​(int numInput, LexScan scanner, RegExps regExps, Macros macros, CharClasses classes)
      Construct new NFA.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addEpsilonTransition​(int start, int dest)  
      void addRegExp​(int regExpNum)
      Add a regexp to this NFA.
      void addStandaloneRule()
      Add a standalone rule that has minimum priority, fires a transition on all single input characters and has a "print yytext" action.
      void addTransition​(int start, int input, int dest)  
      private StateSet closure​(int startState)
      Calculates the epsilon closure for a specified set of states.
      private IntPair complement​(IntPair nfa)
      Constructs an NFA accepting the complement of the language of a given NFA.
      boolean containsFinal​(StateSet set)
      Returns true, iff the specified set of states contains a final state.
      private StateSet DFAEdge​(StateSet start, int input)
      Calculates the set of states that can be reached from another set of states start with an specified input character input
      java.lang.String dotFormat()  
      void dumpTable()  
      private void ensureCapacity​(int newNumStates)
      Make sure the NFA can contain at least newNumStates states.
      StateSet epsilon​(int i)  
      void epsilonFill()  
      Action getAction​(StateSet set)
      Returns the action with highest priority in the specified set of states.
      private void insertCCLNFA​(RegExp regExp, int start, int end)
      Constructs a two state NFA for char class regexps, such that the NFA has exactly one start state, exactly one end state, no transitions leading out of the end state, no transitions leading into the start state.
      private void insertClassNFA​(IntCharSet set, int start, int end)  
      private void insertLetterNFA​(boolean caseless, int ch, int start, int end)  
      private void insertLookAheadChoices​(int baseEnd, Action a, RegExp lookAhead)
      Insert NFAs for the (finitely many) fixed length lookahead choices.
      IntPair insertNFA​(RegExp regExp)
      Constructs an NFA for regExp such that the NFA has
      private IntPair insertStringNFA​(boolean caseless, java.lang.String str)  
      int numEntryStates()  
      int numInput()  
      int numLexStates()  
      int numStates()  
      StateSet reachableStates​(int currentState, int nextChar)
      Returns the set of states that can be reached from currentState with an input nextChar.
      private void removeDead​(int start, int end)
      Find all states from (numerically) start to @end that (transitively) cannot reach reach end, and remove the transitions leading to those states.
      StateSetEnumerator states()  
      StateSet tempStateSet()  
      java.lang.String toString()  
      void writeDot​(java.io.File file)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • table

        private StateSet[][] table
        table[current_state][next_char] is the set of states that can be reached from current_state with an input next_char
      • epsilon

        private StateSet[] epsilon
        epsilon[current_state] is the set of states that can be reached from current_state via epsilon edges
      • isFinal

        private boolean[] isFinal
        isFinal[state] == true <=> state is a final state of the NFA
      • action

        private Action[] action
        action[current_state]: the action associated with the state current_state (null, if there is no action for the state)
      • numStates

        private int numStates
        the number of states in this NFA
      • numInput

        private final int numInput
        the current maximum number of input characters
      • numLexStates

        private int numLexStates
        the number of lexical States. Lexical states have the indices 0..numLexStates-1 in the transition table
      • estSize

        private final int estSize
        estimated size of the NFA (before actual construction)
      • tempStateSet

        private final StateSet tempStateSet
    • Constructor Detail

      • NFA

        public NFA​(int numInput,
                   int estSize)
        Constructor for NFA.
    • Method Detail

      • epsilon

        public StateSet epsilon​(int i)
      • numEntryStates

        public int numEntryStates()
      • numInput

        public int numInput()
      • numLexStates

        public int numLexStates()
      • numStates

        public int numStates()
      • reachableStates

        public StateSet reachableStates​(int currentState,
                                        int nextChar)
        Returns the set of states that can be reached from currentState with an input nextChar.
      • tempStateSet

        public StateSet tempStateSet()
      • addStandaloneRule

        public void addStandaloneRule()
        Add a standalone rule that has minimum priority, fires a transition on all single input characters and has a "print yytext" action.
      • addRegExp

        public void addRegExp​(int regExpNum)
        Add a regexp to this NFA.
        Parameters:
        regExpNum - the number of the regexp to add.
      • insertLookAheadChoices

        private void insertLookAheadChoices​(int baseEnd,
                                            Action a,
                                            RegExp lookAhead)
        Insert NFAs for the (finitely many) fixed length lookahead choices.
        Parameters:
        lookAhead - a lookahead of which isFiniteChoice is true
        baseEnd - the end state of the base expression NFA
        a - the action of the expression
        See Also:
        SemCheck.isFiniteChoice(RegExp)
      • ensureCapacity

        private void ensureCapacity​(int newNumStates)
        Make sure the NFA can contain at least newNumStates states.
        Parameters:
        newNumStates - the minimum number of states.
      • addTransition

        public void addTransition​(int start,
                                  int input,
                                  int dest)
      • addEpsilonTransition

        public void addEpsilonTransition​(int start,
                                         int dest)
      • containsFinal

        public boolean containsFinal​(StateSet set)
        Returns true, iff the specified set of states contains a final state.
        Parameters:
        set - the set of states that is tested for final states.
      • getAction

        public Action getAction​(StateSet set)
        Returns the action with highest priority in the specified set of states.
        Parameters:
        set - the set of states for which to determine the action
      • closure

        private StateSet closure​(int startState)
        Calculates the epsilon closure for a specified set of states.

        The epsilon closure for set a is the set of states that can be reached by epsilon edges from a.

        Parameters:
        startState - the start state for the set of states to calculate the epsilon closure for
        Returns:
        the epsilon closure of the specified set of states in this NFA
      • epsilonFill

        public void epsilonFill()
      • DFAEdge

        private StateSet DFAEdge​(StateSet start,
                                 int input)
        Calculates the set of states that can be reached from another set of states start with an specified input character input
        Parameters:
        start - the set of states to start from
        input - the input character for which to search the next states
        Returns:
        the set of states that are reached from start</code> via <code>input
      • dumpTable

        public void dumpTable()
      • toString

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

        public void writeDot​(java.io.File file)
      • dotFormat

        public java.lang.String dotFormat()
      • insertLetterNFA

        private void insertLetterNFA​(boolean caseless,
                                     int ch,
                                     int start,
                                     int end)
      • insertStringNFA

        private IntPair insertStringNFA​(boolean caseless,
                                        java.lang.String str)
      • insertClassNFA

        private void insertClassNFA​(IntCharSet set,
                                    int start,
                                    int end)
      • complement

        private IntPair complement​(IntPair nfa)
        Constructs an NFA accepting the complement of the language of a given NFA.

        Converts the NFA into a DFA, then negates that DFA. Exponential state blowup possible and common.

        Parameters:
        nfa - the NFA to construct the complement for.
        Returns:
        a pair of integers denoting the index of start and end state of the complement NFA.
      • removeDead

        private void removeDead​(int start,
                                int end)
        Find all states from (numerically) start to @end that (transitively) cannot reach reach end, and remove the transitions leading to those states.

        After a complement operation, there may be dead states left over in the NFA, which could lead the scanning engine into a situation where it is trying to perform lookahead even though no final state can ever be reached.

        Precondition: all states that potentially lead to end are within the interval @{code [start,end]}. This is satisfied by DFA generation in the complement operation.

        Precondition: end state has no outgoing transitions

        Parameters:
        start - the first state from which to compute live states
        end - the state that if it can be reached makes a state live
        See Also:
        complement(IntPair)
      • insertCCLNFA

        private void insertCCLNFA​(RegExp regExp,
                                  int start,
                                  int end)
        Constructs a two state NFA for char class regexps, such that the NFA has
        • exactly one start state,
        • exactly one end state,
        • no transitions leading out of the end state,
        • no transitions leading into the start state.

        Assumes that regExp.isCharClass(macros) == true

        Parameters:
        regExp - the regular expression to construct the NFA for
      • insertNFA

        public IntPair insertNFA​(RegExp regExp)
        Constructs an NFA for regExp such that the NFA has

        exactly one start state, exactly one end state, no transitions leading out of the end state no transitions leading into the start state

        Parameters:
        regExp - the regular expression to construct the NFA for
        Returns:
        a pair of integers denoting the index of start and end state of the NFA.