Package jflex

Class NFA

java.lang.Object

jflex.NFA

public final class NFA
extends java.lang.Object

Non-deterministic finite automata representation in JFlex.

Contains algorithms RegExp → NFA and NFA → DFA.

Version:

JFlex 1.7.0

Field Summary

Fields

Modifier and Type	Field	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 Summary

Constructors

Constructor	Description
NFA(int numInput, int estSize)	Constructor for NFA.
NFA(int numInput, LexScan scanner, RegExps regExps, Macros macros, CharClasses classes)	Construct new NFA.

Method Summary

Modifier and Type	Method	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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

table

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

StateSet[] epsilon

epsilon[current_state] is the set of states that can be reached from current_state via epsilon edges

isFinal

boolean[] isFinal

isFinal[state] == true <=> state is a final state of the NFA

action

Action[] action

action[current_state]: the action associated with the state current_state (null, if there is no action for the state)

numStates

int numStates

the number of states in this NFA

numInput

int numInput

the current maximum number of input characters

numLexStates

int numLexStates

the number of lexical States. Lexical states have the indices 0..numLexStates-1 in the transition table

estSize

int estSize

estimated size of the NFA (before actual construction)

macros

Macros macros

classes

CharClasses classes

scanner

LexScan scanner

regExps

RegExps regExps

states

private static StateSetEnumerator states

tempStateSet

private static StateSet tempStateSet

live

private boolean[] live

visited

private boolean[] visited

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 - a LexScan object.

regExps - a RegExps object.

macros - a Macros object.

classes - a CharClasses object.

See Also:

RegExps.checkLookAheads()

Method Detail

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

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 true

baseEnd - the end state of the base expression NFA

a - 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 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

private 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

private 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

closure

private StateSet closure(StateSet startStates)

Returns the epsilon closure of a set of states

epsilonFill

private 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 via input

getDFA

public DFA 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

public java.lang.String toString()

toString.

Overrides:

toString in class java.lang.Object

Returns:

a String object.

writeDot

public void writeDot(java.io.File file)

writeDot.

Parameters:

file - a File object.

dotFormat

public java.lang.String dotFormat()

dotFormat.

Returns:

a String object.

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(java.util.List<Interval> intervals,
                            int start,
                            int end)

insertNotClassNFA

private void insertNotClassNFA(java.util.List<Interval> intervals,
                               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)

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.