27#include <ext/algorithm>
45class TerminalAlphabet;
46class NonterminalAlphabet;
63template <
class SymbolType = DefaultSymbolType >
64class UnrestrictedGrammar final :
public core::Components < UnrestrictedGrammar < SymbolType >, ext::set < SymbolType >, component::Set, std::tuple < TerminalAlphabet, NonterminalAlphabet >, SymbolType, component::Value, InitialSymbol > {
145 return this->
template accessComponent < InitialSymbol > ( ).get ( );
154 return std::move ( this->
template accessComponent < InitialSymbol > ( ).
get ( ) );
165 return this->
template accessComponent < InitialSymbol > ( ).set ( std::move ( symbol ) );
174 return this->
template accessComponent < NonterminalAlphabet > ( ).get ( );
183 return std::move ( this->
template accessComponent < NonterminalAlphabet > ( ).
get ( ) );
194 return this->
template accessComponent < NonterminalAlphabet > ( ).add ( std::move ( symbol ) );
203 this->
template accessComponent < NonterminalAlphabet > ( ).set ( std::move ( symbols ) );
212 return this->
template accessComponent < TerminalAlphabet > ( ).get ( );
221 return std::move ( this->
template accessComponent < TerminalAlphabet > ( ).
get ( ) );
232 return this->
template accessComponent < TerminalAlphabet > ( ).add ( std::move ( symbol ) );
241 this->
template accessComponent < TerminalAlphabet > ( ).set ( std::move ( symbols ) );
275 return out <<
"(UnrestrictedGrammar"
279 <<
" Rules = " << instance.
getRules ( )
284template <
class SymbolType >
288template <
class SymbolType >
289UnrestrictedGrammar < SymbolType >::UnrestrictedGrammar (
ext::set < SymbolType > nonterminalAlphabet,
ext::set < SymbolType > terminalAlphabet,
SymbolType initialSymbol ) :
core::Components <
UnrestrictedGrammar,
ext::set < SymbolType >, component::Set, std::tuple < TerminalAlphabet, NonterminalAlphabet >,
SymbolType, component::Value, InitialSymbol > ( std::move ( terminalAlphabet), std::move ( nonterminalAlphabet ), std::move ( initialSymbol ) ) {
292template <
class SymbolType >
294 if (
std::all_of ( leftHandSide.begin ( ), leftHandSide.end ( ), [
this] (
const SymbolType symbol ) {
295 return !getNonterminalAlphabet ( ).count ( symbol );
299 for (
const SymbolType & symbol : leftHandSide )
300 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
303 for (
const SymbolType & symbol : rightHandSide )
304 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
307 return rules[std::move ( leftHandSide )].insert ( std::move ( rightHandSide ) ).second;
310template <
class SymbolType >
312 if (
std::all_of ( leftHandSide.begin ( ), leftHandSide.end ( ), [
this] (
const SymbolType symbol ) {
313 return !getNonterminalAlphabet ( ).count ( symbol );
317 for (
const SymbolType & symbol : leftHandSide )
318 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
323 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
329template <
class SymbolType >
334template <
class SymbolType >
336 return std::move ( rules );
339template <
class SymbolType >
341 return rules[leftHandSide].erase ( rightHandSide );
353template <
class SymbolType >
366 if ( std::find ( rule.first.begin ( ), rule.first.end ( ), symbol ) != rule.first.end ( ) )
370 if ( std::find ( rhs.
begin ( ), rhs.
end ( ), symbol ) != rhs.
end ( ) )
399 if (
grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol ) )
409template <
class SymbolType >
422 if ( std::find ( rule.first.begin ( ), rule.first.end ( ), symbol ) != rule.first.end ( ) )
426 if ( std::find ( rhs.
begin ( ), rhs.
end ( ), symbol ) != rhs.
end ( ) )
431 return grammar.template accessComponent < grammar::InitialSymbol > ( ).get ( ) == symbol;
455 if (
grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( symbol ) )
465template <
class SymbolType >
477 return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
495template <
class SymbolType >
512 res.addRules ( std::move ( lhs ), std::move ( rhs ) );
static ext::set< DefaultSymbolType > normalizeAlphabet(ext::set< SymbolType > &&symbols)
Definition: SymbolNormalize.h:50
static ext::vector< DefaultSymbolType > normalizeSymbols(ext::vector< SymbolType > &&symbols)
Definition: SymbolNormalize.h:86
static DefaultSymbolType normalizeSymbol(SymbolType &&symbol)
Definition: SymbolNormalize.h:68
Definition: components.hpp:181
static void valid(const grammar::UnrestrictedGrammar< SymbolType > &, const SymbolType &)
Definition: UnrestrictedGrammar.h:486
static bool available(const grammar::UnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: UnrestrictedGrammar.h:476
Definition: components.hpp:25
static void valid(const grammar::UnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: UnrestrictedGrammar.h:398
static bool used(const grammar::UnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: UnrestrictedGrammar.h:364
static bool available(const grammar::UnrestrictedGrammar< SymbolType > &, const SymbolType &)
Definition: UnrestrictedGrammar.h:386
static bool used(const grammar::UnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: UnrestrictedGrammar.h:420
static bool available(const grammar::UnrestrictedGrammar< SymbolType > &, const SymbolType &)
Definition: UnrestrictedGrammar.h:442
static void valid(const grammar::UnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: UnrestrictedGrammar.h:454
Definition: setComponents.hpp:26
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: vector.hpp:125
auto end() &
Inherited behavior of end for non-const instance.
Definition: vector.hpp:155
Definition: GrammarException.h:15
Unrestricted grammar. Type 0 in Chomsky hierarchy. Generates recursively enumerable languages.
Definition: UnrestrictedGrammar.h:64
bool operator==(const UnrestrictedGrammar &other) const
Definition: UnrestrictedGrammar.h:262
UnrestrictedGrammar(SymbolType initialSymbol)
Creates a new instance of the grammar with a concrete initial symbol.
Definition: UnrestrictedGrammar.h:285
const ext::map< ext::vector< SymbolType >, ext::set< ext::vector< SymbolType > > > & getRules() const &
Definition: UnrestrictedGrammar.h:330
ext::set< SymbolType > && getTerminalAlphabet() &&
Definition: UnrestrictedGrammar.h:220
friend ext::ostream & operator<<(ext::ostream &out, const UnrestrictedGrammar &instance)
Definition: UnrestrictedGrammar.h:274
bool addNonterminalSymbol(SymbolType symbol)
Definition: UnrestrictedGrammar.h:193
bool addRule(ext::vector< SymbolType > leftHandSide, ext::vector< SymbolType > rightHandSide)
Add a new rule of a grammar.
Definition: UnrestrictedGrammar.h:293
bool removeRule(const ext::vector< SymbolType > &leftHandSide, const ext::vector< SymbolType > &rightHandSide)
Definition: UnrestrictedGrammar.h:340
bool setInitialSymbol(SymbolType symbol)
Definition: UnrestrictedGrammar.h:164
const SymbolType & getInitialSymbol() const &
Definition: UnrestrictedGrammar.h:144
SymbolType && getInitialSymbol() &&
Definition: UnrestrictedGrammar.h:153
auto operator<=>(const UnrestrictedGrammar &other) const
Definition: UnrestrictedGrammar.h:251
ext::set< SymbolType > && getNonterminalAlphabet() &&
Definition: UnrestrictedGrammar.h:182
void addRules(ext::vector< SymbolType > leftHandSide, ext::set< ext::vector< SymbolType > > rightHandSide)
Add new rules of a grammar.
Definition: UnrestrictedGrammar.h:311
const ext::set< SymbolType > & getTerminalAlphabet() const &
Definition: UnrestrictedGrammar.h:211
const ext::set< SymbolType > & getNonterminalAlphabet() const &
Definition: UnrestrictedGrammar.h:173
bool addTerminalSymbol(SymbolType symbol)
Definition: UnrestrictedGrammar.h:231
void setNonterminalAlphabet(ext::set< SymbolType > symbols)
Definition: UnrestrictedGrammar.h:202
void setTerminalAlphabet(ext::set< SymbolType > symbols)
Definition: UnrestrictedGrammar.h:240
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
return res
Definition: MinimizeByPartitioning.h:145
Definition: normalize.hpp:10
constexpr tuple< Elements &... > tie(Elements &... args) noexcept
Helper of extended tuple of references construction. The tuple is constructed to reffer to values in ...
Definition: tuple.hpp:218
reference_mover< T > make_mover(T ¶m)
Move adaptor construction function specialized to lvalue reference parameter.
Definition: iterator.hpp:468
std::string to_string(const T &value)
To string method designated for objects that can be casted to string.
Definition: string.hpp:131
all_of(T &&...) -> all_of< T... >
auto begin(Container &&cont) -> decltype(std::forward(cont).begin())
Definition: iterator.hpp:900
Definition: ToAutomaton.h:24
void end()
Definition: measurements.cpp:19
auto & get(ext::ptr_array< Type, N > &tpl)
Specialisation of get function for pointer arrays.
Definition: ptr_array.hpp:693
static grammar::UnrestrictedGrammar< > eval(grammar::UnrestrictedGrammar< SymbolType > &&value)
Definition: UnrestrictedGrammar.h:497
Definition: normalize.hpp:13