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
RightLG.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
64template < class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType >
65class RightLG final : public core::Components < RightLG < TerminalSymbolType, NonterminalSymbolType >, ext::set < TerminalSymbolType >, component::Set, TerminalAlphabet, ext::set < NonterminalSymbolType >, component::Set, NonterminalAlphabet, NonterminalSymbolType, component::Value, InitialSymbol > {
70
71public:
77 explicit RightLG ( NonterminalSymbolType initialSymbol );
78
86 explicit RightLG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol );
87
98 bool addRule ( NonterminalSymbolType leftHandSide, ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > rightHandSide );
99
108 void addRules ( NonterminalSymbolType leftHandSide, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > > rightHandSide );
109
116
123
132 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > & rightHandSide );
133
142 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::vector < TerminalSymbolType > & rightHandSide );
143
152 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > & rightHandSide );
153
159 const NonterminalSymbolType & getInitialSymbol ( ) const & {
160 return this->template accessComponent < InitialSymbol > ( ).get ( );
161 }
162
168 NonterminalSymbolType && getInitialSymbol ( ) && {
169 return std::move ( this->template accessComponent < InitialSymbol > ( ).get ( ) );
170 }
171
179 bool setInitialSymbol ( NonterminalSymbolType symbol ) {
180 return this->template accessComponent < InitialSymbol > ( ).set ( std::move ( symbol ) );
181 }
182
189 return this->template accessComponent < NonterminalAlphabet > ( ).get ( );
190 }
191
198 return std::move ( this->template accessComponent < NonterminalAlphabet > ( ).get ( ) );
199 }
200
208 bool addNonterminalSymbol ( NonterminalSymbolType symbol ) {
209 return this->template accessComponent < NonterminalAlphabet > ( ).add ( std::move ( symbol ) );
210 }
211
218 this->template accessComponent < NonterminalAlphabet > ( ).set ( std::move ( symbols ) );
219 }
220
227 return this->template accessComponent < TerminalAlphabet > ( ).get ( );
228 }
229
236 return std::move ( this->template accessComponent < TerminalAlphabet > ( ).get ( ) );
237 }
238
246 bool addTerminalSymbol ( TerminalSymbolType symbol ) {
247 return this->template accessComponent < TerminalAlphabet > ( ).add ( std::move ( symbol ) );
248 }
249
256 this->template accessComponent < TerminalAlphabet > ( ).set ( std::move ( symbols ) );
257 }
258
266 auto operator <=> ( const RightLG & other ) const {
267 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) <=> std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
268 }
269
277 bool operator == ( const RightLG & other ) const {
278 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) == std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
279 }
280
289 friend ext::ostream & operator << ( ext::ostream & out, const RightLG & instance ) {
290 return out << "(RightLG"
291 << " nonterminalAlphabet = " << instance.getNonterminalAlphabet ( )
292 << " terminalAlphabet = " << instance.getTerminalAlphabet ( )
293 << " initialSymbol = " << instance.getInitialSymbol ( )
294 << " rules = " << instance.getRules ( )
295 << ")";
296 }
297};
298
299template < class TerminalSymbolType, class NonterminalSymbolType >
301}
302
303template < class TerminalSymbolType, class NonterminalSymbolType >
304RightLG < TerminalSymbolType, NonterminalSymbolType >::RightLG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol ) : core::Components < RightLG, 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 ) ) {
305}
306
307template < class TerminalSymbolType, class NonterminalSymbolType >
309 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
310 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
311
312 if ( rightHandSide.template is < ext::vector < TerminalSymbolType > > ( ) ) {
313 for ( const auto & symbol : rightHandSide.template get < ext::vector < TerminalSymbolType > > ( ) )
314 if ( !getTerminalAlphabet ( ).count ( symbol ) )
315 throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
316 } else {
317 const ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > & rhs = rightHandSide.template get < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > ( );
318
319 if ( !getNonterminalAlphabet ( ).count ( rhs.second ) )
320 throw GrammarException ( "Symbol " + ext::to_string ( rhs.second ) + " is not a nonterminal symbol" );
321
322 for ( const auto & symbol : rhs.first )
323 if ( !getTerminalAlphabet ( ).count ( symbol ) )
324 throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
325 }
326
327 return rules [ std::move ( leftHandSide ) ].insert ( std::move ( rightHandSide ) ).second;
328}
329
330template < class TerminalSymbolType, class NonterminalSymbolType >
332 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
333 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
334
335 for ( const ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > & element : rightHandSide ) {
336 if ( element.template is < ext::vector < TerminalSymbolType > > ( ) ) {
337 for ( const auto & symbol : element.template get < ext::vector < TerminalSymbolType > > ( ) )
338 if ( !getTerminalAlphabet ( ).count ( symbol ) )
339 throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
340 } else {
341 const ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > & rhs = element.template get < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > ( );
342
343 if ( !getNonterminalAlphabet ( ).count ( rhs.second ) )
344 throw GrammarException ( "Symbol " + ext::to_string ( rhs.second ) + " is not a nonterminal symbol" );
345
346 for ( const auto & symbol : rhs.first )
347 if ( !getTerminalAlphabet ( ).count ( symbol ) )
348 throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
349 }
350 }
351
352 rules [ std::move ( leftHandSide ) ].insert ( ext::make_mover ( rightHandSide ).begin ( ), ext::make_mover ( rightHandSide ).end ( ) );
353}
354
355template < class TerminalSymbolType, class NonterminalSymbolType >
357 return rules;
358}
359
360template < class TerminalSymbolType, class NonterminalSymbolType >
362 return std::move ( rules );
363}
364
365template < class TerminalSymbolType, class NonterminalSymbolType >
367 return rules[leftHandSide].erase ( rightHandSide );
368}
369
370template < class TerminalSymbolType, class NonterminalSymbolType >
371bool RightLG < TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType & leftHandSide, const ext::vector < TerminalSymbolType > & rightHandSide ) {
373
374 return removeRule ( leftHandSide, rhs );
375}
376
377template < class TerminalSymbolType, class NonterminalSymbolType >
378bool RightLG < TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType & leftHandSide, const ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > & rightHandSide ) {
380
381 return removeRule ( leftHandSide, rhs );
382}
383
384} /* namespace grammar */
385
386namespace core {
387
394template < class TerminalSymbolType, class NonterminalSymbolType >
395class SetConstraint< grammar::RightLG < TerminalSymbolType, NonterminalSymbolType >, TerminalSymbolType, grammar::TerminalAlphabet > {
396public:
405 static bool used ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
406 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
407 for ( const ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > & rhsTmp : rule.second )
408 if ( rhsTmp.template is < ext::vector < TerminalSymbolType > > ( ) ) {
409 const ext::vector < TerminalSymbolType > & rhs = rhsTmp.template get < ext::vector < TerminalSymbolType > > ( );
410
411 if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
412 return true;
413 } else {
414 const ext::vector < TerminalSymbolType > & rhs = rhsTmp.template get < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > ( ).first;
415
416 if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
417 return true;
418 }
419
420 }
421
422 return false;
423 }
424
433 static bool available ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType & ) {
434 return true;
435 }
436
445 static void valid ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
446 if ( grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
447 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the terminal alphabet since it is already in the nonterminal alphabet." );
448 }
449};
450
457template < class TerminalSymbolType, class NonterminalSymbolType >
458class SetConstraint< grammar::RightLG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::NonterminalAlphabet > {
459public:
468 static bool used ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
469 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
470 if ( rule.first == symbol )
471 return true;
472
473 for ( const ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > & rhsTmp : rule.second )
474 if ( rhsTmp.template is < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > ( ) ) {
475 const ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > & rhs = rhsTmp.template get < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > ( );
476
477 if ( rhs.second == symbol )
478 return true;
479 }
480
481 }
482
483 return grammar.template accessComponent < grammar::InitialSymbol > ( ).get ( ) == symbol;
484 }
485
494 static bool available ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
495 return true;
496 }
497
506 static void valid ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
507 if ( grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
508 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the nonterminal alphabet since it is already in the terminal alphabet." );
509 }
510};
511
518template < class TerminalSymbolType, class NonterminalSymbolType >
519class ElementConstraint< grammar::RightLG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::InitialSymbol > {
520public:
529 static bool available ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
530 return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
531 }
532
539 static void valid ( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
540 }
541};
542
548template < class TerminalSymbolType, class NonterminalSymbolType >
549struct normalize < grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > > {
551 ext::set < DefaultSymbolType > nonterminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonterminalAlphabet ( ) );
552 ext::set < DefaultSymbolType > terminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getTerminalAlphabet ( ) );
553 DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getInitialSymbol ( ) );
554
555 grammar::RightLG < > res ( std::move ( nonterminals ), std::move ( terminals ), std::move ( initialSymbol ) );
556
557 for ( std::pair < NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > > > && rule : ext::make_mover ( std::move ( value ).getRules ( ) ) ) {
558
560 for ( ext::variant < ext::vector < TerminalSymbolType >, ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > && target : ext::make_mover ( rule.second ) )
561 rhs.insert ( grammar::GrammarNormalize::normalizeRHS ( std::move ( target ) ) );
562
563 DefaultSymbolType lhs = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( rule.first ) );
564
565 res.addRules ( std::move ( lhs ), std::move ( rhs ) );
566 }
567
568 return res;
569 }
570};
571
572} /* namespace core */
573
574extern template class grammar::RightLG < >;
575
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 bool available(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: RightLG.h:529
static void valid(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: RightLG.h:539
Definition: components.hpp:25
static bool used(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: RightLG.h:405
static bool available(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType &)
Definition: RightLG.h:433
static void valid(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: RightLG.h:445
static bool available(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: RightLG.h:494
static void valid(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: RightLG.h:506
static bool used(const grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: RightLG.h:468
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
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
static ext::pair< DefaultSymbolType, ext::vector< DefaultSymbolType > > normalizeRHS(ext::pair< FirstSymbolType, ext::vector< SecondSymbolType > > &&symbol)
Definition: GrammarNormalize.h:40
Right linear grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: RightLG.h:65
bool addTerminalSymbol(TerminalSymbolType symbol)
Definition: RightLG.h:246
bool operator==(const RightLG &other) const
Definition: RightLG.h:277
RightLG(NonterminalSymbolType initialSymbol)
Creates a new instance of Right linear grammar with a concrete initial symbol.
Definition: RightLG.h:300
bool addRule(NonterminalSymbolType leftHandSide, ext::variant< ext::vector< TerminalSymbolType >, ext::pair< ext::vector< TerminalSymbolType >, NonterminalSymbolType > > rightHandSide)
Add a new rule of a grammar.
Definition: RightLG.h:308
const ext::map< NonterminalSymbolType, ext::set< ext::variant< ext::vector< TerminalSymbolType >, ext::pair< ext::vector< TerminalSymbolType >, NonterminalSymbolType > > > > & getRules() const &
Definition: RightLG.h:356
ext::set< TerminalSymbolType > && getTerminalAlphabet() &&
Definition: RightLG.h:235
void addRules(NonterminalSymbolType leftHandSide, ext::set< ext::variant< ext::vector< TerminalSymbolType >, ext::pair< ext::vector< TerminalSymbolType >, NonterminalSymbolType > > > rightHandSide)
Add new rules of a grammar.
Definition: RightLG.h:331
const NonterminalSymbolType & getInitialSymbol() const &
Definition: RightLG.h:159
friend ext::ostream & operator<<(ext::ostream &out, const RightLG &instance)
Definition: RightLG.h:289
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: RightLG.h:188
bool removeRule(const NonterminalSymbolType &leftHandSide, const ext::variant< ext::vector< TerminalSymbolType >, ext::pair< ext::vector< TerminalSymbolType >, NonterminalSymbolType > > &rightHandSide)
Definition: RightLG.h:366
bool addNonterminalSymbol(NonterminalSymbolType symbol)
Definition: RightLG.h:208
void setTerminalAlphabet(ext::set< TerminalSymbolType > symbols)
Definition: RightLG.h:255
NonterminalSymbolType && getInitialSymbol() &&
Definition: RightLG.h:168
bool setInitialSymbol(NonterminalSymbolType symbol)
Definition: RightLG.h:179
auto operator<=>(const RightLG &other) const
Definition: RightLG.h:266
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: RightLG.h:226
void setNonterminalAlphabet(ext::set< NonterminalSymbolType > symbols)
Definition: RightLG.h:217
ext::set< NonterminalSymbolType > && getNonterminalAlphabet() &&
Definition: RightLG.h:197
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::RightLG< > eval(grammar::RightLG< TerminalSymbolType, NonterminalSymbolType > &&value)
Definition: RightLG.h:550
Definition: normalize.hpp:13