[/============================================================================== Copyright (C) 2001-2011 Hartmut Kaiser Copyright (C) 2001-2011 Joel de Guzman 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 Generator Operators] Operators are used as a means for object composition and embedding. Simple generators 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 generator type which is a composite of its operands, `a` and `b`. This module includes different generators which get instantiated if one of the overloaded operators is used with more primitive generator constructs. It includes sequences (`a << b`), alternatives (`a | b`), Kleene star (unary `*`), plus (unary `+`), optional (unary `-`), lists (`a % b`), and the two predicates, the /and/ predicate (unary `&`) and the /not/ predicate (unary `!`). [heading Module Header] // forwards to #include Also, see __include_structure__. [/////////////////////////////////////////////////////////////////////////////] [section:sequence Sequence Generator (`a << b`)] [heading Description] Generator sequences are used to consecutively combine different, more primitive generators. All generators in a sequence are invoked from left to right as long as they succeed. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__nary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __nary_generator_concept__. [table [[Expression] [Semantics]] [[`a << b`] [The generators `a` and `b` are executed sequentially from left to right and as long as they succeed. A failed generator stops the execution of the entire sequence and makes the sequence fail as well.]] ] It is important to note, that sequences don't perform any buffering of the output generated by its elements. That means that any failing sequence might have already generated some output, which is /not/ rolled back. [tip The simplest way to force a sequence to behave as if it did buffering is to wrap it into a buffering directive (see __karma_buffer__): ``buffer[a << b << c]`` which will /not/ generate any output in case of a failing sequence.] [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a << b` (sequence)] [``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``]] ] [important The table above uses `tuple` and `vector` as placeholders only. The notation `tuple` stands for /any fusion sequence of two elements/, where `A` is the type of its first element and `B` is the type of its second element. The notation of `vector` stands for /any STL container/ holding elements of type `A`.] The attribute composition and propagation rules as shown in the table above make sequences somewhat special as they can operate in two modes if all elements have the same attribute type: consuming fusion sequences and consuming STL containers. The selected mode depends on the type of the attribute supplied. [heading Complexity] [:The overall complexity of the sequence generator 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] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_sequence] Basic usage of a sequence: [reference_karma_sequence] [endsect] [/////////////////////////////////////////////////////////////////////////////] [section:alternative Alternative Generator (`a | b`)] [heading Description] Generator alternatives are used to combine different, more primitive generators into alternatives. All generators in an alternative are invoked from left to right until one of them succeeds. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__nary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __nary_generator_concept__. [table [[Expression] [Semantics]] [[`a | b`] [The generators `a` and `b` are executed sequentially from left to right until one of them succeeds. A failed generator forces the alternative generator to try the next one. The alternative fails as a whole only if all elements of the alternative fail. Each element of the alternative gets passed the whole attribute of the alternative.]] ] Alternatives intercept and buffer the output of the currently executed element. This allows to avoid partial outputs from failing elements as the buffered content will be forwarded to the actual output only after an element succeeded. [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a | b` (alternative)] [``a: A, b: B --> (a | b): variant 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): A``]] ] [important The table above uses `variant` as a placeholder only. The notation `variant` stands for the type `boost::variant`. ] The attribute handling of Alternatives is special as their behavior is not completely defined at compile time. First of all the selected alternative element depends on the actual type of the attribute supplied to the alternative generator (i.e. what is stored in the variant). The attribute type supplied at /runtime/ narrows the set of considered alternatives to those being compatible attribute wise. The remaining alternatives are tried sequentially until the first of them succeeds. See below for an example of this behavior. [heading Complexity] [:The overall complexity of the alternative generator is defined by the sum of the complexities of its elements. The complexity of the alternative itself is O(N), where N is the number of elements in the alternative.] [heading Example] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_alternative] Basic usage of an alternative. While being only the second alternative, the `double_` generator is chosen for output formatting because the supplied attribute type is not compatible (i.e. not convertible) to the attribute type of the `string` alternative. [reference_karma_alternative1] The same formatting rules may be used to output a string. This time we supply the string `"example"`, resulting in the first alternative to be chosen for the generated output. [reference_karma_alternative2] [endsect] [/////////////////////////////////////////////////////////////////////////////] [section:kleene Kleene Star Generator (`*a`)] [heading Description] Kleene star generators are used to repeat the execution of an embedded generator zero or more times. Regardless of the success of the embedded generator, the Kleene star generator always succeeds. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_generator_concept__. [table [[Expression] [Semantics]] [[`*a`] [The generator `a` is executed zero or more times depending on the availability of an attribute. The execution of `a` stops after the attribute values passed to the Kleene star generator are exhausted. The Kleene star always succeeds (unless the underlying output stream reports an error).]] ] [note All failing iterations of the embedded generator will consume one element from the supplied attribute.] [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`*a` (Kleene star, unary `*`)] [``a: A --> *a: vector a: Unused --> *a: Unused``]] ] [important The table above uses `vector` as a placeholder only. The notation of `vector` stands for /any STL container/ holding elements of type `A`.] The Kleene star generator will execute its embedded generator once for each element in the provided container attribute as long as the embedded generator succeeds. On each iteration it will pass the next consecutive element from the container attribute to the embedded generator. Therefore the number of iterations will not be larger than the number of elements in the container passed as its attribute. An empty container will make the Kleene star generate no output at all. It is important to note, that the Kleene star does not perform any buffering of the output generated by its embedded elements. That means that any failing element generator might have already generated some output, which is /not/ rolled back. [tip The simplest way to force a Kleene star to behave as if it did buffering is to wrap it into a buffering directive (see __karma_buffer__): ``buffer[*a]`` which will /not/ generate any output in case of a failing generator `*a`. The expression: ``*(buffer[a])`` will not generate any partial output from a generator `a` if it fails generating in the middle of its output. The overall expression will still generate the output as produced by all successful invocations of the generator `a`.] [heading Complexity] [:The overall complexity of the Kleene star generator is defined by the complexity of its embedded generator multiplied by the number of executed iterations. The complexity of the Kleene star itself is O(N), where N is the number of elements in the container passed as its attribute.] [heading Example] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_kleene] Basic usage of a Kleene star generator: [reference_karma_kleene] [endsect] [/////////////////////////////////////////////////////////////////////////////] [section:plus Plus Generator (`+a`)] [heading Description] The Plus generator is used to repeat the execution of an embedded generator one or more times. It succeeds if the embedded generator has been successfully executed at least once. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_generator_concept__. [table [[Expression] [Semantics]] [[`+a`] [The generator `a` is executed one or more times depending on the availability of an attribute. The execution of `a` stops after the attribute values passed to the plus generator are exhausted. The plus generator succeeds as long as its embedded generator has been successfully executed at least once (unless the underlying output stream reports an error).]] ] [note All failing iterations of the embedded generator will consume one element from the supplied attribute. The overall `+a` will succeed as long as at least one invocation of the embedded generator will succeed (unless the underlying output stream reports an error).] [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`+a` (unary `+`)] [``a: A --> +a: vector a: Unused --> +a: Unused``]] ] [important The table above uses `vector` as a placeholder only. The notation of `vector` stands for /any STL container/ holding elements of type `A`.] The Plus generator will execute its embedded generator once for each element in the provided container attribute as long as the embedded generator succeeds. On each iteration it will pass the next consecutive element from the container attribute to the embedded generator. Therefore the number of iterations will not be larger than the number of elements in the container passed as its attribute. An empty container will make the plus generator fail. It is important to note, that the plus generator does not perform any buffering of the output generated by its embedded elements. That means that any failing element generator might have already generated some output, which is /not/ rolled back. [tip The simplest way to force a plus generator to behave as if it did buffering is to wrap it into a buffering directive (see __karma_buffer__): ``buffer[+a]`` which will /not/ generate any output in case of a failing generator `+a`. The expression: ``+(buffer[a])`` will not generate any partial output from a generator `a` if it fails generating in the middle of its output. The overall expression will still generate the output as produced by all successful invocations of the generator `a`.] [heading Complexity] [:The overall complexity of the plus generator is defined by the complexity of its embedded generator multiplied by the number of executed iterations. The complexity of the plus generator itself is O(N), where N is the number of elements in the container passed as its attribute.] [heading Example] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_plus] Basic usage of a plus generator: [reference_karma_plus1] A more sophisticated use case showing how to leverage the fact that plus is failing for empty containers passed as its attribute: [reference_karma_plus2] [endsect] [/////////////////////////////////////////////////////////////////////////////] [section:list List Generator (`a % b`)] [heading Description] The list generator is used to repeat the execution of an embedded generator and intersperse it with the output of another generator one or more times. It succeeds if the embedded generator has been successfully executed at least once. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__binary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __binary_generator_concept__. [table [[Expression] [Semantics]] [[`a % b`] [The generator `a` is executed one or more times depending on the availability of an attribute. The output generated by `a` is interspersed with the output generated by `b`. The list generator succeeds if its first embedded generator has been successfully executed at least once (unless the underlying output stream reports an error).]] ] The list expression `a % b` is a shortcut for `a << *(b << a)`. It is almost semantically equivalent, except for the attribute of `b`, which gets ignored in the case of the list generator. [note All failing iterations of the embedded generator will consume one element from the supplied attribute. The overall `a % b` will succeed as long as at least one invocation of the embedded generator, `a`, will succeed (unless the underlying output stream reports an error).] [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`a % b` (list)] [``a: A, b: B --> (a % b): vector a: Unused, b: B --> (a % b): Unused``]] ] [important The table above uses `vector` as a placeholder only. The notation of `vector` stands for /any STL container/ holding elements of type `A`.] The list generator will execute its embedded generator once for each element in the provided container attribute and as long as the embedded generator succeeds. The output generated by its first generator will be interspersed by the output generated by the second generator. On each iteration it will pass the next consecutive element from the container attribute to the first embedded generator. The second embedded generator does not get passed any attributes (it gets invoked using an `unused_type` as its attribute). Therefore the number of iterations will not be larger than the number of elements in the container passed as its attribute. An empty container will make the list generator fail. [tip If you want to use the list generator and still allow for an empty attribute, you can use the optional operator (see __karma_optional__): ``-(a % b)`` which will succeed even if the provided container attribute does not contain any elements. ] [heading Complexity] [:The overall complexity of the list generator is defined by the complexity of its embedded generators multiplied by the number of executed iterations. The complexity of the list generator itself is O(N), where N is the number of elements in the container passed as its attribute.] [heading Example] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_list] Basic usage of a list generator: [reference_karma_list] [endsect] [/////////////////////////////////////////////////////////////////////////////] [section:optional Optional Generator (`-a`)] [heading Description] The optional generator is used to conditionally execute an embedded generator. It succeeds always. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_generator_concept__. [table [[Expression] [Semantics]] [[`-a`] [The generator `a` is executed depending on the availability of an attribute. The optional generator succeeds if its embedded generator succeeds (unless the underlying output stream reports an error).]] ] [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`-a` (optional, unary `-`)] [``a: A --> -a: optional a: Unused --> -a: Unused``]] ] [important The table above uses `optional` as a placeholder only. The notation of `optional` stands for the data type `boost::optional`.] The optional generator will execute its embedded generator once if the provided attribute holds a valid value. It forwards the value held in its attribute to the embedded generator. It is important to note, that the optional generator does not perform any buffering of the output generated by its embedded elements. That means that any failing element might have already generated some output, which is /not/ rolled back. [tip The simplest way to force a optional generator to behave as if it did buffering is to wrap it into a buffering directive (see __karma_buffer__): ``buffer[-a]`` which will /not/ generate any output in case of a failing generator `-a`. ] [heading Complexity] [:The overall complexity of the optional generator is defined by the complexity of its embedded generator. The complexity of the optional generator itself is O(1).] [heading Example] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_optional] Basic usage of an optional generator: [reference_karma_optional1] Usage and result of an empty optional generator: [reference_karma_optional2] [endsect] [/////////////////////////////////////////////////////////////////////////////] [section:and_predicate And-Predicate Generator (`&a`)] [heading Description] The and-predicate generator is used to test, whether the embedded generator succeeds without generating any output. It succeeds if the embedded generator succeeds. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_generator_concept__. [table [[Expression] [Semantics]] [[`&a`] [The generator `a` is executed for the sole purpose of testing whether it succeeds. The and-predicate generator succeeds if its embedded generator succeeds (unless the underlying output stream reports an error). The and-predicate never produces any output.]] ] The and generator is implemented by redirecting all output produced by its embedded generator into a discarding device. [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`&a` (and-predicate, unary `&`)] [`a: A --> &a: A`]] ] [note The attribute of the and-predicate is not always `unused_type`, which is different from Qi's and-predicate. This is necessary as the generator the and predicate is attached to most of the time needs an attribute. ] [heading Complexity] [:The overall complexity of the and-predicate generator is defined by the complexity of its embedded generator. The complexity of the and-predicate generator itself is O(1).] [heading Example] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_and_predicate] Basic usage of an and predicate generator: [reference_karma_and_predicate] [endsect] [/////////////////////////////////////////////////////////////////////////////] [section:not_predicate Not-Predicate Generator (`!a`)] [heading Description] The not-predicate generator is used to test, whether the embedded generator fails, without generating any output. It succeeds if the embedded generator fails. [heading Header] // forwards to #include Also, see __include_structure__. [heading Model of] [:__unary_generator_concept__] [heading Expression Semantics] Semantics of an expression is defined only where it differs from, or is not defined in __unary_generator_concept__. [table [[Expression] [Semantics]] [[`!a`] [The generator `a` is executed for the sole purpose of testing whether it succeeds. The not-predicate generator succeeds if its embedded generator fails (unless the underlying output stream reports an error). The not-predicate never produces any output.]] ] The not generator is implemented by redirecting all output produced by its embedded generator into a discarding device. [heading Attributes] See __karma_comp_attr_notation__. [table [[Expression] [Attribute]] [[`!a` (not-predicate, unary `!`)] [`a: A --> !a: A`]] ] [note The attribute of the not-predicate is not always `unused_type`, which is different from Qi's not-predicate. This is necessary as the generator the and-predicate is attached to most of the time needs an attribute. ] [heading Complexity] [:The overall complexity of the not-predicate generator is defined by the complexity of its embedded generator. The complexity of the not-predicate generator itself is O(1).] [heading Example] [note The test harness for the example(s) below is presented in the __karma_basics_examples__ section.] Some includes: [reference_karma_includes] Some using declarations: [reference_karma_using_declarations_not_predicate] Basic usage of a not predicate generator: [reference_karma_not_predicate] [endsect] [endsect]