This file defines forward declarations for various useful NWA-related types. More...

Namespaces
namespace	construct
namespace	details
namespace	experimental
namespace	nwa_pds
namespace	parser
namespace	query
namespace	traverse
Classes
class	ClientInfo
class	NestedWord
	This class represents a single nested word. More...
class	Nwa
	This class models nested word automata (NWA). More...
struct	WaliKey
	Structure for holding Wali keys. More...
struct	FstKey
	Structure for holding OpenFST keys. More...
struct	CallReturnTransitionInserter
struct	EpsilonTransitionInserter
class	WeightGen
	This class is used in NWA::NWAtoPDS and NWA::NWAtoBackwardsPDS. More...
class	ReachGen
class	ShortestPathGen
class	ShortestWordGen
Typedefs
typedef ref_ptr< NestedWord >	NestedWordRefPtr
typedef wali::Key	State
	Globally (within a process) unique ID of a state.
typedef wali::Key	Symbol
	Globally (within a process) unique ID of a symbol.
typedef ref_ptr< Nwa >	NwaRefPtr
	A reference-counted smart pointer to an NWA.
typedef std::set< State >	StateSet
	A set of States.
typedef std::set< Symbol >	SymbolSet
	A set of Symbols.
typedef ref_ptr< ClientInfo >	ClientInfoRefPtr
typedef std::map< std::string, NwaRefPtr >	ProcedureMap
	A collection of named NWAs.
typedef std::map< FstKey, WaliKey >	fst_to_wali_key_map
	Maps a known OpenFST key to the corresponding Wali key.
typedef std::map< WaliKey, FstKey >	wali_to_fst_key_map
	Maps a known Wali key to the corresponding OpenFST key.
typedef std::pair < fst_to_wali_key_map, wali_to_fst_key_map >	fst_wali_key_maps
	Holds bidirectional mappings between Wali and OpenFST keys, to allow bidirectional lookup.
Functions
NwaRefPtr	read_nwa (std::istream &is, std::string *name=NULL)
	Reads a single NWA from 'is'.
ProcedureMap	read_nwa_proc_set (std::istream &is)
	Reads a stream full of NWA descriptions, returning the set of named NWAs.
void	parser_test_all ()
	Run NWA Parser unit tests.
Key	get_wali_key (FstKey fstkey, fst_wali_key_maps const &maps)
StdArc::StateId	get_fst_key (WaliKey walikey, fst_wali_key_maps const &maps)
void	add_fst_state (StdMutableFst &fst, WaliKey walikey, fst_wali_key_maps &maps)
StdVectorFst	internal_only_nwa_to_fst (NwaRefPtr nwa, fst_wali_key_maps *maps=NULL)
	Given an NWA 'nwa' with no call or return transitions, converts 'nwa' to an OpenFST acceptor.
NwaRefPtr	fst_to_nwa (StdExpandedFst const &fst, fst_wali_key_maps &maps, std::string node_prefix)
NwaRefPtr	minimize_internal_nwa (NwaRefPtr internal_nwa, std::string node_prefix="")
	Given an NWA 'internal_nwa' without call or return transitions, treat the NWA as a standard FA and minimize it.
NwaRefPtr	determinize_internal_nwa (NwaRefPtr internal_nwa, std::string node_prefix="")
	Given an NWA 'internal_nwa' without call or return transitions, treat the NWA as a standard FA and determinize it using OpenFST.
NwaRefPtr	fst_to_nwa (fst::StdExpandedFst const &fst, fst_wali_key_maps &maps, std::string node_prefix="")
	Converts an OpenFST acceptor to an NWA.
bool	string_starts_with (std::string const &str, std::string const &prefix)
std::string	remove_prefix (std::string const &str, std::string const &prefix)
NwaRefPtr	assemble_nwa (ProcedureMap const &procedures, boost::function< void(NWA &, State, State)> call_inserter, boost::function< void(NWA &, State, State, State)> return_inserter)
NwaRefPtr	assemble_nwa (ProcedureMap const &procedures, boost::function< void(Nwa &, State, State)> call_inserter, boost::function< void(Nwa &, State, State, State)> return_inserter)
	Assembles all NWAs in 'procedures' into one large NWA.
Variables
const Symbol	EPSILON = wali::WALI_EPSILON
const Symbol	WILD = wali::WALI_WILD

Detailed Description

This file defines forward declarations for various useful NWA-related types.

READ_NWA.

Author:: Amanda Burton

nwa-description ::= ('nwa' name? ':'?)? '{'? block+ '}'? with an opening brace required if 'nwa' is present and name is not (and yes, there must be a space between the name and either : or {)

Reads in an nwa-description

Typedef Documentation

typedef ref_ptr< NestedWord > opennwa::NestedWordRefPtr

typedef wali::Key opennwa::State

Globally (within a process) unique ID of a state.

typedef wali::Key opennwa::Symbol

Globally (within a process) unique ID of a symbol.

typedef ref_ptr<Nwa> opennwa::NwaRefPtr

A reference-counted smart pointer to an NWA.

typedef std::set<State> opennwa::StateSet

A set of States.

(Do not depend on the details of std::set; the type could change to an unordered_set or other type with a similar interface in future versions.)

typedef std::set<Symbol> opennwa::SymbolSet

A set of Symbols.

(Do not depend on the details of std::set; the type could change to an unordered_set or other type with a similar interface in future versions.)

typedef ref_ptr<ClientInfo> opennwa::ClientInfoRefPtr

typedef std::map< std::string, NwaRefPtr > opennwa::ProcedureMap

A collection of named NWAs.

Maps name of procedure to the procedure NWA.

typedef std::map<FstKey, WaliKey> opennwa::fst_to_wali_key_map

Maps a known OpenFST key to the corresponding Wali key.

typedef std::map<WaliKey, FstKey> opennwa::wali_to_fst_key_map

Maps a known Wali key to the corresponding OpenFST key.

typedef std::pair<fst_to_wali_key_map, wali_to_fst_key_map> opennwa::fst_wali_key_maps

Holds bidirectional mappings between Wali and OpenFST keys, to allow bidirectional lookup.

Function Documentation

NwaRefPtr opennwa::read_nwa	(	std::istream &	is,
		std::string *	name = `NULL`
	)

Reads a single NWA from 'is'.

If 'name' is nonnull and the stream specifies a name, store the NWA's name at the location pointed to by 'name'.

Referenced by main().

ProcedureMap opennwa::read_nwa_proc_set ( std::istream & is )

Reads a stream full of NWA descriptions, returning the set of named NWAs.

(The NWAs in the stream better all have unique names, or only the last one of each name will be returned. No attempt is made to verify this fact.)

void opennwa::parser_test_all ( )

Run NWA Parser unit tests.

Key opennwa::get_wali_key	(	FstKey	fstkey,
		fst_wali_key_maps const &	maps
	)

Referenced by fst_to_nwa().

StdArc::StateId opennwa::get_fst_key	(	WaliKey	walikey,
		fst_wali_key_maps const &	maps
	)

void opennwa::add_fst_state	(	StdMutableFst &	fst,
		WaliKey	walikey,
		fst_wali_key_maps &	maps
	)

fst::StdVectorFst opennwa::internal_only_nwa_to_fst	(	NwaRefPtr	nwa,
		fst_wali_key_maps *	maps = `NULL`
	)

Given an NWA 'nwa' with no call or return transitions, converts 'nwa' to an OpenFST acceptor.

If 'fst_wali_key_maps' is non-null, stores the mapping between Wali and OpenFST keys (state IDs) at that location.

Referenced by main().

NwaRefPtr opennwa::fst_to_nwa	(	StdExpandedFst const &	fst,
		fst_wali_key_maps &	maps,
		std::string	node_prefix
	)

References EPSILON, get_wali_key(), and wali::getKey().

Referenced by main().

NwaRefPtr opennwa::minimize_internal_nwa	(	NwaRefPtr	internal_nwa,
		std::string	node_prefix = `""`
	)

Given an NWA 'internal_nwa' without call or return transitions, treat the NWA as a standard FA and minimize it.

(It does this by converting it to an OpenFST acceptor, minimizing that, then converting it back.)

Referenced by assemble_nwa(), and main().

NwaRefPtr opennwa::determinize_internal_nwa	(	NwaRefPtr	internal_nwa,
		std::string	node_prefix = `""`
	)

Given an NWA 'internal_nwa' without call or return transitions, treat the NWA as a standard FA and determinize it using OpenFST.

(It does this by converting it to an OpenFST acceptor, minimizing that, then converting it back.)

NwaRefPtr opennwa::fst_to_nwa	(	fst::StdExpandedFst const &	fst,
		fst_wali_key_maps &	maps,
		std::string	node_prefix = `""`
	)

Converts an OpenFST acceptor to an NWA.

'maps' could specify the mapping to use for the conversion, but the code is broken right now; instead, it is just an output parameter. 'node_prefix' is prepended to the OpenFST key of FST states, and provdies a way to make, say, state 1 of two different FSTs produce different Wali states.

bool opennwa::string_starts_with	(	std::string const &	str,
		std::string const &	prefix
	)

Referenced by assemble_nwa(), and remove_prefix().

std::string opennwa::remove_prefix	(	std::string const &	str,
		std::string const &	prefix
	)

References string_starts_with().

Referenced by assemble_nwa().

NwaRefPtr opennwa::assemble_nwa	(	ProcedureMap const &	procedures,
		boost::function< void(NWA &, State, State)>	call_inserter,
		boost::function< void(NWA &, State, State, State)>	return_inserter
	)

References opennwa::query::getCallSites_Sym(), opennwa::query::getExits_Sym(), opennwa::query::getSources_Sym(), key2str, minimize_internal_nwa(), remove_prefix(), and string_starts_with().

Referenced by main().

NwaRefPtr opennwa::assemble_nwa	(	ProcedureMap const &	procedures,
		boost::function< void(Nwa &, State, State)>	call_inserter,
		boost::function< void(Nwa &, State, State, State)>	return_inserter
	)

Assembles all NWAs in 'procedures' into one large NWA.

Replaces any transition labeled with a symbol '__call__<procname>' with a call transition from the source state to the initial state of the NWA with procedure name 'procname' and a return transition from the final state of the NWA with name 'procname' to the original transition's target state (with the original transition's source state as a predecessor).

The initial state of the NWA named 'main' is the full NWA's start state, and the accepting state of 'main' is the full NWA's accepting state.

Variable Documentation

const Symbol opennwa::EPSILON = wali::WALI_EPSILON

const Symbol opennwa::WILD = wali::WALI_WILD

Referenced by opennwa::Nwa::_private_determinize_(), opennwa::Nwa::_private_isDeterministic_(), opennwa::Nwa::_private_NwaToBackwardsPdsCalls_(), opennwa::Nwa::_private_NwaToBackwardsPdsReturns_(), opennwa::Nwa::_private_NwaToPdsCalls_(), opennwa::Nwa::_private_NwaToPdsReturns_(), opennwa::details::SymbolStorage::addSymbol(), opennwa::details::TransitionStorage::findTrans(), opennwa::Nwa::realizeImplicitTrans(), opennwa::Nwa::removeInternalTrans(), opennwa::Nwa::removeSymbol(), and opennwa::Nwa::transitionIntersect().

opennwa Namespace Reference

Namespaces

Classes

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

Function Documentation

Variable Documentation