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
GrammarCompare.h
Go to the documentation of this file.
1
6#pragma once
7
8#include "grammar/Regular/LeftLG.h"
9#include "grammar/Regular/LeftRG.h"
10#include "grammar/Regular/RightLG.h"
11#include "grammar/Regular/RightRG.h"
12#include "grammar/ContextFree/LG.h"
13#include "grammar/ContextFree/CFG.h"
14#include "grammar/ContextFree/EpsilonFreeCFG.h"
15#include "grammar/ContextFree/CNF.h"
16#include "grammar/ContextFree/GNF.h"
17#include "grammar/ContextSensitive/CSG.h"
18#include "grammar/ContextSensitive/NonContractingGrammar.h"
19#include "grammar/Unrestricted/ContextPreservingUnrestrictedGrammar.h"
20#include "grammar/Unrestricted/UnrestrictedGrammar.h"
21
22namespace compare {
23
24class GrammarCompare {
25public:
26 template < class SymbolType >
27 static bool compare(const grammar::LeftLG < SymbolType > & a, const grammar::LeftLG < SymbolType > & b);
28
29 template < class SymbolType >
30 static bool compare(const grammar::LeftRG < SymbolType > & a, const grammar::LeftRG < SymbolType > & b);
31
32 template < class SymbolType >
33 static bool compare(const grammar::RightLG < SymbolType > & a, const grammar::RightLG < SymbolType > & b);
34
35 template < class SymbolType >
36 static bool compare(const grammar::RightRG < SymbolType > & a, const grammar::RightRG < SymbolType > & b);
37
38 template < class SymbolType >
39 static bool compare(const grammar::LG < SymbolType > & a, const grammar::LG < SymbolType > & b);
40
41 template < class SymbolType >
42 static bool compare(const grammar::CFG < SymbolType > & a, const grammar::CFG < SymbolType > & b);
43
44 template < class SymbolType >
45 static bool compare(const grammar::EpsilonFreeCFG < SymbolType > & a, const grammar::EpsilonFreeCFG < SymbolType > & b);
46
47 template < class SymbolType >
48 static bool compare(const grammar::CNF < SymbolType > & a, const grammar::CNF < SymbolType > & b);
49
50 template < class SymbolType >
51 static bool compare(const grammar::GNF < SymbolType > & a, const grammar::GNF < SymbolType > & b);
52
53 template < class SymbolType >
54 static bool compare(const grammar::CSG < SymbolType > & a, const grammar::CSG < SymbolType > & b);
55
56 template < class SymbolType >
57 static bool compare(const grammar::NonContractingGrammar < SymbolType > & a, const grammar::NonContractingGrammar < SymbolType > & b);
58
59 template < class SymbolType >
60 static bool compare(const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & a, const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & b);
61
62 template < class SymbolType >
63 static bool compare(const grammar::UnrestrictedGrammar < SymbolType > & a, const grammar::UnrestrictedGrammar < SymbolType > & b);
64};
65
66template < class SymbolType >
67bool GrammarCompare::compare(const grammar::LeftLG < SymbolType > & a, const grammar::LeftLG < SymbolType > & b) {
68 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
69 a.getRules() == b.getRules() &&
70// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
71 a.getInitialSymbol() == b.getInitialSymbol() ;
72}
73
74template < class SymbolType >
75bool GrammarCompare::compare(const grammar::LeftRG < SymbolType > & a, const grammar::LeftRG < SymbolType > & b) {
76 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
77 a.getRules() == b.getRules() &&
78// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
79 a.getInitialSymbol() == b.getInitialSymbol() ;
80}
81
82template < class SymbolType >
83bool GrammarCompare::compare(const grammar::RightLG < SymbolType > & a, const grammar::RightLG < SymbolType > & b) {
84 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
85 a.getRules() == b.getRules() &&
86// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
87 a.getInitialSymbol() == b.getInitialSymbol() ;
88}
89
90template < class SymbolType >
91bool GrammarCompare::compare(const grammar::RightRG < SymbolType > & a, const grammar::RightRG < SymbolType > & b) {
92 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
93 a.getRules() == b.getRules() &&
94// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
95 a.getInitialSymbol() == b.getInitialSymbol() ;
96}
97
98template < class SymbolType >
99bool GrammarCompare::compare(const grammar::LG < SymbolType > & a, const grammar::LG < SymbolType > & b) {
100 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
101 a.getRules() == b.getRules() &&
102// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
103 a.getInitialSymbol() == b.getInitialSymbol() ;
104}
105
106template < class SymbolType >
107bool GrammarCompare::compare(const grammar::CFG < SymbolType > & a, const grammar::CFG < SymbolType > & b) {
108 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
109 a.getRules() == b.getRules() &&
110// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
111 a.getInitialSymbol() == b.getInitialSymbol() ;
112}
113
114template < class SymbolType >
115bool GrammarCompare::compare(const grammar::EpsilonFreeCFG < SymbolType > & a, const grammar::EpsilonFreeCFG < SymbolType > & b) {
116 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
117 a.getRules() == b.getRules() &&
118// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
119 a.getInitialSymbol() == b.getInitialSymbol() ;
120}
121
122template < class SymbolType >
123bool GrammarCompare::compare(const grammar::CNF < SymbolType > & a, const grammar::CNF < SymbolType > & b) {
124 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
125 a.getRules() == b.getRules() &&
126// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
127 a.getInitialSymbol() == b.getInitialSymbol() ;
128}
129
130template < class SymbolType >
131bool GrammarCompare::compare(const grammar::GNF < SymbolType > & a, const grammar::GNF < SymbolType > & b) {
132 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
133 a.getRules() == b.getRules() &&
134// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
135 a.getInitialSymbol() == b.getInitialSymbol() ;
136}
137
138template < class SymbolType >
139bool GrammarCompare::compare(const grammar::CSG < SymbolType > & a, const grammar::CSG < SymbolType > & b) {
140 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
141 a.getRules() == b.getRules() &&
142// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
143 a.getInitialSymbol() == b.getInitialSymbol() ;
144}
145
146template < class SymbolType >
147bool GrammarCompare::compare(const grammar::NonContractingGrammar < SymbolType > & a, const grammar::NonContractingGrammar < SymbolType > & b) {
148 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
149 a.getRules() == b.getRules() &&
150// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
151 a.getInitialSymbol() == b.getInitialSymbol() ;
152}
153
154template < class SymbolType >
155bool GrammarCompare::compare(const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & a, const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & b) {
156 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
157 a.getRules() == b.getRules() &&
158// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
159 a.getInitialSymbol() == b.getInitialSymbol() ;
160}
161
162template < class SymbolType >
163bool GrammarCompare::compare(const grammar::UnrestrictedGrammar < SymbolType > & a, const grammar::UnrestrictedGrammar < SymbolType > & b) {
164 return a.getNonterminalAlphabet() == b.getNonterminalAlphabet() &&
165 a.getRules() == b.getRules() &&
166// a.getTerminalAlphabet() == b.getTerminalAlphabet() &&
167 a.getInitialSymbol() == b.getInitialSymbol() ;
168}
169
170} /* namespace compare */
171
compare::GrammarCompare
Definition: GrammarCompare.h:24
compare::GrammarCompare::compare
static bool compare(const grammar::LeftLG< SymbolType > &a, const grammar::LeftLG< SymbolType > &b)
Definition: GrammarCompare.h:67
grammar::CFG
Context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free lang...
Definition: CFG.h:67
grammar::CFG::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: CFG.h:148
grammar::CFG::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: CFG.h:177
grammar::CFG::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > & getRules() const &
Definition: CFG.h:332
grammar::CNF
Chomsky normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: CNF.h:66
grammar::CNF::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: CNF.h:165
grammar::CNF::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, NonterminalSymbolType > > > > & getRules() const &
Definition: CNF.h:373
grammar::CNF::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: CNF.h:194
grammar::CSG
Context sensitive grammar in Chomsky hierarchy or type 1 in Chomsky hierarchy. Generates context sens...
Definition: CSG.h:64
grammar::CSG::getNonterminalAlphabet
const ext::set< SymbolType > & getNonterminalAlphabet() const &
Definition: CSG.h:178
grammar::CSG::getInitialSymbol
const SymbolType & getInitialSymbol() const &
Definition: CSG.h:149
grammar::CSG::getRules
const ext::map< ext::tuple< ext::vector< SymbolType >, SymbolType, ext::vector< SymbolType > >, ext::set< ext::vector< SymbolType > > > & getRules() const &
Definition: CSG.h:363
grammar::ContextPreservingUnrestrictedGrammar
Context preserving unrestricted grammar. Type 0 in Chomsky hierarchy. Generates recursively enumerabl...
Definition: ContextPreservingUnrestrictedGrammar.h:64
grammar::ContextPreservingUnrestrictedGrammar::getRules
const ext::map< ext::tuple< ext::vector< SymbolType >, SymbolType, ext::vector< SymbolType > >, ext::set< ext::vector< SymbolType > > > & getRules() const &
Definition: ContextPreservingUnrestrictedGrammar.h:334
grammar::ContextPreservingUnrestrictedGrammar::getNonterminalAlphabet
const ext::set< SymbolType > & getNonterminalAlphabet() const &
Definition: ContextPreservingUnrestrictedGrammar.h:173
grammar::ContextPreservingUnrestrictedGrammar::getInitialSymbol
const SymbolType & getInitialSymbol() const &
Definition: ContextPreservingUnrestrictedGrammar.h:144
grammar::EpsilonFreeCFG
Context free grammar without epsilon rules in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: EpsilonFreeCFG.h:65
grammar::EpsilonFreeCFG::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: EpsilonFreeCFG.h:173
grammar::EpsilonFreeCFG::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: EpsilonFreeCFG.h:144
grammar::EpsilonFreeCFG::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > & getRules() const &
Definition: EpsilonFreeCFG.h:340
grammar::GNF
Greibach normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: GNF.h:65
grammar::GNF::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::pair< TerminalSymbolType, ext::vector< NonterminalSymbolType > > > > & getRules() const &
Definition: GNF.h:339
grammar::GNF::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: GNF.h:144
grammar::GNF::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: GNF.h:173
grammar::LG
Context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free lang...
Definition: LG.h:67
grammar::LG::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: LG.h:161
grammar::LG::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: LG.h:190
grammar::LG::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::variant< ext::vector< TerminalSymbolType >, ext::tuple< ext::vector< TerminalSymbolType >, NonterminalSymbolType, ext::vector< TerminalSymbolType > > > > > & getRules() const &
Definition: LG.h:370
grammar::LeftLG
Left linear grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages.
Definition: LeftLG.h:66
grammar::LeftLG::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: LeftLG.h:160
grammar::LeftLG::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: LeftLG.h:189
grammar::LeftLG::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::variant< ext::vector< TerminalSymbolType >, ext::pair< NonterminalSymbolType, ext::vector< TerminalSymbolType > > > > > & getRules() const &
Definition: LeftLG.h:359
grammar::LeftRG
Left regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: LeftRG.h:70
grammar::LeftRG::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< NonterminalSymbolType, TerminalSymbolType > > > > & getRules() const &
Definition: LeftRG.h:376
grammar::LeftRG::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: LeftRG.h:169
grammar::LeftRG::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: LeftRG.h:198
grammar::NonContractingGrammar
Noncontracting grammar in Chomsky hierarchy or type 1 in Chomsky hierarchy. Generates context sensiti...
Definition: NonContractingGrammar.h:64
grammar::NonContractingGrammar::getNonterminalAlphabet
const ext::set< SymbolType > & getNonterminalAlphabet() const &
Definition: NonContractingGrammar.h:172
grammar::NonContractingGrammar::getRules
const ext::map< ext::vector< SymbolType >, ext::set< ext::vector< SymbolType > > > & getRules() const &
Definition: NonContractingGrammar.h:360
grammar::NonContractingGrammar::getInitialSymbol
const SymbolType & getInitialSymbol() const &
Definition: NonContractingGrammar.h:143
grammar::RightLG
Right linear grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: RightLG.h:65
grammar::RightLG::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::variant< ext::vector< TerminalSymbolType >, ext::pair< ext::vector< TerminalSymbolType >, NonterminalSymbolType > > > > & getRules() const &
Definition: RightLG.h:356
grammar::RightLG::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: RightLG.h:159
grammar::RightLG::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: RightLG.h:188
grammar::RightRG
Right regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular language...
Definition: RightRG.h:70
grammar::RightRG::getRules
const ext::map< NonterminalSymbolType, ext::set< ext::variant< TerminalSymbolType, ext::pair< TerminalSymbolType, NonterminalSymbolType > > > > & getRules() const &
Definition: RightRG.h:375
grammar::RightRG::getNonterminalAlphabet
const ext::set< NonterminalSymbolType > & getNonterminalAlphabet() const &
Definition: RightRG.h:198
grammar::RightRG::getInitialSymbol
const NonterminalSymbolType & getInitialSymbol() const &
Definition: RightRG.h:169
grammar::UnrestrictedGrammar
Unrestricted grammar. Type 0 in Chomsky hierarchy. Generates recursively enumerable languages.
Definition: UnrestrictedGrammar.h:64
grammar::UnrestrictedGrammar::getRules
const ext::map< ext::vector< SymbolType >, ext::set< ext::vector< SymbolType > > > & getRules() const &
Definition: UnrestrictedGrammar.h:330
grammar::UnrestrictedGrammar::getInitialSymbol
const SymbolType & getInitialSymbol() const &
Definition: UnrestrictedGrammar.h:144
grammar::UnrestrictedGrammar::getNonterminalAlphabet
const ext::set< SymbolType > & getNonterminalAlphabet() const &
Definition: UnrestrictedGrammar.h:173
compare
Definition: AutomatonCompare.h:29
Generated on Mon Dec 27 2021 10:21:52 for Algorithms Library Toolkit by doxygen 1.9.2