Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
GrammarFromStringParserCommon.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/set>
9#include <alib/vector>
10#include <alib/map>
11#include <alib/tuple>
12
13#include <exception/CommonException.h>
14
15#include <grammar/Grammar.h>
16
17#include <core/stringApi.hpp>
18
19#include <grammar/AddRawRule.h>
20
21namespace grammar {
22
23class GrammarFromStringParserCommon {
24 template < class SymbolType >
25 static ext::set < SymbolType > parseSet ( ext::istream & input );
26
27 template < class TerminalSymbolType, class NonterminalSymbolType >
28 static ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > parseCFLikeRules ( ext::istream & input );
29
30 template < class SymbolType >
31 static ext::map < ext::vector < SymbolType >, ext::set < ext::vector < SymbolType > > > parseCSLikeRules ( ext::istream & input );
32
33 template < class SymbolType >
34 static ext::map < ext::tuple < ext::vector < SymbolType >, SymbolType, ext::vector < SymbolType > >, ext::set < ext::vector < SymbolType > > > parsePreservingCSLikeRules ( ext::istream & input );
35
36
37public:
38 template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
39 static T parseCFLikeGrammar ( ext::istream & input );
40
41 template < class T, class SymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T > >
42 static T parseCSLikeGrammar ( ext::istream & input );
43
44 template < class T, class SymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T > >
45 static T parsePreservingCSLikeGrammar ( ext::istream & input );
46};
47
48template < class SymbolType >
49ext::set<SymbolType> GrammarFromStringParserCommon::parseSet (ext::istream& input) {
50 ext::set<SymbolType> res;
51
52 grammar::GrammarFromStringLexer::Token token = grammar::GrammarFromStringLexer::next(input);
53 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_BEGIN) {
54 throw exception::CommonException("Expected SET_BEGIN token.");
55 }
56
57 token = grammar::GrammarFromStringLexer::next(input);
58 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
59 grammar::GrammarFromStringLexer::putback(input, token);
60 while(true) {
61 SymbolType symbol = core::stringApi<SymbolType>::parse(input);
62 res.insert(symbol);
63
64 token = grammar::GrammarFromStringLexer::next(input);
65 if(token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
66 break;
67 }
68 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
69 throw exception::CommonException("Expected SET_END or COMMA token");
70 }
71 }
72 }
73
74 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
75 throw exception::CommonException("Expected SET_END token");
76 }
77
78 return res;
79}
80
81template < class TerminalSymbolType, class NonterminalSymbolType >
82ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > GrammarFromStringParserCommon::parseCFLikeRules ( ext::istream & input ) {
83 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > result;
84
85 grammar::GrammarFromStringLexer::Token token = grammar::GrammarFromStringLexer::next(input);
86 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_BEGIN) {
87 throw exception::CommonException("Expected SET_BEGIN token.");
88 }
89
90 token = grammar::GrammarFromStringLexer::next(input);
91 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
92 grammar::GrammarFromStringLexer::putback(input, token);
93 while(true) {
94 NonterminalSymbolType lhs = core::stringApi < NonterminalSymbolType >::parse ( input );
95
96 token = grammar::GrammarFromStringLexer::next(input);
97 if(token.type != grammar::GrammarFromStringLexer::TokenType::MAPS_TO) {
98 throw exception::CommonException("Expected MAPS_TO token.");
99 }
100
101 while(true) {
102 ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > rhs;
103
104 token = grammar::GrammarFromStringLexer::next(input);
105 if ( token.type != grammar::GrammarFromStringLexer::TokenType::COMMA
106 && token.type != grammar::GrammarFromStringLexer::TokenType::SET_END
107 && token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR ) {
108 if ( token.type == grammar::GrammarFromStringLexer::TokenType::EPSILON ) {
109 token = grammar::GrammarFromStringLexer::next(input);
110 } else while(true) {
111 grammar::GrammarFromStringLexer::putback(input, token);
112
113 rhs.push_back ( core::stringApi < ext::variant < TerminalSymbolType, NonterminalSymbolType > >::parse ( input ) );
114 token = grammar::GrammarFromStringLexer::next(input);
115 if ( token.type == grammar::GrammarFromStringLexer::TokenType::SEPARATOR
116 || token.type == grammar::GrammarFromStringLexer::TokenType::COMMA
117 || token.type == grammar::GrammarFromStringLexer::TokenType::SET_END ) {
118 break;
119 }
120 }
121 }
122 result[lhs].insert(rhs);
123 if(token.type == grammar::GrammarFromStringLexer::TokenType::COMMA || token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
124 break;
125 }
126 if(token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) {
127 throw exception::CommonException("Expected SEPARATOR, SETEND or COMMA token");
128 }
129 }
130
131 if(token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
132 break;
133 }
134 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
135 throw exception::CommonException("Expected SET_END or COMMA token");
136 }
137 }
138 }
139
140 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
141 throw exception::CommonException("Expected SET_END token");
142 }
143 return result;
144}
145
146template< class T, class TerminalSymbolType, class NonterminalSymbolType >
147T GrammarFromStringParserCommon::parseCFLikeGrammar(ext::istream& input) {
148 grammar::GrammarFromStringLexer::Token token = grammar::GrammarFromStringLexer::next(input);
149 if(token.type != grammar::GrammarFromStringLexer::TokenType::TUPLE_BEGIN) {
150 throw exception::CommonException("Unrecognised Tuple begin token.");
151 }
152
153 ext::set < NonterminalSymbolType > nonterminals = parseSet < NonterminalSymbolType > (input);
154
155 token = grammar::GrammarFromStringLexer::next(input);
156 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
157 throw exception::CommonException("Unrecognised Comma token.");
158 }
159
160 ext::set < TerminalSymbolType > terminals = parseSet < TerminalSymbolType > (input);
161
162 token = grammar::GrammarFromStringLexer::next(input);
163 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
164 throw exception::CommonException("Unrecognised Comma token.");
165 }
166
167 ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > rules = parseCFLikeRules < TerminalSymbolType, NonterminalSymbolType > ( input );
168
169 token = grammar::GrammarFromStringLexer::next(input);
170 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
171 throw exception::CommonException("Unrecognised Comma token.");
172 }
173
174 NonterminalSymbolType initialSymbol = core::stringApi < NonterminalSymbolType >::parse ( input );
175
176 token = grammar::GrammarFromStringLexer::next(input);
177 if(token.type != grammar::GrammarFromStringLexer::TokenType::TUPLE_END) {
178 throw exception::CommonException("Unrecognised Tuple end token.");
179 }
180
181 T grammar(nonterminals, terminals, initialSymbol);
182 for(const auto& rule : rules) {
183 for(const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rule.second) {
184 grammar::AddRawRule::addRawRule ( grammar, rule.first, rhs );
185 }
186 }
187 return grammar;
188}
189
190template < class SymbolType >
191ext::map<ext::vector<SymbolType>, ext::set<ext::vector<SymbolType>>> GrammarFromStringParserCommon::parseCSLikeRules (ext::istream& input) {
192 ext::map<ext::vector<SymbolType>, ext::set<ext::vector<SymbolType>>> result;
193
194 grammar::GrammarFromStringLexer::Token token = grammar::GrammarFromStringLexer::next(input);
195 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_BEGIN) {
196 throw exception::CommonException("Expected SET_BEGIN token.");
197 }
198
199 token = grammar::GrammarFromStringLexer::next(input);
200 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
201 grammar::GrammarFromStringLexer::putback(input, token);
202 while(true) {
203 ext::vector<SymbolType> lhs;
204 while(true) {
205 lhs.push_back(core::stringApi<SymbolType>::parse(input));
206 token = grammar::GrammarFromStringLexer::next(input);
207 if(token.type == grammar::GrammarFromStringLexer::TokenType::MAPS_TO) {
208 break;
209 }
210 grammar::GrammarFromStringLexer::putback(input, token);
211 }
212
213 if(token.type != grammar::GrammarFromStringLexer::TokenType::MAPS_TO) {
214 throw exception::CommonException("Expected MAPS_TO token.");
215 }
216
217 while(true) {
218 ext::vector<SymbolType> rhs;
219
220 token = grammar::GrammarFromStringLexer::next(input);
221 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA && token.type != grammar::GrammarFromStringLexer::TokenType::SET_END && token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) while(true) {
222 grammar::GrammarFromStringLexer::putback(input, token);
223
224 rhs.push_back(core::stringApi<SymbolType>::parse(input));
225 token = grammar::GrammarFromStringLexer::next(input);
226 if(token.type == grammar::GrammarFromStringLexer::TokenType::SEPARATOR || token.type == grammar::GrammarFromStringLexer::TokenType::COMMA || token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
227 break;
228 }
229 }
230 result[lhs].insert(rhs);
231 if(token.type == grammar::GrammarFromStringLexer::TokenType::COMMA || token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
232 break;
233 }
234 if(token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) {
235 throw exception::CommonException("Expected SEPARATOR, SETEND or COMMA token");
236 }
237 }
238
239 if(token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
240 break;
241 }
242 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
243 throw exception::CommonException("Expected SET_END or COMMA token");
244 }
245 }
246 }
247
248 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
249 throw exception::CommonException("Expected SET_END token");
250 }
251 return result;
252}
253
254template < class T, class SymbolType >
255T GrammarFromStringParserCommon::parseCSLikeGrammar(ext::istream& input) {
256 grammar::GrammarFromStringLexer::Token token = grammar::GrammarFromStringLexer::next(input);
257 if(token.type != grammar::GrammarFromStringLexer::TokenType::TUPLE_BEGIN) {
258 throw exception::CommonException("Unrecognised Tuple begin token.");
259 }
260
261 ext::set<SymbolType> nonterminals = parseSet < SymbolType > (input);
262
263 token = grammar::GrammarFromStringLexer::next(input);
264 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
265 throw exception::CommonException("Unrecognised Comma token.");
266 }
267
268 ext::set<SymbolType> terminals = parseSet < SymbolType > (input);
269
270 token = grammar::GrammarFromStringLexer::next(input);
271 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
272 throw exception::CommonException("Unrecognised Comma token.");
273 }
274
275 ext::map<ext::vector<SymbolType>, ext::set<ext::vector<SymbolType>>> rules = parseCSLikeRules < SymbolType > (input);
276
277 token = grammar::GrammarFromStringLexer::next(input);
278 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
279 throw exception::CommonException("Unrecognised Comma token.");
280 }
281
282 SymbolType initialSymbol = core::stringApi<SymbolType>::parse(input);
283
284 token = grammar::GrammarFromStringLexer::next(input);
285 if(token.type != grammar::GrammarFromStringLexer::TokenType::TUPLE_END) {
286 throw exception::CommonException("Unrecognised Tuple end token.");
287 }
288
289 T grammar(nonterminals, terminals, initialSymbol);
290 for(const auto& rule : rules) {
291 for(const auto& ruleRHS : rule.second) {
292 grammar.addRule(rule.first, ruleRHS);
293 }
294 }
295 return grammar;
296}
297
298template < class SymbolType >
299ext::map<ext::tuple<ext::vector<SymbolType>, SymbolType, ext::vector<SymbolType>>, ext::set<ext::vector<SymbolType>>> GrammarFromStringParserCommon::parsePreservingCSLikeRules (ext::istream& input) {
300 ext::map<ext::tuple<ext::vector<SymbolType>, SymbolType, ext::vector<SymbolType>>, ext::set<ext::vector<SymbolType>>> result;
301
302 grammar::GrammarFromStringLexer::Token token = grammar::GrammarFromStringLexer::next(input);
303 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_BEGIN) {
304 throw exception::CommonException("Expected SET_BEGIN token.");
305 }
306
307 token = grammar::GrammarFromStringLexer::next(input);
308 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
309 grammar::GrammarFromStringLexer::putback(input, token);
310 while(true) {
311 ext::vector<SymbolType> lContext;
312 token = grammar::GrammarFromStringLexer::next(input);
313 if(token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) while(true) {
314 grammar::GrammarFromStringLexer::putback(input, token);
315 lContext.push_back(core::stringApi<SymbolType>::parse(input));
316 token = grammar::GrammarFromStringLexer::next(input);
317 if(token.type == grammar::GrammarFromStringLexer::TokenType::SEPARATOR) {
318 break;
319 }
320 }
321
322 if(token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) {
323 throw exception::CommonException("Expected SEPARATOR token.");
324 }
325
326 SymbolType lhs = core::stringApi<SymbolType>::parse(input);
327
328 token = grammar::GrammarFromStringLexer::next(input);
329 if(token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) {
330 throw exception::CommonException("Expected SEPARATOR token.");
331 }
332
333 ext::vector<SymbolType> rContext;
334 token = grammar::GrammarFromStringLexer::next(input);
335 if(token.type != grammar::GrammarFromStringLexer::TokenType::MAPS_TO) while(true) {
336 grammar::GrammarFromStringLexer::putback(input, token);
337 rContext.push_back(core::stringApi<SymbolType>::parse(input));
338 token = grammar::GrammarFromStringLexer::next(input);
339 if(token.type == grammar::GrammarFromStringLexer::TokenType::MAPS_TO) {
340 break;
341 }
342 }
343
344 if(token.type != grammar::GrammarFromStringLexer::TokenType::MAPS_TO) {
345 throw exception::CommonException("Expected MAPS_TO token.");
346 }
347
348 ext::tuple<ext::vector<SymbolType>, SymbolType, ext::vector<SymbolType>> key = ext::make_tuple(lContext, lhs, rContext);
349
350 while(true) {
351 ext::vector<SymbolType> rhs;
352
353 token = grammar::GrammarFromStringLexer::next(input);
354 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA && token.type != grammar::GrammarFromStringLexer::TokenType::SET_END && token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) while(true) {
355 grammar::GrammarFromStringLexer::putback(input, token);
356
357 rhs.push_back(core::stringApi<SymbolType>::parse(input));
358 token = grammar::GrammarFromStringLexer::next(input);
359 if(token.type == grammar::GrammarFromStringLexer::TokenType::SEPARATOR || token.type == grammar::GrammarFromStringLexer::TokenType::COMMA || token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
360 break;
361 }
362 }
363 result[key].insert(rhs);
364 if(token.type == grammar::GrammarFromStringLexer::TokenType::COMMA || token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
365 break;
366 }
367 if(token.type != grammar::GrammarFromStringLexer::TokenType::SEPARATOR) {
368 throw exception::CommonException("Expected SEPARATOR, SETEND or COMMA token");
369 }
370 }
371
372 if(token.type == grammar::GrammarFromStringLexer::TokenType::SET_END) {
373 break;
374 }
375 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
376 throw exception::CommonException("Expected SET_END or COMMA token");
377 }
378 }
379 }
380
381 if(token.type != grammar::GrammarFromStringLexer::TokenType::SET_END) {
382 throw exception::CommonException("Expected SET_END token");
383 }
384 return result;
385}
386
387template < class T, class SymbolType >
388T GrammarFromStringParserCommon::parsePreservingCSLikeGrammar(ext::istream& input) {
389 grammar::GrammarFromStringLexer::Token token = grammar::GrammarFromStringLexer::next(input);
390 if(token.type != grammar::GrammarFromStringLexer::TokenType::TUPLE_BEGIN) {
391 throw exception::CommonException("Unrecognised Tuple begin token.");
392 }
393
394 ext::set<SymbolType> nonterminals = parseSet < SymbolType > (input);
395
396 token = grammar::GrammarFromStringLexer::next(input);
397 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
398 throw exception::CommonException("Unrecognised Comma token.");
399 }
400
401 ext::set<SymbolType> terminals = parseSet < SymbolType > (input);
402
403 token = grammar::GrammarFromStringLexer::next(input);
404 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
405 throw exception::CommonException("Unrecognised Comma token.");
406 }
407
408 ext::map<ext::tuple<ext::vector<SymbolType>, SymbolType, ext::vector<SymbolType>>, ext::set<ext::vector<SymbolType>>> rules = parsePreservingCSLikeRules < SymbolType > (input);
409
410 token = grammar::GrammarFromStringLexer::next(input);
411 if(token.type != grammar::GrammarFromStringLexer::TokenType::COMMA) {
412 throw exception::CommonException("Unrecognised Comma token.");
413 }
414
415 SymbolType initialSymbol = core::stringApi<SymbolType>::parse(input);
416
417 token = grammar::GrammarFromStringLexer::next(input);
418 if(token.type != grammar::GrammarFromStringLexer::TokenType::TUPLE_END) {
419 throw exception::CommonException("Unrecognised Tuple end token.");
420 }
421
422 T grammar(nonterminals, terminals, initialSymbol);
423 for(const auto& rule : rules) {
424 for(const auto& ruleRHS : rule.second) {
425 grammar.addRule(std::get<0>(rule.first), std::get<1>(rule.first), std::get<2>(rule.first), ruleRHS);
426 }
427 }
428 return grammar;
429}
430
431} /* namespace grammar */
432
exception::CommonException
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
ext::Lexer< GrammarFromStringLexer >::putback
static void putback(ext::istream &input, const Token &token)
Definition: lexer.hpp:61
ext::istream
Definition: istream.h:32
ext::map
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
ext::set
Definition: set.hpp:44
ext::tuple
Class extending the tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
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
grammar::AddRawRule::addRawRule
static bool addRawRule(LG< TerminalSymbolType, NonterminalSymbolType > &grammar, NonterminalSymbolType leftHandSide, ext::vector< ext::variant< TerminalSymbolType, NonterminalSymbolType > > rightHandSide)
Definition: AddRawRule.h:92
grammar::GrammarFromStringLexer::next
static Token next(ext::istream &input)
Definition: GrammarFromStringLexer.cpp:10
grammar::GrammarFromStringParserCommon
Definition: GrammarFromStringParserCommon.h:23
grammar::GrammarFromStringParserCommon::parsePreservingCSLikeGrammar
static T parsePreservingCSLikeGrammar(ext::istream &input)
Definition: GrammarFromStringParserCommon.h:388
grammar::GrammarFromStringParserCommon::parseCSLikeGrammar
static T parseCSLikeGrammar(ext::istream &input)
Definition: GrammarFromStringParserCommon.h:255
grammar::GrammarFromStringParserCommon::parseCFLikeGrammar
static T parseCFLikeGrammar(ext::istream &input)
Definition: GrammarFromStringParserCommon.h:147
automaton::convert::grammar
return grammar
Definition: ToGrammarLeftRG.h:99
automaton::properties::SymbolType
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
automaton::simplify::res
return res
Definition: MinimizeByPartitioning.h:145
automaton::simplify::result
for(const StateType &state :fsm.getStates()) renamingData.insert(std Rename::RenamedAutomaton< T > result(renamingData.at(fsm.getInitialState()))
Definition: Rename.h:253
ext::make_tuple
constexpr auto make_tuple(Elements &&... args)
Helper of extended tuple construction. The tuple is constructed from values pack, types are deduced.
Definition: tuple.hpp:203
grammar
Definition: ToAutomaton.h:24
core::stringApi
Definition: stringApi.hpp:26
Generated on Mon Dec 27 2021 10:21:54 for Algorithms Library Toolkit by doxygen 1.9.2