]>
Commit | Line | Data |
---|---|---|
1 | [/============================================================================== | |
2 | Copyright (C) 2001-2011 Joel de Guzman | |
3 | Copyright (C) 2001-2011 Hartmut Kaiser | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
6 | file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
7 | ===============================================================================/] | |
8 | [section:operator Parser Operators] | |
9 | ||
10 | Operators are used as a means for object composition and embedding. | |
11 | Simple parsers may be composed to form composites through operator | |
12 | overloading, crafted to approximate the syntax of __peg__ (PEG). An | |
13 | expression such as: | |
14 | ||
15 | a | b | |
16 | ||
17 | yields a new parser type which is a composite of its operands, `a` and | |
18 | `b`. | |
19 | ||
20 | This module includes different parsers which get instantiated if one of | |
21 | the overloaded operators is used with more primitive parser constructs. | |
22 | It includes Alternative (`|`), And-predicate (unary `&`), Difference | |
23 | (`-`), Expect (`>`), Kleene star (unary `*`), Lists (`%`), Not-predicate (`!`), | |
24 | Optional (unary `-`), Permutation (`^`), Plus (unary | |
25 | `+`), Sequence (`>>`), and Sequential-Or (`||`). | |
26 | ||
27 | [heading Module Header] | |
28 | ||
29 | // forwards to <boost/spirit/home/qi/operator.hpp> | |
30 | #include <boost/spirit/include/qi_operator.hpp> | |
31 | ||
32 | Also, see __include_structure__. | |
33 | ||
34 | [/------------------------------------------------------------------------------] | |
35 | [section:alternative Alternative Parser (`a | b`)] | |
36 | ||
37 | [heading Description] | |
38 | ||
39 | The alternative operator, `a | b`, matches one of two or more operands | |
40 | (`a`, `b`, ... etc.): | |
41 | ||
42 | a | b | ... | |
43 | ||
44 | Alternative operands are tried one by one on a first-match-wins basis | |
45 | starting from the leftmost operand. After a successfully matched | |
46 | alternative is found, the parser concludes its search, essentially | |
47 | short-circuiting the search for other potentially viable candidates. | |
48 | This short-circuiting implicitly gives the highest priority to the | |
49 | leftmost alternative. | |
50 | ||
51 | Short-circuiting is done in the same manner as C or C++'s logical | |
52 | expressions; e.g. `if (x < 3 || y < 2)` where, if `x < 3`, the `y < 2` | |
53 | test is not done at all. In addition to providing an implicit priority | |
54 | rule for alternatives which is necessary, given its non-deterministic | |
55 | nature, short-circuiting improves the execution time. If the order of | |
56 | your alternatives is logically irrelevant, strive to put the (expected) | |
57 | most common choice first for maximum efficiency. | |
58 | ||
59 | [heading Header] | |
60 | ||
61 | // forwards to <boost/spirit/home/qi/operator/alternative.hpp> | |
62 | #include <boost/spirit/include/qi_alternative.hpp> | |
63 | ||
64 | Also, see __include_structure__. | |
65 | ||
66 | [heading Model of] | |
67 | ||
68 | [:__nary_parser_concept__] | |
69 | ||
70 | [variablelist Notation | |
71 | [[`a`, `b`] [A __parser_concept__]] | |
72 | ] | |
73 | ||
74 | [heading Expression Semantics] | |
75 | ||
76 | Semantics of an expression is defined only where it differs from, or is not | |
77 | defined in __nary_parser_concept__. | |
78 | ||
79 | [table | |
80 | [[Expression] [Semantics]] | |
81 | [[`a | b`] [Match `a` or `b`.]] | |
82 | ] | |
83 | ||
84 | [heading Attributes] | |
85 | ||
86 | See __qi_comp_attr_notation__. | |
87 | ||
88 | [table | |
89 | [[Expression] [Attribute]] | |
90 | [[`a | b`] | |
91 | [``a: A, b: B --> (a | b): variant<A, B> | |
92 | a: A, b: Unused --> (a | b): optional<A> | |
93 | a: A, b: B, c: Unused --> (a | b | c): optional<variant<A, B> > | |
94 | a: Unused, b: B --> (a | b): optional<B> | |
95 | a: Unused, b: Unused --> (a | b): Unused | |
96 | a: A, b: A --> (a | b): A``]] | |
97 | ] | |
98 | ||
99 | [note Alternative parsers do not roll back changes made to the outer attribute | |
100 | because of a failed alternative. If you need to enforce that only the | |
101 | succeeded alternative changes the outer attribute please utilize the | |
102 | directive __qi_hold__`[]`.] | |
103 | ||
104 | [heading Complexity] | |
105 | ||
106 | [:The overall complexity of the alternative parser is defined by the sum | |
107 | of the complexities of its elements. The complexity of the alternative | |
108 | parser itself is O(N), where N is the number of alternatives.] | |
109 | ||
110 | [heading Example] | |
111 | ||
112 | [note The test harness for the example(s) below is presented in the | |
113 | __qi_basics_examples__ section.] | |
114 | ||
115 | Some using declarations: | |
116 | ||
117 | [reference_using_declarations_alternative] | |
118 | ||
119 | [reference_alternative] | |
120 | ||
121 | [endsect] [/ Alternative] | |
122 | ||
123 | [/------------------------------------------------------------------------------] | |
124 | [section:and_predicate And-Predicate Parser (`&a`)] | |
125 | ||
126 | [heading Description] | |
127 | ||
128 | Syntactic predicates assert a certain conditional syntax to be satisfied | |
129 | before evaluating another production. Similar to semantic predicates, | |
130 | __qi_eps__, syntactic predicates do not consume any input. The /and-predicate/, | |
131 | `&a`, is a positive syntactic predicate that returns a zero | |
132 | length match only if its predicate matches. | |
133 | ||
134 | [heading Header] | |
135 | ||
136 | // forwards to <boost/spirit/home/qi/operator/and_predicate.hpp> | |
137 | #include <boost/spirit/include/qi_and_predicate.hpp> | |
138 | ||
139 | Also, see __include_structure__. | |
140 | ||
141 | [heading Model of] | |
142 | ||
143 | [:__unary_parser_concept__] | |
144 | ||
145 | [variablelist Notation | |
146 | [[`a`] [A __parser_concept__]] | |
147 | ] | |
148 | ||
149 | [heading Expression Semantics] | |
150 | ||
151 | Semantics of an expression is defined only where it differs from, or is | |
152 | not defined in __unary_parser_concept__. | |
153 | ||
154 | [table | |
155 | [[Expression] [Semantics]] | |
156 | [[`&a`] [If the predicate `a` matches, return a zero | |
157 | length match. Otherwise, fail.]] | |
158 | ] | |
159 | ||
160 | [heading Attributes] | |
161 | ||
162 | See __qi_comp_attr_notation__. | |
163 | ||
164 | [table | |
165 | [[Expression] [Attribute]] | |
166 | [[`&a`] [__unused_type__]] | |
167 | ] | |
168 | ||
169 | [heading Complexity] | |
170 | ||
171 | [:The complexity is defined by the complexity of the predicate, `a`] | |
172 | ||
173 | [heading Example] | |
174 | ||
175 | [note The test harness for the example(s) below is presented in the | |
176 | __qi_basics_examples__ section.] | |
177 | ||
178 | [reference_and_predicate] | |
179 | ||
180 | [endsect] [/ And Predicate] | |
181 | ||
182 | [/------------------------------------------------------------------------------] | |
183 | [section:difference Difference Parser (`a - b`)] | |
184 | ||
185 | [heading Description] | |
186 | ||
187 | The difference operator, `a - b`, is a binary operator that matches the | |
188 | first (LHS) operand but not the second (RHS). [footnote Unlike classic | |
189 | Spirit, with Spirit2, the expression will always fail if the RHS is a | |
190 | successful match regardless if the RHS matches less characters. For | |
191 | example, the rule `lit("policeman") - "police"` will always fail to | |
192 | match. Spirit2 does not count the matching chars while parsing and there | |
193 | is no reliable and fast way to check if the LHS matches more than the | |
194 | RHS.] | |
195 | ||
196 | [heading Header] | |
197 | ||
198 | // forwards to <boost/spirit/home/qi/operator/difference.hpp> | |
199 | #include <boost/spirit/include/qi_difference.hpp> | |
200 | ||
201 | Also, see __include_structure__. | |
202 | ||
203 | [heading Model of] | |
204 | ||
205 | [:__binary_parser_concept__] | |
206 | ||
207 | [variablelist Notation | |
208 | [[`a`, `b`] [A __parser_concept__]] | |
209 | ] | |
210 | ||
211 | [heading Expression Semantics] | |
212 | ||
213 | Semantics of an expression is defined only where it differs from, or is | |
214 | not defined in __binary_parser_concept__. | |
215 | ||
216 | [table | |
217 | [[Expression] [Semantics]] | |
218 | [[`a - b`] [Parse `a` but not `b`.]] | |
219 | ] | |
220 | ||
221 | [heading Attributes] | |
222 | ||
223 | See __qi_comp_attr_notation__. | |
224 | ||
225 | [table | |
226 | [[Expression] [Attribute]] | |
227 | [[`a - b`] | |
228 | [``a: A, b: B --> (a - b): A | |
229 | a: Unused, b: B --> (a - b): Unused``]] | |
230 | ] | |
231 | ||
232 | [heading Complexity] | |
233 | ||
234 | [:The complexity of the difference parser is defined by the sum of the | |
235 | complexities of both operands.] | |
236 | ||
237 | [heading Example] | |
238 | ||
239 | [note The test harness for the example(s) below is presented in the | |
240 | __qi_basics_examples__ section.] | |
241 | ||
242 | [reference_difference] | |
243 | ||
244 | [endsect] [/ Difference] | |
245 | ||
246 | [/------------------------------------------------------------------------------] | |
247 | [section:expect Expectation Parser (`a > b`)] | |
248 | ||
249 | [heading Description] | |
250 | ||
251 | There are occasions in which it is expected that the input must match a | |
252 | particular parser or the input is invalid. Such cases generally arise | |
253 | after matching a portion of a grammar, such that the context is fully | |
254 | known. In such a situation, failure to match should result in an | |
255 | exception. For example, when parsing an e-mail address, after matching a | |
256 | name and "@" there must be a domain name or the address is invalid. | |
257 | ||
258 | The expectation operator (>) requires that the following parser match | |
259 | the input or an exception is emitted. Using on_error(), that exception | |
260 | can be handled by calling a handler with the context at which the | |
261 | parsing failed can be reported. | |
262 | ||
263 | By contrast, the follows operator (>>) does not require that the | |
264 | following parser match the input, which allows for backtracking or | |
265 | simply returning false from the parse() function with no exceptions. | |
266 | ||
267 | Like the __qi_sequence__, the expectation operator, `a > b`, parses two or | |
268 | more operands (`a`, `b`, ... etc.), in sequence: | |
269 | ||
270 | a > b > ... | |
271 | ||
272 | However, while the plain __qi_sequence__ simply returns a no-match | |
273 | (returns `false`) when one of the elements fail, the expectation: `>` | |
274 | operator throws an __qi_expectation_failure__`<Iter>` when the second or | |
275 | succeeding operands (all operands except the first) fail to match. | |
276 | ||
277 | [heading Header] | |
278 | ||
279 | // forwards to <boost/spirit/home/qi/operator/expect.hpp> | |
280 | #include <boost/spirit/include/qi_expect.hpp> | |
281 | ||
282 | Also, see __include_structure__. | |
283 | ||
284 | [heading Model of] | |
285 | ||
286 | [:__nary_parser_concept__] | |
287 | ||
288 | [variablelist Notation | |
289 | [[`a`, `b`] [A __parser_concept__]] | |
290 | [[`Iter`] [A __fwditer__ type]] | |
291 | ] | |
292 | ||
293 | [heading Expectation Failure] | |
294 | ||
295 | When any operand, except the first, fail to match an | |
296 | `expectation_failure<Iter>` is thrown: | |
297 | ||
298 | template <typename Iter> | |
299 | struct expectation_failure : std::runtime_error | |
300 | { | |
301 | Iter first; // [first, last) iterator pointing | |
302 | Iter last; // to the error position in the input. | |
303 | __info__ what_; // Information about the nature of the error. | |
304 | }; | |
305 | ||
306 | [heading Expression Semantics] | |
307 | ||
308 | Semantics of an expression is defined only where it differs from, or is not | |
309 | defined in __nary_parser_concept__. | |
310 | ||
311 | [table | |
312 | [[Expression] [Semantics]] | |
313 | [[`a > b`] [Match `a` followed by `b`. If `a` fails, no-match. | |
314 | If `b` fails, throw an `expectation_failure<Iter>`]] | |
315 | ] | |
316 | ||
317 | [heading Attributes] | |
318 | ||
319 | See __qi_comp_attr_notation__. | |
320 | ||
321 | [table | |
322 | [[Expression] [Attribute]] | |
323 | [[`a > b`] | |
324 | [``a: A, b: B --> (a > b): tuple<A, B> | |
325 | a: A, b: Unused --> (a > b): A | |
326 | a: Unused, b: B --> (a > b): B | |
327 | a: Unused, b: Unused --> (a > b): Unused | |
328 | ||
329 | a: A, b: A --> (a > b): vector<A> | |
330 | a: vector<A>, b: A --> (a > b): vector<A> | |
331 | a: A, b: vector<A> --> (a > b): vector<A> | |
332 | a: vector<A>, b: vector<A> --> (a > b): vector<A>``]] | |
333 | ] | |
334 | ||
335 | [heading Complexity] | |
336 | ||
337 | [:The overall complexity of the expectation parser is defined by the sum | |
338 | of the complexities of its elements. The complexity of the expectation | |
339 | operator itself is O(N), where N is the number of elements in the | |
340 | sequence.] | |
341 | ||
342 | [heading Example] | |
343 | ||
344 | [note The test harness for the example(s) below is presented in the | |
345 | __qi_basics_examples__ section.] | |
346 | ||
347 | Some using declarations: | |
348 | ||
349 | [reference_using_declarations_expect] | |
350 | ||
351 | [reference_expect] | |
352 | ||
353 | [endsect] [/ Expectation] | |
354 | ||
355 | [/------------------------------------------------------------------------------] | |
356 | [section:kleene Kleene Parser (`*a`)] | |
357 | ||
358 | [heading Description] | |
359 | ||
360 | The kleene operator, `*a`, is a unary operator that matches its operand | |
361 | zero or more times. | |
362 | ||
363 | [heading Header] | |
364 | ||
365 | // forwards to <boost/spirit/home/qi/operator/kleene.hpp> | |
366 | #include <boost/spirit/include/qi_kleene.hpp> | |
367 | ||
368 | Also, see __include_structure__. | |
369 | ||
370 | [heading Model of] | |
371 | ||
372 | [:__unary_parser_concept__] | |
373 | ||
374 | [variablelist Notation | |
375 | [[`a`] [A __parser_concept__]] | |
376 | ] | |
377 | ||
378 | [heading Expression Semantics] | |
379 | ||
380 | Semantics of an expression is defined only where it differs from, or is not | |
381 | defined in __unary_parser_concept__. | |
382 | ||
383 | [table | |
384 | [[Expression] [Semantics]] | |
385 | [[`*a`] [Match `a` zero or more times.]] | |
386 | ] | |
387 | ||
388 | [heading Attributes] | |
389 | ||
390 | See __qi_comp_attr_notation__. | |
391 | ||
392 | [table | |
393 | [[Expression] [Attribute]] | |
394 | [[`*a`] | |
395 | [``a: A --> *a: vector<A> | |
396 | a: Unused --> *a: Unused``]] | |
397 | ] | |
398 | ||
399 | [heading Complexity] | |
400 | ||
401 | [:The overall complexity of the Kleene star is defined by the complexity | |
402 | of its subject, `a`, multiplied by the number of repetitions. The | |
403 | complexity of the Kleene star itself is O(N), where N is the number | |
404 | successful repetitions.] | |
405 | ||
406 | [heading Example] | |
407 | ||
408 | [note The test harness for the example(s) below is presented in the | |
409 | __qi_basics_examples__ section.] | |
410 | ||
411 | [reference_kleene] | |
412 | ||
413 | [endsect] [/ Kleene] | |
414 | ||
415 | [/------------------------------------------------------------------------------] | |
416 | [section:list List Parser (`a % b`)] | |
417 | ||
418 | [heading Description] | |
419 | ||
420 | The list operator, `a % b`, is a binary operator that matches a list of | |
421 | one or more repetitions of `a` separated by occurrences of `b`. This is | |
422 | equivalent to `a >> *(b >> a)`. | |
423 | ||
424 | [heading Header] | |
425 | ||
426 | // forwards to <boost/spirit/home/qi/operator/list.hpp> | |
427 | #include <boost/spirit/include/qi_list.hpp> | |
428 | ||
429 | Also, see __include_structure__. | |
430 | ||
431 | [heading Model of] | |
432 | ||
433 | [:__binary_parser_concept__] | |
434 | ||
435 | [variablelist Notation | |
436 | [[`a`, `b`] [A __parser_concept__]] | |
437 | ] | |
438 | ||
439 | [heading Expression Semantics] | |
440 | ||
441 | Semantics of an expression is defined only where it differs from, or is | |
442 | not defined in __binary_parser_concept__. | |
443 | ||
444 | [table | |
445 | [[Expression] [Semantics]] | |
446 | [[`a % b`] [Match a list of one or more repetitions of `a` | |
447 | separated by occurrences of `b`. This is equivalent | |
448 | to `a >> *(b >> a)`.]] | |
449 | ] | |
450 | ||
451 | [heading Attributes] | |
452 | ||
453 | See __qi_comp_attr_notation__. | |
454 | ||
455 | [table | |
456 | [[Expression] [Attribute]] | |
457 | [[`a % b`] | |
458 | [``a: A, b: B --> (a % b): vector<A> | |
459 | a: Unused, b: B --> (a % b): Unused``]] | |
460 | ] | |
461 | ||
462 | [heading Complexity] | |
463 | ||
464 | [:The overall complexity of the List is defined by the complexity of its | |
465 | subject, `a`, multiplied by the number of repetitions. The complexity of | |
466 | the List itself is O(N), where N is the number successful repetitions.] | |
467 | ||
468 | [heading Example] | |
469 | ||
470 | [note The test harness for the example(s) below is presented in the | |
471 | __qi_basics_examples__ section.] | |
472 | ||
473 | [reference_list] | |
474 | ||
475 | [endsect] [/ List] | |
476 | ||
477 | [/------------------------------------------------------------------------------] | |
478 | [section:not_predicate Not-Predicate Parser (`!a`)] | |
479 | ||
480 | [heading Description] | |
481 | ||
482 | Syntactic predicates assert a certain conditional syntax to be satisfied | |
483 | before evaluating another production. Similar to semantic predicates, | |
484 | __qi_eps__, syntactic predicates do not consume any input. The /not-predicate/, | |
485 | `!a`, is a negative syntactic predicate that returns a zero | |
486 | length match only if its predicate fails to match. | |
487 | ||
488 | [heading Header] | |
489 | ||
490 | // forwards to <boost/spirit/home/qi/operator/not_predicate.hpp> | |
491 | #include <boost/spirit/include/qi_not_predicate.hpp> | |
492 | ||
493 | Also, see __include_structure__. | |
494 | ||
495 | [heading Model of] | |
496 | ||
497 | [:__unary_parser_concept__] | |
498 | ||
499 | [variablelist Notation | |
500 | [[`a`] [A __parser_concept__]] | |
501 | ] | |
502 | ||
503 | [heading Expression Semantics] | |
504 | ||
505 | Semantics of an expression is defined only where it differs from, or is | |
506 | not defined in __unary_parser_concept__. | |
507 | ||
508 | [table | |
509 | [[Expression] [Semantics]] | |
510 | [[`!a`] [If the predicate `a` matches, fail. Otherwise, | |
511 | return a zero length match.]] | |
512 | ] | |
513 | ||
514 | [heading Attributes] | |
515 | ||
516 | See __qi_comp_attr_notation__. | |
517 | ||
518 | [table | |
519 | [[Expression] [Attribute]] | |
520 | [[`!a`] [__unused_type__]] | |
521 | ] | |
522 | ||
523 | [heading Complexity] | |
524 | ||
525 | [:The complexity is defined by the complexity of the predicate, `a`] | |
526 | ||
527 | [heading Example] | |
528 | ||
529 | [note The test harness for the example(s) below is presented in the | |
530 | __qi_basics_examples__ section.] | |
531 | ||
532 | [reference_not_predicate] | |
533 | ||
534 | [endsect] [/ Not Predicate] | |
535 | ||
536 | [/------------------------------------------------------------------------------] | |
537 | [section:optional Optional Parser (`-a`)] | |
538 | ||
539 | [heading Description] | |
540 | ||
541 | The optional operator, `-a`, is a unary operator that matches its | |
542 | operand zero or one time. | |
543 | ||
544 | [heading Header] | |
545 | ||
546 | // forwards to <boost/spirit/home/qi/operator/optional.hpp> | |
547 | #include <boost/spirit/include/qi_optional.hpp> | |
548 | ||
549 | Also, see __include_structure__. | |
550 | ||
551 | [heading Model of] | |
552 | ||
553 | [:__unary_parser_concept__] | |
554 | ||
555 | [variablelist Notation | |
556 | [[`a`] [A __parser_concept__]] | |
557 | ] | |
558 | ||
559 | [heading Expression Semantics] | |
560 | ||
561 | Semantics of an expression is defined only where it differs from, or is not | |
562 | defined in __unary_parser_concept__. | |
563 | ||
564 | [table | |
565 | [[Expression] [Semantics]] | |
566 | [[`-a`] [Match `a` zero or one time.]] | |
567 | ] | |
568 | ||
569 | [heading Attributes] | |
570 | ||
571 | See __qi_comp_attr_notation__. | |
572 | ||
573 | [table | |
574 | [[Expression] [Attribute]] | |
575 | [[`-a`] | |
576 | [``a: A --> -a: optional<A> | |
577 | a: Unused --> -a: Unused``]] | |
578 | ] | |
579 | ||
580 | [heading Complexity] | |
581 | ||
582 | [:The complexity is defined by the complexity of the operand, `a`] | |
583 | ||
584 | [heading Example] | |
585 | ||
586 | [note The test harness for the example(s) below is presented in the | |
587 | __qi_basics_examples__ section.] | |
588 | ||
589 | [reference_optional] | |
590 | ||
591 | [endsect] [/ Optional] | |
592 | ||
593 | [/------------------------------------------------------------------------------] | |
594 | [section:permutation Permutation Parser (`a ^ b`)] | |
595 | ||
596 | [heading Description] | |
597 | ||
598 | The permutation operator, `a ^ b`, matches one or more operands (`a`, `b`, | |
599 | ... etc.) in any order: | |
600 | ||
601 | a ^ b ^ ... | |
602 | ||
603 | The operands are the elements in the permutation set. Each element in | |
604 | the permutation set may occur at most once, but not all elements of the | |
605 | given set need to be present. Note that by this definition, the | |
606 | permutation operator is not limited to strict permutations. | |
607 | ||
608 | For example: | |
609 | ||
610 | char_('a') ^ 'b' ^ 'c' | |
611 | ||
612 | matches: | |
613 | ||
614 | "a", "ab", "abc", "cba", "bca" ... etc. | |
615 | ||
616 | [heading Header] | |
617 | ||
618 | // forwards to <boost/spirit/home/qi/operator/permutation.hpp> | |
619 | #include <boost/spirit/include/qi_permutation.hpp> | |
620 | ||
621 | Also, see __include_structure__. | |
622 | ||
623 | [heading Model of] | |
624 | ||
625 | [:__nary_parser_concept__] | |
626 | ||
627 | [variablelist Notation | |
628 | [[`a`, `b`] [A __parser_concept__]] | |
629 | ] | |
630 | ||
631 | [heading Expression Semantics] | |
632 | ||
633 | Semantics of an expression is defined only where it differs from, or is not | |
634 | defined in __nary_parser_concept__. | |
635 | ||
636 | [table | |
637 | [[Expression] [Semantics]] | |
638 | [[`a ^ b`] [Match `a` or `b` in any order. Each operand | |
639 | may match zero or one time as long as at least | |
640 | one operand matches.]] | |
641 | ] | |
642 | ||
643 | [heading Attributes] | |
644 | ||
645 | See __qi_comp_attr_notation__. | |
646 | ||
647 | [table | |
648 | [[Expression] [Attribute]] | |
649 | [[`a ^ b`] | |
650 | [``a: A, b: B --> (a ^ b): tuple<optional<A>, optional<B> > | |
651 | a: A, b: Unused --> (a ^ b): optional<A> | |
652 | a: Unused, b: B --> (a ^ b): optional<B> | |
653 | a: Unused, b: Unused --> (a ^ b): Unused``]] | |
654 | ] | |
655 | ||
656 | [heading Complexity] | |
657 | ||
658 | [:The overall complexity of the permutation parser is defined by the sum | |
659 | of the complexities of its elements, s, multiplied by log s. The | |
660 | complexity of the permutation parser itself is O(N log N), where N is | |
661 | the number of elements.] | |
662 | ||
663 | [heading Example] | |
664 | ||
665 | [note The test harness for the example(s) below is presented in the | |
666 | __qi_basics_examples__ section.] | |
667 | ||
668 | Some using declarations: | |
669 | ||
670 | [reference_using_declarations_permutation] | |
671 | ||
672 | [reference_permutation] | |
673 | ||
674 | [endsect] [/ Permutation] | |
675 | ||
676 | [/------------------------------------------------------------------------------] | |
677 | [section:plus Plus Parser (`+a`)] | |
678 | ||
679 | [heading Description] | |
680 | ||
681 | The plus operator, `+a`, is a unary operator that matches its operand one | |
682 | or more times. | |
683 | ||
684 | [heading Header] | |
685 | ||
686 | // forwards to <boost/spirit/home/qi/operator/plus.hpp> | |
687 | #include <boost/spirit/include/qi_plus.hpp> | |
688 | ||
689 | Also, see __include_structure__. | |
690 | ||
691 | [heading Model of] | |
692 | ||
693 | [:__unary_parser_concept__] | |
694 | ||
695 | [variablelist Notation | |
696 | [[`a`] [A __parser_concept__]] | |
697 | ] | |
698 | ||
699 | [heading Expression Semantics] | |
700 | ||
701 | Semantics of an expression is defined only where it differs from, or is not | |
702 | defined in __unary_parser_concept__. | |
703 | ||
704 | [table | |
705 | [[Expression] [Semantics]] | |
706 | [[`+a`] [Match `a` one or more times.]] | |
707 | ] | |
708 | ||
709 | [heading Attributes] | |
710 | ||
711 | See __qi_comp_attr_notation__. | |
712 | ||
713 | [table | |
714 | [[Expression] [Attribute]] | |
715 | [[`+a`] | |
716 | [``a: A --> +a: vector<A> | |
717 | a: Unused --> +a: Unused``]] | |
718 | ] | |
719 | ||
720 | [heading Complexity] | |
721 | ||
722 | [:The overall complexity of the Plus is defined by the complexity of its | |
723 | subject, `a`, multiplied by the number of repetitions. The complexity of | |
724 | the Plus itself is O(N), where N is the number successful repetitions.] | |
725 | ||
726 | [heading Example] | |
727 | ||
728 | [note The test harness for the example(s) below is presented in the | |
729 | __qi_basics_examples__ section.] | |
730 | ||
731 | [reference_plus] | |
732 | ||
733 | [endsect] [/ Plus] | |
734 | ||
735 | [/------------------------------------------------------------------------------] | |
736 | [section:sequence Sequence Parser (`a >> b`)] | |
737 | ||
738 | [heading Description] | |
739 | ||
740 | The sequence operator, `a >> b`, parses two or more operands (`a`, | |
741 | `b`, ... etc.), in sequence: | |
742 | ||
743 | a >> b >> ... | |
744 | ||
745 | [heading Header] | |
746 | ||
747 | // forwards to <boost/spirit/home/qi/operator/sequence.hpp> | |
748 | #include <boost/spirit/include/qi_sequence.hpp> | |
749 | ||
750 | Also, see __include_structure__. | |
751 | ||
752 | [heading Model of] | |
753 | ||
754 | [:__nary_parser_concept__] | |
755 | ||
756 | [variablelist Notation | |
757 | [[`a`, `b`] [A __parser_concept__]] | |
758 | ] | |
759 | ||
760 | [heading Expression Semantics] | |
761 | ||
762 | Semantics of an expression is defined only where it differs from, or is not | |
763 | defined in __nary_parser_concept__. | |
764 | ||
765 | [table | |
766 | [[Expression] [Semantics]] | |
767 | [[`a >> b`] [Match `a` followed by `b`.]] | |
768 | ] | |
769 | ||
770 | [heading Attributes] | |
771 | ||
772 | See __qi_comp_attr_notation__. | |
773 | ||
774 | [table | |
775 | [[Expression] [Attribute]] | |
776 | [[`a >> b`] | |
777 | [``a: A, b: B --> (a >> b): tuple<A, B> | |
778 | a: A, b: Unused --> (a >> b): A | |
779 | a: Unused, b: B --> (a >> b): B | |
780 | a: Unused, b: Unused --> (a >> b): Unused | |
781 | ||
782 | a: A, b: A --> (a >> b): vector<A> | |
783 | a: vector<A>, b: A --> (a >> b): vector<A> | |
784 | a: A, b: vector<A> --> (a >> b): vector<A> | |
785 | a: vector<A>, b: vector<A> --> (a >> b): vector<A>``]] | |
786 | ] | |
787 | ||
788 | [heading Complexity] | |
789 | ||
790 | [:The overall complexity of the sequence parser is defined by the sum of | |
791 | the complexities of its elements. The complexity of the sequence itself | |
792 | is O(N), where N is the number of elements in the sequence.] | |
793 | ||
794 | [heading Example] | |
795 | ||
796 | Some using declarations: | |
797 | ||
798 | [reference_using_declarations_sequence] | |
799 | ||
800 | [note The test harness for the example(s) below is presented in the | |
801 | __qi_basics_examples__ section.] | |
802 | ||
803 | [reference_sequence] | |
804 | ||
805 | [endsect] [/ Sequence] | |
806 | ||
807 | [/------------------------------------------------------------------------------] | |
808 | [section:sequential_or Sequential Or Parser (`a || b`)] | |
809 | ||
810 | [heading Description] | |
811 | ||
812 | The sequential-or operator, `a || b`, matches `a` or `b` or `a` followed | |
813 | by `b`. That is, if both `a` and `b` match, it must be in sequence; this | |
814 | is equivalent to `a >> -b | b`: | |
815 | ||
816 | a || b || ... | |
817 | ||
818 | [heading Header] | |
819 | ||
820 | // forwards to <boost/spirit/home/qi/operator/sequential_or.hpp> | |
821 | #include <boost/spirit/include/qi_sequential_or.hpp> | |
822 | ||
823 | Also, see __include_structure__. | |
824 | ||
825 | [heading Model of] | |
826 | ||
827 | [:__nary_parser_concept__] | |
828 | ||
829 | [variablelist Notation | |
830 | [[`a`, `b`] [A __parser_concept__]] | |
831 | ] | |
832 | ||
833 | [heading Expression Semantics] | |
834 | ||
835 | Semantics of an expression is defined only where it differs from, or is not | |
836 | defined in __nary_parser_concept__. | |
837 | ||
838 | [table | |
839 | [[Expression] [Semantics]] | |
840 | [[`a || b`] [Match `a` or `b` in sequence. equivalent to `a >> -b | b`]] | |
841 | ] | |
842 | ||
843 | [heading Attributes] | |
844 | ||
845 | See __qi_comp_attr_notation__. | |
846 | ||
847 | [table | |
848 | [[Expression] [Attribute]] | |
849 | [[`a || b`] | |
850 | [``a: A, b: B --> (a || b): tuple<optional<A>, optional<B> > | |
851 | a: A, b: Unused --> (a || b): optional<A> | |
852 | a: Unused, b: B --> (a || b): optional<B> | |
853 | a: Unused, b: Unused --> (a || b): Unused | |
854 | ||
855 | a: A, b: A --> (a || b): vector<optional<A> >``]] | |
856 | ] | |
857 | ||
858 | [note The sequential-or parser behaves attribute-wise very similar to the | |
859 | plain sequence parser (`a >> b`) in the sense that it exposes the | |
860 | attributes of its elements separately. For instance, if you attach a | |
861 | semantic action to the whole sequential-or: | |
862 | `` | |
863 | (int_ || int_)[print_pair(_1, _2)] | |
864 | `` | |
865 | the function object `print_pair` would be invoked with the | |
866 | attribute of the first `int_` (`boost::optional<int>`) as its first | |
867 | parameter and the attribute of the second `int_` (`boost::optional<int>` | |
868 | as well) as its second parameter.] | |
869 | ||
870 | [heading Complexity] | |
871 | ||
872 | [:The overall complexity of the sequential-or parser is defined by the | |
873 | sum of the complexities of its elements. The complexity of the | |
874 | sequential-or itself is O(N), where N is the number of elements in the | |
875 | sequence.] | |
876 | ||
877 | [heading Example] | |
878 | ||
879 | [note The test harness for the example(s) below is presented in the | |
880 | __qi_basics_examples__ section.] | |
881 | ||
882 | Some using declarations: | |
883 | ||
884 | [reference_using_declarations_sequential_or] | |
885 | ||
886 | [reference_sequential_or] | |
887 | ||
888 | [endsect] [/ Sequential Or] | |
889 | ||
890 | [endsect] |