290 lines
25 KiB
HTML
290 lines
25 KiB
HTML
<html>
|
|
<head>
|
|
<title>Subrules</title>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
|
|
<link rel="stylesheet" href="theme/style.css" type="text/css">
|
|
</head>
|
|
|
|
<body>
|
|
<table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
|
|
<tr>
|
|
<td width="10">
|
|
</td>
|
|
<td width="85%">
|
|
<font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Subrules</b></font>
|
|
</td>
|
|
<td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
<table border="0">
|
|
<tr>
|
|
<td width="10"></td>
|
|
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
|
|
<td width="30"><a href="grammar.html"><img src="theme/l_arr.gif" border="0"></a></td>
|
|
<td width="30"><a href="semantic_actions.html"><img src="theme/r_arr.gif" border="0"></a></td>
|
|
</tr>
|
|
</table>
|
|
<p>Spirit is implemented using expression templates. This is a very powerful technique.
|
|
Along with its power comes some complications. We almost take for granted that
|
|
when we write <tt>i | j >> k</tt> where <tt>i</tt>, <tt>j</tt> and <tt>k</tt>
|
|
are all integers the result is still an integer. Yet, with expression templates,
|
|
the same expression <tt>i | j >> k</tt> where <tt>i</tt>, <tt>j</tt> and
|
|
<tt>k</tt> are of type <tt>T</tt>, the result is a complex composite type [see
|
|
<a href="basic_concepts.html">Basic Concepts</a>]. Spirit expressions, which
|
|
are combinations of primitives and composites yield an infinite set of new types.
|
|
One problem is that C++ offers no easy facility to deduce the type of an arbitrarily
|
|
complex expression that yields a complex type. Thus, while it is easy to write:</p>
|
|
<pre><code><font color="#000000"><span class=identifier> </span><span class=keyword>int </span><span class=identifier>r </span><span class=special>= </span><span class=identifier>i </span><span class=special>| </span><span class=identifier>j </span><span class=special>>> </span><span class=identifier>k</span><span class=special>; </span><span class=comment>// where i, j, and k are ints</span></font></code></pre>
|
|
<p>Expression templates yield an endless supply of types. Without the <a href="rule.html">rule</a>,
|
|
there is no easy way to do this in C++ if <tt>i</tt>, <tt>j</tt> and <tt>k</tt>
|
|
are Spirit parsers:</p>
|
|
<pre><code><font color="#000000"><span class=comment> </span><span class=special><</span><span class=identifier>what_type???</span><span class=special>> </span><span class=identifier>r </span><span class=special>= </span><span class=identifier>i </span><span class=special>| </span><span class=identifier>j </span><span class=special>>> </span><span class=identifier>k</span><span class=special>; </span><span class=comment>// where i, j, and k are Spirit parsers</span></font></code></pre>
|
|
<p>If <tt>i</tt>, <tt>j</tt> and <tt>k</tt> are all <tt>chlit<></tt> objects,
|
|
the type that we want is:</p>
|
|
<pre><code><font color="#000000"><span class=comment> </span><span class=keyword>typedef
|
|
</span><span class=identifier>alternative</span><span class=special><
|
|
</span><span class=identifier>chlit</span><span class=special><></span><span class=comment> // i
|
|
</span><span class=special>,</span> <span class=identifier>sequence</span><span class=special><
|
|
</span><span class=identifier>chlit</span><span class=special><> </span><span class=comment>// j
|
|
</span><span class=special> ,</span><span class=comment> </span><span class=identifier>chlit</span><span class=special><> </span><span class=comment>// k
|
|
</span><span class=special>>
|
|
>
|
|
</span><span class=identifier>rule_t</span><span class=special>;
|
|
|
|
</span><span class=identifier>rule_t r </span><span class=special>= </span><span class=identifier>i </span><span class=special>| </span><span class=identifier>j </span><span class=special>>> </span><span class=identifier>k</span><span class=special>; </span><span class=comment>// where i, j, and k are chlit<> objects</span></font></code></pre>
|
|
<p>We deliberately formatted the type declaration nicely to make it understandable.
|
|
Try that with a more complex expression. While it can be done, explicitly spelling
|
|
out the type of a Spirit expression template is tedious and error prone. The
|
|
right hand side (rhs) has to mirror the type of the left hand side (lhs). (<img src="theme/lens.gif" width="15" height="16">
|
|
Yet, if you still wish to do it, see this <a href="techniques.html#no_rules">link</a>
|
|
for a technique). </p>
|
|
<table width="80%" border="0" align="center">
|
|
<tr>
|
|
<td class="note_box"><p><img src="theme/lens.gif" width="15" height="16"><b>
|
|
typeof and auto</b> <br>
|
|
<br>
|
|
Some compilers already support the <tt>typeof</tt> keyword. This can be
|
|
used to free us from having to explicitly type the type (pun intentional).
|
|
Using the <tt>typeof</tt>, we can rewrite the Spirit expression above
|
|
as:<br>
|
|
<br>
|
|
<span class="keyword"><code>typeof</code><code></code></span><code><span class=special>(</span><span class=identifier>i
|
|
</span><span class=special>| </span><span class=identifier>j </span><span class=special>>>
|
|
</span><span class=identifier>k</span><span class=special>) </span><span class=identifier>r
|
|
</span><span class=special>= </span><span class=identifier>i </span><span class=special>|
|
|
</span><span class=identifier>j </span><span class=special>>> </span><span class=identifier>k</span><span class=special>;</span></code><br>
|
|
<br>
|
|
While this is better than having to explicitly declare a complex type,
|
|
it is redundant, error prone and still an eye sore. The expression is
|
|
typed twice. The only way to simplify this is to introduce a macro (See
|
|
this <a href="techniques.html#typeof">link</a> for more information).<br>
|
|
<br>
|
|
<a href="http://www.boost-consulting.com">David Abrahams</a> proposed
|
|
in comp.std.c++ to reuse the <tt>auto</tt> keyword for type deduced variables.
|
|
This has been extensibly discussed in <a href="http://www.boost.org">boost.org</a>. Example:
|
|
<br>
|
|
<br>
|
|
<span class=keyword><code>auto </code></span><code><span class=identifier>r
|
|
</span><span class=special>= </span><span class=identifier>i </span><span class=special>|
|
|
</span><span class=identifier>j </span><span class=special>>> </span><span class=identifier>k</span><span class=special>;</span></code><br>
|
|
<br>
|
|
Once such a C++ extension is accepted into the standard, this would be
|
|
a neat solution and a nice fit for our purpose. It's not a complete solution
|
|
though since there are still situations where we do not know the rhs beforehand;
|
|
for instance when pre-declaring cyclic dependent rules.</p>
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
<p>Fortunately, rules come to the rescue. Rules can capture the type of the expression
|
|
assigned to it. Thus:</p>
|
|
<pre><code><font color="#000000"> <span class=identifier>rule</span><span class=special><> </span><span class=identifier>r </span><span class=special>= </span><span class=identifier>i </span><span class=special>| </span><span class=identifier>j </span><span class=special>>> </span><span class=identifier>k</span><span class=special>; </span><span class=comment>// where i, j, and k are chlit<> objects</span></font></code></pre>
|
|
<p>It might not be apparent but behind the scenes, plain rules are actually implemented
|
|
using a pointer to a runtime polymorphic abstract class that holds the dynamic
|
|
type of the parser assigned to it. When a Spirit expression is assigned to a
|
|
rule, its type is encapsulated in a concrete subclass of the abstract class.
|
|
A virtual parse function delegates the parsing to the encapsulated object.</p>
|
|
<p>Rules have drawbacks though:</p>
|
|
<p><img src="theme/bullet.gif" width="12" height="12"> It is coupled to a specific
|
|
scanner type. The rule is tied to a specific scanner [see <a href="faq.html#scanner_business">The
|
|
Scanner Business</a>].<br>
|
|
<img src="theme/bullet.gif" width="12" height="12"> The rule's parse member
|
|
function has a virtual function call overhead that cannot be inlined.</p>
|
|
<h2>Static rules: subrules</h2>
|
|
<p>The subrule is a fully static version of the rule. The subrule does not have
|
|
the drawbacks listed above. </p>
|
|
<p><img src="theme/bullet.gif" width="12" height="12"> The subrule is not tied
|
|
to a specific scanner so just about any scanner type may be used<br>
|
|
<img src="theme/bullet.gif" width="12" height="12"> The subrule also allows
|
|
aggressive inlining since there are no virtual function calls</p>
|
|
<pre><code><font color="#000000"><span class=identifier> </span><span class=keyword>template</span><span class=special><</span><span class=keyword>int </span></font><span class="identifier">ID</span><font color="#000000"><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ContextT </span><span class=special>= </span><span class=identifier>parser_context</span><span class=special><></span> <span class=special>>
|
|
</span><span class=keyword>class </span><span class=identifier>subrule</span><span class=special>;</span></font></code></pre>
|
|
<p>The first template parameter gives the subrule an identification tag. Like
|
|
the <a href="rule.html">rule</a>, there is a ContextT template parameter that
|
|
defaults to <code><tt>parser_context</tt></code>. You need not be concerned
|
|
at all with the <tt>ContextT</tt> template parameter unless you wish to tweak
|
|
the low level behavior of the subrule. Detailed information on the <tt>ContextT</tt>
|
|
template parameter is provided <a href="indepth_the_parser_context.html">elsewhere</a>.
|
|
</p>
|
|
<p>Presented above is the public API. There may actually be more template parameters
|
|
after <tt>ContextT</tt>. Everything after the <tt>ContextT</tt> parameter should
|
|
not be of concern to the client and are strictly for internal use only.</p>
|
|
<p>Apart from a few minor differences, the subrule follows the usage and syntax
|
|
of the rule closely. Here's the calculator grammar using subrules:</p>
|
|
<pre><code><font color="#000000"><span class=comment> </span><span class=keyword>struct </span><span class=identifier>calculator </span><span class=special>: </span><span class=keyword>public </span><span class=identifier>grammar</span><span class=special><</span><span class=identifier>calculator</span><span class=special>>
|
|
</span><span class=special>{
|
|
</span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>>
|
|
</span><span class=keyword>struct </span><span class=identifier>definition
|
|
</span><span class=special>{
|
|
</span><span class=identifier>definition</span><span class=special>(</span><span class=identifier>calculator </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>self</span><span class=special>)
|
|
</span><span class=special>{
|
|
</span><span class=identifier>first </span><span class=special>=
|
|
</span><span class=special>(
|
|
</span><span class=identifier>expression </span><span class=special>= </span><span class=identifier>term </span><span class=special>>> </span><span class=special>*((</span><span class=literal>'+' </span><span class=special>>> </span><span class=identifier>term</span><span class=special>) </span><span class=special>| </span><span class=special>(</span><span class=literal>'-' </span><span class=special>>> </span><span class=identifier>term</span><span class=special>)),
|
|
</span><span class=identifier>term </span><span class=special>= </span><span class=identifier>factor </span><span class=special>>> </span><span class=special>*((</span><span class=literal>'*' </span><span class=special>>> </span><span class=identifier>factor</span><span class=special>) </span><span class=special>| </span><span class=special>(</span><span class=literal>'/' </span><span class=special>>> </span><span class=identifier>factor</span><span class=special>)),
|
|
</span><span class=identifier>factor </span><span class=special>= </span><span class=identifier>integer </span><span class=special>| </span><span class=identifier>group</span><span class=special>,
|
|
</span><span class=identifier>group </span><span class=special>= </span><span class=literal>'(' </span><span class=special>>> </span><span class=identifier>expression </span><span class=special>>> </span><span class=literal>')'
|
|
</span><span class=special>);
|
|
</span><span class=special>}
|
|
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>0</span><span class=special>> </span><span class=identifier>expression</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>1</span><span class=special>> </span><span class=identifier>term</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>2</span><span class=special>> </span><span class=identifier>factor</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>3</span><span class=special>> </span><span class=identifier>group</span><span class=special>;
|
|
|
|
</span><span class=identifier>rule</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>> </span><span class=identifier>first</span><span class=special>;
|
|
</span><span class=identifier>rule</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>> </span><span class=keyword>const</span><span class=special>&
|
|
</span><span class=identifier>start</span><span class=special>() </span><span class=keyword>const </span><span class=special>{ </span><span class=keyword>return </span><span class=identifier>first</span><span class=special>; </span><span class=special>}
|
|
</span><span class=special>};
|
|
</span><span class=special>};</span></font></code></pre>
|
|
<p><img src="theme/lens.gif" width="15" height="16"> A fully working example with
|
|
<a href="semantic_actions.html">semantic actions</a> can be <a href="../example/fundamental/subrule_calc.cpp">viewed
|
|
here</a>. This is part of the Spirit distribution. </p>
|
|
<table border="0" align="left">
|
|
<tr>
|
|
<td width="199"><img src="theme/subrule1.png" width="234" height="224"></td>
|
|
<td width="2"></td>
|
|
</tr>
|
|
</table>
|
|
<p>The subrule as an efficient version of the rule. Compiler optimizations such
|
|
as aggressive inlining help reduce the code size and increase performance significantly.
|
|
</p>
|
|
<p>The subrule is not a panacea however. Subrules push the C++ compiler hard to
|
|
its knees. For example, current compilers have a limit on recursion depth that
|
|
may not be exceeded. Don't even think about writing a full pascal grammar using
|
|
subrules alone. A grammar using subrules is a single C++ expression. Current
|
|
C++ compilers cannot handle very complex expressions very well. Finally, a plain
|
|
rule is still needed to act as place holder for subrules.</p>
|
|
<p>The code above is a good example of the recommended way to use subrules. Notice
|
|
the hierarchy. We have a grammar that encapsulates the whole calculator. The
|
|
start rule is a plain rule that holds the set of subrules. The subrules in turn
|
|
defines the actual details of the grammar.</p>
|
|
<table width="80%" border="0" align="center">
|
|
<tr>
|
|
<td class="note_box"><img src="theme/lens.gif" width="15" height="16"><b>
|
|
Template instantiation depth</b> <br> <br>
|
|
Spirit pushes the C++ compiler hard. Current C++ compilers cannot handle
|
|
very complex heavily nested expressions very well. One restricting factor
|
|
is the typical compiler's limit on template recursion depth. Some, but not
|
|
all, compilers allow this limit to be configured.<br>
|
|
<br>
|
|
g++'s maximum can be set using a compiler flag: -ftemplate-depth. Set this
|
|
appropriately if you have a relatively complex grammar.<br>
|
|
<br>
|
|
Microsoft Visual C++ can take greater than 1000 for both template class
|
|
and function instantiation depths. However, the linker chokes with deep
|
|
template function instantiation unless inline recursion depth is set using
|
|
these pragmas:<br>
|
|
<br>
|
|
<span class="preprocessor">#pragma</span> inline_depth<span class="special">(</span>255<span class="special">)</span><br>
|
|
<span class="preprocessor">#pragma</span> inline_recursion<span class="special">(</span>on<span class="special">)<br>
|
|
<br>
|
|
</span>Perhaps this limitations no longer applies to more current versions
|
|
of these compilers. Be sure to check your compiler documentation.</td>
|
|
</tr>
|
|
</table>
|
|
<p>This setup gives a good balance. The subrules do all the work. Each grammar
|
|
will have only one rule: <tt>first</tt>. The rule is used just to hold the subrules
|
|
and make them visible to the grammar. </p>
|
|
<h3>The subrule definition</h3>
|
|
<p>Like the rule, the expression after assignment operator <tt>=</tt> defines
|
|
the subrule:</p>
|
|
<pre> <span class=identifier>identifier </span><span class=special>= </span><span class=identifier>expression</span></pre>
|
|
<p>Unlike rules, subrules may be defined only once. Redefining a subrule is illegal
|
|
and will result to a compile time assertion.</p>
|
|
<h3>Separators [ , ]</h3>
|
|
<p>While rules are terminated by the semicollon <tt>';'</tt>. Subrules are not
|
|
terminated but are separated by the comma: <tt>','</tt>. Like Pascal statements,
|
|
the last subrule in a group may not have a trailing comma.</p>
|
|
<pre><span class=identifier> </span><span class=identifier>a </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'a'</span><span class=special>),
|
|
</span><span class=identifier>b </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'b'</span><span class=special>),
|
|
</span><span class=identifier>c </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'c'</span><span class=special>), </span><span class=comment>// BAD, trailing comma</span><code><font color="#000000"><font color="#800000"><i></i></font></font></code><code><font color="#000000"><font color="#800000"><i></i></font></font><i></i></code></pre>
|
|
<p>
|
|
<pre><code><span class=comment> </span><span class=identifier>a </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'a'</span><span class=special>),
|
|
</span><span class=identifier>b </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'b'</span><span class=special>),
|
|
</span><span class=identifier>c </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'c'</span><span class=special>) </span><span class=comment>// OK</span></code></pre>
|
|
<h3> The start subrule</h3>
|
|
<p>Unlike rules, parsing proceeds from the start subrule. The first (topmost)
|
|
subrule in a group of subrules is called the <b>start subrule</b>. In our example
|
|
above, <tt>expression</tt> is the start subrule. When a group of subrules is
|
|
called forth, the start subrule <tt>expression</tt> is called first.</p>
|
|
<h3>IDs</h3>
|
|
<p>Each subrule has a corresponding ID; an integral constant that uniquely specifies
|
|
the subrule. Our example above has four subrules. They are declared as:</p>
|
|
<pre><code><span class=comment> </span><span class=identifier>subrule</span><span class=special><</span><span class=number>0</span><span class=special>> </span><span class=identifier>expression</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>1</span><span class=special>> </span><span class=identifier>term</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>2</span><span class=special>> </span><span class=identifier>factor</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>3</span><span class=special>> </span><span class=identifier>group</span><span class=special>;</span></code></pre>
|
|
<h3> Aliases</h3>
|
|
<p>It is possible to have subrules with similar IDs. A subrule with a similar
|
|
ID to will be an alias of the other. Both subrules may be used interchangeably.</p>
|
|
<pre><code><span class=special> </span><span class=identifier>subrule</span><span class=special><</span><span class=number>0</span><span class=special>> </span><span class=identifier>a</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>0</span><span class=special>> </span><span class=identifier>alias</span><span class=special>; </span><span class=comment>// alias of a</span></code></pre>
|
|
<h3>Groups: scope and nesting</h3>
|
|
<p>The scope of a subrule and its definition is the enclosing group, typically
|
|
(and by convention) enclosed inside the parentheses. IDs outside a scope are
|
|
not directly visible. Inner subrule groups can be nested by enclosing each sub-group
|
|
inside another set of parentheses. Each group is unique and acts independently.
|
|
Consequently, while it may not be advisable to do so, a subrule in a group may
|
|
share the same ID as a subrule in another group since both groups are independent
|
|
of each other.</p>
|
|
<pre><code><span class=comment> </span><span class=identifier>subrule</span><span class=special><</span><span class=number>0</span><span class=special>> </span><span class=identifier>a</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>1</span><span class=special>> </span><span class=identifier>b</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>0</span><span class=special>> </span><span class=identifier>c</span><span class=special>;
|
|
</span><span class=identifier>subrule</span><span class=special><</span><span class=number>1</span><span class=special>> </span><span class=identifier>d</span><span class=special>;
|
|
|
|
</span><span class=special>( </span><span class=comment>// outer subrule group, scope of a and b
|
|
</span><span class=identifier>a </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'a'</span><span class=special>),
|
|
</span><span class=identifier>b </span><span class=special>=
|
|
</span><span class=special>( </span><span class=comment>// inner subrule group, scope of b and c
|
|
</span><span class=identifier>c </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'c'</span><span class=special>),
|
|
</span><span class=identifier>d </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'d'</span><span class=special>)
|
|
</span><span class=special>)
|
|
</span><span class=special>)</span></code></pre>
|
|
<p>Subrule IDs need to be unique only within a group. A grammar is an implicit
|
|
group. Furthermore, even subrules in a grammar may have the same IDs without
|
|
clashing if they are inside a group. Subrules may be explicitly grouped using
|
|
the parentheses. Parenthesized groups have unique scopes. In the code above,
|
|
the outer subrule group defines the subrules <tt>a</tt> and <tt>b</tt> while
|
|
the inner subrule group defines the subrules <tt>c</tt> and <tt>d</tt>. Notice
|
|
that the definition of <tt>b</tt> is the inner subrule.</p>
|
|
<table border="0">
|
|
<tr>
|
|
<td width="10"></td>
|
|
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
|
|
<td width="30"><a href="grammar.html"><img src="theme/l_arr.gif" border="0"></a></td>
|
|
<td width="30"><a href="semantic_actions.html"><img src="theme/r_arr.gif" border="0"></a></td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
<hr size="1">
|
|
<p class="copyright">Copyright © 1998-2003 Joel de Guzman<br>
|
|
<br>
|
|
<font size="2">Use, modification and distribution is subject to 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)</font></p>
|
|
<p> </p>
|
|
<p><code><font color="#000000"><font color="#0000ff"></font></font></code></p>
|
|
</body>
|
|
</html>
|