1// parser.hpp
2// Copyright (c) 2007-2009 Ben Hanson (http://www.benhanson.net/)
3//
4// Distributed under the Boost Software License, Version 1.0. (See accompanying
5// file licence_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6#ifndef BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARSER_PARSER_HPP
7#define BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARSER_PARSER_HPP
8
9#include <boost/assert.hpp>
10#include "tree/end_node.hpp"
11#include "tree/iteration_node.hpp"
12#include "tree/leaf_node.hpp"
13#include "../runtime_error.hpp"
14#include "tree/selection_node.hpp"
15#include "tree/sequence_node.hpp"
16#include "../size_t.hpp"
17#include "tokeniser/re_tokeniser.hpp"
18#include <sstream>
19
20namespace boost
21{
22namespace lexer
23{
24namespace detail
25{
26template<typename CharT>
27class basic_parser
28{
29public:
30 typedef basic_re_tokeniser<CharT> tokeniser;
31 typedef typename tokeniser::string string;
32 typedef std::map<string, const node *> macro_map;
33 typedef node::node_ptr_vector node_ptr_vector;
34 typedef typename tokeniser::num_token token;
35
36/*
37 General principles of regex parsing:
38 - Every regex is a sequence of sub-regexes.
39 - Regexes consist of operands and operators
40 - All operators decompose to sequence, selection ('|') and iteration ('*')
41 - Regex tokens are stored on the stack.
42 - When a complete sequence of regex tokens is on the stack it is processed.
43
44Grammar:
45
46<REGEX> -> <OREXP>
47<OREXP> -> <SEQUENCE> | <OREXP>'|'<SEQUENCE>
48<SEQUENCE> -> <SUB>
49<SUB> -> <EXPRESSION> | <SUB><EXPRESSION>
50<EXPRESSION> -> <REPEAT>
51<REPEAT> -> charset | macro | '('<REGEX>')' | <REPEAT><DUPLICATE>
52<DUPLICATE> -> '?' | '*' | '+' | '{n[,[m]]}'
53*/
54 static node *parse (const CharT *start_, const CharT * const end_,
55 const std::size_t id_, const std::size_t unique_id_,
56 const std::size_t dfa_state_, const regex_flags flags_,
57 const std::locale &locale_, node_ptr_vector &node_ptr_vector_,
58 const macro_map &macromap_, typename tokeniser::token_map &map_,
59 bool &seen_BOL_assertion_, bool &seen_EOL_assertion_)
60 {
61 node *root_ = 0;
62 state state_ (start_, end_, flags_, locale_);
63 token lhs_token_;
64 token rhs_token_;
65 token_stack token_stack_;
66 tree_node_stack tree_node_stack_;
67 char action_ = 0;
68
69 token_stack_.push (rhs_token_);
70 tokeniser::next (state_, map_, rhs_token_);
71
72 do
73 {
74 lhs_token_ = token_stack_.top ();
75 action_ = lhs_token_.precedence (rhs_token_._type);
76
77 switch (action_)
78 {
79 case '<':
80 case '=':
81 token_stack_.push (rhs_token_);
82 tokeniser::next (state_, map_, rhs_token_);
83 break;
84 case '>':
85 reduce (token_stack_, macromap_, node_vector_ptr_&: node_ptr_vector_,
86 tree_node_stack_);
87 break;
88 default:
89 std::ostringstream ss_;
90
91 ss_ << "A syntax error occurred: '" <<
92 lhs_token_.precedence_string () <<
93 "' against '" << rhs_token_.precedence_string () <<
94 "' at index " << state_.index () << ".";
95 throw runtime_error (ss_.str ().c_str ());
96 break;
97 }
98 } while (!token_stack_.empty ());
99
100 if (tree_node_stack_.empty ())
101 {
102 throw runtime_error ("Empty rules are not allowed.");
103 }
104
105 BOOST_ASSERT(tree_node_stack_.size () == 1);
106
107 node *lhs_node_ = tree_node_stack_.top ();
108
109 tree_node_stack_.pop ();
110
111 if (id_ == 0)
112 {
113 // Macros have no end state...
114 root_ = lhs_node_;
115 }
116 else
117 {
118 node_ptr_vector_->push_back (x: static_cast<end_node *>(0));
119
120 node *rhs_node_ = new end_node (id_, unique_id_, dfa_state_);
121
122 node_ptr_vector_->back () = rhs_node_;
123 node_ptr_vector_->push_back (x: static_cast<sequence_node *>(0));
124 node_ptr_vector_->back () = new sequence_node
125 (lhs_node_, rhs_node_);
126 root_ = node_ptr_vector_->back ();
127 }
128
129 // Done this way as bug in VC++ 6 prevents |= operator working
130 // properly!
131 if (state_._seen_BOL_assertion) seen_BOL_assertion_ = true;
132
133 if (state_._seen_EOL_assertion) seen_EOL_assertion_ = true;
134
135 return root_;
136 }
137
138private:
139 typedef typename tokeniser::state state;
140 typedef std::stack<token> token_stack;
141 typedef node::node_stack tree_node_stack;
142
143 static void reduce (token_stack &token_stack_,
144 const macro_map &macromap_, node_ptr_vector &node_vector_ptr_,
145 tree_node_stack &tree_node_stack_)
146 {
147 typename tokeniser::num_token lhs_;
148 typename tokeniser::num_token rhs_;
149 token_stack handle_;
150 char action_ = 0;
151
152 do
153 {
154 rhs_ = token_stack_.top ();
155 token_stack_.pop ();
156 handle_.push (rhs_);
157
158 if (!token_stack_.empty ())
159 {
160 lhs_ = token_stack_.top ();
161 action_ = lhs_.precedence (rhs_._type);
162 }
163 } while (!token_stack_.empty () && action_ == '=');
164
165 BOOST_ASSERT(token_stack_.empty () || action_ == '<');
166
167 switch (rhs_._type)
168 {
169 case token::BEGIN:
170 // finished processing so exit
171 break;
172 case token::REGEX:
173 // finished parsing, nothing to do
174 break;
175 case token::OREXP:
176 orexp (handle_, token_stack_, node_ptr_vector_&: node_vector_ptr_, tree_node_stack_);
177 break;
178 case token::SEQUENCE:
179 token_stack_.push (token::OREXP);
180 break;
181 case token::SUB:
182 sub (handle_, token_stack_, node_ptr_vector_&: node_vector_ptr_, tree_node_stack_);
183 break;
184 case token::EXPRESSION:
185 token_stack_.push (token::SUB);
186 break;
187 case token::REPEAT:
188 repeat (handle_, token_stack_);
189 break;
190 case token::CHARSET:
191 charset (handle_, token_stack_, node_ptr_vector_&: node_vector_ptr_,
192 tree_node_stack_);
193 break;
194 case token::MACRO:
195 macro (handle_, token_stack_, macromap_, node_ptr_vector_&: node_vector_ptr_,
196 tree_node_stack_);
197 break;
198 case token::OPENPAREN:
199 openparen (handle_, token_stack_);
200 break;
201 case token::OPT:
202 case token::AOPT:
203 optional (greedy_: rhs_._type == token::OPT, node_ptr_vector_&: node_vector_ptr_,
204 tree_node_stack_);
205 token_stack_.push (token::DUP);
206 break;
207 case token::ZEROORMORE:
208 case token::AZEROORMORE:
209 zero_or_more (greedy_: rhs_._type == token::ZEROORMORE, node_ptr_vector_&: node_vector_ptr_,
210 tree_node_stack_);
211 token_stack_.push (token::DUP);
212 break;
213 case token::ONEORMORE:
214 case token::AONEORMORE:
215 one_or_more (greedy_: rhs_._type == token::ONEORMORE, node_ptr_vector_&: node_vector_ptr_,
216 tree_node_stack_);
217 token_stack_.push (token::DUP);
218 break;
219 case token::REPEATN:
220 case token::AREPEATN:
221 repeatn (greedy_: rhs_._type == token::REPEATN, token_: handle_.top (),
222 node_ptr_vector_&: node_vector_ptr_, tree_node_stack_);
223 token_stack_.push (token::DUP);
224 break;
225 default:
226 throw runtime_error
227 ("Internal error regex_parser::reduce");
228 break;
229 }
230 }
231
232 static void orexp (token_stack &handle_, token_stack &token_stack_,
233 node_ptr_vector &node_ptr_vector_, tree_node_stack &tree_node_stack_)
234 {
235 BOOST_ASSERT(handle_.top ()._type == token::OREXP &&
236 (handle_.size () == 1 || handle_.size () == 3));
237
238 if (handle_.size () == 1)
239 {
240 token_stack_.push (token::REGEX);
241 }
242 else
243 {
244 handle_.pop ();
245 BOOST_ASSERT(handle_.top ()._type == token::OR);
246 handle_.pop ();
247 BOOST_ASSERT(handle_.top ()._type == token::SEQUENCE);
248 perform_or (node_ptr_vector_, tree_node_stack_);
249 token_stack_.push (token::OREXP);
250 }
251 }
252
253 static void sub (token_stack &handle_, token_stack &token_stack_,
254 node_ptr_vector &node_ptr_vector_, tree_node_stack &tree_node_stack_)
255 {
256 BOOST_ASSERT(handle_.top ()._type == token::SUB &&
257 (handle_.size () == 1 || handle_.size () == 2));
258
259 if (handle_.size () == 1)
260 {
261 token_stack_.push (token::SEQUENCE);
262 }
263 else
264 {
265 handle_.pop ();
266 BOOST_ASSERT(handle_.top ()._type == token::EXPRESSION);
267 // perform join
268 sequence (node_ptr_vector_, tree_node_stack_);
269 token_stack_.push (token::SUB);
270 }
271 }
272
273 static void repeat (token_stack &handle_, token_stack &token_stack_)
274 {
275 BOOST_ASSERT(handle_.top ()._type == token::REPEAT &&
276 handle_.size () >= 1 && handle_.size () <= 3);
277
278 if (handle_.size () == 1)
279 {
280 token_stack_.push (token::EXPRESSION);
281 }
282 else
283 {
284 handle_.pop ();
285 BOOST_ASSERT(handle_.top ()._type == token::DUP);
286 token_stack_.push (token::REPEAT);
287 }
288 }
289
290 static void charset (token_stack &handle_, token_stack &token_stack_,
291 node_ptr_vector &node_ptr_vector_, tree_node_stack &tree_node_stack_)
292 {
293 BOOST_ASSERT(handle_.top ()._type == token::CHARSET &&
294 handle_.size () == 1);
295 // store charset
296 node_ptr_vector_->push_back (x: static_cast<leaf_node *>(0));
297
298 const size_t id_ = handle_.top ()._id;
299
300 node_ptr_vector_->back () = new leaf_node (id_, true);
301 tree_node_stack_.push (x: node_ptr_vector_->back ());
302 token_stack_.push (token::REPEAT);
303 }
304
305 static void macro (token_stack &handle_, token_stack &token_stack_,
306 const macro_map &macromap_, node_ptr_vector &node_ptr_vector_,
307 tree_node_stack &tree_node_stack_)
308 {
309 token &top_ = handle_.top ();
310
311 BOOST_ASSERT(top_._type == token::MACRO && handle_.size () == 1);
312
313 typename macro_map::const_iterator iter_ =
314 macromap_.find (top_._macro);
315
316 if (iter_ == macromap_.end ())
317 {
318 const CharT *name_ = top_._macro;
319 std::basic_stringstream<CharT> ss_;
320 std::ostringstream os_;
321
322 os_ << "Unknown MACRO name '";
323
324 while (*name_)
325 {
326 os_ << ss_.narrow (*name_++, ' ');
327 }
328
329 os_ << "'.";
330 throw runtime_error (os_.str ());
331 }
332
333 tree_node_stack_.push (iter_->second->copy (node_ptr_vector_));
334 token_stack_.push (token::REPEAT);
335 }
336
337 static void openparen (token_stack &handle_, token_stack &token_stack_)
338 {
339 BOOST_ASSERT(handle_.top ()._type == token::OPENPAREN &&
340 handle_.size () == 3);
341 handle_.pop ();
342 BOOST_ASSERT(handle_.top ()._type == token::REGEX);
343 handle_.pop ();
344 BOOST_ASSERT(handle_.top ()._type == token::CLOSEPAREN);
345 token_stack_.push (token::REPEAT);
346 }
347
348 static void perform_or (node_ptr_vector &node_ptr_vector_,
349 tree_node_stack &tree_node_stack_)
350 {
351 // perform or
352 node *rhs_ = tree_node_stack_.top ();
353
354 tree_node_stack_.pop ();
355
356 node *lhs_ = tree_node_stack_.top ();
357
358 node_ptr_vector_->push_back (x: static_cast<selection_node *>(0));
359 node_ptr_vector_->back () = new selection_node (lhs_, rhs_);
360 tree_node_stack_.top () = node_ptr_vector_->back ();
361 }
362
363 static void sequence (node_ptr_vector &node_ptr_vector_,
364 tree_node_stack &tree_node_stack_)
365 {
366 node *rhs_ = tree_node_stack_.top ();
367
368 tree_node_stack_.pop ();
369
370 node *lhs_ = tree_node_stack_.top ();
371
372 node_ptr_vector_->push_back (x: static_cast<sequence_node *>(0));
373 node_ptr_vector_->back () = new sequence_node (lhs_, rhs_);
374 tree_node_stack_.top () = node_ptr_vector_->back ();
375 }
376
377 static void optional (const bool greedy_,
378 node_ptr_vector &node_ptr_vector_, tree_node_stack &tree_node_stack_)
379 {
380 // perform ?
381 node *lhs_ = tree_node_stack_.top ();
382 // You don't know if lhs_ is a leaf_node, so get firstpos.
383 node::node_vector &firstpos_ = lhs_->firstpos ();
384
385 for (node::node_vector::iterator iter_ = firstpos_.begin (),
386 end_ = firstpos_.end (); iter_ != end_; ++iter_)
387 {
388 // These are leaf_nodes!
389 (*iter_)->greedy (greedy_);
390 }
391
392 node_ptr_vector_->push_back (x: static_cast<leaf_node *>(0));
393
394 node *rhs_ = new leaf_node (null_token, greedy_);
395
396 node_ptr_vector_->back () = rhs_;
397 node_ptr_vector_->push_back (x: static_cast<selection_node *>(0));
398 node_ptr_vector_->back () = new selection_node (lhs_, rhs_);
399 tree_node_stack_.top () = node_ptr_vector_->back ();
400 }
401
402 static void zero_or_more (const bool greedy_,
403 node_ptr_vector &node_ptr_vector_, tree_node_stack &tree_node_stack_)
404 {
405 // perform *
406 node *ptr_ = tree_node_stack_.top ();
407
408 node_ptr_vector_->push_back (x: static_cast<iteration_node *>(0));
409 node_ptr_vector_->back () = new iteration_node (ptr_, greedy_);
410 tree_node_stack_.top () = node_ptr_vector_->back ();
411 }
412
413 static void one_or_more (const bool greedy_,
414 node_ptr_vector &node_ptr_vector_, tree_node_stack &tree_node_stack_)
415 {
416 // perform +
417 node *lhs_ = tree_node_stack_.top ();
418 node *copy_ = lhs_->copy (node_ptr_vector_);
419
420 node_ptr_vector_->push_back (x: static_cast<iteration_node *>(0));
421
422 node *rhs_ = new iteration_node (copy_, greedy_);
423
424 node_ptr_vector_->back () = rhs_;
425 node_ptr_vector_->push_back (x: static_cast<sequence_node *>(0));
426 node_ptr_vector_->back () = new sequence_node (lhs_, rhs_);
427 tree_node_stack_.top () = node_ptr_vector_->back ();
428 }
429
430 // This is one of the most mind bending routines in this code...
431 static void repeatn (const bool greedy_, const token &token_,
432 node_ptr_vector &node_ptr_vector_, tree_node_stack &tree_node_stack_)
433 {
434 // perform {n[,[m]]}
435 // Semantic checks have already been performed.
436 // {0,} = *
437 // {0,1} = ?
438 // {1,} = +
439 // therefore we do not check for these cases.
440 if (!(token_._min == 1 && !token_._comma))
441 {
442 const std::size_t top_ = token_._min > 0 ?
443 token_._min : token_._max;
444
445 if (token_._min == 0)
446 {
447 optional (greedy_, node_ptr_vector_, tree_node_stack_);
448 }
449
450 node *prev_ = tree_node_stack_.top ()->copy (node_ptr_vector_);
451 node *curr_ = 0;
452
453 for (std::size_t i_ = 2; i_ < top_; ++i_)
454 {
455 curr_ = prev_->copy (node_ptr_vector_);
456 tree_node_stack_.push (x: static_cast<node *>(0));
457 tree_node_stack_.top () = prev_;
458 sequence (node_ptr_vector_, tree_node_stack_);
459 prev_ = curr_;
460 }
461
462 if (token_._comma && token_._min > 0)
463 {
464 if (token_._min > 1)
465 {
466 curr_ = prev_->copy (node_ptr_vector_);
467 tree_node_stack_.push (x: static_cast<node *>(0));
468 tree_node_stack_.top () = prev_;
469 sequence (node_ptr_vector_, tree_node_stack_);
470 prev_ = curr_;
471 }
472
473 if (token_._comma && token_._max)
474 {
475 tree_node_stack_.push (x: static_cast<node *>(0));
476 tree_node_stack_.top () = prev_;
477 optional (greedy_, node_ptr_vector_, tree_node_stack_);
478 prev_ = tree_node_stack_.top ();
479 tree_node_stack_.pop ();
480
481 const std::size_t count_ = token_._max - token_._min;
482
483 for (std::size_t i_ = 1; i_ < count_; ++i_)
484 {
485 curr_ = prev_->copy (node_ptr_vector_);
486 tree_node_stack_.push (x: static_cast<node *>(0));
487 tree_node_stack_.top () = prev_;
488 sequence (node_ptr_vector_, tree_node_stack_);
489 prev_ = curr_;
490 }
491 }
492 else
493 {
494 tree_node_stack_.push (x: static_cast<node *>(0));
495 tree_node_stack_.top () = prev_;
496 zero_or_more (greedy_, node_ptr_vector_, tree_node_stack_);
497 prev_ = tree_node_stack_.top ();
498 tree_node_stack_.pop ();
499 }
500 }
501
502 tree_node_stack_.push (x: static_cast<node *>(0));
503 tree_node_stack_.top () = prev_;
504 sequence (node_ptr_vector_, tree_node_stack_);
505 }
506 }
507};
508}
509}
510}
511
512#endif
513

source code of boost/libs/spirit/include/boost/spirit/home/support/detail/lexer/parser/parser.hpp