Package jflex

Class NFA


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

    Contains algorithms RegExp → NFA and NFA → DFA.

    Version:
    JFlex 1.7.0
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) Action[] action
      action[current_state]: the action associated with the state current_state (null, if there is no action for the state)
      (package private) CharClasses classes  
      (package private) StateSet[] epsilon
      epsilon[current_state] is the set of states that can be reached from current_state via epsilon edges
      (package private) int estSize
      estimated size of the NFA (before actual construction)
      (package private) boolean[] isFinal
      isFinal[state] == true <=> state is a final state of the NFA
      private boolean[] live  
      (package private) Macros macros  
      (package private) int numInput
      the current maximum number of input characters
      (package private) int numLexStates
      the number of lexical States.
      (package private) int numStates
      the number of states in this NFA
      (package private) RegExps regExps  
      (package private) LexScan scanner  
      private static StateSetEnumerator states  
      (package 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 static StateSet tempStateSet  
      private boolean[] visited  
    • 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)
      addEpsilonTransition.
      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)
      addTransition.
      private StateSet closure​(int startState)
      Calculates the epsilon closure for a specified set of states.
      private StateSet closure​(StateSet startStates)
      Returns the epsilon closure of a set of states
      private IntPair complement​(IntPair nfa)
      Constructs an NFA accepting the complement of the language of a given NFA.
      private 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()
      dotFormat.
      void dumpTable()
      dumpTable.
      private void ensureCapacity​(int newNumStates)
      Make sure the NFA can contain at least newNumStates states.
      private void epsilonFill()  
      private Action getAction​(StateSet set)
      Returns the action with highest priority in the specified set of states.
      DFA getDFA()
      Returns an DFA that accepts the same language as this NFA.
      private void insertCCLNFA​(RegExp regExp, int start, int end)
      Constructs a two state NFA for char class regexps, such that the NFA has
      private void insertClassNFA​(java.util.List<Interval> intervals, 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 void insertNotClassNFA​(java.util.List<Interval> intervals, int start, int end)  
      private IntPair insertStringNFA​(boolean caseless, java.lang.String str)  
      int numEntryStates()
      numEntryStates.
      private void removeDead​(int start, int end)  
      java.lang.String toString()
      toString.
      void writeDot​(java.io.File file)
      writeDot.
      • Methods inherited from class java.lang.Object

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

      • table

        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

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

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

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

        int numStates
        the number of states in this NFA
      • numInput

        int numInput
        the current maximum number of input characters
      • numLexStates

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

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

        private static StateSet tempStateSet
      • live

        private boolean[] live
      • visited

        private boolean[] visited
    • Constructor Detail

      • NFA

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

      • numEntryStates

        public int numEntryStates()
        numEntryStates.
        Returns:
        a int.
      • 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 minimu number of states.
      • addTransition

        public void addTransition​(int start,
                                  int input,
                                  int dest)
        addTransition.
        Parameters:
        start - a int.
        input - a int.
        dest - a int.
      • addEpsilonTransition

        public void addEpsilonTransition​(int start,
                                         int dest)
        addEpsilonTransition.
        Parameters:
        start - a int.
        dest - a int.
      • containsFinal

        private 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

        private 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
      • closure

        private StateSet closure​(StateSet startStates)
        Returns the epsilon closure of a set of states
      • epsilonFill

        private 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 via input
      • getDFA

        public DFA getDFA()
        Returns an DFA that accepts the same language as this NFA. This DFA is usually not minimal.
        Returns:
        a DFA object.
      • dumpTable

        public void dumpTable()
        dumpTable.
      • toString

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

        public void writeDot​(java.io.File file)
        writeDot.
        Parameters:
        file - a File object.
      • dotFormat

        public java.lang.String dotFormat()
        dotFormat.
        Returns:
        a String object.
      • 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​(java.util.List<Interval> intervals,
                                    int start,
                                    int end)
      • insertNotClassNFA

        private void insertNotClassNFA​(java.util.List<Interval> intervals,
                                       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)
      • 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.