Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
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