public final class NFA
extends java.lang.Object
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) |
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) |
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 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() |
void |
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
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
|
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
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 |
insertNotClassNFA(java.util.List<Interval> intervals,
int start,
int end) |
private IntPair |
insertStringNFA(boolean caseless,
java.lang.String str) |
int |
numEntryStates() |
private void |
removeDead(int start,
int end) |
java.lang.String |
toString() |
void |
writeDot(java.io.File file) |
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)
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)
public void addEpsilonTransition(int start, int dest)
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)
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()
public void dumpTable()
public java.lang.String toString()
toString
in class java.lang.Object
public void writeDot(java.io.File file)
public java.lang.String dotFormat()
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)
nfa
- the NFA to construct the complement for.private void removeDead(int start, int end)
private void insertCCLNFA(RegExp regExp, int start, int end)
regExp
- the regular expression to construct the
NFA forpublic IntPair insertNFA(RegExp regExp)
regExp
- the regular expression to construct the
NFA for