Archon::Utilities::NFA Class Reference

Nondeterministic finite state automata (NFA). More...

#include <archon/util/nfa.H>

Collaboration diagram for Archon::Utilities::NFA:

[legend]List of all members.

Public Member Functions
	NFA ()
	Make a special null NFA that behaves like an NFA that accepts nothing in an alternation and like an NFA that accepts the empty string in a concattenation.
	NFA (basic_string< unsigned > s, int finalValue=0)
	Accept the specified string.
	NFA (unsigned begin, unsigned end, int finalValue=0)
	Accept any symbol s such that 'begin' <= s <= 'end'.
	NFA (const vector< pair< unsigned, unsigned > > &ranges, int finalValue=0)
	Accept any symbol s from any of the ranges of 'ranges'.
	NFA (const DFA &)
	Make an NFA that is identical to the DFA passed as argument.
	NFA (const Regex &, int finalValue=0)
	Make an NFA that accepts the same language as the regular expression passed as argument.
void	altern (const NFA &)
	Make this NFA accept anything that it did before and anything that the argument NFA accepts.
void	concat (const NFA &)
	Make this NFA accept anything that it did before followed by anything that the argument NFA accepts.
void	repeat (bool includeZero=false, int finalValue=0)
	Make this NFA accept one or more occurances of what it accepted before or if 'includeZero' is true then zero or more occurances of what it accepted before.
void	setFinalValue (int finalValue)
int	addStartState (int finalValue=-1)
	Add a new start state to the NFA.
int	addState (int finalValue=-1)
	Add a new state to the NFA.
void	addEdge (int originalState, int targetState)
	Add an epsilon edge between two states.
void	addEdge (int originalState, int targetState, unsigned symbol)
	Add an edge between two states.
void	addEdge (int originalState, int targetState, unsigned begin, unsigned end)
	Add a range of edges between two states.
string	print (const Printer &printer=getDefaultPrinter(), int width=0) const
Static Public Member Functions
static const Printer &	getDefaultPrinter ()
Classes
struct	Edge
struct	Printer
struct	State

---

Detailed Description

Nondeterministic finite state automata (NFA).

As an extension to a standard NFA, this one may have more than one start state.

Definition at line 46 of file nfa.H.

---

Constructor & Destructor Documentation

Archon::Utilities::NFA::NFA (   )  [inline]

Make a special null NFA that behaves like an NFA that accepts nothing in an alternation and like an NFA that accepts the empty string in a concattenation. Also the alternation of two null NFA's and the concattenation of two null NFA's and the repetition of a null NFA all yields a null NFA. Definition at line 86 of file nfa.H.

Archon::Utilities::NFA::NFA (  basic_string< unsigned >  s, int  finalValue = 0 )

Accept the specified string. Parameters: finalValue  Should not be negative unless you want an automaton that accepts nothing. Definition at line 406 of file nfa.C.

Archon::Utilities::NFA::NFA (  unsigned  begin, unsigned  end, int  finalValue = 0 )

Accept any symbol s such that 'begin' <= s <= 'end'. Parameters: finalValue  Should not be negative unless you want an automaton that accepts nothing. Definition at line 415 of file nfa.C.

Archon::Utilities::NFA::NFA (  const vector< pair< unsigned, unsigned > > &  ranges, int  finalValue = 0 )

Accept any symbol s from any of the ranges of 'ranges'. Each range must have a first component that is less than or equal to its second component. Definition at line 424 of file nfa.C.

---

Member Function Documentation

void Archon::Utilities::NFA::addEdge (  int  originalState, int  targetState, unsigned  begin, unsigned  end )

Add a range of edges between two states. The range starts with 'begin' and ends with 'end' both inclusive. Definition at line 571 of file nfa.C.

int Archon::Utilities::NFA::addStartState (  int  finalValue = -1  )

Add a new start state to the NFA. Parameters: finalValue  is -1 if the new state is not a final state. Different non-negative final values can be used to distinguish the final states, and this feature is used by the regular expression controlled lexer for example. Returns: the identifier for the new start state. See also: addState(int) Definition at line 554 of file nfa.C. References addState(). Referenced by Archon::Utilities::ClrParser::ClrParser(), and Archon::Utilities::SlrParser::SlrParser().

int Archon::Utilities::NFA::addState (  int  finalValue = -1  )

Add a new state to the NFA. Parameters: finalValue  is -1 if the new state is not a final state. Different non-negative final values can be used to distinguish the final states, and this feature is used by the regular expression controlled lexer for example. Returns: the identifier for the new state. See also: addStartState(int) Definition at line 560 of file nfa.C. Referenced by addStartState(), Archon::Utilities::ClrParser::ClrParser(), and Archon::Utilities::SlrParser::SlrParser().

void Archon::Utilities::NFA::altern (  const NFA &   )

Make this NFA accept anything that it did before and anything that the argument NFA accepts. Both NFA's must have exactly one start state. Definition at line 437 of file nfa.C. References m, n, startStates, and states. Referenced by Archon::Utilities::Lexer::Engine::Engine().

void Archon::Utilities::NFA::concat (  const NFA &   )

Make this NFA accept anything that it did before followed by anything that the argument NFA accepts. The argument NFA must have exactly one start state. Definition at line 467 of file nfa.C. References m, n, startStates, and states.

void Archon::Utilities::NFA::repeat (  bool  includeZero = false, int  finalValue = 0 )

Make this NFA accept one or more occurances of what it accepted before or if 'includeZero' is true then zero or more occurances of what it accepted before. This NFA must have exactly one start state. Definition at line 498 of file nfa.C. References n.

void Archon::Utilities::NFA::setFinalValue (  int  finalValue  )

Parameters: finalValue  Should not be negative unless you want an automaton that accepts nothing. Definition at line 533 of file nfa.C. Referenced by NFA().

---

The documentation for this class was generated from the following files:

• archon/util/nfa.H
• archon/util/nfa.C

---