Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
UnrestrictedGrammar.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26
27#include <ext/algorithm>
28
29#include <alib/map>
30#include <alib/set>
31#include <alib/vector>
32
33#include <core/components.hpp>
34
36
38
39#include <core/normalize.hpp>
42
43namespace grammar {
44
45class TerminalAlphabet;
46class NonterminalAlphabet;
47class InitialSymbol;
48
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 > {
69
70public:
76 explicit UnrestrictedGrammar ( SymbolType initialSymbol );
77
85 explicit UnrestrictedGrammar ( ext::set < SymbolType > nonterminalAlphabet, ext::set < SymbolType > terminalAlphabet, SymbolType initialSymbol );
86
99 bool addRule ( ext::vector < SymbolType > leftHandSide, ext::vector < SymbolType > rightHandSide );
100
111 void addRules ( ext::vector < SymbolType > leftHandSide, ext::set < ext::vector < SymbolType > > rightHandSide );
112
119
126
137 bool removeRule ( const ext::vector < SymbolType > & leftHandSide, const ext::vector < SymbolType > & rightHandSide );
138
144 const SymbolType & getInitialSymbol ( ) const & {
145 return this->template accessComponent < InitialSymbol > ( ).get ( );
146 }
147
154 return std::move ( this->template accessComponent < InitialSymbol > ( ).get ( ) );
155 }
156
164 bool setInitialSymbol ( SymbolType symbol ) {
165 return this->template accessComponent < InitialSymbol > ( ).set ( std::move ( symbol ) );
166 }
167
174 return this->template accessComponent < NonterminalAlphabet > ( ).get ( );
175 }
176
183 return std::move ( this->template accessComponent < NonterminalAlphabet > ( ).get ( ) );
184 }
185
194 return this->template accessComponent < NonterminalAlphabet > ( ).add ( std::move ( symbol ) );
195 }
196
203 this->template accessComponent < NonterminalAlphabet > ( ).set ( std::move ( symbols ) );
204 }
205
212 return this->template accessComponent < TerminalAlphabet > ( ).get ( );
213 }
214
221 return std::move ( this->template accessComponent < TerminalAlphabet > ( ).get ( ) );
222 }
223
232 return this->template accessComponent < TerminalAlphabet > ( ).add ( std::move ( symbol ) );
233 }
234
241 this->template accessComponent < TerminalAlphabet > ( ).set ( std::move ( symbols ) );
242 }
243
251 auto operator <=> ( const UnrestrictedGrammar & other ) const {
252 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) <=> std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
253 }
254
262 bool operator == ( const UnrestrictedGrammar & other ) const {
263 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) == std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
264 }
265
274 friend ext::ostream & operator << ( ext::ostream & out, const UnrestrictedGrammar & instance ) {
275 return out << "(UnrestrictedGrammar"
276 << " NonterminalAlphabet = " << instance.getNonterminalAlphabet ( )
277 << " TerminalAlphabet = " << instance.getTerminalAlphabet ( )
278 << " InitialSymbol = " << instance.getInitialSymbol ( )
279 << " Rules = " << instance.getRules ( )
280 << ")";
281 }
282};
283
284template < class SymbolType >
286}
287
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 ) ) {
290}
291
292template < class SymbolType >
294 if ( std::all_of ( leftHandSide.begin ( ), leftHandSide.end ( ), [this] ( const SymbolType symbol ) {
295 return !getNonterminalAlphabet ( ).count ( symbol );
296 } ) )
297 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
298
299 for ( const SymbolType & symbol : leftHandSide )
300 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
301 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
302
303 for ( const SymbolType & symbol : rightHandSide )
304 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
305 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
306
307 return rules[std::move ( leftHandSide )].insert ( std::move ( rightHandSide ) ).second;
308}
309
310template < class SymbolType >
312 if ( std::all_of ( leftHandSide.begin ( ), leftHandSide.end ( ), [this] ( const SymbolType symbol ) {
313 return !getNonterminalAlphabet ( ).count ( symbol );
314 } ) )
315 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
316
317 for ( const SymbolType & symbol : leftHandSide )
318 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
319 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
320
321 for ( const ext::vector < SymbolType > & rhs : rightHandSide )
322 for ( const SymbolType & symbol : rhs )
323 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
324 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
325
326 rules [ std::move ( leftHandSide ) ].insert ( ext::make_mover ( rightHandSide ).begin ( ), ext::make_mover ( rightHandSide ).end ( ) );
327}
328
329template < class SymbolType >
331 return rules;
332}
333
334template < class SymbolType >
336 return std::move ( rules );
337}
338
339template < class SymbolType >
341 return rules[leftHandSide].erase ( rightHandSide );
342}
343
344} /* namespace grammar */
345
346namespace core {
347
353template < class SymbolType >
354class SetConstraint< grammar::UnrestrictedGrammar < SymbolType >, SymbolType, grammar::TerminalAlphabet > {
355public:
364 static bool used ( const grammar::UnrestrictedGrammar < SymbolType > & grammar, const SymbolType & symbol ) {
365 for ( const std::pair < const ext::vector < SymbolType >, ext::set < ext::vector < SymbolType > > > & rule : grammar.getRules ( ) ) {
366 if ( std::find ( rule.first.begin ( ), rule.first.end ( ), symbol ) != rule.first.end ( ) )
367 return true;
368
369 for ( const ext::vector < SymbolType > & rhs : rule.second )
370 if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
371 return true;
372
373 }
374
375 return false;
376 }
377
387 return true;
388 }
389
398 static void valid ( const grammar::UnrestrictedGrammar < SymbolType > & grammar, const SymbolType & symbol ) {
399 if ( grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol ) )
400 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the terminal alphabet since it is already in the nonterminal alphabet." );
401 }
402};
403
409template < class SymbolType >
410class SetConstraint< grammar::UnrestrictedGrammar < SymbolType >, SymbolType, grammar::NonterminalAlphabet > {
411public:
420 static bool used ( const grammar::UnrestrictedGrammar < SymbolType > & grammar, const SymbolType & symbol ) {
421 for ( const std::pair < const ext::vector < SymbolType >, ext::set < ext::vector < SymbolType > > > & rule : grammar.getRules ( ) ) {
422 if ( std::find ( rule.first.begin ( ), rule.first.end ( ), symbol ) != rule.first.end ( ) )
423 return true;
424
425 for ( const ext::vector < SymbolType > & rhs : rule.second )
426 if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
427 return true;
428
429 }
430
431 return grammar.template accessComponent < grammar::InitialSymbol > ( ).get ( ) == symbol;
432 }
433
443 return true;
444 }
445
454 static void valid ( const grammar::UnrestrictedGrammar < SymbolType > & grammar, const SymbolType & symbol ) {
455 if ( grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( symbol ) )
456 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the nonterminal alphabet since it is already in the terminal alphabet." );
457 }
458};
459
465template < class SymbolType >
466class ElementConstraint< grammar::UnrestrictedGrammar < SymbolType >, SymbolType, grammar::InitialSymbol > {
467public:
477 return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
478 }
479
487 }
488};
489
495template < class SymbolType >
496struct normalize < grammar::UnrestrictedGrammar < SymbolType > > {
498 ext::set < DefaultSymbolType > nonterminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonterminalAlphabet ( ) );
499 ext::set < DefaultSymbolType > terminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getTerminalAlphabet ( ) );
500 DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getInitialSymbol ( ) );
501
502 grammar::UnrestrictedGrammar < > res ( std::move ( nonterminals ), std::move ( terminals ), std::move ( initialSymbol ) );
503
504 for ( std::pair < ext::vector < SymbolType >, ext::set < ext::vector < SymbolType > > > && rule : ext::make_mover ( std::move ( value ).getRules ( ) ) ) {
505
507 for ( ext::vector < SymbolType > && target : ext::make_mover ( rule.second ) )
508 rhs.insert ( alphabet::SymbolNormalize::normalizeSymbols ( std::move ( target ) ) );
509
511
512 res.addRules ( std::move ( lhs ), std::move ( rhs ) );
513 }
514
515 return res;
516 }
517};
518
519} /* namespace core */
520
521extern template class grammar::UnrestrictedGrammar < >;
522
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
Definition: ostream.h:14
Definition: set.hpp:44
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
Definition: Object.h:16
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 &param)
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