blob: 6cfae1f43b7aa2ae5bb9c669d27262235505c55b [file] [log] [blame]
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Repetition (repeat[])</title>
<link rel="stylesheet" href="../../../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.75.0">
<link rel="home" href="../../../../index.html" title="Spirit 2.4.1">
<link rel="up" href="../directive.html" title="Directive">
<link rel="prev" href="raw.html" title="Transduction Parsing (raw[])">
<link rel="next" href="matches.html" title="Test if Parser Succeeded (matches[])">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="raw.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../directive.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="matches.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h5 class="title">
<a name="spirit.qi.reference.directive.repeat"></a><a class="link" href="repeat.html" title="Repetition (repeat[])">Repetition
(<code class="computeroutput"><span class="identifier">repeat</span><span class="special">[]</span></code>)</a>
</h5></div></div></div>
<a name="spirit.qi.reference.directive.repeat.description"></a><h6>
<a name="id892172"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.description">Description</a>
</h6>
<p>
The <code class="computeroutput"><span class="identifier">repeat</span><span class="special">[]</span></code>
provides a more powerful and flexible mechanism for repeating a parser.
There are grammars that are impractical and cumbersome, if not impossible,
for the basic EBNF iteration syntax (<a class="link" href="../operator/kleene.html" title="Kleene (*a)">Kleene</a>
and the <a class="link" href="../operator/plus.html" title="Plus (+a)">Plus</a>)
to specify. Examples:
</p>
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
A file name may have a maximum of 255 characters only.
</li>
<li class="listitem">
A specific bitmap file format has exactly 4096 RGB color information.
</li>
<li class="listitem">
A 256 bit binary string (1..256 1s or 0s).
</li>
</ul></div>
<a name="spirit.qi.reference.directive.repeat.header"></a><h6>
<a name="id892235"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.header">Header</a>
</h6>
<pre class="programlisting"><span class="comment">// forwards to &lt;boost/spirit/home/qi/directive/repeat.hpp&gt;
</span><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">spirit</span><span class="special">/</span><span class="identifier">include</span><span class="special">/</span><span class="identifier">qi_repeat</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<p>
Also, see <a class="link" href="../../../structure/include.html" title="Include">Include Structure</a>.
</p>
<a name="spirit.qi.reference.directive.repeat.namespace"></a><h6>
<a name="id893538"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.namespace">Namespace</a>
</h6>
<div class="informaltable"><table class="table">
<colgroup><col></colgroup>
<thead><tr><th>
<p>
Name
</p>
</th></tr></thead>
<tbody>
<tr><td>
<p>
<code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">repeat</span> <span class="comment">//
alias: boost::spirit::qi::repeat</span></code>
</p>
</td></tr>
<tr><td>
<p>
<code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">inf</span> <span class="comment">// alias:
boost::spirit::qi::inf</span></code>
</p>
</td></tr>
</tbody>
</table></div>
<a name="spirit.qi.reference.directive.repeat.model_of"></a><h6>
<a name="id893655"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.model_of">Model of</a>
</h6>
<div class="blockquote"><blockquote class="blockquote"><p>
<a class="link" href="../parser_concepts/unaryparser.html" title="UnaryParser"><code class="computeroutput"><span class="identifier">UnaryParser</span></code></a>
</p></blockquote></div>
<div class="variablelist">
<p class="title"><b>Notation</b></p>
<dl>
<dt><span class="term"><code class="computeroutput"><span class="identifier">a</span></code></span></dt>
<dd><p>
A <a class="link" href="../parser_concepts/parser.html" title="Parser"><code class="computeroutput"><span class="identifier">Parser</span></code></a>.
</p></dd>
<dt><span class="term"><code class="computeroutput"><span class="identifier">n</span></code>, <code class="computeroutput"><span class="identifier">min</span></code>, <code class="computeroutput"><span class="identifier">max</span></code></span></dt>
<dd><p>
An <code class="computeroutput"><span class="keyword">int</span></code> anything that
can be converted to an <code class="computeroutput"><span class="keyword">int</span></code>,
or a <a class="link" href="../basics.html#spirit.qi.reference.basics.lazy_argument">Lazy
Argument</a> that evaluates to anything that can be converted
to an <code class="computeroutput"><span class="keyword">int</span></code>.
</p></dd>
</dl>
</div>
<a name="spirit.qi.reference.directive.repeat.expression_semantics"></a><h6>
<a name="id893784"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.expression_semantics">Expression
Semantics</a>
</h6>
<p>
Semantics of an expression is defined only where it differs from, or
is not defined in <a class="link" href="../parser_concepts/unaryparser.html" title="UnaryParser"><code class="computeroutput"><span class="identifier">UnaryParser</span></code></a>.
</p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<thead><tr>
<th>
<p>
Expression
</p>
</th>
<th>
<p>
Semantics
</p>
</th>
</tr></thead>
<tbody>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
Repeat <code class="computeroutput"><span class="identifier">a</span></code> zero
or more times. Same as <a class="link" href="../operator/kleene.html" title="Kleene (*a)">Kleene</a>.
</p>
</td>
</tr>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">(</span><span class="identifier">n</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
Repeat <code class="computeroutput"><span class="identifier">a</span></code> exactly
<code class="computeroutput"><span class="identifier">n</span></code> times.
</p>
</td>
</tr>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span>
<span class="identifier">max</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
Repeat <code class="computeroutput"><span class="identifier">a</span></code> at
least <code class="computeroutput"><span class="identifier">min</span></code> times
and at most <code class="computeroutput"><span class="identifier">max</span></code>
times.
</p>
</td>
</tr>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span>
<span class="identifier">inf</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
Repeat <code class="computeroutput"><span class="identifier">a</span></code> at
least <code class="computeroutput"><span class="identifier">min</span></code> or
more (continuing until <code class="computeroutput"><span class="identifier">a</span></code>
fails or the input is consumed).
</p>
</td>
</tr>
</tbody>
</table></div>
<a name="spirit.qi.reference.directive.repeat.attributes"></a><h6>
<a name="id894100"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.attributes">Attributes</a>
</h6>
<p>
See <a class="link" href="../../quick_reference/compound_attribute_rules.html#spirit.qi.quick_reference.compound_attribute_rules.notation">Compound
Attribute Notation</a>.
</p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<thead><tr>
<th>
<p>
Expression
</p>
</th>
<th>
<p>
Attribute
</p>
</th>
</tr></thead>
<tbody>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
</p>
<pre xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="table-programlisting"><span class="identifier">a</span><span class="special">:</span> <span class="identifier">A</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">&gt;</span>
<span class="identifier">a</span><span class="special">:</span> <span class="identifier">Unused</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">Unused</span></pre>
<p>
</p>
</td>
</tr>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">(</span><span class="identifier">n</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
</p>
<pre xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="table-programlisting"><span class="identifier">a</span><span class="special">:</span> <span class="identifier">A</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">(</span><span class="identifier">n</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">&gt;</span>
<span class="identifier">a</span><span class="special">:</span> <span class="identifier">Unused</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">(</span><span class="identifier">n</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">Unused</span></pre>
<p>
</p>
</td>
</tr>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span>
<span class="identifier">max</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
</p>
<pre xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="table-programlisting"><span class="identifier">a</span><span class="special">:</span> <span class="identifier">A</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span> <span class="identifier">max</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">&gt;</span>
<span class="identifier">a</span><span class="special">:</span> <span class="identifier">Unused</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span> <span class="identifier">max</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">Unused</span></pre>
<p>
</p>
</td>
</tr>
<tr>
<td>
<p>
<code class="computeroutput"><span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span>
<span class="identifier">inf</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]</span></code>
</p>
</td>
<td>
<p>
</p>
<pre xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class="table-programlisting"><span class="identifier">a</span><span class="special">:</span> <span class="identifier">A</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span> <span class="identifier">inf</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">&gt;</span>
<span class="identifier">a</span><span class="special">:</span> <span class="identifier">Unused</span> <span class="special">--&gt;</span> <span class="identifier">repeat</span><span class="special">(</span><span class="identifier">min</span><span class="special">,</span> <span class="identifier">inf</span><span class="special">)[</span><span class="identifier">a</span><span class="special">]:</span> <span class="identifier">Unused</span></pre>
<p>
</p>
</td>
</tr>
</tbody>
</table></div>
<a name="spirit.qi.reference.directive.repeat.complexity"></a><h6>
<a name="id894778"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.complexity">Complexity</a>
</h6>
<div class="blockquote"><blockquote class="blockquote"><p>
The overall complexity is defined by the complexity of its subject
parser. The complexity of <code class="computeroutput"><span class="identifier">repeat</span></code>
itself is O(N), where N is the number of repetitions to execute.
</p></blockquote></div>
<a name="spirit.qi.reference.directive.repeat.example"></a><h6>
<a name="id894806"></a>
<a class="link" href="repeat.html#spirit.qi.reference.directive.repeat.example">Example</a>
</h6>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p>
The test harness for the example(s) below is presented in the <a class="link" href="../basics.html#spirit.qi.reference.basics.examples">Basics Examples</a>
section.
</p></td></tr>
</table></div>
<p>
Using the repeat directive, we can now write our examples above.
</p>
<p>
Some using declarations:
</p>
<p>
</p>
<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">qi</span><span class="special">::</span><span class="identifier">repeat</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">qi</span><span class="special">::</span><span class="identifier">lit</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">qi</span><span class="special">::</span><span class="identifier">uint_parser</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">qi</span><span class="special">::</span><span class="identifier">_1</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">ascii</span><span class="special">::</span><span class="identifier">char_</span><span class="special">;</span>
<span class="keyword">namespace</span> <span class="identifier">phx</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">phoenix</span><span class="special">;</span>
</pre>
<p>
</p>
<p>
A parser for a file name with a maximum of 255 characters:
</p>
<p>
</p>
<pre class="programlisting"><span class="identifier">test_parser</span><span class="special">(</span><span class="string">"batman.jpeg"</span><span class="special">,</span> <span class="identifier">repeat</span><span class="special">(</span><span class="number">1</span><span class="special">,</span> <span class="number">255</span><span class="special">)[</span><span class="identifier">char_</span><span class="special">(</span><span class="string">"a-zA-Z_./"</span><span class="special">)]);</span></pre>
<p>
</p>
<p>
A parser for a specific bitmap file format which has exactly 4096 RGB
color information. (for the purpose of this example, we will be testing
only 3 RGB color information.)
</p>
<p>
</p>
<pre class="programlisting"><span class="identifier">uint_parser</span><span class="special">&lt;</span><span class="keyword">unsigned</span><span class="special">,</span> <span class="number">16</span><span class="special">,</span> <span class="number">6</span><span class="special">,</span> <span class="number">6</span><span class="special">&gt;</span> <span class="identifier">rgb</span><span class="special">;</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="keyword">unsigned</span><span class="special">&gt;</span> <span class="identifier">colors</span><span class="special">;</span>
<span class="identifier">test_parser_attr</span><span class="special">(</span><span class="string">"ffffff0000003f3f3f"</span><span class="special">,</span> <span class="identifier">repeat</span><span class="special">(</span><span class="number">3</span><span class="special">)[</span><span class="identifier">rgb</span><span class="special">],</span> <span class="identifier">colors</span><span class="special">);</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span>
<span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">hex</span>
<span class="special">&lt;&lt;</span> <span class="identifier">colors</span><span class="special">[</span><span class="number">0</span><span class="special">]</span> <span class="special">&lt;&lt;</span> <span class="char">','</span>
<span class="special">&lt;&lt;</span> <span class="identifier">colors</span><span class="special">[</span><span class="number">1</span><span class="special">]</span> <span class="special">&lt;&lt;</span> <span class="char">','</span>
<span class="special">&lt;&lt;</span> <span class="identifier">colors</span><span class="special">[</span><span class="number">2</span><span class="special">]</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span></pre>
<p>
</p>
<p>
A 256 bit binary string (1..256 1s or 0s). (For the purpose of this example,
we will be testing only 16 bits.)
</p>
<p>
</p>
<pre class="programlisting"><span class="identifier">test_parser</span><span class="special">(</span><span class="string">"1011101011110010"</span><span class="special">,</span> <span class="identifier">repeat</span><span class="special">(</span><span class="number">16</span><span class="special">)[</span><span class="identifier">lit</span><span class="special">(</span><span class="char">'1'</span><span class="special">)</span> <span class="special">|</span> <span class="char">'0'</span><span class="special">]);</span>
</pre>
<p>
</p>
<p>
The Loop parsers can be dynamic. Consider the parsing of a binary file
of Pascal-style length prefixed string, where the first byte determines
the length of the incoming string. Here's a sample input:
</p>
<div class="blockquote"><blockquote class="blockquote"><p>
<span class="inlinemediaobject"><img src="../../../.././images/pascal_string.png" alt="pascal_string"></span>
</p></blockquote></div>
<p>
This trivial example cannot be practically defined in traditional EBNF.
Although some EBNF variants allow more powerful repetition constructs
other than the Kleene Star, we are still limited to parsing fixed strings.
The nature of EBNF forces the repetition factor to be a constant. On
the other hand, Spirit allows the repetition factor to be variable at
run time. We could write a grammar that accepts the input string above.
Example using phoenix:
</p>
<p>
</p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">str</span><span class="special">;</span>
<span class="keyword">int</span> <span class="identifier">n</span><span class="special">;</span>
<span class="identifier">test_parser_attr</span><span class="special">(</span><span class="string">"\x0bHello World"</span><span class="special">,</span>
<span class="identifier">char_</span><span class="special">[</span><span class="identifier">phx</span><span class="special">::</span><span class="identifier">ref</span><span class="special">(</span><span class="identifier">n</span><span class="special">)</span> <span class="special">=</span> <span class="identifier">_1</span><span class="special">]</span> <span class="special">&gt;&gt;</span> <span class="identifier">repeat</span><span class="special">(</span><span class="identifier">phx</span><span class="special">::</span><span class="identifier">ref</span><span class="special">(</span><span class="identifier">n</span><span class="special">))[</span><span class="identifier">char_</span><span class="special">],</span> <span class="identifier">str</span><span class="special">);</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">n</span> <span class="special">&lt;&lt;</span> <span class="char">','</span> <span class="special">&lt;&lt;</span> <span class="identifier">str</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span> <span class="comment">// will print "11,Hello World"
</span></pre>
<p>
</p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright &#169; 2001-2010 Joel de Guzman, Hartmut Kaiser<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="raw.html"><img src="../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../directive.html"><img src="../../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../../index.html"><img src="../../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="matches.html"><img src="../../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>