public final class NFA
extends java.lang.Object
Contains algorithms RegExp → NFA and NFA → DFA.
Modifier and Type | Field and 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 and Description |
---|
NFA(int numInput,
int estSize)
Constructor for NFA.
|
NFA(int numInput,
LexScan scanner,
RegExps regExps,
Macros macros,
CharClasses classes)
Construct new NFA.
|
Modifier and Type | Method and 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.
|
StateSet[][] table
StateSet[] epsilon
boolean[] isFinal
Action[] action
int numStates
int numInput
int numLexStates
int estSize
Macros macros
CharClasses classes
LexScan scanner
RegExps regExps
private static StateSetEnumerator states
private static StateSet tempStateSet
private boolean[] live
private boolean[] visited
public NFA(int numInput, int estSize)
public NFA(int numInput, LexScan scanner, RegExps regExps, Macros macros, CharClasses classes)
Assumes that lookahead cases and numbers are already resolved in RegExps.
numInput
- a int.scanner
- a LexScan
object.regExps
- a RegExps
object.macros
- a Macros
object.classes
- a CharClasses
object.RegExps.checkLookAheads()
public int numEntryStates()
public void addStandaloneRule()
public void addRegExp(int regExpNum)
regExpNum
- the number of the regexp to add.private void insertLookAheadChoices(int baseEnd, Action a, RegExp lookAhead)
lookAhead
- a lookahead of which isFiniteChoice is truebaseEnd
- the end state of the base expression NFAa
- the action of the expressionSemCheck.isFiniteChoice(RegExp)
private void ensureCapacity(int newNumStates)
newNumStates
- the minimu number of states.public void addTransition(int start, int input, int dest)
start
- a int.input
- a int.dest
- a int.public void addEpsilonTransition(int start, int dest)
start
- a int.dest
- a int.private boolean containsFinal(StateSet set)
true
, iff the specified set of states contains a final state.set
- the set of states that is tested for final states.private Action getAction(StateSet set)
set
- the set of states for which to determine the actionprivate StateSet closure(int startState)
The epsilon closure for set a is the set of states that can be reached by epsilon edges from a.
startState
- the start state for the set of states to calculate the epsilon closure forprivate StateSet closure(StateSet startStates)
private void epsilonFill()
private StateSet DFAEdge(StateSet start, int input)
start
with an specified input character input
start
- the set of states to start frominput
- the input character for which to search the next statesstart
via input
public DFA getDFA()
DFA
object.public void dumpTable()
public java.lang.String toString()
toString
in class java.lang.Object
String
object.public void writeDot(java.io.File file)
file
- a File
object.public java.lang.String dotFormat()
String
object.private void insertLetterNFA(boolean caseless, int ch, int start, int end)
private IntPair insertStringNFA(boolean caseless, java.lang.String str)
private void insertClassNFA(java.util.List<Interval> intervals, int start, int end)
private void insertNotClassNFA(java.util.List<Interval> intervals, int start, int end)
private IntPair complement(IntPair nfa)
Converts the NFA into a DFA, then negates that DFA. Exponential state blowup possible and common.
nfa
- the NFA to construct the complement for.private void removeDead(int start, int end)
private void insertCCLNFA(RegExp regExp, int start, int end)
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
regExp
- the regular expression to construct the NFA forpublic IntPair insertNFA(RegExp regExp)
exactly one start state, exactly one end state, no transitions leading out of the end state no transitions leading into the start state
regExp
- the regular expression to construct the NFA for