Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
RawRules.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/set>
9#include <alib/map>
10#include <grammar/ContextFree/CFG.h>
11#include <grammar/ContextFree/EpsilonFreeCFG.h>
12#include <grammar/ContextFree/GNF.h>
13#include <grammar/ContextFree/CNF.h>
14#include <grammar/ContextFree/LG.h>
15#include <grammar/Regular/LeftLG.h>
16#include <grammar/Regular/LeftRG.h>
17#include <grammar/Regular/RightLG.h>
18#include <grammar/Regular/RightRG.h>
19
20#include <grammar/Grammar.h>
21
22namespace grammar {
23
27class RawRules {
28public:
39 template < class TerminalSymbolType, class NonterminalSymbolType >
40 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const LG < TerminalSymbolType, NonterminalSymbolType > & grammar );
41
45 template < class TerminalSymbolType, class NonterminalSymbolType >
46 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const GNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
47
51 template < class TerminalSymbolType, class NonterminalSymbolType >
52 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
53
57 template < class TerminalSymbolType, class NonterminalSymbolType >
58 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const CNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
59
63 template < class TerminalSymbolType, class NonterminalSymbolType >
64 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const CFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
65
69 template < class TerminalSymbolType, class NonterminalSymbolType >
70 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
71
75 template < class TerminalSymbolType, class NonterminalSymbolType >
76 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
77
81 template < class TerminalSymbolType, class NonterminalSymbolType >
82 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
83
87 template < class TerminalSymbolType, class NonterminalSymbolType >
88 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > getRawRules ( const RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
89};
90
91template < class TerminalSymbolType, class NonterminalSymbolType >
92ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const LG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
93 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
94
95 for ( const auto & rule : grammar.getRules ( ) )
96 for ( const auto & rhs : rule.second ) {
97 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp;
98
99 if ( rhs.template is < ext::vector < TerminalSymbolType > > ( ) ) {
100 tmp.insert ( tmp.end ( ), rhs.template get < ext::vector < TerminalSymbolType > > ( ).begin ( ), rhs.template get < ext::vector < TerminalSymbolType > > ( ).end ( ) );
101 } else {
102 const auto & rhsTuple = rhs.template get < ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > ( );
103
104 tmp.insert ( tmp.end ( ), std::get < 0 > ( rhsTuple ).begin ( ), std::get < 0 > ( rhsTuple ).end ( ) );
105
106 tmp.push_back ( std::get < 1 > ( rhsTuple ) );
107
108 tmp.insert ( tmp.end ( ), std::get < 2 > ( rhsTuple ).begin ( ), std::get < 2 > ( rhsTuple ).end ( ) );
109 }
110
111 res[rule.first].insert ( std::move ( tmp ) );
112 }
113
114 return res;
115}
116
117template < class TerminalSymbolType, class NonterminalSymbolType >
118ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const GNF < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
119 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
120
121 for ( const auto & rule : grammar.getRules ( ) )
122 for ( const auto & rhs : rule.second ) {
123 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp;
124 tmp.push_back ( rhs.first );
125
126 tmp.insert ( tmp.end ( ), rhs.second.begin ( ), rhs.second.end ( ) );
127
128 res[rule.first].insert ( std::move ( tmp ) );
129 }
130
131 if ( grammar.getGeneratesEpsilon ( ) )
132 res [ grammar.getInitialSymbol ( ) ].insert ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } );
133
134 return res;
135}
136
137template < class TerminalSymbolType, class NonterminalSymbolType >
138ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
139 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res = grammar.getRules ( );
140
141 if ( grammar.getGeneratesEpsilon ( ) )
142 res [ grammar.getInitialSymbol ( ) ].insert ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } );
143
144 return res;
145}
146
147template < class TerminalSymbolType, class NonterminalSymbolType >
148ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const CNF < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
149 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
150
151 for ( const auto & rule : grammar.getRules ( ) )
152 for ( const auto & rhs : rule.second ) {
153 if ( rhs.template is < TerminalSymbolType > ( ) ) {
154 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp { ext::variant < TerminalSymbolType, NonterminalSymbolType > ( rhs.template get < TerminalSymbolType > ( ) ) };
155 res[rule.first].insert ( std::move ( tmp ) );
156 } else {
157 const auto & realRHS = rhs.template get < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( );
158 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp { ext::variant < TerminalSymbolType, NonterminalSymbolType > ( realRHS.first ), ext::variant < TerminalSymbolType, NonterminalSymbolType > ( realRHS.second ) };
159 res[rule.first].insert ( std::move ( tmp ) );
160 }
161 }
162
163 if ( grammar.getGeneratesEpsilon ( ) )
164 res [ grammar.getInitialSymbol ( ) ].insert ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } );
165
166 return res;
167}
168
169template < class TerminalSymbolType, class NonterminalSymbolType >
170ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const CFG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
171 return grammar.getRules ( );
172}
173
174template < class TerminalSymbolType, class NonterminalSymbolType >
175ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
176 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
177
178 for ( const auto & rule : grammar.getRules ( ) )
179 for ( const auto & rhs : rule.second ) {
180 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp;
181
182 if ( rhs.template is < ext::vector < TerminalSymbolType > > ( ) ) {
183 tmp.insert ( tmp.end ( ), rhs.template get < ext::vector < TerminalSymbolType > > ( ).begin ( ), rhs.template get < ext::vector < TerminalSymbolType > > ( ).end ( ) );
184 } else {
185 const auto & rhsTuple = rhs.template get < ext::pair < NonterminalSymbolType, ext::vector < TerminalSymbolType > > > ( );
186
187 tmp.push_back ( rhsTuple.first );
188 tmp.insert ( tmp.end ( ), rhsTuple.second.begin ( ), rhsTuple.second.end ( ) );
189 }
190
191 res[rule.first].insert ( std::move ( tmp ) );
192 }
193
194 return res;
195}
196
197template < class TerminalSymbolType, class NonterminalSymbolType >
198ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
199 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
200
201 for ( const auto & rule : grammar.getRules ( ) )
202 for ( const auto & rhs : rule.second ) {
203 if ( rhs.template is < TerminalSymbolType > ( ) ) {
204 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp { ext::variant < TerminalSymbolType, NonterminalSymbolType > ( rhs.template get < TerminalSymbolType > ( ) ) };
205 res[rule.first].insert ( std::move ( tmp ) );
206 } else {
207 const auto & rhsPair = rhs.template get < ext::pair < NonterminalSymbolType, TerminalSymbolType > > ( );
208 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp { ext::variant < TerminalSymbolType, NonterminalSymbolType > ( rhsPair.first ), ext::variant < TerminalSymbolType, NonterminalSymbolType > ( rhsPair.second ) };
209 res[rule.first].insert ( std::move ( tmp ) );
210 }
211 }
212
213 if ( grammar.getGeneratesEpsilon ( ) )
214 res [ grammar.getInitialSymbol ( ) ].insert ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } );
215
216 return res;
217}
218
219template < class TerminalSymbolType, class NonterminalSymbolType >
220ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
221 ext::map < TerminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
222
223 for ( const auto & rule : grammar.getRules ( ) )
224 for ( const auto & rhs : rule.second ) {
225 if ( rhs.template is < TerminalSymbolType > ( ) ) {
226 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp { ext::variant < TerminalSymbolType, NonterminalSymbolType > ( rhs.template get < TerminalSymbolType > ( ) ) };
227 res[rule.first].insert ( std::move ( tmp ) );
228 } else {
229 const auto & rhsPair = rhs.template get < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( );
230 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp { ext::variant < TerminalSymbolType, NonterminalSymbolType > ( rhsPair.first ), ext::variant < TerminalSymbolType, NonterminalSymbolType > ( rhsPair.second ) };
231 res[rule.first].insert ( std::move ( tmp ) );
232 }
233 }
234
235 if ( grammar.getGeneratesEpsilon ( ) )
236 res [ grammar.getInitialSymbol ( ) ].insert ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } );
237
238 return res;
239}
240
241template < class TerminalSymbolType, class NonterminalSymbolType >
242ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > RawRules::getRawRules ( const RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
243 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
244
245 for ( const auto & rule : grammar.getRules ( ) )
246 for ( const auto & rhs : rule.second ) {
247 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmp;
248
249 if ( rhs.template is < ext::vector < TerminalSymbolType > > ( ) ) {
250 tmp.insert ( tmp.end ( ), rhs.template get < ext::vector < TerminalSymbolType > > ( ).begin ( ), rhs.template get < ext::vector < TerminalSymbolType > > ( ).end ( ) );
251 } else {
252 const auto & rhsTuple = rhs.template get < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType > > ( );
253
254 tmp.insert ( tmp.end ( ), rhsTuple.first.begin ( ), rhsTuple.first.end ( ) );
255 tmp.push_back ( rhsTuple.second );
256 }
257
258 res[rule.first].insert ( std::move ( tmp ) );
259 }
260
261 return res;
262}
263
264} /* namespace grammar */
265
ext::map
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
ext::variant
Implementation of the variant class allowing to store any type of those listed in the template parame...
Definition: variant.hpp:98
ext::vector
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
ext::vector::begin
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: vector.hpp:125
ext::vector::insert
reverse_iterator insert(const_reverse_iterator pos, const T &value)
Inserts the value on position given by iterator pos.
Definition: vector.hpp:229
ext::vector::end
auto end() &
Inherited behavior of end for non-const instance.
Definition: vector.hpp:155
grammar::CFG
Context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free lang...
Definition: CFG.h:67
grammar::CNF
Chomsky normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: CNF.h:66
grammar::EpsilonFreeCFG
Context free grammar without epsilon rules in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: EpsilonFreeCFG.h:65
grammar::GNF
Greibach normal form of a context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy....
Definition: GNF.h:65
grammar::LG
Context free grammar in Chomsky hierarchy or type 2 in Chomsky hierarchy. Generates context free lang...
Definition: LG.h:67
grammar::LeftLG
Left linear grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages.
Definition: LeftLG.h:66
grammar::LeftRG
Left regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: LeftRG.h:70
grammar::RawRules
Definition: RawRules.h:27
grammar::RawRules::getRawRules
static ext::map< NonterminalSymbolType, ext::set< ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > > > getRawRules(const LG< TerminalSymbolType, NonterminalSymbolType > &grammar)
Definition: RawRules.h:92
grammar::RightLG
Right linear grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: RightLG.h:65
grammar::RightRG
Right regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular language...
Definition: RightRG.h:70
automaton::simplify::res
return res
Definition: MinimizeByPartitioning.h:145
grammar
Definition: ToAutomaton.h:24
std::get
auto & get(ext::ptr_array< Type, N > &tpl)
Specialisation of get function for pointer arrays.
Definition: ptr_array.hpp:693
Generated on Mon Dec 27 2021 10:21:53 for Algorithms Library Toolkit by doxygen 1.9.2