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
RightRG.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#include <alib/variant>
33
34#include <core/components.hpp>
35
37
39
40#include <core/normalize.hpp>
43
44namespace grammar {
45
46class TerminalAlphabet;
47class NonterminalAlphabet;
48class InitialSymbol;
49
69template < class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType >
70class RightRG final : public core::Components < RightRG < TerminalSymbolType, NonterminalSymbolType >, ext::set < TerminalSymbolType >, component::Set, TerminalAlphabet, ext::set < NonterminalSymbolType >, component::Set, NonterminalAlphabet, NonterminalSymbolType, component::Value, InitialSymbol > {
75
79 bool generatesEpsilon;
80
81public:
87 explicit RightRG ( NonterminalSymbolType initialSymbol );
88
96 explicit RightRG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol );
97
108 bool addRule ( NonterminalSymbolType leftHandSide, ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
109
118 void addRules ( NonterminalSymbolType leftHandSide, ext::set < ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > > rightHandSide );
119
126
133
142 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > & rightHandSide );
143
152 bool removeRule ( const NonterminalSymbolType & leftHandSide, const TerminalSymbolType & rightHandSide );
153
162 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::pair < TerminalSymbolType, NonterminalSymbolType > & rightHandSide );
163
169 const NonterminalSymbolType & getInitialSymbol ( ) const & {
170 return this->template accessComponent < InitialSymbol > ( ).get ( );
171 }
172
178 NonterminalSymbolType && getInitialSymbol ( ) && {
179 return std::move ( this->template accessComponent < InitialSymbol > ( ).get ( ) );
180 }
181
189 bool setInitialSymbol ( NonterminalSymbolType symbol ) {
190 return this->template accessComponent < InitialSymbol > ( ).set ( std::move ( symbol ) );
191 }
192
199 return this->template accessComponent < NonterminalAlphabet > ( ).get ( );
200 }
201
208 return std::move ( this->template accessComponent < NonterminalAlphabet > ( ).get ( ) );
209 }
210
218 bool addNonterminalSymbol ( NonterminalSymbolType symbol ) {
219 return this->template accessComponent < NonterminalAlphabet > ( ).add ( std::move ( symbol ) );
220 }
221
228 this->template accessComponent < NonterminalAlphabet > ( ).set ( std::move ( symbols ) );
229 }
230
237 return this->template accessComponent < TerminalAlphabet > ( ).get ( );
238 }
239
246 return std::move ( this->template accessComponent < TerminalAlphabet > ( ).get ( ) );
247 }
248
256 bool addTerminalSymbol ( TerminalSymbolType symbol ) {
257 return this->template accessComponent < TerminalAlphabet > ( ).add ( std::move ( symbol ) );
258 }
259
266 this->template accessComponent < TerminalAlphabet > ( ).set ( std::move ( symbols ) );
267 }
268
274 void setGeneratesEpsilon ( bool genEps );
275
281 bool getGeneratesEpsilon ( ) const;
282
290 auto operator <=> ( const RightRG & other ) const {
291 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) <=> std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
292 }
293
301 bool operator == ( const RightRG & other ) const {
302 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) == std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
303 }
304
313 friend ext::ostream & operator << ( ext::ostream & out, const RightRG & instance ) {
314 return out << "(RightRG"
315 << " nonterminalAlphabet = " << instance.getNonterminalAlphabet ( )
316 << " terminalAlphabet = " << instance.getTerminalAlphabet ( )
317 << " initialSymbol = " << instance.getInitialSymbol ( )
318 << " rules = " << instance.getRules ( )
319 << " generatesEpsilon = " << instance.getGeneratesEpsilon ( )
320 << ")";
321 }
322};
323
324template < class TerminalSymbolType, class NonterminalSymbolType >
326}
327
328template < class TerminalSymbolType, class NonterminalSymbolType >
329RightRG < TerminalSymbolType, NonterminalSymbolType >::RightRG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol ) : core::Components < RightRG < TerminalSymbolType, NonterminalSymbolType >, ext::set < TerminalSymbolType >, component::Set, TerminalAlphabet, ext::set < NonterminalSymbolType >, component::Set, NonterminalAlphabet, NonterminalSymbolType, component::Value, InitialSymbol > ( std::move ( terminalAlphabet), std::move ( nonterminalAlphabet ), std::move ( initialSymbol ) ), generatesEpsilon ( false ) {
330}
331
332template < class TerminalSymbolType, class NonterminalSymbolType >
334 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
335 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
336
337 if ( rightHandSide.template is < TerminalSymbolType > ( ) ) {
338 const TerminalSymbolType & rhs = rightHandSide.template get < TerminalSymbolType > ( );
339
340 if ( !getTerminalAlphabet ( ).count ( rhs ) )
341 throw GrammarException ( "Rule must rewrite to terminal symbol" );
342 } else {
343 const ext::pair < TerminalSymbolType, NonterminalSymbolType > & rhs = rightHandSide.template get < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( );
344
345 if ( !getTerminalAlphabet ( ).count ( rhs.first ) || !getNonterminalAlphabet ( ).count ( rhs.second ) )
346 throw GrammarException ( "Rule must rewrite to terminal symbol followed by nonterminal symbol" );
347 }
348
349 return rules[std::move ( leftHandSide )].insert ( std::move ( rightHandSide ) ).second;
350}
351
352template < class TerminalSymbolType, class NonterminalSymbolType >
354 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
355 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
356
357 for ( const ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > & element : rightHandSide ) {
358 if ( element.template is < TerminalSymbolType > ( ) ) {
359 const TerminalSymbolType & rhs = element.template get < TerminalSymbolType > ( );
360
361 if ( ! getTerminalAlphabet ( ).count ( rhs ) )
362 throw GrammarException ( "Rule must rewrite to terminal symbol" );
363 } else {
364 const ext::pair < TerminalSymbolType, NonterminalSymbolType > & rhs = element.template get < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( );
365
366 if ( ! getTerminalAlphabet ( ).count ( rhs.first ) || ! getNonterminalAlphabet ( ).count ( rhs.second ) )
367 throw GrammarException ( "Rule must rewrite to terminal symbol followed by nonterminal symbol" );
368 }
369 }
370
371 rules[std::move ( leftHandSide )].insert ( ext::make_mover ( rightHandSide ).begin ( ), ext::make_mover ( rightHandSide ).end ( ) );
372}
373
374template < class TerminalSymbolType, class NonterminalSymbolType >
376 return rules;
377}
378
379template < class TerminalSymbolType, class NonterminalSymbolType >
381 return std::move ( rules );
382}
383
384template < class TerminalSymbolType, class NonterminalSymbolType >
386 return rules[leftHandSide].erase ( rightHandSide );
387}
388
389template < class TerminalSymbolType, class NonterminalSymbolType >
390bool RightRG < TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType & leftHandSide, const TerminalSymbolType & rightHandSide ) {
392
393 return removeRule ( leftHandSide, rhs );
394}
395
396template < class TerminalSymbolType, class NonterminalSymbolType >
399
400 return removeRule ( leftHandSide, rhs );
401}
402
403template < class TerminalSymbolType, class NonterminalSymbolType >
405 generatesEpsilon = genEps;
406}
407
408template < class TerminalSymbolType, class NonterminalSymbolType >
410 return generatesEpsilon;
411}
412
413} /* namespace grammar */
414
415namespace core {
416
423template < class TerminalSymbolType, class NonterminalSymbolType >
424class SetConstraint< grammar::RightRG < TerminalSymbolType, NonterminalSymbolType >, TerminalSymbolType, grammar::TerminalAlphabet > {
425public:
434 static bool used ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
435 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) )
436 for ( const ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > & rhs : rule.second )
437 if ( ( rhs.template is < TerminalSymbolType > ( ) && ( rhs.template get < TerminalSymbolType > ( ) == symbol ) ) || ( rhs.template get < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( ).first == symbol ) )
438 return true;
439
440 return false;
441 }
442
451 static bool available ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType & ) {
452 return true;
453 }
454
463 static void valid ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
464 if ( grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
465 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the terminal alphabet since it is already in the nonterminal alphabet." );
466 }
467};
468
475template < class TerminalSymbolType, class NonterminalSymbolType >
476class SetConstraint< grammar::RightRG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::NonterminalAlphabet > {
477public:
486 static bool used ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
487 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
488 if ( rule.first == symbol )
489 return true;
490
491 for ( const ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > & rhs : rule.second )
492 if ( rhs.template get < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( ).second == symbol )
493 return true;
494
495 }
496
497 return grammar.template accessComponent < grammar::InitialSymbol > ( ).get ( ) == symbol;
498 }
499
508 static bool available ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
509 return true;
510 }
511
520 static void valid ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
521 if ( grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
522 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the nonterminal alphabet since it is already in the terminal alphabet." );
523 }
524};
525
532template < class TerminalSymbolType, class NonterminalSymbolType >
533class ElementConstraint< grammar::RightRG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::InitialSymbol > {
534public:
543 static bool available ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
544 return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
545 }
546
553 static void valid ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
554 }
555};
556
562template < class TerminalSymbolType, class NonterminalSymbolType >
563struct normalize < grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > > {
565 ext::set < DefaultSymbolType > nonterminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonterminalAlphabet ( ) );
566 ext::set < DefaultSymbolType > terminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getTerminalAlphabet ( ) );
567 DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getInitialSymbol ( ) );
568
569 grammar::RightRG < > res ( std::move ( nonterminals ), std::move ( terminals ), std::move ( initialSymbol ) );
570
571 for ( std::pair < NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > > > && rule : ext::make_mover ( std::move ( value ).getRules ( ) ) ) {
572
574 for ( ext::variant < TerminalSymbolType, ext::pair < TerminalSymbolType, NonterminalSymbolType > > && target : ext::make_mover ( rule.second ) )
575 rhs.insert ( grammar::GrammarNormalize::normalizeRHS ( std::move ( target ) ) );
576
577 DefaultSymbolType lhs = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( rule.first ) );
578
579 res.addRules ( std::move ( lhs ), std::move ( rhs ) );
580 }
581
582 res.setGeneratesEpsilon ( value.getGeneratesEpsilon ( ) );
583
584 return res;
585 }
586};
587
588} /* namespace core */
589
590extern template class grammar::RightRG < >;
591
static ext::set< DefaultSymbolType > normalizeAlphabet(ext::set< SymbolType > &&symbols)
Definition: SymbolNormalize.h:50
static DefaultSymbolType normalizeSymbol(SymbolType &&symbol)
Definition: SymbolNormalize.h:68
Definition: components.hpp:181
static void valid(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: RightRG.h:553
static bool available(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: RightRG.h:543
Definition: components.hpp:25
static bool used(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: RightRG.h:434
static void valid(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: RightRG.h:463
static bool available(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType &)
Definition: RightRG.h:451
static void valid(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: RightRG.h:520
static bool used(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: RightRG.h:486
static bool available(const grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: RightRG.h:508
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
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Definition: set.hpp:44
Implementation of the variant class allowing to store any type of those listed in the template parame...
Definition: variant.hpp:98
Definition: GrammarException.h:15
static ext::pair< DefaultSymbolType, ext::vector< DefaultSymbolType > > normalizeRHS(ext::pair< FirstSymbolType, ext::vector< SecondSymbolType > > &&symbol)
Definition: GrammarNormalize.h:40
Right regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular language...
Definition: RightRG.h:70
bool operator==(const RightRG &other) const
Definition: RightRG.h:301
const ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< TerminalSymbolType, NonterminalSymbolType > > > > & getRules() const &
Definition: RightRG.h:375
void setGeneratesEpsilon(bool genEps)
Definition: RightRG.h:404
bool addTerminalSymbol(TerminalSymbolType symbol)
Definition: RightRG.h:256
bool addNonterminalSymbol(NonterminalSymbolType symbol)
Definition: RightRG.h:218
bool setInitialSymbol(NonterminalSymbolType symbol)
Definition: RightRG.h:189
friend ext::ostream & operator<<(ext::ostream &out, const RightRG &instance)
Definition: RightRG.h:313
ext::set< TerminalSymbolType > && getTerminalAlphabet() &&
Definition: RightRG.h:245
NonterminalSymbolType && getInitialSymbol() &&
Definition: RightRG.h:178
bool removeRule(const NonterminalSymbolType &leftHandSide, const ext::variant< TerminalSymbolType, ext::pair< TerminalSymbolType, NonterminalSymbolType > > &rightHandSide)
Definition: RightRG.h:385
bool addRule(NonterminalSymbolType leftHandSide, ext::variant< TerminalSymbolType, ext::pair< TerminalSymbolType, NonterminalSymbolType > > rightHandSide)
Add a new rule of a grammar.
Definition: RightRG.h:333
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: RightRG.h:198
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: RightRG.h:236
RightRG(NonterminalSymbolType initialSymbol)
Creates a new instance of Right regular grammar with a concrete initial symbol.
Definition: RightRG.h:325
auto operator<=>(const RightRG &other) const
Definition: RightRG.h:290
void setTerminalAlphabet(ext::set< TerminalSymbolType > symbols)
Definition: RightRG.h:265
void addRules(NonterminalSymbolType leftHandSide, ext::set< ext::variant< TerminalSymbolType, ext::pair< TerminalSymbolType, NonterminalSymbolType > > > rightHandSide)
Add new rules of a grammar.
Definition: RightRG.h:353
void setNonterminalAlphabet(ext::set< NonterminalSymbolType > symbols)
Definition: RightRG.h:227
ext::set< NonterminalSymbolType > && getNonterminalAlphabet() &&
Definition: RightRG.h:207
const NonterminalSymbolType & getInitialSymbol() const &
Definition: RightRG.h:169
bool getGeneratesEpsilon() const
Definition: RightRG.h:409
Definition: Object.h:16
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
PolyComp< T > poly_comp(const T &inst)
Definition: functional.hpp:60
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::RightRG< > eval(grammar::RightRG< TerminalSymbolType, NonterminalSymbolType > &&value)
Definition: RightRG.h:564
Definition: normalize.hpp:13