123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422 |
- [/==============================================================================
- 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 Parser Concepts]
- Spirit.Qi parsers fall into a couple of generalized __concepts__. The
- /Parser/ is the most fundamental concept. All Spirit.Qi parsers are
- models of the /Parser/ concept. /PrimitiveParser/, /UnaryParser/,
- /BinaryParser/, /NaryParser/, and /Nonterminal/ are all refinements of the
- /Parser/ concept.
- The following sections provide details on these concepts.
- [/------------------------------------------------------------------------------]
- [section Parser]
- [heading Description]
- The /Parser/ is the most fundamental concept. A Parser has a member
- function, `parse`, that accepts a first-last __fwditer__ pair and returns
- bool as its result. The iterators delimit the data being parsed.
- The Parser's `parse` member function returns `true` if the parse
- succeeds, in which case the first iterator is advanced accordingly. Each
- Parser can represent a specific pattern or algorithm, or it can be a
- more complex parser formed as a composition of other Parsers.
- [variablelist Notation
- [[`p`] [A `Parser`.]]
- [[`P`] [A `Parser` type.]]
- [[`Iter`] [a __fwditer__ type.]]
- [[`f`, `l`] [__fwditer__. first/last iterator pair.]]
- [[`Context`] [The parser's __context__ type.]]
- [[`context`] [The parser's __context__, or __unused__.]]
- [[`skip`] [A skip Parser, or __unused__.]]
- [[`attrib`] [A __compatible_attribute__, or __unused__.]]
- ]
- [heading Valid Expressions]
- In the expressions below, the behavior of the parser, `p`, and how `skip`
- and `attrib` are handled by `p`, are left unspecified in the base `Parser`
- concept. These are specified in subsequent, more refined concepts and by
- the actual models thereof.
- For any Parser the following expressions must be valid:
- [table
- [[Expression] [Semantics] [Return type]]
- [[
- ``p.parse(f, l, context, skip, attr)``]
- [Match the input sequence
- starting from `f`. Return
- `true` if successful, otherwise
- return `false`.] [`bool`]]
- [[`p.what(context)`] [Get information about a Parser.] [__info__]]
- ]
- [heading Type Expressions]
- [table
- [[Expression] [Description]]
- [[`P::template attribute<Context, Iter>::type`] [The Parser's expected attribute.]]
- [[`traits::is_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
- a certain type, `P` is a Parser, `mpl::false_`
- otherwise (See __mpl_boolean_constant__).]]
- ]
- [heading Postcondition]
- Upon return from `p.parse` the following post conditions should hold:
- * On a successful match, `f` is positioned one past the last
- matching character/token.
- * On a failed match, if a `skip` parser is __unused__,
- `f` is restored to its original position prior to entry.
- * On a failed match, if a `skip` parser is not __unused__,
- `f` is positioned one past the last character/token
- matching `skip`.
- * On a failed match, `attrib` state is undefined.
- * No post-skips: trailing `skip` characters/tokens will not be skipped.
- [heading Models]
- All parsers in Spirit.Qi are models of the /Parser/ concept.
- [endsect] [/ Parser Concept]
- [/------------------------------------------------------------------------------]
- [section PrimitiveParser]
- [heading Description]
- /PrimitiveParser/ is the most basic building block that the client uses
- to build more complex parsers.
- [heading Refinement of]
- [:__parser_concept__]
- [heading Pre-skip]
- Upon entry to the `parse` member function, a PrimitiveParser is required
- to do a pre-skip. Leading `skip` characters/tokens will be skipped prior
- to parsing. Only PrimitiveParsers are required to perform this pre-skip.
- This is typically carried out through a call to `qi::skip_over`:
- qi::skip_over(f, l, skip);
- [heading Type Expressions]
- [table
- [[Expression] [Description]]
- [[`traits::is_primitive_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
- a certain type, `P`, is a PrimitiveParser, `mpl::false_`
- otherwise (See __mpl_boolean_constant__).]]
- ]
- [heading Models]
- * __qi_attr__
- * __qi_eoi__
- * __qi_eol__
- * __qi_eps__
- * __qi_symbols__
- [endsect] [/ PrimitiveParser Concept]
- [/------------------------------------------------------------------------------]
- [section UnaryParser]
- [heading Description]
- /UnaryParser/ is a composite parser that has a single subject. The
- UnaryParser may change the behavior of its subject following the
- __delegate_pattern__.
- [heading Refinement of]
- [:__parser_concept__]
- [variablelist Notation
- [[`p`] [A UnaryParser.]]
- [[`P`] [A UnaryParser type.]]
- ]
- [heading Valid Expressions]
- In addition to the requirements defined in __parser_concept__, for any
- UnaryParser the following must be met:
- [table
- [[Expression] [Semantics] [Return type]]
- [[`p.subject`] [Subject parser.] [__parser_concept__]]
- ]
- [heading Type Expressions]
- [table
- [[Expression] [Description]]
- [[`P::subject_type`] [The subject parser type.]]
- [[`traits::is_unary_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
- a certain type, `P` is a UnaryParser, `mpl::false_`
- otherwise (See __mpl_boolean_constant__).]]
- ]
- [heading Invariants]
- For any UnaryParser, `P`, the following invariant always holds:
- * `traits::is_parser<P::subject_type>::type` evaluates to `mpl::true_`
- [heading Models]
- * __qi_and_predicate__
- * __qi_kleene__
- * __qi_lexeme__
- * __qi_not_predicate__
- * __qi_omit__
- * __qi_plus__
- * __qi_raw__
- * [qi_repeat `repeat`]
- * __qi_skip__
- [endsect] [/ UnaryParser Concept]
- [/------------------------------------------------------------------------------]
- [section BinaryParser]
- [heading Description]
- /BinaryParser/ is a composite parser that has a two subjects, `left` and
- `right`. The BinaryParser allows its subjects to be treated in the same
- way as a single instance of a __parser_concept__ following the
- __composite_pattern__.
- [heading Refinement of]
- [:__parser_concept__]
- [variablelist Notation
- [[`p`] [A BinaryParser.]]
- [[`P`] [A BinaryParser type.]]
- ]
- [heading Valid Expressions]
- In addition to the requirements defined in __parser_concept__, for any
- BinaryParser the following must be met:
- [table
- [[Expression] [Semantics] [Return type]]
- [[`p.left`] [Left parser.] [__parser_concept__]]
- [[`p.right`] [Right parser.] [__parser_concept__]]
- ]
- [heading Type Expressions]
- [table
- [[Expression] [Description]]
- [[`P::left_type`] [The left parser type.]]
- [[`P::right_type`] [The right parser type.]]
- [[`traits::is_binary_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
- a certain type, `P` is a BinaryParser, `mpl::false_`
- otherwise (See __mpl_boolean_constant__).]]
- ]
- [heading Invariants]
- For any BinaryParser, `P`, the following invariants always hold:
- * `traits::is_parser<P::left_type>::type` evaluates to `mpl::true_`
- * `traits::is_parser<P::right_type>::type` evaluates to `mpl::true_`
- [heading Models]
- * __qi_difference__
- * __qi_list__
- [endsect] [/ BinaryParser Concept]
- [/------------------------------------------------------------------------------]
- [section NaryParser]
- [heading Description]
- /NaryParser/ is a composite parser that has one or more subjects. The
- NaryParser allows its subjects to be treated in the same way as a single
- instance of a __parser_concept__ following the __composite_pattern__.
- [heading Refinement of]
- [:__parser_concept__]
- [variablelist Notation
- [[`p`] [A NaryParser.]]
- [[`P`] [A NaryParser type.]]
- ]
- [heading Valid Expressions]
- In addition to the requirements defined in __parser_concept__, for any
- NaryParser the following must be met:
- [table
- [[Expression] [Semantics] [Return type]]
- [[`p.elements`] [The tuple of elements.] [A __fusion__ Sequence of __parser_concept__ types.]]
- ]
- [heading Type Expressions]
- [table
- [[Expression] [Description]]
- [[`p.elements_type`] [Elements tuple type.]]
- [[`traits::is_nary_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
- a certain type, `P` is a NaryParser, `mpl::false_`
- otherwise (See __mpl_boolean_constant__).]]
- ]
- [heading Invariants]
- For each element, `E`, in any NaryParser, `P`, the following invariant
- always holds:
- * `traits::is_parser<E>::type` evaluates to `mpl::true_`
- [heading Models]
- * __qi_alternative__
- * __qi_expect__
- * __qi_permutation__
- * __qi_sequence__
- * __qi_sequential_or__
- [endsect] [/ NaryParser Concept]
- [/------------------------------------------------------------------------------]
- [section Nonterminal]
- [heading Description]
- A Nonterminal is a symbol in a __peg__ production that represents a
- grammar fragment. Nonterminals may self reference to specify recursion.
- This is one of the most important concepts and the reason behind the
- word "recursive" in recursive descent parsing.
- [heading Refinement of]
- [:__parser_concept__]
- [heading Signature]
- Nonterminals can have both synthesized and inherited attributes. The
- Nonterminal's /Signature/ specifies both the synthesized and inherited
- attributes. The specification uses the function declarator syntax:
- RT(A0, A1, A2, ..., AN)
- where `RT` is the Nonterminal's synthesized attribute and `A0` ... `AN`
- are the Nonterminal's inherited attributes.
- The default value is `void()` (no synthesized and inherited attributes).
- [heading Attributes]
- The Nonterminal models a C++ function. The Nonterminal's synthesized
- attribute is analogous to the function return value and its inherited
- attributes are analogous to function arguments. The inherited attributes
- (arguments) can be passed in just like any __qi_lazy_argument__, e.g.:
- r(expr) // Evaluate expr at parse time and pass the result to the Nonterminal r
- [heading `_val`]
- The `boost::spirit::qi::_val` placeholder can be used in __phoenix__
- semantic actions anywhere in the Nonterminal's definition. This
- __phoenix__ placeholder refers to the Nonterminal's (synthesized)
- attribute. The `_val` placeholder acts like a mutable reference to the
- Nonterminal's attribute.
- [note Starting with __spirit__ V2.5 (distributed with Boost V1.47) the
- placeholder `_val` can be used in semantic actions attached to top level
- parser components as well. See __parse_api__ for more information.]
- [heading `_r1` ... `r10`]
- The `boost::spirit::_r1` ... `boost::spirit::r10` placeholders can be used
- in __phoenix__ semantic actions anywhere in the Nonterminal's
- definition. These __phoenix__ placeholders refer to the Nonterminal's
- inherited attributes.
- [heading Locals]
- Nonterminals can have local variables that will be created on the stack
- at parse time. A locals descriptor added to the Nonterminal declaration
- will give the Nonterminal local variables:
- template <typename T0, typename T1, typename T2, ..., typename TN>
- struct locals;
- where `T0` ... `TN` are the types of local variables accessible in your
- __phoenix__ semantic actions using the placeholders:
- * `boost::spirit::_a`
- * `boost::spirit::_b`
- * `boost::spirit::_c`
- * `boost::spirit::_d`
- * `boost::spirit::_e`
- * `boost::spirit::_f`
- * `boost::spirit::_g`
- * `boost::spirit::_h`
- * `boost::spirit::_i`
- * `boost::spirit::_j`
- which correspond to the Nonterminal's local variables `T0` ... `T9`.
- [variablelist Notation
- [[`x`] [A Nonterminal]]
- [[`X`] [A Nonterminal type]]
- [[`arg1`, `arg2`, ..., `argN`] [__qi_lazy_arguments__ that evaluate to each of
- the Nonterminal's inherited attributes.]]
- ]
- [heading Valid Expressions]
- In addition to the requirements defined in __parser_concept__, for any
- Nonterminal the following must be met:
- [table
- [[Expression] [Semantics] [Return type]]
- [[`x`] [In a parser expression, invoke Nonterminal `x`] [`X`]]
- [[`x(arg1, arg2, ..., argN)`][In a parser expression, invoke Nonterminal `r`
- passing in inherited attributes
- `arg1` ... `argN`] [`X`]]
- [[`x.name(name)`] [Naming a Nonterminal.] [`void`]]
- [[`x.name()`] [Getting the name of a Nonterminal.] [`std::string`]]
- [[debug(x)] [Debug Nonterminal `x`.] [`void`]]
- ]
- [heading Type Expressions]
- [table
- [[Expression] [Description]]
- [[`X::sig_type`] [The Signature of `X`: In a function signature form
- as described above in the Signature paragraph.]]
- [[`X::locals_type`] [The local variables of `X`: An __mpl_fwd_sequence__.]]
- ]
- [heading Models]
- * __qi_rule__
- * __qi_grammar__
- [endsect] [/ Concept]
- [endsect]
|