1 [/==============================================================================
2 Copyright (C) 2001-2011 Joel de Guzman
3 Copyright (C) 2001-2011 Hartmut Kaiser
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 ===============================================================================/]
9 [section Parser Concepts]
11 Spirit.Qi parsers fall into a couple of generalized __concepts__. The
12 /Parser/ is the most fundamental concept. All Spirit.Qi parsers are
13 models of the /Parser/ concept. /PrimitiveParser/, /UnaryParser/,
14 /BinaryParser/, /NaryParser/, and /Nonterminal/ are all refinements of the
17 The following sections provide details on these concepts.
19 [/------------------------------------------------------------------------------]
24 The /Parser/ is the most fundamental concept. A Parser has a member
25 function, `parse`, that accepts a first-last __fwditer__ pair and returns
26 bool as its result. The iterators delimit the data being parsed.
27 The Parser's `parse` member function returns `true` if the parse
28 succeeds, in which case the first iterator is advanced accordingly. Each
29 Parser can represent a specific pattern or algorithm, or it can be a
30 more complex parser formed as a composition of other Parsers.
32 [variablelist Notation
34 [[`P`] [A `Parser` type.]]
35 [[`Iter`] [a __fwditer__ type.]]
36 [[`f`, `l`] [__fwditer__. first/last iterator pair.]]
37 [[`Context`] [The parser's __context__ type.]]
38 [[`context`] [The parser's __context__, or __unused__.]]
39 [[`skip`] [A skip Parser, or __unused__.]]
40 [[`attrib`] [A __compatible_attribute__, or __unused__.]]
43 [heading Valid Expressions]
45 In the expressions below, the behavior of the parser, `p`, and how `skip`
46 and `attrib` are handled by `p`, are left unspecified in the base `Parser`
47 concept. These are specified in subsequent, more refined concepts and by
48 the actual models thereof.
50 For any Parser the following expressions must be valid:
53 [[Expression] [Semantics] [Return type]]
55 ``p.parse(f, l, context, skip, attr)``]
56 [Match the input sequence
57 starting from `f`. Return
58 `true` if successful, otherwise
59 return `false`.] [`bool`]]
60 [[`p.what(context)`] [Get information about a Parser.] [__info__]]
63 [heading Type Expressions]
66 [[Expression] [Description]]
67 [[`P::template attribute<Context, Iter>::type`] [The Parser's expected attribute.]]
68 [[`traits::is_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
69 a certain type, `P` is a Parser, `mpl::false_`
70 otherwise (See __mpl_boolean_constant__).]]
73 [heading Postcondition]
75 Upon return from `p.parse` the following post conditions should hold:
77 * On a successful match, `f` is positioned one past the last
78 matching character/token.
79 * On a failed match, if a `skip` parser is __unused__,
80 `f` is restored to its original position prior to entry.
81 * On a failed match, if a `skip` parser is not __unused__,
82 `f` is positioned one past the last character/token
84 * On a failed match, `attrib` state is undefined.
85 * No post-skips: trailing `skip` characters/tokens will not be skipped.
89 All parsers in Spirit.Qi are models of the /Parser/ concept.
91 [endsect] [/ Parser Concept]
93 [/------------------------------------------------------------------------------]
94 [section PrimitiveParser]
98 /PrimitiveParser/ is the most basic building block that the client uses
99 to build more complex parsers.
101 [heading Refinement of]
103 [:__parser_concept__]
107 Upon entry to the `parse` member function, a PrimitiveParser is required
108 to do a pre-skip. Leading `skip` characters/tokens will be skipped prior
109 to parsing. Only PrimitiveParsers are required to perform this pre-skip.
110 This is typically carried out through a call to `qi::skip_over`:
112 qi::skip_over(f, l, skip);
114 [heading Type Expressions]
117 [[Expression] [Description]]
118 [[`traits::is_primitive_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
119 a certain type, `P`, is a PrimitiveParser, `mpl::false_`
120 otherwise (See __mpl_boolean_constant__).]]
131 [endsect] [/ PrimitiveParser Concept]
133 [/------------------------------------------------------------------------------]
134 [section UnaryParser]
136 [heading Description]
138 /UnaryParser/ is a composite parser that has a single subject. The
139 UnaryParser may change the behavior of its subject following the
140 __delegate_pattern__.
142 [heading Refinement of]
144 [:__parser_concept__]
146 [variablelist Notation
147 [[`p`] [A UnaryParser.]]
148 [[`P`] [A UnaryParser type.]]
151 [heading Valid Expressions]
153 In addition to the requirements defined in __parser_concept__, for any
154 UnaryParser the following must be met:
157 [[Expression] [Semantics] [Return type]]
158 [[`p.subject`] [Subject parser.] [__parser_concept__]]
161 [heading Type Expressions]
164 [[Expression] [Description]]
165 [[`P::subject_type`] [The subject parser type.]]
166 [[`traits::is_unary_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
167 a certain type, `P` is a UnaryParser, `mpl::false_`
168 otherwise (See __mpl_boolean_constant__).]]
173 For any UnaryParser, `P`, the following invariant always holds:
175 * `traits::is_parser<P::subject_type>::type` evaluates to `mpl::true_`
179 * __qi_and_predicate__
182 * __qi_not_predicate__
186 * [qi_repeat `repeat`]
189 [endsect] [/ UnaryParser Concept]
191 [/------------------------------------------------------------------------------]
192 [section BinaryParser]
194 [heading Description]
196 /BinaryParser/ is a composite parser that has a two subjects, `left` and
197 `right`. The BinaryParser allows its subjects to be treated in the same
198 way as a single instance of a __parser_concept__ following the
199 __composite_pattern__.
201 [heading Refinement of]
203 [:__parser_concept__]
205 [variablelist Notation
206 [[`p`] [A BinaryParser.]]
207 [[`P`] [A BinaryParser type.]]
210 [heading Valid Expressions]
212 In addition to the requirements defined in __parser_concept__, for any
213 BinaryParser the following must be met:
216 [[Expression] [Semantics] [Return type]]
217 [[`p.left`] [Left parser.] [__parser_concept__]]
218 [[`p.right`] [Right parser.] [__parser_concept__]]
221 [heading Type Expressions]
224 [[Expression] [Description]]
225 [[`P::left_type`] [The left parser type.]]
226 [[`P::right_type`] [The right parser type.]]
227 [[`traits::is_binary_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
228 a certain type, `P` is a BinaryParser, `mpl::false_`
229 otherwise (See __mpl_boolean_constant__).]]
234 For any BinaryParser, `P`, the following invariants always hold:
236 * `traits::is_parser<P::left_type>::type` evaluates to `mpl::true_`
237 * `traits::is_parser<P::right_type>::type` evaluates to `mpl::true_`
244 [endsect] [/ BinaryParser Concept]
246 [/------------------------------------------------------------------------------]
249 [heading Description]
251 /NaryParser/ is a composite parser that has one or more subjects. The
252 NaryParser allows its subjects to be treated in the same way as a single
253 instance of a __parser_concept__ following the __composite_pattern__.
255 [heading Refinement of]
257 [:__parser_concept__]
259 [variablelist Notation
260 [[`p`] [A NaryParser.]]
261 [[`P`] [A NaryParser type.]]
264 [heading Valid Expressions]
266 In addition to the requirements defined in __parser_concept__, for any
267 NaryParser the following must be met:
270 [[Expression] [Semantics] [Return type]]
271 [[`p.elements`] [The tuple of elements.] [A __fusion__ Sequence of __parser_concept__ types.]]
274 [heading Type Expressions]
277 [[Expression] [Description]]
278 [[`p.elements_type`] [Elements tuple type.]]
279 [[`traits::is_nary_parser<P>::type`] [Metafunction that evaluates to `mpl::true_` if
280 a certain type, `P` is a NaryParser, `mpl::false_`
281 otherwise (See __mpl_boolean_constant__).]]
286 For each element, `E`, in any NaryParser, `P`, the following invariant
289 * `traits::is_parser<E>::type` evaluates to `mpl::true_`
297 * __qi_sequential_or__
299 [endsect] [/ NaryParser Concept]
301 [/------------------------------------------------------------------------------]
302 [section Nonterminal]
304 [heading Description]
306 A Nonterminal is a symbol in a __peg__ production that represents a
307 grammar fragment. Nonterminals may self reference to specify recursion.
308 This is one of the most important concepts and the reason behind the
309 word "recursive" in recursive descent parsing.
311 [heading Refinement of]
313 [:__parser_concept__]
317 Nonterminals can have both synthesized and inherited attributes. The
318 Nonterminal's /Signature/ specifies both the synthesized and inherited
319 attributes. The specification uses the function declarator syntax:
321 RT(A0, A1, A2, ..., AN)
323 where `RT` is the Nonterminal's synthesized attribute and `A0` ... `AN`
324 are the Nonterminal's inherited attributes.
328 The Nonterminal models a C++ function. The Nonterminal's synthesized
329 attribute is analogous to the function return value and its inherited
330 attributes are analogous to function arguments. The inherited attributes
331 (arguments) can be passed in just like any __qi_lazy_argument__, e.g.:
333 r(expr) // Evaluate expr at parse time and pass the result to the Nonterminal r
337 The `boost::spirit::qi::_val` placeholder can be used in __phoenix__
338 semantic actions anywhere in the Nonterminal's definition. This
339 __phoenix__ placeholder refers to the Nonterminal's (synthesized)
340 attribute. The `_val` placeholder acts like a mutable reference to the
341 Nonterminal's attribute.
343 [note Starting with __spirit__ V2.5 (distributed with Boost V1.47) the
344 placeholder `_val` can be used in semantic actions attached to top level
345 parser components as well. See __parse_api__ for more information.]
347 [heading `_r1` ... `r10`]
349 The `boost::spirit::_r1` ... `boost::spirit::r10` placeholders can be used
350 in __phoenix__ semantic actions anywhere in the Nonterminal's
351 definition. These __phoenix__ placeholders refer to the Nonterminal's
352 inherited attributes.
356 Nonterminals can have local variables that will be created on the stack
357 at parse time. A locals descriptor added to the Nonterminal declaration
358 will give the Nonterminal local variables:
360 template <typename T0, typename T1, typename T2, ..., typename TN>
363 where `T0` ... `TN` are the types of local variables accessible in your
364 __phoenix__ semantic actions using the placeholders:
366 * `boost::spirit::_a`
367 * `boost::spirit::_b`
368 * `boost::spirit::_c`
369 * `boost::spirit::_d`
370 * `boost::spirit::_e`
371 * `boost::spirit::_f`
372 * `boost::spirit::_g`
373 * `boost::spirit::_h`
374 * `boost::spirit::_i`
375 * `boost::spirit::_j`
377 which correspond to the Nonterminal's local variables `T0` ... `T9`.
379 [variablelist Notation
380 [[`x`] [A Nonterminal]]
381 [[`X`] [A Nonterminal type]]
382 [[`arg1`, `arg2`, ..., `argN`] [__qi_lazy_arguments__ that evaluate to each of
383 the Nonterminal's inherited attributes.]]
386 [heading Valid Expressions]
388 In addition to the requirements defined in __parser_concept__, for any
389 Nonterminal the following must be met:
392 [[Expression] [Semantics] [Return type]]
393 [[`x`] [In a parser expression, invoke Nonterminal `x`] [`X`]]
394 [[`x(arg1, arg2, ..., argN)`][In a parser expression, invoke Nonterminal `r`
395 passing in inherited attributes
396 `arg1` ... `argN`] [`X`]]
397 [[`x.name(name)`] [Naming a Nonterminal.] [`void`]]
398 [[`x.name()`] [Getting the name of a Nonterminal.] [`std::string`]]
399 [[debug(x)] [Debug Nonterminal `x`.] [`void`]]
402 [heading Type Expressions]
405 [[Expression] [Description]]
406 [[`X::sig_type`] [The Signature of `X`: An __mpl_fwd_sequence__.
407 The first element is the Nonterminal's synthesized attribute
408 type and the rest are the inherited attribute types.]]
409 [[`X::locals_type`] [The local variables of `X`: An __mpl_fwd_sequence__.]]
417 [endsect] [/ Concept]