1[/============================================================================== 2 Copyright (C) 2001-2011 Joel de Guzman 3 Copyright (C) 2001-2011 Hartmut Kaiser 4 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===============================================================================/] 8 9[section Parser Concepts] 10 11Spirit.Qi parsers fall into a couple of generalized __concepts__. The 12/Parser/ is the most fundamental concept. All Spirit.Qi parsers are 13models of the /Parser/ concept. /PrimitiveParser/, /UnaryParser/, 14/BinaryParser/, /NaryParser/, and /Nonterminal/ are all refinements of the 15/Parser/ concept. 16 17The following sections provide details on these concepts. 18 19[/------------------------------------------------------------------------------] 20[section Parser] 21 22[heading Description] 23 24The /Parser/ is the most fundamental concept. A Parser has a member 25function, `parse`, that accepts a first-last __fwditer__ pair and returns 26bool as its result. The iterators delimit the data being parsed. 27The Parser's `parse` member function returns `true` if the parse 28succeeds, in which case the first iterator is advanced accordingly. Each 29Parser can represent a specific pattern or algorithm, or it can be a 30more complex parser formed as a composition of other Parsers. 31 32[variablelist Notation 33 [[`p`] [A `Parser`.]] 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__.]] 41] 42 43[heading Valid Expressions] 44 45In the expressions below, the behavior of the parser, `p`, and how `skip` 46and `attrib` are handled by `p`, are left unspecified in the base `Parser` 47concept. These are specified in subsequent, more refined concepts and by 48the actual models thereof. 49 50For any Parser the following expressions must be valid: 51 52[table 53 [[Expression] [Semantics] [Return type]] 54 [[ 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__]] 61] 62 63[heading Type Expressions] 64 65[table 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__).]] 71] 72 73[heading Postcondition] 74 75Upon return from `p.parse` the following post conditions should hold: 76 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 83 matching `skip`. 84* On a failed match, `attrib` state is undefined. 85* No post-skips: trailing `skip` characters/tokens will not be skipped. 86 87[heading Models] 88 89All parsers in Spirit.Qi are models of the /Parser/ concept. 90 91[endsect] [/ Parser Concept] 92 93[/------------------------------------------------------------------------------] 94[section PrimitiveParser] 95 96[heading Description] 97 98/PrimitiveParser/ is the most basic building block that the client uses 99to build more complex parsers. 100 101[heading Refinement of] 102 103[:__parser_concept__] 104 105[heading Pre-skip] 106 107Upon entry to the `parse` member function, a PrimitiveParser is required 108to do a pre-skip. Leading `skip` characters/tokens will be skipped prior 109to parsing. Only PrimitiveParsers are required to perform this pre-skip. 110This is typically carried out through a call to `qi::skip_over`: 111 112 qi::skip_over(f, l, skip); 113 114[heading Type Expressions] 115 116[table 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__).]] 121] 122 123[heading Models] 124 125* __qi_attr__ 126* __qi_eoi__ 127* __qi_eol__ 128* __qi_eps__ 129* __qi_symbols__ 130 131[endsect] [/ PrimitiveParser Concept] 132 133[/------------------------------------------------------------------------------] 134[section UnaryParser] 135 136[heading Description] 137 138/UnaryParser/ is a composite parser that has a single subject. The 139UnaryParser may change the behavior of its subject following the 140__delegate_pattern__. 141 142[heading Refinement of] 143 144[:__parser_concept__] 145 146[variablelist Notation 147 [[`p`] [A UnaryParser.]] 148 [[`P`] [A UnaryParser type.]] 149] 150 151[heading Valid Expressions] 152 153In addition to the requirements defined in __parser_concept__, for any 154UnaryParser the following must be met: 155 156[table 157 [[Expression] [Semantics] [Return type]] 158 [[`p.subject`] [Subject parser.] [__parser_concept__]] 159] 160 161[heading Type Expressions] 162 163[table 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__).]] 169] 170 171[heading Invariants] 172 173For any UnaryParser, `P`, the following invariant always holds: 174 175* `traits::is_parser<P::subject_type>::type` evaluates to `mpl::true_` 176 177[heading Models] 178 179* __qi_and_predicate__ 180* __qi_kleene__ 181* __qi_lexeme__ 182* __qi_not_predicate__ 183* __qi_omit__ 184* __qi_plus__ 185* __qi_raw__ 186* [qi_repeat `repeat`] 187* __qi_skip__ 188 189[endsect] [/ UnaryParser Concept] 190 191[/------------------------------------------------------------------------------] 192[section BinaryParser] 193 194[heading Description] 195 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 198way as a single instance of a __parser_concept__ following the 199__composite_pattern__. 200 201[heading Refinement of] 202 203[:__parser_concept__] 204 205[variablelist Notation 206 [[`p`] [A BinaryParser.]] 207 [[`P`] [A BinaryParser type.]] 208] 209 210[heading Valid Expressions] 211 212In addition to the requirements defined in __parser_concept__, for any 213BinaryParser the following must be met: 214 215[table 216 [[Expression] [Semantics] [Return type]] 217 [[`p.left`] [Left parser.] [__parser_concept__]] 218 [[`p.right`] [Right parser.] [__parser_concept__]] 219] 220 221[heading Type Expressions] 222 223[table 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__).]] 230] 231 232[heading Invariants] 233 234For any BinaryParser, `P`, the following invariants always hold: 235 236* `traits::is_parser<P::left_type>::type` evaluates to `mpl::true_` 237* `traits::is_parser<P::right_type>::type` evaluates to `mpl::true_` 238 239[heading Models] 240 241* __qi_difference__ 242* __qi_list__ 243 244[endsect] [/ BinaryParser Concept] 245 246[/------------------------------------------------------------------------------] 247[section NaryParser] 248 249[heading Description] 250 251/NaryParser/ is a composite parser that has one or more subjects. The 252NaryParser allows its subjects to be treated in the same way as a single 253instance of a __parser_concept__ following the __composite_pattern__. 254 255[heading Refinement of] 256 257[:__parser_concept__] 258 259[variablelist Notation 260 [[`p`] [A NaryParser.]] 261 [[`P`] [A NaryParser type.]] 262] 263 264[heading Valid Expressions] 265 266In addition to the requirements defined in __parser_concept__, for any 267NaryParser the following must be met: 268 269[table 270 [[Expression] [Semantics] [Return type]] 271 [[`p.elements`] [The tuple of elements.] [A __fusion__ Sequence of __parser_concept__ types.]] 272] 273 274[heading Type Expressions] 275 276[table 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__).]] 282] 283 284[heading Invariants] 285 286For each element, `E`, in any NaryParser, `P`, the following invariant 287always holds: 288 289* `traits::is_parser<E>::type` evaluates to `mpl::true_` 290 291[heading Models] 292 293* __qi_alternative__ 294* __qi_expect__ 295* __qi_permutation__ 296* __qi_sequence__ 297* __qi_sequential_or__ 298 299[endsect] [/ NaryParser Concept] 300 301[/------------------------------------------------------------------------------] 302[section Nonterminal] 303 304[heading Description] 305 306A Nonterminal is a symbol in a __peg__ production that represents a 307grammar fragment. Nonterminals may self reference to specify recursion. 308This is one of the most important concepts and the reason behind the 309word "recursive" in recursive descent parsing. 310 311[heading Refinement of] 312 313[:__parser_concept__] 314 315[heading Signature] 316 317Nonterminals can have both synthesized and inherited attributes. The 318Nonterminal's /Signature/ specifies both the synthesized and inherited 319attributes. The specification uses the function declarator syntax: 320 321 RT(A0, A1, A2, ..., AN) 322 323where `RT` is the Nonterminal's synthesized attribute and `A0` ... `AN` 324are the Nonterminal's inherited attributes. 325 326The default value is `void()` (no synthesized and inherited attributes). 327 328[heading Attributes] 329 330The Nonterminal models a C++ function. The Nonterminal's synthesized 331attribute is analogous to the function return value and its inherited 332attributes are analogous to function arguments. The inherited attributes 333(arguments) can be passed in just like any __qi_lazy_argument__, e.g.: 334 335 r(expr) // Evaluate expr at parse time and pass the result to the Nonterminal r 336 337[heading `_val`] 338 339The `boost::spirit::qi::_val` placeholder can be used in __phoenix__ 340semantic actions anywhere in the Nonterminal's definition. This 341__phoenix__ placeholder refers to the Nonterminal's (synthesized) 342attribute. The `_val` placeholder acts like a mutable reference to the 343Nonterminal's attribute. 344 345[note Starting with __spirit__ V2.5 (distributed with Boost V1.47) the 346 placeholder `_val` can be used in semantic actions attached to top level 347 parser components as well. See __parse_api__ for more information.] 348 349[heading `_r1` ... `r10`] 350 351The `boost::spirit::_r1` ... `boost::spirit::r10` placeholders can be used 352in __phoenix__ semantic actions anywhere in the Nonterminal's 353definition. These __phoenix__ placeholders refer to the Nonterminal's 354inherited attributes. 355 356[heading Locals] 357 358Nonterminals can have local variables that will be created on the stack 359at parse time. A locals descriptor added to the Nonterminal declaration 360will give the Nonterminal local variables: 361 362 template <typename T0, typename T1, typename T2, ..., typename TN> 363 struct locals; 364 365where `T0` ... `TN` are the types of local variables accessible in your 366__phoenix__ semantic actions using the placeholders: 367 368* `boost::spirit::_a` 369* `boost::spirit::_b` 370* `boost::spirit::_c` 371* `boost::spirit::_d` 372* `boost::spirit::_e` 373* `boost::spirit::_f` 374* `boost::spirit::_g` 375* `boost::spirit::_h` 376* `boost::spirit::_i` 377* `boost::spirit::_j` 378 379which correspond to the Nonterminal's local variables `T0` ... `T9`. 380 381[variablelist Notation 382 [[`x`] [A Nonterminal]] 383 [[`X`] [A Nonterminal type]] 384 [[`arg1`, `arg2`, ..., `argN`] [__qi_lazy_arguments__ that evaluate to each of 385 the Nonterminal's inherited attributes.]] 386] 387 388[heading Valid Expressions] 389 390In addition to the requirements defined in __parser_concept__, for any 391Nonterminal the following must be met: 392 393[table 394 [[Expression] [Semantics] [Return type]] 395 [[`x`] [In a parser expression, invoke Nonterminal `x`] [`X`]] 396 [[`x(arg1, arg2, ..., argN)`][In a parser expression, invoke Nonterminal `r` 397 passing in inherited attributes 398 `arg1` ... `argN`] [`X`]] 399 [[`x.name(name)`] [Naming a Nonterminal.] [`void`]] 400 [[`x.name()`] [Getting the name of a Nonterminal.] [`std::string`]] 401 [[debug(x)] [Debug Nonterminal `x`.] [`void`]] 402] 403 404[heading Type Expressions] 405 406[table 407 [[Expression] [Description]] 408 [[`X::sig_type`] [The Signature of `X`: In a function signature form 409 as described above in the Signature paragraph.]] 410 [[`X::locals_type`] [The local variables of `X`: An __mpl_fwd_sequence__.]] 411] 412 413[heading Models] 414 415* __qi_rule__ 416* __qi_grammar__ 417 418[endsect] [/ Concept] 419 420 421 422[endsect] 423