Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
EpsilonFreeCFG.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
64template < class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType >
65class EpsilonFreeCFG final : public core::Components < EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType >, ext::set < TerminalSymbolType >, component::Set, TerminalAlphabet, ext::set < NonterminalSymbolType >, component::Set, NonterminalAlphabet, NonterminalSymbolType, component::Value, InitialSymbol > {
70
74 bool generatesEpsilon;
75
76public:
82 explicit EpsilonFreeCFG ( NonterminalSymbolType initialSymbol );
83
91 explicit EpsilonFreeCFG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol );
92
103 bool addRule ( NonterminalSymbolType leftHandSide, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rightHandSide );
104
113 void addRules ( NonterminalSymbolType leftHandSide, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > rightHandSide );
114
121
128
137 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rightHandSide );
138
144 const NonterminalSymbolType & getInitialSymbol ( ) const & {
145 return this->template accessComponent < InitialSymbol > ( ).get ( );
146 }
147
153 NonterminalSymbolType && getInitialSymbol ( ) && {
154 return std::move ( this->template accessComponent < InitialSymbol > ( ).get ( ) );
155 }
156
164 bool setInitialSymbol ( NonterminalSymbolType 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
193 bool addNonterminalSymbol ( NonterminalSymbolType symbol ) {
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
231 bool addTerminalSymbol ( TerminalSymbolType symbol ) {
232 return this->template accessComponent < TerminalAlphabet > ( ).add ( std::move ( symbol ) );
233 }
234
241 this->template accessComponent < TerminalAlphabet > ( ).set ( std::move ( symbols ) );
242 }
243
249 void setGeneratesEpsilon ( bool genEps );
250
256 bool getGeneratesEpsilon ( ) const;
257
265 auto operator <=> ( const EpsilonFreeCFG & other ) const {
266 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) <=> std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
267 }
268
276 bool operator == ( const EpsilonFreeCFG & other ) const {
277 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) == std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
278 }
279
288 friend ext::ostream & operator << ( ext::ostream & out, const EpsilonFreeCFG & instance ) {
289 return out << "(EpsilonFreeCFG"
290 << " nonterminalAlphabet = " << instance.getNonterminalAlphabet ( )
291 << " terminalAlphabet = " << instance.getTerminalAlphabet ( )
292 << " initialSymbol = " << instance.getInitialSymbol ( )
293 << " rules = " << instance.getRules ( )
294 << " generatesEpsilon = " << instance.getGeneratesEpsilon ( )
295 << ")";
296 }
297};
298
299template < class TerminalSymbolType, class NonterminalSymbolType >
301}
302
303template < class TerminalSymbolType, class NonterminalSymbolType >
304EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType >::EpsilonFreeCFG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol ) : core::Components < EpsilonFreeCFG, 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 ) {
305}
306
307template < class TerminalSymbolType, class NonterminalSymbolType >
309 if ( rightHandSide.empty ( ) )
310 throw GrammarException ( "Epsilon rule is not allowed" );
311
312 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
313 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
314
315 for ( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol : rightHandSide )
316 if ( !getTerminalAlphabet ( ).count ( symbol ) && !getNonterminalAlphabet ( ).count ( symbol ) )
317 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
318
319 return rules[std::move ( leftHandSide )].insert ( std::move ( rightHandSide ) ).second;
320}
321
322template < class TerminalSymbolType, class NonterminalSymbolType >
324 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
325 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
326
327 for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rightHandSide ) {
328 if ( rhs.empty ( ) )
329 throw GrammarException ( "Epsilon rule is not allowed" );
330
332 if ( ! getTerminalAlphabet ( ).count ( symbol ) && ! getNonterminalAlphabet ( ).count ( symbol ) )
333 throw GrammarException ( "Symbol \"" + ext::to_string ( symbol ) + "\" is not neither terminal nor nonterminal symbol" );
334 }
335
336 rules [ std::move ( leftHandSide ) ].insert ( ext::make_mover ( rightHandSide ).begin ( ), ext::make_mover ( rightHandSide ).end ( ) );
337}
338
339template < class TerminalSymbolType, class NonterminalSymbolType >
341 return rules;
342}
343
344template < class TerminalSymbolType, class NonterminalSymbolType >
346 return std::move ( rules );
347}
348
349template < class TerminalSymbolType, class NonterminalSymbolType >
351 return rules[leftHandSide].erase ( rightHandSide );
352}
353
354template < class TerminalSymbolType, class NonterminalSymbolType >
356 generatesEpsilon = genEps;
357}
358
359template < class TerminalSymbolType, class NonterminalSymbolType >
361 return generatesEpsilon;
362}
363
364} /* namespace grammar */
365
366namespace core {
367
374template < class TerminalSymbolType, class NonterminalSymbolType >
375class SetConstraint< grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType >, TerminalSymbolType, grammar::TerminalAlphabet > {
376public:
385 static bool used ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
386 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) )
388 if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
389 return true;
390
391 return false;
392 }
393
402 static bool available ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType & ) {
403 return true;
404 }
405
414 static void valid ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
415 if ( grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
416 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the terminal alphabet since it is already in the nonterminal alphabet." );
417 }
418};
419
426template < class TerminalSymbolType, class NonterminalSymbolType >
427class SetConstraint< grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::NonterminalAlphabet > {
428public:
437 static bool used ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
438 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
439 if ( rule.first == symbol )
440 return true;
441
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
459 static bool available ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
460 return true;
461 }
462
471 static void valid ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
472 if ( grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( 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
483template < class TerminalSymbolType, class NonterminalSymbolType >
484class ElementConstraint< grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::InitialSymbol > {
485public:
494 static bool available ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
495 return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
496 }
497
504 static void valid ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
505 }
506};
507
513template < class TerminalSymbolType, class NonterminalSymbolType >
514struct normalize < grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > > {
516 ext::set < DefaultSymbolType > nonterminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonterminalAlphabet ( ) );
517 ext::set < DefaultSymbolType > terminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getTerminalAlphabet ( ) );
518 DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getInitialSymbol ( ) );
519
520 grammar::EpsilonFreeCFG < > res ( std::move ( nonterminals ), std::move ( terminals ), std::move ( initialSymbol ) );
521
522 for ( std::pair < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > && rule : ext::make_mover ( std::move ( value ).getRules ( ) ) ) {
523
526 rhs.insert ( alphabet::SymbolNormalize::normalizeVariantSymbols ( std::move ( target ) ) );
527
528 DefaultSymbolType lhs = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( rule.first ) );
529
530 res.addRules ( std::move ( lhs ), std::move ( rhs ) );
531 }
532
533 res.setGeneratesEpsilon ( value.getGeneratesEpsilon ( ) );
534
535 return res;
536 }
537};
538
539} /* namespace core */
540
541extern template class grammar::EpsilonFreeCFG < >;
542
static ext::set< DefaultSymbolType > normalizeAlphabet(ext::set< SymbolType > &&symbols)
Definition: SymbolNormalize.h:50
static ext::vector< ext::variant< DefaultSymbolType, DefaultSymbolType > > normalizeVariantSymbols(ext::vector< ext::variant< FirstSymbolType, SecondSymbolType > > &&symbols)
Definition: SymbolNormalize.h:95
static DefaultSymbolType normalizeSymbol(SymbolType &&symbol)
Definition: SymbolNormalize.h:68
Definition: components.hpp:181
static void valid(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: EpsilonFreeCFG.h:504
static bool available(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: EpsilonFreeCFG.h:494
Definition: components.hpp:25
static void valid(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: EpsilonFreeCFG.h:414
static bool available(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType &)
Definition: EpsilonFreeCFG.h:402
static bool used(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: EpsilonFreeCFG.h:385
static void valid(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: EpsilonFreeCFG.h:471
static bool used(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: EpsilonFreeCFG.h:437
static bool available(const grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: EpsilonFreeCFG.h:459
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
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
Context free grammar without epsilon rules in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: EpsilonFreeCFG.h:65
void setTerminalAlphabet(ext::set< TerminalSymbolType > symbols)
Definition: EpsilonFreeCFG.h:240
bool addNonterminalSymbol(NonterminalSymbolType symbol)
Definition: EpsilonFreeCFG.h:193
void setNonterminalAlphabet(ext::set< NonterminalSymbolType > symbols)
Definition: EpsilonFreeCFG.h:202
bool setInitialSymbol(NonterminalSymbolType symbol)
Definition: EpsilonFreeCFG.h:164
bool addTerminalSymbol(TerminalSymbolType symbol)
Definition: EpsilonFreeCFG.h:231
EpsilonFreeCFG(NonterminalSymbolType initialSymbol)
Creates a new instance of the grammar with a concrete initial symbol.
Definition: EpsilonFreeCFG.h:300
NonterminalSymbolType && getInitialSymbol() &&
Definition: EpsilonFreeCFG.h:153
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: EpsilonFreeCFG.h:173
ext::set< TerminalSymbolType > && getTerminalAlphabet() &&
Definition: EpsilonFreeCFG.h:220
const NonterminalSymbolType & getInitialSymbol() const &
Definition: EpsilonFreeCFG.h:144
auto operator<=>(const EpsilonFreeCFG &other) const
Definition: EpsilonFreeCFG.h:265
ext::set< NonterminalSymbolType > && getNonterminalAlphabet() &&
Definition: EpsilonFreeCFG.h:182
void addRules(NonterminalSymbolType leftHandSide, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > rightHandSide)
Add new rules of a grammar.
Definition: EpsilonFreeCFG.h:323
bool addRule(NonterminalSymbolType leftHandSide, ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > rightHandSide)
Add a new rule of a grammar.
Definition: EpsilonFreeCFG.h:308
bool operator==(const EpsilonFreeCFG &other) const
Definition: EpsilonFreeCFG.h:276
bool getGeneratesEpsilon() const
Definition: EpsilonFreeCFG.h:360
const ext::map< NonterminalSymbolType, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > & getRules() const &
Definition: EpsilonFreeCFG.h:340
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: EpsilonFreeCFG.h:211
void setGeneratesEpsilon(bool genEps)
Definition: EpsilonFreeCFG.h:355
bool removeRule(const NonterminalSymbolType &leftHandSide, const ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > &rightHandSide)
Definition: EpsilonFreeCFG.h:350
friend ext::ostream & operator<<(ext::ostream &out, const EpsilonFreeCFG &instance)
Definition: EpsilonFreeCFG.h:288
Definition: GrammarException.h:15
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::EpsilonFreeCFG< > eval(grammar::EpsilonFreeCFG< TerminalSymbolType, NonterminalSymbolType > &&value)
Definition: EpsilonFreeCFG.h:515
Definition: normalize.hpp:13