Package jflex
Class NFA
java.lang.Object
jflex.NFA
Non-deterministic finite automata representation in JFlex.
Contains algorithms RegExp → NFA and NFA → DFA.
- Version:
- JFlex 1.7.0
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) Action[]
action[current_state]: the action associated with the state current_state (null, if there is no action for the state)(package private) CharClasses
(package private) StateSet[]
epsilon[current_state] is the set of states that can be reached from current_state via epsilon edges(package private) int
estimated size of the NFA (before actual construction)(package private) boolean[]
isFinal[state] == true <=> state is a final state of the NFAprivate boolean[]
(package private) Macros
(package private) int
the current maximum number of input characters(package private) int
the number of lexical States.(package private) int
the number of states in this NFA(package private) RegExps
(package private) LexScan
private static StateSetEnumerator
(package private) StateSet[][]
table[current_state][next_char] is the set of states that can be reached from current_state with an input next_charprivate static StateSet
private boolean[]
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
addEpsilonTransition
(int start, int dest) addEpsilonTransition.void
addRegExp
(int regExpNum) Add a regexp to this NFA.void
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
Returns the epsilon closure of a set of statesprivate IntPair
complement
(IntPair nfa) Constructs an NFA accepting the complement of the language of a given NFA.private boolean
containsFinal
(StateSet set) Returnstrue
, iff the specified set of states contains a final state.private StateSet
Calculates the set of states that can be reached from another set of statesstart
with an specified input characterinput
dotFormat.void
dumpTable.private void
ensureCapacity
(int newNumStates) Make sure the NFA can contain at least newNumStates states.private void
private Action
Returns the action with highest priority in the specified set of states.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 hasprivate void
insertClassNFA
(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.Constructs an NFA for regExp such that the NFA hasprivate void
insertNotClassNFA
(List<Interval> intervals, int start, int end) private IntPair
insertStringNFA
(boolean caseless, String str) int
numEntryStates.private void
removeDead
(int start, int end) toString()
toString.void
writeDot.
-
Field Details
-
table
StateSet[][] tabletable[current_state][next_char] is the set of states that can be reached from current_state with an input next_char -
epsilon
StateSet[] epsilonepsilon[current_state] is the set of states that can be reached from current_state via epsilon edges -
isFinal
boolean[] isFinalisFinal[state] == true <=> state is a final state of the NFA -
action
Action[] actionaction[current_state]: the action associated with the state current_state (null, if there is no action for the state) -
numStates
int numStatesthe number of states in this NFA -
numInput
int numInputthe current maximum number of input characters -
numLexStates
int numLexStatesthe number of lexical States. Lexical states have the indices 0..numLexStates-1 in the transition table -
estSize
int estSizeestimated size of the NFA (before actual construction) -
macros
Macros macros -
classes
CharClasses classes -
scanner
LexScan scanner -
regExps
RegExps regExps -
states
-
tempStateSet
-
live
private boolean[] live -
visited
private boolean[] visited
-
-
Constructor Details
-
NFA
public NFA(int numInput, int estSize) Constructor for NFA. -
NFA
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:
-
-
Method Details
-
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
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:
-
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
Returnstrue
, iff the specified set of states contains a final state.- Parameters:
set
- the set of states that is tested for final states.
-
getAction
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
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
Returns the epsilon closure of a set of states -
epsilonFill
private void epsilonFill() -
DFAEdge
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
viainput
-
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
toString. -
writeDot
writeDot.- Parameters:
file
- aFile
object.
-
dotFormat
dotFormat.- Returns:
- a
String
object.
-
insertLetterNFA
private void insertLetterNFA(boolean caseless, int ch, int start, int end) -
insertStringNFA
-
insertClassNFA
-
insertNotClassNFA
-
complement
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
Constructs a two state NFA for char class regexps, 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
Assumes that regExp.isCharClass(macros) == true
- Parameters:
regExp
- the regular expression to construct the NFA for
-
insertNFA
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.
-