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
ContextPreservingUnrestrictedGrammar.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 ContextPreservingUnrestrictedGrammar final : public core::Components < ContextPreservingUnrestrictedGrammar < SymbolType >, ext::set < SymbolType >, component::Set, std::tuple < TerminalAlphabet, NonterminalAlphabet >, SymbolType, component::Value, InitialSymbol > {
69
70public:
76 explicit ContextPreservingUnrestrictedGrammar ( SymbolType initialSymbol );
77
85 explicit ContextPreservingUnrestrictedGrammar ( ext::set < SymbolType > nonterminalAlphabet, ext::set < SymbolType > terminalAlphabet, SymbolType initialSymbol );
86
99 bool addRule ( ext::vector < SymbolType > lContext, SymbolType leftHandSide, ext::vector < SymbolType > rContext, ext::vector < SymbolType > rightHandSide );
100
111 void addRules ( ext::vector < SymbolType > lContext, SymbolType leftHandSide, ext::vector < SymbolType > rContext, ext::set < ext::vector < SymbolType > > rightHandSide );
112
119
126
137 bool removeRule ( const ext::vector < SymbolType > & lContext, const SymbolType & leftHandSide, const ext::vector < SymbolType > & rContext, 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
252 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) <=> std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
253 }
254
263 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) == std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
264 }
265
275 return out << "(ContextPreservingUnrestrictedGrammar"
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 >
289ContextPreservingUnrestrictedGrammar < SymbolType >::ContextPreservingUnrestrictedGrammar ( ext::set < SymbolType > nonterminalAlphabet, ext::set < SymbolType > terminalAlphabet, SymbolType initialSymbol ) : core::Components < ContextPreservingUnrestrictedGrammar, 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 for ( const SymbolType & symbol : lContext )
295 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
296 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
297
298 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
299 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
300
301 for ( const SymbolType & symbol : rContext )
302 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
303 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
304
305 for ( const SymbolType & symbol : rightHandSide )
306 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
307 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
308
309 return rules [ ext::make_tuple ( std::move ( lContext ), std::move ( leftHandSide ), std::move ( rContext ) ) ].insert ( std::move ( rightHandSide ) ).second;
310}
311
312template < class SymbolType >
314 for ( const SymbolType & symbol : lContext )
315 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
316 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
317
318 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
319 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
320
321 for ( const SymbolType & symbol : rContext )
322 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
323 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
324
325 for ( const ext::vector < SymbolType > & rhs : rightHandSide )
326 for ( const SymbolType & symbol : rhs )
327 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
328 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
329
330 rules [ ext::make_tuple ( std::move ( lContext ), std::move ( leftHandSide ), std::move ( rContext ) ) ].insert ( ext::make_mover ( rightHandSide ).begin ( ), ext::make_mover ( rightHandSide ).end ( ) );
331}
332
333template < class SymbolType >
335 return rules;
336}
337
338template < class SymbolType >
340 return std::move ( rules );
341}
342
343template < class SymbolType >
345 return rules [ ext::make_tuple ( lContext, leftHandSide, rContext ) ].erase ( rightHandSide );
346}
347
348} /* namespace grammar */
349
350namespace core {
351
357template < class SymbolType >
358class SetConstraint< grammar::ContextPreservingUnrestrictedGrammar < SymbolType >, SymbolType, grammar::TerminalAlphabet > {
359public:
369 for ( const std::pair < const ext::tuple < ext::vector < SymbolType >, SymbolType, ext::vector < SymbolType > >, ext::set < ext::vector < SymbolType > > > & rule : grammar.getRules ( ) ) {
370 for ( const SymbolType & lCont : std::get < 0 > ( rule.first ) )
371 if ( lCont == symbol )
372 return true;
373
374 for ( const SymbolType & rCont : std::get < 2 > ( rule.first ) )
375 if ( rCont == symbol )
376 return true;
377
378 for ( const ext::vector < SymbolType > & rhs : rule.second )
379 if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
380 return true;
381
382 }
383
384 return false;
385 }
386
396 return true;
397 }
398
408 if ( grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol ) )
409 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the terminal alphabet since it is already in the nonterminal alphabet." );
410 }
411};
412
418template < class SymbolType >
419class SetConstraint< grammar::ContextPreservingUnrestrictedGrammar < SymbolType >, SymbolType, grammar::NonterminalAlphabet > {
420public:
430 for ( const std::pair < const ext::tuple < ext::vector < SymbolType >, SymbolType, ext::vector < SymbolType > >, ext::set < ext::vector < SymbolType > > > & rule : grammar.getRules ( ) ) {
431 for ( const SymbolType & lCont : std::get < 0 > ( rule.first ) )
432 if ( lCont == symbol )
433 return true;
434
435 if ( std::get < 1 > ( rule.first ) == symbol )
436 return true;
437
438 for ( const SymbolType & rCont : std::get < 2 > ( rule.first ) )
439 if ( rCont == symbol )
440 return true;
441
442 for ( const ext::vector < SymbolType > & rhs : rule.second )
443 if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
444 return true;
445
446 }
447
448 return grammar.template accessComponent < grammar::InitialSymbol > ( ).get ( ) == symbol;
449 }
450
460 return true;
461 }
462
472 if ( grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( symbol ) )
473 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the nonterminal alphabet since it is already in the terminal alphabet." );
474 }
475};
476
482template < class SymbolType >
483class ElementConstraint< grammar::ContextPreservingUnrestrictedGrammar < SymbolType >, SymbolType, grammar::InitialSymbol > {
484public:
494 return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
495 }
496
504 }
505};
506
512template < class SymbolType >
513struct normalize < grammar::ContextPreservingUnrestrictedGrammar < SymbolType > > {
515 ext::set < DefaultSymbolType > nonterminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonterminalAlphabet ( ) );
516 ext::set < DefaultSymbolType > terminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getTerminalAlphabet ( ) );
517 DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getInitialSymbol ( ) );
518
519 grammar::ContextPreservingUnrestrictedGrammar < > res ( std::move ( nonterminals ), std::move ( terminals ), std::move ( initialSymbol ) );
520
521 for ( std::pair < ext::tuple < ext::vector < SymbolType >, SymbolType, ext::vector < SymbolType > >, ext::set < ext::vector < SymbolType > > > && rule : ext::make_mover ( std::move ( value ).getRules ( ) ) ) {
522
524 for ( ext::vector < SymbolType > && target : ext::make_mover ( rule.second ) )
525 rhs.insert ( alphabet::SymbolNormalize::normalizeSymbols ( std::move ( target ) ) );
526
527 ext::vector < DefaultSymbolType > lContext = alphabet::SymbolNormalize::normalizeSymbols ( std::move ( std::get < 0 > ( rule.first ) ) );
528 DefaultSymbolType lhs = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( std::get < 1 > ( rule.first ) ) );
529 ext::vector < DefaultSymbolType > rContext = alphabet::SymbolNormalize::normalizeSymbols ( std::move ( std::get < 2 > ( rule.first ) ) );
530
531 res.addRules ( std::move ( lContext ), std::move ( lhs ), std::move ( rContext ), std::move ( rhs ) );
532 }
533
534 return res;
535 }
536};
537
538} /* namespace core */
539
541
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::ContextPreservingUnrestrictedGrammar< SymbolType > &, const SymbolType &)
Definition: ContextPreservingUnrestrictedGrammar.h:503
static bool available(const grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:493
Definition: components.hpp:25
static bool used(const grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:429
static void valid(const grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:471
static bool available(const grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &, const SymbolType &)
Definition: ContextPreservingUnrestrictedGrammar.h:459
static void valid(const grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:407
static bool used(const grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &grammar, const SymbolType &symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:368
static bool available(const grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &, const SymbolType &)
Definition: ContextPreservingUnrestrictedGrammar.h:395
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 tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
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
Context preserving unrestricted grammar. Type 0 in Chomsky hierarchy. Generates recursively enumerabl...
Definition: ContextPreservingUnrestrictedGrammar.h:64
bool addNonterminalSymbol(SymbolType symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:193
const ext::map< ext::tuple< ext::vector< SymbolType >, SymbolType, ext::vector< SymbolType > >, ext::set< ext::vector< SymbolType > > > & getRules() const &
Definition: ContextPreservingUnrestrictedGrammar.h:334
void addRules(ext::vector< SymbolType > lContext, SymbolType leftHandSide, ext::vector< SymbolType > rContext, ext::set< ext::vector< SymbolType > > rightHandSide)
Add new rules of a grammar.
Definition: ContextPreservingUnrestrictedGrammar.h:313
void setNonterminalAlphabet(ext::set< SymbolType > symbols)
Definition: ContextPreservingUnrestrictedGrammar.h:202
bool addRule(ext::vector< SymbolType > lContext, SymbolType leftHandSide, ext::vector< SymbolType > rContext, ext::vector< SymbolType > rightHandSide)
Add a new rule of a grammar.
Definition: ContextPreservingUnrestrictedGrammar.h:293
const ext::set< SymbolType > & getNonterminalAlphabet() const &
Definition: ContextPreservingUnrestrictedGrammar.h:173
friend ext::ostream & operator<<(ext::ostream &out, const ContextPreservingUnrestrictedGrammar &instance)
Definition: ContextPreservingUnrestrictedGrammar.h:274
ext::set< SymbolType > && getNonterminalAlphabet() &&
Definition: ContextPreservingUnrestrictedGrammar.h:182
auto operator<=>(const ContextPreservingUnrestrictedGrammar &other) const
Definition: ContextPreservingUnrestrictedGrammar.h:251
bool removeRule(const ext::vector< SymbolType > &lContext, const SymbolType &leftHandSide, const ext::vector< SymbolType > &rContext, const ext::vector< SymbolType > &rightHandSide)
Definition: ContextPreservingUnrestrictedGrammar.h:344
ContextPreservingUnrestrictedGrammar(SymbolType initialSymbol)
Creates a new instance of the grammar with a concrete initial symbol.
Definition: ContextPreservingUnrestrictedGrammar.h:285
const ext::set< SymbolType > & getTerminalAlphabet() const &
Definition: ContextPreservingUnrestrictedGrammar.h:211
bool setInitialSymbol(SymbolType symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:164
void setTerminalAlphabet(ext::set< SymbolType > symbols)
Definition: ContextPreservingUnrestrictedGrammar.h:240
bool operator==(const ContextPreservingUnrestrictedGrammar &other) const
Definition: ContextPreservingUnrestrictedGrammar.h:262
const SymbolType & getInitialSymbol() const &
Definition: ContextPreservingUnrestrictedGrammar.h:144
SymbolType && getInitialSymbol() &&
Definition: ContextPreservingUnrestrictedGrammar.h:153
bool addTerminalSymbol(SymbolType symbol)
Definition: ContextPreservingUnrestrictedGrammar.h:231
ext::set< SymbolType > && getTerminalAlphabet() &&
Definition: ContextPreservingUnrestrictedGrammar.h:220
Definition: GrammarException.h:15
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
constexpr auto make_tuple(Elements &&... args)
Helper of extended tuple construction. The tuple is constructed from values pack, types are deduced.
Definition: tuple.hpp:203
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::ContextPreservingUnrestrictedGrammar< > eval(grammar::ContextPreservingUnrestrictedGrammar< SymbolType > &&value)
Definition: ContextPreservingUnrestrictedGrammar.h:514
Definition: normalize.hpp:13