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