Chomsky normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free languages. More...

#include <CNF.h>

Inheritance diagram for grammar::CNF< TerminalSymbolType, NonterminalSymbolType >:

[legend]

Collaboration diagram for grammar::CNF< TerminalSymbolType, NonterminalSymbolType >:

[legend]

Public Member Functions
	CNF (NonterminalSymbolType initialSymbol)
	Creates a new instance of the grammar with a concrete initial symbol. More...

	CNF (ext::set< NonterminalSymbolType > nonterminalAlphabet, ext::set< TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol)
	Creates a new instance of the grammar with a concrete nonterminal alphabet, terminal alphabet and initial symbol. More...

bool	addRule (NonterminalSymbolType leftHandSide, ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > rightHandSide)
	Add a new rule of a grammar. More...

void	addRules (NonterminalSymbolType leftHandSide, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > rightHandSide)
	Add new rules of a grammar. More...

const ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > > &	getRules () const &

ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > > &&	getRules () &&

bool	removeRule (const NonterminalSymbolType &leftHandSide, const ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > &rightHandSide)

bool	removeRule (const NonterminalSymbolType &leftHandSide, const TerminalSymbolType &rightHandSide)

bool	removeRule (const NonterminalSymbolType &leftHandSide, const ext::pair< NonterminalSymbolType, NonterminalSymbolType > &rightHandSide)

const NonterminalSymbolType &	getInitialSymbol () const &

NonterminalSymbolType &&	getInitialSymbol () &&

bool	setInitialSymbol (NonterminalSymbolType symbol)

const ext::set< NonterminalSymbolType > &	getNonterminalAlphabet () const &

ext::set< NonterminalSymbolType > &&	getNonterminalAlphabet () &&

bool	addNonterminalSymbol (NonterminalSymbolType symbol)

void	setNonterminalAlphabet (ext::set< NonterminalSymbolType > symbols)

const ext::set< TerminalSymbolType > &	getTerminalAlphabet () const &

ext::set< TerminalSymbolType > &&	getTerminalAlphabet () &&

bool	addTerminalSymbol (TerminalSymbolType symbol)

void	setTerminalAlphabet (ext::set< TerminalSymbolType > symbols)

void	setGeneratesEpsilon (bool genEps)

bool	getGeneratesEpsilon () const

auto	operator<=> (const CNF &other) const

bool	operator== (const CNF &other) const

Public Member Functions inherited from core::Components< CNF< DefaultSymbolType, DefaultSymbolType >, ext::set< DefaultSymbolType >, component::Set, TerminalAlphabet, ext::set< DefaultSymbolType >, component::Set, NonterminalAlphabet, DefaultSymbolType, component::Value, InitialSymbol >
void	accessComponent ()

Friends
ext::ostream &	operator<< (ext::ostream &out, const CNF &instance)

Additional Inherited Members
Static Public Member Functions inherited from core::Components< CNF< DefaultSymbolType, DefaultSymbolType >, ext::set< DefaultSymbolType >, component::Set, TerminalAlphabet, ext::set< DefaultSymbolType >, component::Set, NonterminalAlphabet, DefaultSymbolType, component::Value, InitialSymbol >
static void	registerComponent ()

static void	unregisterComponent ()

Detailed Description

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>
class grammar::CNF< TerminalSymbolType, NonterminalSymbolType >

Chomsky normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free languages.

Definition is similar to all common definitions of context free grammars. G = (N, T, P, S), N (NonterminalAlphabet) = nonempty finite set of nonterminal symbols, T (TerminalAlphabet) = finite set of terminal symbols - having this empty won't let grammar do much though, P = set of production rules of the form A -> BC or A -> a, where A, B, C \in N and a \in T, S (InitialSymbol) = initial nonterminal symbol,

Template Parameters

TerminalSymbolType	used for the terminal alphabet of the grammar.
NonterminalSymbolType	used for the nonterminal alphabet, and the initial symbol of the grammar.

Constructor & Destructor Documentation

◆ CNF() [1/2]

template<class TerminalSymbolType , class NonterminalSymbolType >

grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::CNF ( NonterminalSymbolType initialSymbol )

explicit

Creates a new instance of the grammar with a concrete initial symbol.

Parameters

initialSymbol the initial symbol of the grammar

◆ CNF() [2/2]

template<class TerminalSymbolType , class NonterminalSymbolType >

grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::CNF	(	ext::set< NonterminalSymbolType >	nonterminalAlphabet,
		ext::set< TerminalSymbolType >	terminalAlphabet,
		NonterminalSymbolType	initialSymbol
	)

explicit

Creates a new instance of the grammar with a concrete nonterminal alphabet, terminal alphabet and initial symbol.

Parameters

nonTerminalSymbols	the initial nonterminal alphabet
terminalSymbols	the initial terminal alphabet
initialSymbol	the initial symbol of the grammar

Member Function Documentation

◆ addNonterminalSymbol()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::addNonterminalSymbol ( NonterminalSymbolType symbol )

inline

Adder of nonterminal symbol.

Parameters

symbol the new symbol to be added to nonterminal alphabet

Returns: true if the symbol was indeed added

◆ addRule()

template<class TerminalSymbolType , class NonterminalSymbolType >

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::addRule	(	NonterminalSymbolType	leftHandSide,
		ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > >	rightHandSide
	)

Add a new rule of a grammar.

The rule is in a form of A -> BC or A -> a, where A, B, C, \in N and a \in T.

Parameters

leftHandSide	the left hand side of the rule
rightHandSide	the right hand side of the rule

Returns: true if the rule was indeed added, false othervise

Here is the call graph for this function:

◆ addRules()

template<class TerminalSymbolType , class NonterminalSymbolType >

void grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::addRules	(	NonterminalSymbolType	leftHandSide,
		ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > >	rightHandSide
	)

Add new rules of a grammar.

The rules are in form of A -> BC | DE | ... | a | b | ..., where A, B, C, D, E \in N and a, b in T.

Parameters

leftHandSide	the left hand side of the rule
rightHandSide	a set of right hand sides of the rule

Here is the call graph for this function:

◆ addTerminalSymbol()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::addTerminalSymbol ( TerminalSymbolType symbol )

inline

Adder of terminal symbol.

Parameters

symbol the new symbol tuo be added to nonterminal alphabet

Returns: true if the symbol was indeed added

◆ getGeneratesEpsilon()

template<class TerminalSymbolType , class NonterminalSymbolType >

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getGeneratesEpsilon

Gets sign representing that grammar generates or doesn't generate empty word.

Returns: sign representing the posibility of generating empty string from the grammar

◆ getInitialSymbol() [1/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

NonterminalSymbolType && grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getInitialSymbol ( ) &&

inline

Getter of initial symbol.

Returns: the initial symbol of the grammar

Here is the call graph for this function:

◆ getInitialSymbol() [2/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

const NonterminalSymbolType & grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getInitialSymbol ( ) const &

inline

Getter of initial symbol.

Returns: the initial symbol of the grammar

Here is the caller graph for this function:

◆ getNonterminalAlphabet() [1/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

ext::set< NonterminalSymbolType > && grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getNonterminalAlphabet ( ) &&

inline

Getter of nonterminal alphabet.

Returns: the nonterminal alphabet of the grammar

Here is the call graph for this function:

◆ getNonterminalAlphabet() [2/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

const ext::set< NonterminalSymbolType > & grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getNonterminalAlphabet ( ) const &

inline

Getter of nonterminal alphabet.

Returns: the nonterminal alphabet of the grammar

Here is the caller graph for this function:

◆ getRules() [1/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > > && grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getRules ( ) &&

Get rules of the grammar.

Returns: rules of the grammar

◆ getRules() [2/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

const ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > > & grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getRules ( ) const &

Get rules of the grammar.

Returns: rules of the grammar

Here is the caller graph for this function:

◆ getTerminalAlphabet() [1/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

ext::set< TerminalSymbolType > && grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getTerminalAlphabet ( ) &&

inline

Getter of terminal alphabet.

Returns: the terminal alphabet of the grammar

Here is the call graph for this function:

◆ getTerminalAlphabet() [2/2]

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

const ext::set< TerminalSymbolType > & grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::getTerminalAlphabet ( ) const &

inline

Getter of terminal alphabet.

Returns: the terminal alphabet of the grammar

Here is the caller graph for this function:

◆ operator<=>()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

auto grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::operator<=> ( const CNF< TerminalSymbolType, NonterminalSymbolType > & other ) const

inline

The three way comparison implementation

Parameters

other the other instance

Returns: the ordering between this object and the other.

Here is the call graph for this function:

◆ operator==()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::operator== ( const CNF< TerminalSymbolType, NonterminalSymbolType > & other ) const

inline

The equality comparison implementation.

Parameters

other the other object to compare with.

Returns: true if this and other objects are equal, false othervise

Here is the call graph for this function:

◆ removeRule() [1/3]

template<class TerminalSymbolType , class NonterminalSymbolType >

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::removeRule	(	const NonterminalSymbolType &	leftHandSide,
		const ext::pair< NonterminalSymbolType, NonterminalSymbolType > &	rightHandSide
	)

Remove a rule of a grammar in form of A -> BC, where A, B, C.

Parameters

leftHandSide	the left hand side of the rule
rightHandSide	the right hand side of the rule

Returns: true if the rule was indeed removed, false othervise

◆ removeRule() [2/3]

template<class TerminalSymbolType , class NonterminalSymbolType >

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::removeRule	(	const NonterminalSymbolType &	leftHandSide,
		const ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > &	rightHandSide
	)

Remove a rule of a grammar in form of A -> BC or A -> a, where A, B, C \in N and a \in T.

Parameters

leftHandSide	the left hand side of the rule
rightHandSide	the right hand side of the rule

Returns: true if the rule was indeed removed, false othervise

◆ removeRule() [3/3]

template<class TerminalSymbolType , class NonterminalSymbolType >

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::removeRule	(	const NonterminalSymbolType &	leftHandSide,
		const TerminalSymbolType &	rightHandSide
	)

Remove a rule of a grammar in form of A -> a, where A \in N and a \in T.

Parameters

leftHandSide	the left hand side of the rule
rightHandSide	the right hand side of the rule

Returns: true if the rule was indeed removed, false othervise

◆ setGeneratesEpsilon()

template<class TerminalSymbolType , class NonterminalSymbolType >

void grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::setGeneratesEpsilon ( bool genEps )

Sets sign representing that grammar generates or doesn't generate empty word.

Parameters

genEps sign representing the posibility of generating empty string from the grammar

◆ setInitialSymbol()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

bool grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::setInitialSymbol ( NonterminalSymbolType symbol )

inline

Setter of initial symbol.

Parameters

symbol new initial symbol of the grammar

Returns: true if the initial symbol was indeed changed

◆ setNonterminalAlphabet()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

void grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::setNonterminalAlphabet ( ext::set< NonterminalSymbolType > symbols )

inline

Setter of nonterminal alphabet.

Parameters

symbols completely new nonterminal alphabet

◆ setTerminalAlphabet()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

void grammar::CNF< TerminalSymbolType, NonterminalSymbolType >::setTerminalAlphabet ( ext::set< TerminalSymbolType > symbols )

inline

Setter of terminal alphabet.

Parameters

symbol completely new nontemrinal alphabet

Friends And Related Function Documentation

◆ operator<<

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>

ext::ostream & operator<<	(	ext::ostream &	out,
		const CNF< TerminalSymbolType, NonterminalSymbolType > &	instance
	)

friend

Print this object as raw representation to ostream.

Parameters

out	ostream where to print
instance	object to print

Returns: modified output stream

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

alib2data/src/grammar/ContextFree/CNF.h

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CNF() [1/2]

◆ CNF() [2/2]

Member Function Documentation

◆ addNonterminalSymbol()

◆ addRule()

◆ addRules()

◆ addTerminalSymbol()

◆ getGeneratesEpsilon()

◆ getInitialSymbol() [1/2]

◆ getInitialSymbol() [2/2]

◆ getNonterminalAlphabet() [1/2]

◆ getNonterminalAlphabet() [2/2]

◆ getRules() [1/2]

◆ getRules() [2/2]

◆ getTerminalAlphabet() [1/2]

◆ getTerminalAlphabet() [2/2]

◆ operator<=>()

◆ operator==()

◆ removeRule() [1/3]

◆ removeRule() [2/3]

◆ removeRule() [3/3]

◆ setGeneratesEpsilon()

◆ setInitialSymbol()

◆ setNonterminalAlphabet()

◆ setTerminalAlphabet()

Friends And Related Function Documentation

◆ operator<<