Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
Public Member Functions | Friends
grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > Class Template Referencefinal

Context free grammar without epsilon rules in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free languages. More...

#include <EpsilonFreeCFG.h>

Inheritance diagram for grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >:
[legend]
Collaboration diagram for grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >:
[legend]

Public Member Functions

 EpsilonFreeCFG (NonterminalSymbolType initialSymbol)
 Creates a new instance of the grammar with a concrete initial symbol. More...
 
 EpsilonFreeCFG (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::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > rightHandSide)
 Add a new rule of a grammar. More...
 
void addRules (NonterminalSymbolType leftHandSide, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > rightHandSide)
 Add new rules of a grammar. More...
 
const ext::map< NonterminalSymbolType, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > & getRules () const &
 
ext::map< NonterminalSymbolType, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > && getRules () &&
 
bool removeRule (const NonterminalSymbolType &leftHandSide, const ext::vector< ext::variant< TerminalSymbolType, 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 EpsilonFreeCFG &other) const
 
bool operator== (const EpsilonFreeCFG &other) const
 
- Public Member Functions inherited from core::Components< EpsilonFreeCFG< DefaultSymbolType, DefaultSymbolType >, ext::set< DefaultSymbolType >, component::Set, TerminalAlphabet, ext::set< DefaultSymbolType >, component::Set, NonterminalAlphabet, DefaultSymbolType, component::Value, InitialSymbol >
void accessComponent ()
 

Friends

ext::ostreamoperator<< (ext::ostream &out, const EpsilonFreeCFG &instance)
 

Additional Inherited Members

- Static Public Member Functions inherited from core::Components< EpsilonFreeCFG< 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::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >

Context free grammar without epsilon rules 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 -> B, where A \in N and B \in ( N \cup T )+, S (InitialSymbol) = initial nonterminal symbol,

Template Parameters
TerminalSymbolTypeused for the terminal alphabet of the grammar.
NonterminalSymbolTypeused for the nonterminal alphabet, and the initial symbol of the grammar.

Constructor & Destructor Documentation

◆ EpsilonFreeCFG() [1/2]

template<class TerminalSymbolType , class NonterminalSymbolType >
grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::EpsilonFreeCFG ( NonterminalSymbolType  initialSymbol)
explicit

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

Parameters
initialSymbolthe initial symbol of the grammar

◆ EpsilonFreeCFG() [2/2]

template<class TerminalSymbolType , class NonterminalSymbolType >
grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::EpsilonFreeCFG ( 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
nonTerminalSymbolsthe initial nonterminal alphabet
terminalSymbolsthe initial terminal alphabet
initialSymbolthe initial symbol of the grammar

Member Function Documentation

◆ addNonterminalSymbol()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>
bool grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::addNonterminalSymbol ( NonterminalSymbolType  symbol)
inline

Adder of nonterminal symbol.

Parameters
symbolthe new symbol to be added to nonterminal alphabet
Returns
true if the symbol was indeed added

◆ addRule()

template<class TerminalSymbolType , class NonterminalSymbolType >
bool grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::addRule ( NonterminalSymbolType  leftHandSide,
ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > >  rightHandSide 
)

Add a new rule of a grammar.

The rule is in a form of A -> B, where A, \in N and B \in (N \cup T )+.

Parameters
leftHandSidethe left hand side of the rule
rightHandSidethe right hand side of the rule
Returns
true if the rule was indeed added, false othervise
Here is the call graph for this function:
Here is the caller graph for this function:

◆ addRules()

template<class TerminalSymbolType , class NonterminalSymbolType >
void grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::addRules ( NonterminalSymbolType  leftHandSide,
ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > >  rightHandSide 
)

Add new rules of a grammar.

The rules are in form of A -> B | C | ..., where A \in N and B, C ... \in (N \cup T)+.

Parameters
leftHandSidethe left hand side of the rule
rightHandSidea 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::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::addTerminalSymbol ( TerminalSymbolType  symbol)
inline

Adder of terminal symbol.

Parameters
symbolthe new symbol tuo be added to nonterminal alphabet
Returns
true if the symbol was indeed added

◆ getGeneratesEpsilon()

template<class TerminalSymbolType , class NonterminalSymbolType >
bool grammar::EpsilonFreeCFG< 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::EpsilonFreeCFG< 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::EpsilonFreeCFG< 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::EpsilonFreeCFG< 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::EpsilonFreeCFG< 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::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > && grammar::EpsilonFreeCFG< 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::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > & grammar::EpsilonFreeCFG< 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::EpsilonFreeCFG< 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::EpsilonFreeCFG< 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::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::operator<=> ( const EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &  other) const
inline

The three way comparison implementation

Parameters
otherthe 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::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::operator== ( const EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &  other) const
inline

The equality comparison implementation.

Parameters
otherthe 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()

template<class TerminalSymbolType , class NonterminalSymbolType >
bool grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType &  leftHandSide,
const ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > &  rightHandSide 
)

Remove a rule of a grammar in form of A -> B, where A \in N and B \in (N \cup T)+.

Parameters
leftHandSidethe left hand side of the rule
rightHandSidethe right hand side of the rule
Returns
true if the rule was indeed removed, false othervise
Here is the caller graph for this function:

◆ setGeneratesEpsilon()

template<class TerminalSymbolType , class NonterminalSymbolType >
void grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::setGeneratesEpsilon ( bool  genEps)

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

Parameters
genEpssign representing the posibility of generating empty string from the grammar
Here is the caller graph for this function:

◆ setInitialSymbol()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>
bool grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::setInitialSymbol ( NonterminalSymbolType  symbol)
inline

Setter of initial symbol.

Parameters
symbolnew initial symbol of the grammar
Returns
true if the initial symbol was indeed changed

◆ setNonterminalAlphabet()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>
void grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::setNonterminalAlphabet ( ext::set< NonterminalSymbolType >  symbols)
inline

Setter of nonterminal alphabet.

Parameters
symbolscompletely new nonterminal alphabet
Here is the caller graph for this function:

◆ setTerminalAlphabet()

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>
void grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType >::setTerminalAlphabet ( ext::set< TerminalSymbolType >  symbols)
inline

Setter of terminal alphabet.

Parameters
symbolcompletely new nontemrinal alphabet
Here is the caller graph for this function:

Friends And Related Function Documentation

◆ operator<<

template<class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType>
ext::ostream & operator<< ( ext::ostream out,
const EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &  instance 
)
friend

Print this object as raw representation to ostream.

Parameters
outostream where to print
instanceobject to print
Returns
modified output stream

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