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
GrammarDiff.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <compare/DiffAux.h>
9#include <compare/GrammarCompare.h>
10
11#include <ostream>
12
13#include <ext/utility>
14#include <ext/typeinfo>
15#include <ext/iostream>
16#include <ext/algorithm>
17
18#include <alib/set>
19#include <alib/map>
20#include <alib/list>
21#include <alib/vector>
22
23#include "grammar/Regular/LeftLG.h"
24#include "grammar/Regular/LeftRG.h"
25#include "grammar/Regular/RightLG.h"
26#include "grammar/Regular/RightRG.h"
27#include "grammar/ContextFree/LG.h"
28#include "grammar/ContextFree/CFG.h"
29#include "grammar/ContextFree/EpsilonFreeCFG.h"
30#include "grammar/ContextFree/CNF.h"
31#include "grammar/ContextFree/GNF.h"
32#include "grammar/ContextSensitive/CSG.h"
33#include "grammar/ContextSensitive/NonContractingGrammar.h"
34#include "grammar/Unrestricted/ContextPreservingUnrestrictedGrammar.h"
35#include "grammar/Unrestricted/UnrestrictedGrammar.h"
36
37namespace compare {
38
39class GrammarDiff {
40private:
41 template < class SymbolType >
42 static void printDiff(const grammar::LeftLG < SymbolType > & a, const grammar::LeftLG < SymbolType > & b, ext::ostream & out );
43
44 template < class SymbolType >
45 static void printDiff(const grammar::LeftRG < SymbolType > & a, const grammar::LeftRG < SymbolType > & b, ext::ostream & out );
46
47 template < class SymbolType >
48 static void printDiff(const grammar::RightLG < SymbolType > & a, const grammar::RightLG < SymbolType > & b, ext::ostream & out );
49
50 template < class SymbolType >
51 static void printDiff(const grammar::RightRG < SymbolType > & a, const grammar::RightRG < SymbolType > & b, ext::ostream & out );
52
53 template < class SymbolType >
54 static void printDiff(const grammar::LG < SymbolType > & a, const grammar::LG < SymbolType > & b, ext::ostream & out );
55
56 template < class SymbolType >
57 static void printDiff(const grammar::CFG < SymbolType > & a, const grammar::CFG < SymbolType > & b, ext::ostream & out );
58
59 template < class SymbolType >
60 static void printDiff(const grammar::EpsilonFreeCFG < SymbolType > & a, const grammar::EpsilonFreeCFG < SymbolType > & b, ext::ostream & out );
61
62 template < class SymbolType >
63 static void printDiff(const grammar::CNF < SymbolType > & a, const grammar::CNF < SymbolType > & b, ext::ostream & out );
64
65 template < class SymbolType >
66 static void printDiff(const grammar::GNF < SymbolType > & a, const grammar::GNF < SymbolType > & b, ext::ostream & out );
67
68 template < class SymbolType >
69 static void printDiff(const grammar::CSG < SymbolType > & a, const grammar::CSG < SymbolType > & b, ext::ostream & out );
70
71 template < class SymbolType >
72 static void printDiff(const grammar::NonContractingGrammar < SymbolType > & a, const grammar::NonContractingGrammar < SymbolType > & b, ext::ostream & out );
73
74 template < class SymbolType >
75 static void printDiff(const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & a, const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & b, ext::ostream & out );
76
77 template < class SymbolType >
78 static void printDiff(const grammar::UnrestrictedGrammar < SymbolType > & a, const grammar::UnrestrictedGrammar < SymbolType > & b, ext::ostream & out );
79public:
80 template<class T>
81 static void diff(const T & a, const T & b, ext::ostream & out );
82
83 template < class T >
84 static std::string diff ( const T & a, const T & b );
85};
86
87template < class SymbolType >
88void GrammarDiff::printDiff(const grammar::LeftLG < SymbolType > & a, const grammar::LeftLG < SymbolType > & b, ext::ostream & out ) {
89 out << "GrammarsComparer" << std::endl;
90
91 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
92 out << "Nonterminal alphabet" << std::endl;
93
94 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
95 }
96
97 if(a.getRules() != b.getRules()){
98 out << "Rules" << std::endl;
99
100 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
101 }
102
103 if(a.getInitialSymbol() != b.getInitialSymbol()){
104 out << "Initial symbol" << std::endl;
105
106 out << "< " << a.getInitialSymbol() << std::endl;
107 out << "---" << std::endl;
108 out << "> " << b.getInitialSymbol() << std::endl;
109 }
110
111 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
112 out << "Terminal alphabet" << std::endl;
113
114 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
115 }
116}
117
118template < class SymbolType >
119void GrammarDiff::printDiff(const grammar::LeftRG < SymbolType > & a, const grammar::LeftRG < SymbolType > & b, ext::ostream & out ) {
120 out << "GrammarsComparer" << std::endl;
121
122 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
123 out << "Nonterminal alphabet" << std::endl;
124
125 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
126 }
127
128 if(a.getRules() != b.getRules()){
129 out << "Rules" << std::endl;
130
131 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
132 }
133
134 if(a.getInitialSymbol() != b.getInitialSymbol()){
135 out << "Initial symbol" << std::endl;
136
137 out << "< " << a.getInitialSymbol() << std::endl;
138 out << "---" << std::endl;
139 out << "> " << b.getInitialSymbol() << std::endl;
140 }
141
142 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
143 out << "Terminal alphabet" << std::endl;
144
145 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
146 }
147}
148
149template < class SymbolType >
150void GrammarDiff::printDiff(const grammar::RightLG < SymbolType > & a, const grammar::RightLG < SymbolType > & b, ext::ostream & out ) {
151 out << "GrammarsComparer" << std::endl;
152
153 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
154 out << "Nonterminal alphabet" << std::endl;
155
156 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
157 }
158
159 if(a.getRules() != b.getRules()){
160 out << "Rules" << std::endl;
161
162 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
163 }
164
165 if(a.getInitialSymbol() != b.getInitialSymbol()){
166 out << "Initial symbol" << std::endl;
167
168 out << "< " << a.getInitialSymbol() << std::endl;
169 out << "---" << std::endl;
170 out << "> " << b.getInitialSymbol() << std::endl;
171 }
172
173 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
174 out << "Terminal alphabet" << std::endl;
175
176 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
177 }
178}
179
180template < class SymbolType >
181void GrammarDiff::printDiff(const grammar::RightRG < SymbolType > & a, const grammar::RightRG < SymbolType > & b, ext::ostream & out ) {
182 out << "GrammarsComparer" << std::endl;
183
184 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
185 out << "Nonterminal alphabet" << std::endl;
186
187 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
188 }
189
190 if(a.getRules() != b.getRules()){
191 out << "Rules" << std::endl;
192
193 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
194 }
195
196 if(a.getInitialSymbol() != b.getInitialSymbol()){
197 out << "Initial symbol" << std::endl;
198
199 out << "< " << a.getInitialSymbol() << std::endl;
200 out << "---" << std::endl;
201 out << "> " << b.getInitialSymbol() << std::endl;
202 }
203
204 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
205 out << "Terminal alphabet" << std::endl;
206
207 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
208 }
209}
210
211template < class SymbolType >
212void GrammarDiff::printDiff(const grammar::LG < SymbolType > & a, const grammar::LG < SymbolType > & b, ext::ostream & out ) {
213 out << "GrammarsComparer" << std::endl;
214
215 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
216 out << "Nonterminal alphabet" << std::endl;
217
218 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
219 }
220
221 if(a.getRules() != b.getRules()){
222 out << "Rules" << std::endl;
223
224 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
225 }
226
227 if(a.getInitialSymbol() != b.getInitialSymbol()){
228 out << "Initial symbol" << std::endl;
229
230 out << "< " << a.getInitialSymbol() << std::endl;
231 out << "---" << std::endl;
232 out << "> " << b.getInitialSymbol() << std::endl;
233 }
234
235 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
236 out << "Terminal alphabet" << std::endl;
237
238 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
239 }
240}
241
242template < class SymbolType >
243void GrammarDiff::printDiff(const grammar::CFG < SymbolType > & a, const grammar::CFG < SymbolType > & b, ext::ostream & out ) {
244 out << "GrammarsComparer" << std::endl;
245
246 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
247 out << "Nonterminal alphabet" << std::endl;
248
249 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
250 }
251
252 if(a.getRules() != b.getRules()){
253 out << "Rules" << std::endl;
254
255 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
256 }
257
258 if(a.getInitialSymbol() != b.getInitialSymbol()){
259 out << "Initial symbol" << std::endl;
260
261 out << "< " << a.getInitialSymbol() << std::endl;
262 out << "---" << std::endl;
263 out << "> " << b.getInitialSymbol() << std::endl;
264 }
265
266 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
267 out << "Terminal alphabet" << std::endl;
268
269 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
270 }
271}
272
273template < class SymbolType >
274void GrammarDiff::printDiff(const grammar::EpsilonFreeCFG < SymbolType > & a, const grammar::EpsilonFreeCFG < SymbolType > & b, ext::ostream & out ) {
275 out << "GrammarsComparer" << std::endl;
276
277 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
278 out << "Nonterminal alphabet" << std::endl;
279
280 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
281 }
282
283 if(a.getRules() != b.getRules()){
284 out << "Rules" << std::endl;
285
286 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
287 }
288
289 if(a.getInitialSymbol() != b.getInitialSymbol()){
290 out << "Initial symbol" << std::endl;
291
292 out << "< " << a.getInitialSymbol() << std::endl;
293 out << "---" << std::endl;
294 out << "> " << b.getInitialSymbol() << std::endl;
295 }
296
297 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
298 out << "Terminal alphabet" << std::endl;
299
300 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
301 }
302}
303
304template < class SymbolType >
305void GrammarDiff::printDiff(const grammar::CNF < SymbolType > & a, const grammar::CNF < SymbolType > & b, ext::ostream & out ) {
306 out << "GrammarsComparer" << std::endl;
307
308 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
309 out << "Nonterminal alphabet" << std::endl;
310
311 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
312 }
313
314 if(a.getRules() != b.getRules()){
315 out << "Rules" << std::endl;
316
317 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
318 }
319
320 if(a.getInitialSymbol() != b.getInitialSymbol()){
321 out << "Initial symbol" << std::endl;
322
323 out << "< " << a.getInitialSymbol() << std::endl;
324 out << "---" << std::endl;
325 out << "> " << b.getInitialSymbol() << std::endl;
326 }
327
328 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
329 out << "Terminal alphabet" << std::endl;
330
331 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
332 }
333}
334
335template < class SymbolType >
336void GrammarDiff::printDiff(const grammar::GNF < SymbolType > & a, const grammar::GNF < SymbolType > & b, ext::ostream & out ) {
337 out << "GrammarsComparer" << std::endl;
338
339 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
340 out << "Nonterminal alphabet" << std::endl;
341
342 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
343 }
344
345 if(a.getRules() != b.getRules()){
346 out << "Rules" << std::endl;
347
348 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
349 }
350
351 if(a.getInitialSymbol() != b.getInitialSymbol()){
352 out << "Initial symbol" << std::endl;
353
354 out << "< " << a.getInitialSymbol() << std::endl;
355 out << "---" << std::endl;
356 out << "> " << b.getInitialSymbol() << std::endl;
357 }
358
359 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
360 out << "Terminal alphabet" << std::endl;
361
362 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
363 }
364}
365
366template < class SymbolType >
367void GrammarDiff::printDiff(const grammar::CSG < SymbolType > & a, const grammar::CSG < SymbolType > & b, ext::ostream & out ) {
368 out << "GrammarsComparer" << std::endl;
369
370 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
371 out << "Nonterminal alphabet" << std::endl;
372
373 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
374 }
375
376 if(a.getRules() != b.getRules()){
377 out << "Rules" << std::endl;
378
379 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
380 }
381
382 if(a.getInitialSymbol() != b.getInitialSymbol()){
383 out << "Initial symbol" << std::endl;
384
385 out << "< " << a.getInitialSymbol() << std::endl;
386 out << "---" << std::endl;
387 out << "> " << b.getInitialSymbol() << std::endl;
388 }
389
390 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
391 out << "Terminal alphabet" << std::endl;
392
393 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
394 }
395}
396
397template < class SymbolType >
398void GrammarDiff::printDiff(const grammar::NonContractingGrammar < SymbolType > & a, const grammar::NonContractingGrammar < SymbolType > & b, ext::ostream & out ) {
399 out << "GrammarsComparer" << std::endl;
400
401 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
402 out << "Nonterminal alphabet" << std::endl;
403
404 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
405 }
406
407 if(a.getRules() != b.getRules()){
408 out << "Rules" << std::endl;
409
410 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
411 }
412
413 if(a.getInitialSymbol() != b.getInitialSymbol()){
414 out << "Initial symbol" << std::endl;
415
416 out << "< " << a.getInitialSymbol() << std::endl;
417 out << "---" << std::endl;
418 out << "> " << b.getInitialSymbol() << std::endl;
419 }
420
421 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
422 out << "Terminal alphabet" << std::endl;
423
424 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
425 }
426}
427
428template < class SymbolType >
429void GrammarDiff::printDiff(const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & a, const grammar::ContextPreservingUnrestrictedGrammar < SymbolType > & b, ext::ostream & out ) {
430 out << "GrammarsComparer" << std::endl;
431
432 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
433 out << "Nonterminal alphabet" << std::endl;
434
435 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
436 }
437
438 if(a.getRules() != b.getRules()){
439 out << "Rules" << std::endl;
440
441 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
442 }
443
444 if(a.getInitialSymbol() != b.getInitialSymbol()){
445 out << "Initial symbol" << std::endl;
446
447 out << "< " << a.getInitialSymbol() << std::endl;
448 out << "---" << std::endl;
449 out << "> " << b.getInitialSymbol() << std::endl;
450 }
451
452 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
453 out << "Terminal alphabet" << std::endl;
454
455 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
456 }
457}
458
459template < class SymbolType >
460void GrammarDiff::printDiff(const grammar::UnrestrictedGrammar < SymbolType > & a, const grammar::UnrestrictedGrammar < SymbolType > & b, ext::ostream & out ) {
461 out << "GrammarsComparer" << std::endl;
462
463 if(a.getNonterminalAlphabet() != b.getNonterminalAlphabet()) {
464 out << "Nonterminal alphabet" << std::endl;
465
466 DiffAux::setDiff ( out, a.getNonterminalAlphabet(), b.getNonterminalAlphabet());
467 }
468
469 if(a.getRules() != b.getRules()){
470 out << "Rules" << std::endl;
471
472 DiffAux::mapDiff ( out, a.getRules(), b.getRules());
473 }
474
475 if(a.getInitialSymbol() != b.getInitialSymbol()){
476 out << "Initial symbol" << std::endl;
477
478 out << "< " << a.getInitialSymbol() << std::endl;
479 out << "---" << std::endl;
480 out << "> " << b.getInitialSymbol() << std::endl;
481 }
482
483 if(a.getTerminalAlphabet() != b.getTerminalAlphabet()) {
484 out << "Terminal alphabet" << std::endl;
485
486 DiffAux::setDiff ( out, a.getTerminalAlphabet(), b.getTerminalAlphabet());
487 }
488}
489
490template < class T >
491void GrammarDiff::diff(const T & a, const T & b, ext::ostream & out ) {
492 if(!GrammarCompare::compare(a, b)) {
493 GrammarDiff::printDiff ( a, b, out );
494 }
495}
496
497template < class T >
498std::string GrammarDiff::diff ( const T & a, const T & b ) {
499 ext::ostringstream ss;
500 diff ( a, b, ss );
501 return ss.str ( );
502}
503
504} /* namespace compare */
505
compare::DiffAux::setDiff
static void setDiff(ext::ostream &out, const ext::set< T > &a, const ext::set< T > &b)
Definition: DiffAux.h:33
compare::DiffAux::mapDiff
static void mapDiff(ext::ostream &out, const ext::map< T, R > &a, const ext::map< T, R > &b)
Definition: DiffAux.h:84
compare::GrammarCompare::compare
static bool compare(const grammar::LeftLG< SymbolType > &a, const grammar::LeftLG< SymbolType > &b)
Definition: GrammarCompare.h:67
compare::GrammarDiff
Definition: GrammarDiff.h:39
compare::GrammarDiff::diff
static void diff(const T &a, const T &b, ext::ostream &out)
Definition: GrammarDiff.h:491
ext::ostream
Definition: ostream.h:14
ext::ostringstream
Definition: sstream.h:15
ext::ostringstream::str
std::string str() const &
Definition: sstream.cpp:29
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::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: CFG.h:215
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::CNF::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: CNF.h:232
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::getTerminalAlphabet
const ext::set< SymbolType > & getTerminalAlphabet() const &
Definition: CSG.h:216
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::getTerminalAlphabet
const ext::set< SymbolType > & getTerminalAlphabet() const &
Definition: ContextPreservingUnrestrictedGrammar.h:211
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::EpsilonFreeCFG::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: EpsilonFreeCFG.h:211
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::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: GNF.h:211
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::LG::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: LG.h:228
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::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: LeftLG.h:227
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::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: LeftRG.h:236
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::getTerminalAlphabet
const ext::set< SymbolType > & getTerminalAlphabet() const &
Definition: NonContractingGrammar.h:210
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::RightLG::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: RightLG.h:226
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::getTerminalAlphabet
const ext::set< TerminalSymbolType > & getTerminalAlphabet() const &
Definition: RightRG.h:236
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::getTerminalAlphabet
const ext::set< SymbolType > & getTerminalAlphabet() const &
Definition: UnrestrictedGrammar.h:211
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