ceph/src/boost/libs/spirit/repository/doc/qi/subrule.qbk

   1 [/==============================================================================
   2     Copyright (C) 2001-2011 Joel de Guzman
   3     Copyright (C) 2001-2011 Hartmut Kaiser
   4     Copyright (C) 2009 Francois Barel
   5
   6     Distributed under the Boost Software License, Version 1.0. (See accompanying
   7     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   8 ===============================================================================/]
   9
  10 [section:subrule Qi subrules]
  11
  12 [heading Description]
  13
  14 The __qi__ `subrule` is a component allowing to create a named parser, and
  15 to refer to it by name -- much like rules and grammars. It is in fact a fully
  16 static version of the rule.
  17
  18 The strength of subrules is performance. Replacing some rules with subrules
  19 can make a parser slightly faster (see
  20 [link spirit_repository.qi_components.nonterminal.subrule.performance Performance]
  21 below for measurements). The reason is that subrules allow aggressive inlining
  22 by the C++ compiler, whereas the implementation of rules is based on a virtual
  23 function call which, depending on the compiler, can have some run-time overhead
  24 and stop inlining.
  25
  26 The weaknesses of subrules are:
  27
  28 * subrules can only be defined and used within the same parser expression. A
  29   subrule cannot be defined at one location, and then used in another location.
  30 * subrules put a massive strain on the C++ compiler. They increase compile
  31   times and memory usage during compilation, and also increase the risk of
  32   hitting compiler limits and/or bugs.
  33
  34 [import ../../example/qi/calc1_sr.cpp]
  35
  36 [calc1_sr_def]
  37
  38 The example above can be found here: [@../../example/qi/calc1_sr.cpp]
  39
  40 As shown in this code snippet (an extract from the calc1_sr example),
  41 subrules can be freely mixed with rules and grammars. Here, a group of
  42 3 subrules (`expression`, `term`, `factor`) is assigned to a rule (named
  43 `entry`). This means that parts of a parser can use subrules (typically
  44 the innermost, most performance-critical parts), whereas the rest can use
  45 rules and grammars.
  46
  47 [heading Header]
  48
  49     // forwards to <boost/spirit/repository/home/qi/nonterminal/subrule.hpp>
  50     #include <boost/spirit/repository/include/qi_subrule.hpp>
  51
  52 [heading Synopsis (declaration)]
  53
  54     subrule<ID, A1, A2> sr(name);
  55
  56 [heading Parameters (declaration)]
  57
  58 [table
  59     [[Parameter]            [Description]]
  60     [[`ID`]                 [Required numeric argument. Gives the subrule
  61                              a unique 'identification tag'.]]
  62     [[`A1`, `A2`]           [Optional types, can be specified in any order.
  63                              Can be one of 1. signature, 2. locals
  64                              (see rules reference for more information on
  65                              those parameters).
  66
  67                              Note that the skipper type need not be specified
  68                              in the parameters, unlike with grammars and rules.
  69                              Subrules will automatically use the skipper type
  70                              which is in effect when they are invoked.]]
  71     [[`name`]               [Optional string. Gives the subrule a name,
  72                              useful for debugging and error handling.]]
  73 ]
  74
  75 [heading Synopsis (usage)]
  76
  77 Subrules are defined and used within groups, typically (and by convention)
  78 enclosed inside parentheses.
  79
  80     // Group containing N subrules
  81     (
  82         sr1 = expr1
  83       , sr2 = expr2
  84       , ... // Any number of subrules
  85     }
  86
  87 The IDs of all subrules defined within the same group must be different. It is
  88 an error to define several subrules with the same ID (or to define the same
  89 subrule multiple times) in the same group.
  90
  91     // Auto-subrules and inherited attributes
  92     (
  93         srA %= exprA >> srB >> srC(c1, c2, ...) // Arguments to subrule srC
  94       , srB %= exprB
  95       , srC  = exprC
  96       , ...
  97     )(a1, a2, ...)         // Arguments to group, i.e. to start subrule srA
  98
  99 [heading Parameters (usage)]
 100
 101 [table
 102     [[Parameter]            [Description]]
 103     [[`sr1`, `sr2`]         [Subrules with different IDs.]]
 104     [[`expr1`, `expr2`]     [Parser expressions. Can include `sr1` and `sr2`,
 105                              as well as any other valid parser expressions.]]
 106     [[`srA`]                [Subrule with a synthesized attribute and inherited
 107                              attributes.]]
 108     [[`srB`]                [Subrule with a synthesized attribute.]]
 109     [[`srC`]                [Subrule with inherited attributes.]]
 110     [[`exprA`, `exprB`, `exprC`]
 111                             [Parser expressions.]]
 112     [[`a1`, `a2`]           [Arguments passed to the subrule group. They are
 113                              passed as inherited attributes to the group's
 114                              start subrule, `srA`.]]
 115     [[`c1`, `c2`]           [Arguments passed as inherited attributes to
 116                              subrule `srC`.]]
 117 ]
 118
 119 [heading Groups]
 120
 121 A subrule group (a set of subrule definitions) is a parser, which can be
 122 used anywhere in a parser expression (in assignments to rules, as well as
 123 directly in arguments to functions such as `parse`).
 124 In a group, parsing proceeds from the start subrule, which is the first
 125 (topmost) subrule defined in that group. In the two groups in the synopsis
 126 above, `sr1` and `srA` are the start subrules respectively -- for example
 127 when the first subrule group is called forth, the `sr1` subrule is called.
 128
 129 A subrule can only be used in a group which defines it. Groups can be viewed
 130 as scopes: a definition of a subrule is limited to its enclosing group.
 131
 132     rule<char const*> r1, r2, r3;
 133     subrule<1> sr1;
 134     subrule<2> sr2;
 135
 136     r1 =
 137             ( sr1 = 'a' >> int_ )       // First group in r1.
 138         >>  ( sr2 = +sr1 )              // Second group in r1.
 139         //           ^^^
 140         // DOES NOT COMPILE: sr1 is not defined in this
 141         // second group, it cannot be used here (its
 142         // previous definition is out of scope).
 143     ;
 144
 145     r2 =
 146             ( sr1 = 'a' >> int_ )       // Only group in r2.
 147         >>  sr1
 148         //  ^^^
 149         // DOES NOT COMPILE: not in a subrule group,
 150         // sr1 cannot be used here (here too, its
 151         // previous definition is out of scope).
 152     ;
 153
 154     r3 =
 155             ( sr1 = 'x' >> double_ )    // Another group. The same subrule `sr1`
 156                                         // can have another, independent
 157                                         // definition in this group.
 158     ;
 159
 160 [heading Attributes]
 161
 162 A subrule has the same behavior as a rule with respect to attributes. In
 163 particular:
 164
 165 * the type of its synthesized attribute is the one specified in the
 166   subrule's signature, if any. Otherwise it is `unused_type`.
 167 * the types of its inherited attributes are the ones specified in the
 168   subrule's signature, if any. Otherwise the subrule has no inherited
 169   attributes.
 170 * an auto-subrule can be defined by assigning it with the `%=` syntax.
 171   In this case, the RHS parser's attribute is automatically propagated
 172   to the subrule's synthesized attribute.
 173 * the Phoenix placeholders `_val`, `_r1`, `_r2`, ... are available to
 174   refer to the subrule's synthesized and inherited attributes, if present.
 175
 176 [heading Locals]
 177
 178 A subrule has the same behavior as a rule with respect to locals. In
 179 particular, the Phoenix placeholders `_a`, `_b`, ... are available to
 180 refer to the subrule's locals, if present.
 181
 182 [heading Example]
 183
 184 [import ../../example/qi/mini_xml2_sr.cpp]
 185
 186 Some includes:
 187
 188 [mini_xml2_sr_includes]
 189
 190 Some using declarations:
 191
 192 [mini_xml2_sr_using]
 193
 194 A grammar containing only one rule, defined with a group of 5 subrules:
 195
 196 [mini_xml2_sr_grammar]
 197
 198 The definitions of the `mini_xml` and `mini_xml_node` data structures
 199 are not shown here. The full example above can be found here:
 200 [@../../example/qi/mini_xml2_sr.cpp]
 201
 202 [heading Performance]
 203
 204 This table compares run-time and compile-time performance when converting
 205 examples to subrules, with various compilers.
 206
 207 [table Subrules performance
 208
 209 [[Example] [Compiler]
 210     [Speed (run-time)] [Time (compile-time)] [Memory (compile-time)]]
 211
 212 [[calc1_sr]      [gcc 4.4.1]                  [ +6%] [ n/a] [ n/a]]
 213 [[calc1_sr]      [Visual C++ 2008 (VC9)]      [ +5%] [ n/a] [ n/a]]
 214 [[mini_xml2_sr]  [gcc 3.4.6]                  [ -1%] [+54%] [+32%]]
 215 [[mini_xml2_sr]  [gcc 4.1.2]                  [ +5%] [+58%] [+25%]]
 216 [[mini_xml2_sr]  [gcc 4.4.1]                  [ +8%] [+20%] [+14%]]
 217 [[mini_xml2_sr]  [Visual C++ 2005 (VC8) SP1]  [ +1%] [+33%] [+27%]]
 218 [[mini_xml2_sr]  [Visual C++ 2008 (VC9)]      [ +9%] [+52%] [+40%]]
 219
 220 ]
 221
 222 The columns are:
 223
 224 * *Speed (run-time)*: speed-up of the parser resulting from the use of
 225   subrules (higher is better).
 226 * *Time (compile-time)*: increase in compile time (lower is better).
 227 * *Memory (compile-time)*: increase in compiler memory usage (lower is better).
 228
 229 [heading Notes]
 230
 231 Subrules push the C++ compiler hard. A group of subrules is a single C++
 232 expression. Current C++ compilers cannot handle very complex expressions very
 233 well. One restricting factor is the typical compiler's limit on template
 234 recursion depth. Some, but not all, compilers allow this limit to be
 235 configured.
 236
 237 g++'s maximum can be set using a compiler flag: `-ftemplate-depth`. Set this
 238 appropriately if you use relatively complex subrules.
 239
 240 [endsect]