Package jflex.core

Class NFA

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

Contains algorithms RegExp → NFA.

Version:
JFlex 1.9.1

  • Field Details

    • 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 invalid input: '<'=> 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)

    • classes

      private CharClasses classes

    • scanner

      private LexScan scanner

    • regExps

      private RegExps regExps

    • states

      private final StateSetEnumerator states

    • tempStateSet

      private final StateSet tempStateSet

  • Constructor Details

    • NFA

      public NFA(int numInput, int estSize)
      Constructor for NFA.

    • NFA

      public NFA(int numInput, LexScan scanner, RegExps regExps, Macros macros, CharClasses classes)
      Construct new NFA.

      Assumes that lookahead cases and numbers are already resolved in RegExps.

      Parameters:
      numInput - a int.
      scanner - a LexScan object.
      regExps - a RegExps object.
      macros - a Macros object.
      classes - a CharClasses object.
      See Also:

  • Method Details

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

    • states

      public StateSetEnumerator states()

    • 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:
      baseEnd - the end state of the base expression NFA
      a - the action of the expression
      lookAhead - a lookahead of which isFiniteChoice is true
      See Also:

    • 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 String toString()
      Overrides:
      toString in class Object

    • writeDot

      public void writeDot(File file)

    • dotFormat

      public String dotFormat()

    • insertLetterNFA

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

    • insertStringNFA

      private IntPair insertStringNFA(boolean caseless, 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:

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