Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
CNF.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
65template < class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType >
66class CNF final : public core::Components < CNF < TerminalSymbolType, NonterminalSymbolType >, ext::set < TerminalSymbolType >, component::Set, TerminalAlphabet, ext::set < NonterminalSymbolType >, component::Set, NonterminalAlphabet, NonterminalSymbolType, component::Value, InitialSymbol > {
71
75 bool generatesEpsilon;
76
77public:
83 explicit CNF ( NonterminalSymbolType initialSymbol );
84
92 explicit CNF ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol );
93
104 bool addRule ( NonterminalSymbolType leftHandSide, ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > rightHandSide );
105
114 void addRules ( NonterminalSymbolType leftHandSide, ext::set < ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > > rightHandSide );
115
122
129
138 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > & rightHandSide );
139
148 bool removeRule ( const NonterminalSymbolType & leftHandSide, const TerminalSymbolType & rightHandSide );
149
158 bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::pair < NonterminalSymbolType, NonterminalSymbolType > & rightHandSide );
159
165 const NonterminalSymbolType & getInitialSymbol ( ) const & {
166 return this->template accessComponent < InitialSymbol > ( ).get ( );
167 }
168
174 NonterminalSymbolType && getInitialSymbol ( ) && {
175 return std::move ( this->template accessComponent < InitialSymbol > ( ).get ( ) );
176 }
177
185 bool setInitialSymbol ( NonterminalSymbolType symbol ) {
186 return this->template accessComponent < InitialSymbol > ( ).set ( std::move ( symbol ) );
187 }
188
195 return this->template accessComponent < NonterminalAlphabet > ( ).get ( );
196 }
197
204 return std::move ( this->template accessComponent < NonterminalAlphabet > ( ).get ( ) );
205 }
206
214 bool addNonterminalSymbol ( NonterminalSymbolType symbol ) {
215 return this->template accessComponent < NonterminalAlphabet > ( ).add ( std::move ( symbol ) );
216 }
217
224 this->template accessComponent < NonterminalAlphabet > ( ).set ( std::move ( symbols ) );
225 }
226
233 return this->template accessComponent < TerminalAlphabet > ( ).get ( );
234 }
235
242 return std::move ( this->template accessComponent < TerminalAlphabet > ( ).get ( ) );
243 }
244
252 bool addTerminalSymbol ( TerminalSymbolType symbol ) {
253 return this->template accessComponent < TerminalAlphabet > ( ).add ( std::move ( symbol ) );
254 }
255
262 this->template accessComponent < TerminalAlphabet > ( ).set ( std::move ( symbols ) );
263 }
264
270 void setGeneratesEpsilon ( bool genEps );
271
277 bool getGeneratesEpsilon ( ) const;
278
286 auto operator <=> ( const CNF & other ) const {
287 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) <=> std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
288 }
289
297 bool operator == ( const CNF & other ) const {
298 return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) == std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
299 }
300
309 friend ext::ostream & operator << ( ext::ostream & out, const CNF & instance ) {
310 return out << "(CNF"
311 << " nonterminalAlphabet = " << instance.getNonterminalAlphabet ( )
312 << " terminalAlphabet = " << instance.getTerminalAlphabet ( )
313 << " initialSymbol = " << instance.getInitialSymbol ( )
314 << " rules = " << instance.getRules ( )
315 << " generatesEpsilon = " << instance.getGeneratesEpsilon ( )
316 << ")";
317 }
318};
319
320template < class TerminalSymbolType, class NonterminalSymbolType >
321CNF < TerminalSymbolType, NonterminalSymbolType >::CNF ( NonterminalSymbolType initialSymbol ) : CNF ( ext::set < NonterminalSymbolType > { initialSymbol }, ext::set < TerminalSymbolType > ( ), initialSymbol ) {
322}
323
324template < class TerminalSymbolType, class NonterminalSymbolType >
325CNF < TerminalSymbolType, NonterminalSymbolType >::CNF ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol ) : core::Components < CNF, 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 ) {
326}
327
328template < class TerminalSymbolType, class NonterminalSymbolType >
330 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
331 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
332
333 if ( rightHandSide.template is < TerminalSymbolType > ( ) ) {
334 if ( !getTerminalAlphabet ( ).count ( rightHandSide.template get < TerminalSymbolType > ( ) ) )
335 throw GrammarException ( "Rule must rewrite to terminal symbol" );
336 } else {
337 const ext::pair < NonterminalSymbolType, NonterminalSymbolType > rhs = rightHandSide.template get < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( );
338
339 if ( !getNonterminalAlphabet ( ).count ( rhs.first ) )
340 throw GrammarException ( "Symbol \"" + ext::to_string ( rhs.first ) + "\" is not a nonterminal symbol" );
341
342 if ( !getNonterminalAlphabet ( ).count ( rhs.second ) )
343 throw GrammarException ( "Symbol \"" + ext::to_string ( rhs.second ) + "\" is not a nonterminal symbol" );
344 }
345
346 return rules[std::move ( leftHandSide )].insert ( std::move ( rightHandSide ) ).second;
347}
348
349template < class TerminalSymbolType, class NonterminalSymbolType >
351 if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
352 throw GrammarException ( "Rule must rewrite nonterminal symbol" );
353
354 for ( const ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > & element : rightHandSide ) {
355 if ( element.template is < TerminalSymbolType > ( ) ) {
356 if ( !getTerminalAlphabet ( ).count ( element.template get < TerminalSymbolType > ( ) ) )
357 throw GrammarException ( "Rule must rewrite to terminal symbol" );
358 } else {
359 const ext::pair < NonterminalSymbolType, NonterminalSymbolType > & rhs = element.template get < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( );
360
361 if ( !getNonterminalAlphabet ( ).count ( rhs.first ) )
362 throw GrammarException ( "Symbol \"" + ext::to_string ( rhs.first ) + "\" is not a nonterminal symbol" );
363
364 if ( !getNonterminalAlphabet ( ).count ( rhs.second ) )
365 throw GrammarException ( "Symbol \"" + ext::to_string ( rhs.second ) + "\" is not a nonterminal symbol" );
366 }
367 }
368
369 rules[std::move ( leftHandSide )].insert ( ext::make_mover ( rightHandSide ).begin ( ), ext::make_mover ( rightHandSide ).end ( ) );
370}
371
372template < class TerminalSymbolType, class NonterminalSymbolType >
374 return rules;
375}
376
377template < class TerminalSymbolType, class NonterminalSymbolType >
379 return std::move ( rules );
380}
381
382template < class TerminalSymbolType, class NonterminalSymbolType >
384 return rules[leftHandSide].erase ( rightHandSide );
385}
386
387template < class TerminalSymbolType, class NonterminalSymbolType >
388bool CNF < TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType & leftHandSide, const TerminalSymbolType & rightHandSide ) {
390
391 return removeRule ( leftHandSide, rhs );
392}
393
394template < class TerminalSymbolType, class NonterminalSymbolType >
397
398 return removeRule ( leftHandSide, rhs );
399}
400
401template < class TerminalSymbolType, class NonterminalSymbolType >
403 generatesEpsilon = genEps;
404}
405
406template < class TerminalSymbolType, class NonterminalSymbolType >
408 return generatesEpsilon;
409}
410
411} /* namespace grammar */
412
413namespace core {
414
421template < class TerminalSymbolType, class NonterminalSymbolType >
422class SetConstraint< grammar::CNF < TerminalSymbolType, NonterminalSymbolType >, TerminalSymbolType, grammar::TerminalAlphabet > {
423public:
432 static bool used ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
433 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) )
434 for ( const ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > & rhs : rule.second )
435 if ( ( rhs.template is < TerminalSymbolType > ( ) && ( rhs.template get < TerminalSymbolType > ( ) == symbol ) ) )
436 return true;
437
438 return false;
439 }
440
449 static bool available ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType & ) {
450 return true;
451 }
452
461 static void valid ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
462 if ( grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
463 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the terminal alphabet since it is already in the nonterminal alphabet." );
464 }
465};
466
473template < class TerminalSymbolType, class NonterminalSymbolType >
474class SetConstraint< grammar::CNF < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::NonterminalAlphabet > {
475public:
484 static bool used ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
485 for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
486 if ( rule.first == symbol )
487 return true;
488
489 for ( const ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > & rhs : rule.second ) {
490 if ( rhs.template is < TerminalSymbolType > ( ) )
491 continue;
492
493 if ( rhs.template get < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( ).first == symbol || rhs.template get < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( ).second == symbol )
494 return true;
495 }
496
497 }
498
499 return grammar.template accessComponent < grammar::InitialSymbol > ( ).get ( ) == symbol;
500 }
501
510 static bool available ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
511 return true;
512 }
513
522 static void valid ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
523 if ( grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
524 throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the nonterminal alphabet since it is already in the terminal alphabet." );
525 }
526};
527
534template < class TerminalSymbolType, class NonterminalSymbolType >
535class ElementConstraint< grammar::CNF < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::InitialSymbol > {
536public:
545 static bool available ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
546 return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
547 }
548
555 static void valid ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
556 }
557};
558
564template < class TerminalSymbolType, class NonterminalSymbolType >
565struct normalize < grammar::CNF < TerminalSymbolType, NonterminalSymbolType > > {
567 ext::set < DefaultSymbolType > nonterminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonterminalAlphabet ( ) );
568 ext::set < DefaultSymbolType > terminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getTerminalAlphabet ( ) );
569 DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getInitialSymbol ( ) );
570
571 grammar::CNF < > res ( std::move ( nonterminals ), std::move ( terminals ), std::move ( initialSymbol ) );
572
573 for ( std::pair < NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > > > && rule : ext::make_mover ( std::move ( value ).getRules ( ) ) ) {
574
576 for ( ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > && target : ext::make_mover ( rule.second ) )
577 rhs.insert ( grammar::GrammarNormalize::normalizeRHS ( std::move ( target ) ) );
578
579 DefaultSymbolType lhs = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( rule.first ) );
580
581 res.addRules ( std::move ( lhs ), std::move ( rhs ) );
582 }
583
584 res.setGeneratesEpsilon ( value.getGeneratesEpsilon ( ) );
585
586 return res;
587 }
588};
589
590} /* namespace core */
591
592extern template class grammar::CNF < >;
593
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::CNF< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: CNF.h:555
static bool available(const grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: CNF.h:545
Definition: components.hpp:25
static bool used(const grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: CNF.h:484
static bool available(const grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType &)
Definition: CNF.h:510
static void valid(const grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &grammar, const NonterminalSymbolType &symbol)
Definition: CNF.h:522
static void valid(const grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: CNF.h:461
static bool available(const grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType &)
Definition: CNF.h:449
static bool used(const grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &grammar, const TerminalSymbolType &symbol)
Definition: CNF.h:432
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
Chomsky normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: CNF.h:66
CNF(NonterminalSymbolType initialSymbol)
Creates a new instance of the grammar with a concrete initial symbol.
Definition: CNF.h:321
auto operator<=>(const CNF &other) const
Definition: CNF.h:286
bool addTerminalSymbol(TerminalSymbolType symbol)
Definition: CNF.h:252
void setTerminalAlphabet(ext::set< TerminalSymbolType > symbols)
Definition: CNF.h:261
void addRules(NonterminalSymbolType leftHandSide, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > rightHandSide)
Add new rules of a grammar.
Definition: CNF.h:350
const NonterminalSymbolType & getInitialSymbol() const &
Definition: CNF.h:165
NonterminalSymbolType && getInitialSymbol() &&
Definition: CNF.h:174
bool addRule(NonterminalSymbolType leftHandSide, ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > rightHandSide)
Add a new rule of a grammar.
Definition: CNF.h:329
const ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > > & getRules() const &
Definition: CNF.h:373
void setGeneratesEpsilon(bool genEps)
Definition: CNF.h:402
friend ext::ostream & operator<<(ext::ostream &out, const CNF &instance)
Definition: CNF.h:309
void setNonterminalAlphabet(ext::set< NonterminalSymbolType > symbols)
Definition: CNF.h:223
bool getGeneratesEpsilon() const
Definition: CNF.h:407
ext::set< TerminalSymbolType > && getTerminalAlphabet() &&
Definition: CNF.h:241
bool setInitialSymbol(NonterminalSymbolType symbol)
Definition: CNF.h:185
bool removeRule(const NonterminalSymbolType &leftHandSide, const ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > &rightHandSide)
Definition: CNF.h:383
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: CNF.h:194
ext::set< NonterminalSymbolType > && getNonterminalAlphabet() &&
Definition: CNF.h:203
bool operator==(const CNF &other) const
Definition: CNF.h:297
bool addNonterminalSymbol(NonterminalSymbolType symbol)
Definition: CNF.h:214
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: CNF.h:232
Definition: GrammarException.h:15
static ext::pair< DefaultSymbolType, ext::vector< DefaultSymbolType > > normalizeRHS(ext::pair< FirstSymbolType, ext::vector< SecondSymbolType > > &&symbol)
Definition: GrammarNormalize.h:40
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::CNF< > eval(grammar::CNF< TerminalSymbolType, NonterminalSymbolType > &&value)
Definition: CNF.h:566
Definition: normalize.hpp:13