Class NFA
- java.lang.Object
-
- jflex.core.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 edgesprivate int
estSize
estimated size of the NFA (before actual construction)private boolean[]
isFinal
isFinal[state] == true <=> state is a final state of the NFAprivate int
numInput
the current maximum number of input charactersprivate int
numLexStates
the number of lexical States.private int
numStates
the number of states in this NFAprivate 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_charprivate StateSet
tempStateSet
-
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)
Returnstrue
, 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 statesstart
with an specified input characterinput
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 hasprivate 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 reachend
, and remove the transitions leading to those states.StateSetEnumerator
states()
StateSet
tempStateSet()
java.lang.String
toString()
void
writeDot(java.io.File file)
-
-
-
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)
-
classes
private CharClasses classes
-
scanner
private LexScan scanner
-
regExps
private RegExps regExps
-
states
private final StateSetEnumerator states
-
tempStateSet
private final StateSet tempStateSet
-
-
Constructor Detail
-
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
- aLexScan
object.regExps
- aRegExps
object.macros
- aMacros
object.classes
- aCharClasses
object.- See Also:
RegExps.checkLookAheads()
-
-
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.
-
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:
lookAhead
- a lookahead of which isFiniteChoice is truebaseEnd
- the end state of the base expression NFAa
- 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)
Returnstrue
, 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 statesstart
with an specified input characterinput
- Parameters:
start
- the set of states to start frominput
- 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 classjava.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 reachend
, 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 statesend
- 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 hasexactly 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.
-
-