Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
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