423 lines
14 KiB
Plaintext
423 lines
14 KiB
Plaintext
[/==============================================================================
|
|
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]
|