[/============================================================================== Copyright (C) 2001-2011 Joel de Guzman Copyright (C) 2001-2011 Hartmut Kaiser Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) ===============================================================================/] [section:operator Parser Operators] Operators are used as a means for object composition and embedding. Simple parsers may be composed to form composites through operator overloading, crafted to approximate the syntax of __peg__ (PEG). An expression such as: a | b yields a new parser type which is a composite of its operands, `a` and `b`. This module includes different parsers which get instantiated if one of the overloaded operators is used with more primitive parser constructs. It includes Alternative (`|`), And-predicate (unary `&`), Difference (`-`), Expect (`>`), Kleene star (unary `*`), Lists (`%`), Not-predicate (`!`), Optional (unary `-`), Permutation (`^`), Plus (unary `+`), Sequence (`>>`), and Sequential-Or (`||`). [heading Module Header] // forwards to #include Also, see __include_structure__. [/------------------------------------------------------------------------------] [section:alternative Alternative Parser (`a | b`)] [heading Description] The alternative operator, `a | b`, matches one of two or more operands (`a`, `b`, ... etc.): a | b | ... Alternative operands are tried one by one on a first-match-wins basis starting from the leftmost operand. After a successfully matched alternative is found, the parser concludes its search, essentially short-circuiting the search for other potentially viable candidates. This short-circuiting implicitly gives the highest priority to the leftmost alternative. Short-circuiting is done in the same manner as C or C++'s logical expressions; e.g. `if (x < 3 || y < 2)` where, if `x < 3`, the `y < 2` test is not done at all. In addition to providing an implicit priority rule for alternatives which is necessary, given its non-deterministic nature, short-circuiting improves the execution time. If the order of your alternatives is logically irrelevant, strive to put the (expected) most common choice first for maximum efficiency. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__nary_parser_concept__] [variablelist Notation [[`a`, `b`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __nary_parser_concept__. [table [[Expression] [Semantics]] [[`a | b`] [Match `a` or `b`.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a | b`] [``a: A, b: B --> (a | b): variant a: A, b: Unused --> (a | b): optional a: A, b: B, c: Unused --> (a | b | c): optional > a: Unused, b: B --> (a | b): optional a: Unused, b: Unused --> (a | b): Unused a: A, b: A --> (a | b): A``]] ] [note Alternative parsers do not roll back changes made to the outer attribute because of a failed alternative. If you need to enforce that only the succeeded alternative changes the outer attribute please utilize the directive __qi_hold__`[]`.] [heading Complexity] [:The overall complexity of the alternative parser is defined by the sum of the complexities of its elements. The complexity of the alternative parser itself is O(N), where N is the number of alternatives.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] Some using declarations: [reference_using_declarations_alternative] [reference_alternative] [endsect] [/ Alternative] [/------------------------------------------------------------------------------] [section:and_predicate And-Predicate Parser (`&a`)] [heading Description] Syntactic predicates assert a certain conditional syntax to be satisfied before evaluating another production. Similar to semantic predicates, __qi_eps__, syntactic predicates do not consume any input. The /and-predicate/, `&a`, is a positive syntactic predicate that returns a zero length match only if its predicate matches. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_parser_concept__] [variablelist Notation [[`a`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_parser_concept__. [table [[Expression] [Semantics]] [[`&a`] [If the predicate `a` matches, return a zero length match. Otherwise, fail.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`&a`] [__unused_type__]] ] [heading Complexity] [:The complexity is defined by the complexity of the predicate, `a`] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_and_predicate] [endsect] [/ And Predicate] [/------------------------------------------------------------------------------] [section:difference Difference Parser (`a - b`)] [heading Description] The difference operator, `a - b`, is a binary operator that matches the first (LHS) operand but not the second (RHS). [footnote Unlike classic Spirit, with Spirit2, the expression will always fail if the RHS is a successful match regardless if the RHS matches less characters. For example, the rule `lit("policeman") - "police"` will always fail to match. Spirit2 does not count the matching chars while parsing and there is no reliable and fast way to check if the LHS matches more than the RHS.] [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__binary_parser_concept__] [variablelist Notation [[`a`, `b`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __binary_parser_concept__. [table [[Expression] [Semantics]] [[`a - b`] [Parse `a` but not `b`.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a - b`] [``a: A, b: B --> (a - b): A a: Unused, b: B --> (a - b): Unused``]] ] [heading Complexity] [:The complexity of the difference parser is defined by the sum of the complexities of both operands.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_difference] [endsect] [/ Difference] [/------------------------------------------------------------------------------] [section:expect Expectation Operator (`a > b`)] [heading Description] There are occasions in which it is expected that the input must match a particular parser or the input is invalid. Such cases generally arise after matching a portion of a grammar, such that the context is fully known. In such a situation, failure to match should result in an exception. For example, when parsing an e-mail address, after matching a name and "@" there must be a domain name or the address is invalid. The expectation operator (>) requires that the following parser match the input or an exception is emitted. Using on_error(), that exception can be handled by calling a handler with the context at which the parsing failed can be reported. By contrast, the follows operator (>>) does not require that the following parser match the input, which allows for backtracking or simply returning false from the parse() function with no exceptions. Like the __qi_sequence__, the expectation operator, `a > b`, parses two or more operands (`a`, `b`, ... etc.), in sequence: a > b > ... However, while the plain __qi_sequence__ simply returns a no-match (returns `false`) when one of the elements fail, the expectation: `>` operator throws an __qi_expectation_failure__`` when the second or succeeding operands (all operands except the first) fail to match. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__nary_parser_concept__] [variablelist Notation [[`a`, `b`] [A __parser_concept__]] [[`Iter`] [A __fwditer__ type]] ] [heading Expectation Failure] When any operand, except the first, fail to match an `expectation_failure` is thrown: template struct expectation_failure : std::runtime_error { Iter first; // [first, last) iterator pointing Iter last; // to the error position in the input. __info__ what_; // Information about the nature of the error. }; [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __nary_parser_concept__. [table [[Expression] [Semantics]] [[`a > b`] [Match `a` followed by `b`. If `a` fails, no-match. If `b` fails, throw an `expectation_failure`]] ] [note If you need an exception to be thrown if `a` fails, use the __qi_expectd__ directive instead of the expectation operator.] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a > b`] [``a: A, b: B --> (a > b): tuple a: A, b: Unused --> (a > b): A a: Unused, b: B --> (a > b): B a: Unused, b: Unused --> (a > b): Unused a: A, b: A --> (a > b): vector a: vector, b: A --> (a > b): vector a: A, b: vector --> (a > b): vector a: vector, b: vector --> (a > b): vector``]] ] [heading Complexity] [:The overall complexity of the expectation parser is defined by the sum of the complexities of its elements. The complexity of the expectation operator itself is O(N), where N is the number of elements in the sequence.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] Some using declarations: [reference_using_declarations_expect] [reference_expect] [endsect] [/ Expectation] [/------------------------------------------------------------------------------] [section:kleene Kleene Parser (`*a`)] [heading Description] The kleene operator, `*a`, is a unary operator that matches its operand zero or more times. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_parser_concept__] [variablelist Notation [[`a`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_parser_concept__. [table [[Expression] [Semantics]] [[`*a`] [Match `a` zero or more times.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`*a`] [``a: A --> *a: vector a: Unused --> *a: Unused``]] ] [heading Complexity] [:The overall complexity of the Kleene star is defined by the complexity of its subject, `a`, multiplied by the number of repetitions. The complexity of the Kleene star itself is O(N), where N is the number successful repetitions.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_kleene] [endsect] [/ Kleene] [/------------------------------------------------------------------------------] [section:list List Parser (`a % b`)] [heading Description] The list operator, `a % b`, is a binary operator that matches a list of one or more repetitions of `a` separated by occurrences of `b`. This is equivalent to `a >> *(b >> a)`. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__binary_parser_concept__] [variablelist Notation [[`a`, `b`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __binary_parser_concept__. [table [[Expression] [Semantics]] [[`a % b`] [Match a list of one or more repetitions of `a` separated by occurrences of `b`. This is equivalent to `a >> *(omit[b] >> a)`.]] ] [note The list operator `a % b` omits the attribute of parser `b`. If you need `b` to contribute to the result attribute choose `a >> *(b >> a)` over the list operator `a % b`.] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a % b`] [``a: A, b: B --> (a % b): vector a: Unused, b: B --> (a % b): Unused``]] ] [heading Complexity] [:The overall complexity of the List is defined by the complexity of its subject, `a`, multiplied by the number of repetitions. The complexity of the List itself is O(N), where N is the number successful repetitions.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_list] [endsect] [/ List] [/------------------------------------------------------------------------------] [section:not_predicate Not-Predicate Parser (`!a`)] [heading Description] Syntactic predicates assert a certain conditional syntax to be satisfied before evaluating another production. Similar to semantic predicates, __qi_eps__, syntactic predicates do not consume any input. The /not-predicate/, `!a`, is a negative syntactic predicate that returns a zero length match only if its predicate fails to match. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_parser_concept__] [variablelist Notation [[`a`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_parser_concept__. [table [[Expression] [Semantics]] [[`!a`] [If the predicate `a` matches, fail. Otherwise, return a zero length match.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`!a`] [__unused_type__]] ] [heading Complexity] [:The complexity is defined by the complexity of the predicate, `a`] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_not_predicate] [endsect] [/ Not Predicate] [/------------------------------------------------------------------------------] [section:optional Optional Parser (`-a`)] [heading Description] The optional operator, `-a`, is a unary operator that matches its operand zero or one time. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_parser_concept__] [variablelist Notation [[`a`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_parser_concept__. [table [[Expression] [Semantics]] [[`-a`] [Match `a` zero or one time.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`-a`] [``a: A --> -a: optional a: Unused --> -a: Unused``]] ] [heading Complexity] [:The complexity is defined by the complexity of the operand, `a`] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_optional] [endsect] [/ Optional] [/------------------------------------------------------------------------------] [section:permutation Permutation Parser (`a ^ b`)] [heading Description] The permutation operator, `a ^ b`, matches one or more operands (`a`, `b`, ... etc.) in any order: a ^ b ^ ... The operands are the elements in the permutation set. Each element in the permutation set may occur at most once, but not all elements of the given set need to be present. Note that by this definition, the permutation operator is not limited to strict permutations. For example: char_('a') ^ 'b' ^ 'c' matches: "a", "ab", "abc", "cba", "bca" ... etc. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__nary_parser_concept__] [variablelist Notation [[`a`, `b`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __nary_parser_concept__. [table [[Expression] [Semantics]] [[`a ^ b`] [Match `a` or `b` in any order. Each operand may match zero or one time as long as at least one operand matches.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a ^ b`] [``a: A, b: B --> (a ^ b): tuple, optional > a: A, b: Unused --> (a ^ b): optional a: Unused, b: B --> (a ^ b): optional a: Unused, b: Unused --> (a ^ b): Unused``]] ] [heading Complexity] [:The overall complexity of the permutation parser is defined by the sum of the complexities of its elements, s, multiplied by log s. The complexity of the permutation parser itself is O(N log N), where N is the number of elements.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] Some using declarations: [reference_using_declarations_permutation] [reference_permutation] [endsect] [/ Permutation] [/------------------------------------------------------------------------------] [section:plus Plus Parser (`+a`)] [heading Description] The plus operator, `+a`, is a unary operator that matches its operand one or more times. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_parser_concept__] [variablelist Notation [[`a`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_parser_concept__. [table [[Expression] [Semantics]] [[`+a`] [Match `a` one or more times.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`+a`] [``a: A --> +a: vector a: Unused --> +a: Unused``]] ] [heading Complexity] [:The overall complexity of the Plus is defined by the complexity of its subject, `a`, multiplied by the number of repetitions. The complexity of the Plus itself is O(N), where N is the number successful repetitions.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_plus] [endsect] [/ Plus] [/------------------------------------------------------------------------------] [section:sequence Sequence Parser (`a >> b`)] [heading Description] The sequence operator, `a >> b`, parses two or more operands (`a`, `b`, ... etc.), in sequence: a >> b >> ... [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__nary_parser_concept__] [variablelist Notation [[`a`, `b`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __nary_parser_concept__. [table [[Expression] [Semantics]] [[`a >> b`] [Match `a` followed by `b`.]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a >> b`] [``a: A, b: B --> (a >> b): tuple a: A, b: Unused --> (a >> b): A a: Unused, b: B --> (a >> b): B a: Unused, b: Unused --> (a >> b): Unused a: A, b: A --> (a >> b): vector a: vector, b: A --> (a >> b): vector a: A, b: vector --> (a >> b): vector a: vector, b: vector --> (a >> b): vector``]] ] [heading Complexity] [:The overall complexity of the sequence parser is defined by the sum of the complexities of its elements. The complexity of the sequence itself is O(N), where N is the number of elements in the sequence.] [heading Example] Some using declarations: [reference_using_declarations_sequence] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] [reference_sequence] [endsect] [/ Sequence] [/------------------------------------------------------------------------------] [section:sequential_or Sequential Or Parser (`a || b`)] [heading Description] The sequential-or operator, `a || b`, matches `a` or `b` or `a` followed by `b`. That is, if both `a` and `b` match, it must be in sequence; this is equivalent to `a >> -b | b`: a || b || ... [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__nary_parser_concept__] [variablelist Notation [[`a`, `b`] [A __parser_concept__]] ] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __nary_parser_concept__. [table [[Expression] [Semantics]] [[`a || b`] [Match `a` or `b` in sequence. equivalent to `a >> -b | b`]] ] [heading Attributes] See __qi_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a || b`] [``a: A, b: B --> (a || b): tuple, optional > a: A, b: Unused --> (a || b): optional a: Unused, b: B --> (a || b): optional a: Unused, b: Unused --> (a || b): Unused a: A, b: A --> (a || b): vector >``]] ] [note The sequential-or parser behaves attribute-wise very similar to the plain sequence parser (`a >> b`) in the sense that it exposes the attributes of its elements separately. For instance, if you attach a semantic action to the whole sequential-or: `` (int_ || int_)[print_pair(_1, _2)] `` the function object `print_pair` would be invoked with the attribute of the first `int_` (`boost::optional`) as its first parameter and the attribute of the second `int_` (`boost::optional` as well) as its second parameter.] [heading Complexity] [:The overall complexity of the sequential-or parser is defined by the sum of the complexities of its elements. The complexity of the sequential-or itself is O(N), where N is the number of elements in the sequence.] [heading Example] [note The test harness for the example(s) below is presented in the __qi_basics_examples__ section.] Some using declarations: [reference_using_declarations_sequential_or] [reference_sequential_or] [endsect] [/ Sequential Or] [endsect]