1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>User manual</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../metaparse.html" title="Chapter 24. Boost.Metaparse"> 10<link rel="prev" href="getting_started_with_boost_metap.html" title="Getting started with Boost.Metaparse"> 11<link rel="next" href="versioning.html" title="Versioning"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="getting_started_with_boost_metap.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../metaparse.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="versioning.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="metaparse.user_manual"></a><a name="manual"></a><a class="link" href="user_manual.html" title="User manual">User manual</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser">What is a parser</a></span></dt> 32<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.parsing_based_on_constexpr">Parsing 33 based on <code class="computeroutput"><span class="keyword">constexpr</span></code></a></span></dt> 34<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_types_of_grammars_can_be_us">What 35 types of grammars can be used?</a></span></dt> 36</dl></div> 37<div class="section"> 38<div class="titlepage"><div><div><h3 class="title"> 39<a name="metaparse.user_manual.what_is_a_parser"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser" title="What is a parser">What is a parser</a> 40</h3></div></div></div> 41<div class="toc"><dl class="toc"> 42<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.the_input_of_the_parsers">The 43 input of the parsers</a></span></dt> 44<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.source_positions">Source 45 positions</a></span></dt> 46<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.error_handling">Error 47 handling</a></span></dt> 48<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.some_examples_of_simple_parsers">Some 49 examples of simple parsers</a></span></dt> 50<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.combining_parsers">Combining 51 parsers</a></span></dt> 52<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.sequence">Sequence</a></span></dt> 53<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition">Repetition</a></span></dt> 54<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.what_can_be_built_from_a_compile">What 55 can be built from a compile-time string?</a></span></dt> 56<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.grammars">Grammars</a></span></dt> 57</dl></div> 58<p> 59 See the <a class="link" href="reference.html#parser">parser</a> section of the <a class="link" href="reference.html#reference">reference</a> 60 for the explanation of what a parser is. 61 </p> 62<div class="section"> 63<div class="titlepage"><div><div><h4 class="title"> 64<a name="metaparse.user_manual.what_is_a_parser.the_input_of_the_parsers"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.the_input_of_the_parsers" title="The input of the parsers">The 65 input of the parsers</a> 66</h4></div></div></div> 67<p> 68 Parsers take a <a class="link" href="reference.html#string"><code class="computeroutput"><span class="identifier">string</span></code></a> 69 as input, which represents a string for template metaprograms. For example 70 the string <code class="computeroutput"><span class="string">"Hello World!"</span></code> 71 can be defined the following way: 72 </p> 73<pre class="programlisting"><span class="identifier">string</span><span class="special"><</span><span class="char">'H'</span><span class="special">,</span><span class="char">'e'</span><span class="special">,</span><span class="char">'l'</span><span class="special">,</span><span class="char">'l'</span><span class="special">,</span><span class="char">'o'</span><span class="special">,</span><span class="char">' '</span><span class="special">,</span><span class="char">'W'</span><span class="special">,</span><span class="char">'o'</span><span class="special">,</span><span class="char">'r'</span><span class="special">,</span><span class="char">'l'</span><span class="special">,</span><span class="char">'d'</span><span class="special">,</span><span class="char">'!'</span><span class="special">></span> 74</pre> 75<p> 76 This syntax makes the input of the parsers difficult to read. Metaparse 77 works with compilers using C++98, but the input of the parsers has to be 78 defined the way it is described above. 79 </p> 80<p> 81 Based on <code class="computeroutput"><span class="keyword">constexpr</span></code>, a feature 82 provided by C++11, Metaparse provides a macro, <a class="link" href="reference.html#BOOST_METAPARSE_STRING"><code class="computeroutput"><span class="identifier">BOOST_METAPARSE_STRING</span></code></a> for defining 83 strings: 84 </p> 85<pre class="programlisting"><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"Hello World!"</span><span class="special">)</span> 86</pre> 87<p> 88 This defines a <a class="link" href="reference.html#string"><code class="computeroutput"><span class="identifier">string</span></code></a> 89 as well, however, it is easier to read. The maximum length of the string 90 that can be defined this way is limited, however, this limit is configurable. 91 It is specified by the <code class="computeroutput"><span class="identifier">BOOST_METAPARSE_LIMIT_STRING_SIZE</span></code> 92 macro. 93 </p> 94</div> 95<div class="section"> 96<div class="titlepage"><div><div><h4 class="title"> 97<a name="metaparse.user_manual.what_is_a_parser.source_positions"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.source_positions" title="Source positions">Source 98 positions</a> 99</h4></div></div></div> 100<p> 101 A source position is described using a compile-time data structure. The 102 following functions can be used to query it: 103 </p> 104<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 105<li class="listitem"> 106 <a class="link" href="reference.html#get_col"><code class="computeroutput"><span class="identifier">get_col</span></code></a> 107 </li> 108<li class="listitem"> 109 <a class="link" href="reference.html#get_line"><code class="computeroutput"><span class="identifier">get_line</span></code></a> 110 </li> 111</ul></div> 112<p> 113 The beginning of the input is <a class="link" href="reference.html#start"><code class="computeroutput"><span class="identifier">start</span></code></a> 114 which requires <code class="computeroutput"><span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">metaparse</span><span class="special">/</span><span class="identifier">start</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code> to be included. 115 </p> 116</div> 117<div class="section"> 118<div class="titlepage"><div><div><h4 class="title"> 119<a name="metaparse.user_manual.what_is_a_parser.error_handling"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.error_handling" title="Error handling">Error 120 handling</a> 121</h4></div></div></div> 122<p> 123 An error is described using a compile-time data structure. It contains 124 information about the source position where the error was detected and 125 some <a class="link" href="reference.html#parsing_error_message">description</a> about the 126 error. <a class="link" href="reference.html#debug_parsing_error"><code class="computeroutput"><span class="identifier">debug_parsing_error</span></code></a> 127 can be used to display the error message. Metaparse provides the <a class="link" href="reference.html#BOOST_METAPARSE_DEFINE_ERROR"><code class="computeroutput"><span class="identifier">BOOST_METAPARSE_DEFINE_ERROR</span></code></a> 128 macro for defining simple <a class="link" href="reference.html#parsing_error_message">parsing 129 error message</a>s. 130 </p> 131</div> 132<div class="section"> 133<div class="titlepage"><div><div><h4 class="title"> 134<a name="metaparse.user_manual.what_is_a_parser.some_examples_of_simple_parsers"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.some_examples_of_simple_parsers" title="Some examples of simple parsers">Some 135 examples of simple parsers</a> 136</h4></div></div></div> 137<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 138<li class="listitem"> 139 A parser that parses nothing and always succeeds is <a class="link" href="reference.html#return_"><code class="computeroutput"><span class="identifier">return_</span></code></a>. 140 </li> 141<li class="listitem"> 142 A parser that always fails is <a class="link" href="reference.html#fail"><code class="computeroutput"><span class="identifier">fail</span></code></a>. 143 </li> 144<li class="listitem"> 145 A parser that parses one character and returns the parsed character 146 as the result is <a class="link" href="reference.html#one_char"><code class="computeroutput"><span class="identifier">one_char</span></code></a>. 147 </li> 148</ul></div> 149</div> 150<div class="section"> 151<div class="titlepage"><div><div><h4 class="title"> 152<a name="metaparse.user_manual.what_is_a_parser.combining_parsers"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.combining_parsers" title="Combining parsers">Combining 153 parsers</a> 154</h4></div></div></div> 155<p> 156 Complex parsers can be built by combining simple parsers. The parser library 157 contains a number of parser combinators that build new parsers from already 158 existing ones. 159 </p> 160<p> 161 For example <a class="link" href="reference.html#accept_when"><code class="computeroutput"><span class="identifier">accept_when</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">Parser</span><span class="special">,</span> <span class="identifier">Predicate</span><span class="special">,</span> <span class="identifier">RejectErrorMsg</span><span class="special">></span></code> is a parser. It uses <code class="computeroutput"><span class="identifier">Parser</span></code> to parse the input. When <code class="computeroutput"><span class="identifier">Parser</span></code> rejects the input, the combinator 162 returns the error <code class="computeroutput"><span class="identifier">Parser</span></code> 163 failed with. When <code class="computeroutput"><span class="identifier">Parser</span></code> 164 is successful, the combinator validates the result using <code class="computeroutput"><span class="identifier">Predicate</span></code>. If the predicate returns true, 165 the combinator accepts the input, otherwise it generates an error with 166 the message <code class="computeroutput"><span class="identifier">RejectErrorMsg</span></code>. 167 </p> 168<p> 169 Having <a class="link" href="reference.html#accept_when"><code class="computeroutput"><span class="identifier">accept_when</span></code></a>, 170 <a class="link" href="reference.html#one_char"><code class="computeroutput"><span class="identifier">one_char</span></code></a> 171 can be used to build parsers that accept only digit characters, only whitespaces, 172 etc. For example <a class="link" href="reference.html#digit"><code class="computeroutput"><span class="identifier">digit</span></code></a> 173 accepts only digit characters: 174 </p> 175<pre class="programlisting"><span class="keyword">typedef</span> 176 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">metaparse</span><span class="special">::</span><span class="identifier">accept_when</span><span class="special"><</span> 177 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">metaparse</span><span class="special">::</span><span class="identifier">one_char</span><span class="special">,</span> 178 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">metaparse</span><span class="special">::</span><span class="identifier">util</span><span class="special">::</span><span class="identifier">is_digit</span><span class="special">,</span> 179 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">metaparse</span><span class="special">::</span><span class="identifier">errors</span><span class="special">::</span><span class="identifier">digit_expected</span> 180 <span class="special">></span> 181 <span class="identifier">digit</span><span class="special">;</span> 182</pre> 183</div> 184<div class="section"> 185<div class="titlepage"><div><div><h4 class="title"> 186<a name="metaparse.user_manual.what_is_a_parser.sequence"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.sequence" title="Sequence">Sequence</a> 187</h4></div></div></div> 188<p> 189 The result of a successful parsing is some value and the remaining string 190 that was not parsed. The remaining string can be processed by another parser. 191 The parser library provides a parser combinator, <a class="link" href="reference.html#sequence"><code class="computeroutput"><span class="identifier">sequence</span></code></a>, that takes a number 192 of parsers as arguments and builds a new parser from them that: 193 </p> 194<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 195<li class="listitem"> 196 Parses the input using the first parser 197 </li> 198<li class="listitem"> 199 If parsing succeeds, it parses the remaining string with the second 200 parser 201 </li> 202<li class="listitem"> 203 It continues applying the parsers in order as long as they succeed 204 </li> 205<li class="listitem"> 206 If all of them succeed, it returns the list of results 207 </li> 208<li class="listitem"> 209 If any of the parsers fails, the combinator fails as well and returns 210 the error the first failing parser returned with 211 </li> 212</ul></div> 213</div> 214<div class="section"> 215<div class="titlepage"><div><div><h4 class="title"> 216<a name="metaparse.user_manual.what_is_a_parser.repetition"></a><a name="repetition"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition" title="Repetition">Repetition</a> 217</h4></div></div></div> 218<div class="toc"><dl class="toc"> 219<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl">Introducing 220 foldl</a></span></dt> 221<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldr">Introducing 222 foldr</a></span></dt> 223<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl_start_with_par">Introducing 224 foldl_start_with_parser</a></span></dt> 225<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldr_start_with_par">Introducing 226 foldr_start_with_parser</a></span></dt> 227<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl_reject_incompl">Introducing 228 foldl_reject_incomplete_start_with_parser</a></span></dt> 229<dt><span class="section"><a href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.finding_the_right_folding_parser">Finding 230 the right folding parser combinator</a></span></dt> 231</dl></div> 232<p> 233 It is a common thing to parse a list of things of unknown length. As an 234 example let's start with something simple: the text is a list of numbers. 235 For example: 236 </p> 237<pre class="programlisting"><span class="number">11</span> <span class="number">13</span> <span class="number">3</span> <span class="number">21</span> 238</pre> 239<p> 240 We want the result of parsing to be the sum of these values. Metaparse 241 provides the <a class="link" href="reference.html#int_"><code class="computeroutput"><span class="identifier">int_</span></code></a> 242 parser we can use to parse one of these numbers. Metaparse provides the 243 <a class="link" href="reference.html#token"><code class="computeroutput"><span class="identifier">token</span></code></a> 244 combinator to consume the whitespaces after the number. So the following 245 parser parses one number and the whitespaces after it: 246 </p> 247<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">int_token</span> <span class="special">=</span> <span class="identifier">token</span><span class="special"><</span><span class="identifier">int_</span><span class="special">>;</span> 248</pre> 249<p> 250 The result of parsing is a boxed integer value: the value of the parsed 251 number. For example parsing <a class="link" href="reference.html#BOOST_METAPARSE_STRING"><code class="computeroutput"><span class="identifier">BOOST_METAPARSE_STRING</span></code></a><code class="computeroutput"><span class="special">(</span><span class="string">"13 "</span><span class="special">)</span></code> gives <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">int_</span><span class="special"><</span><span class="number">13</span><span class="special">></span></code> 252 as the result. 253 </p> 254<p> 255 Our example input is a list of numbers. Each number can be parsed by <code class="computeroutput"><span class="identifier">int_token</span></code>: 256 </p> 257<p> 258 <span class="inlinemediaobject"><img src="../images/metaparse/repeated_diag0.png" width="70%"></span> 259 </p> 260<p> 261 This diagram shows how the repeated application of <code class="computeroutput"><span class="identifier">int_token</span></code> 262 can parse the example input. Metaparse provides the <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a> parser to easily implement 263 this. The result of parsing is a typelist: the list of the individual numbers. 264 </p> 265<p> 266 <span class="inlinemediaobject"><img src="../images/metaparse/repeated_diag1.png" width="70%"></span> 267 </p> 268<p> 269 This diagram shows how <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">></span></code> works. It uses the <code class="computeroutput"><span class="identifier">int_token</span></code> 270 parser repeatedly and builds a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">vector</span></code> 271 from the results it provides. 272 </p> 273<p> 274 But we need the sum of these, so we need to summarise the result. We can 275 do this by wrapping our parser, <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">></span></code> 276 with <a class="link" href="reference.html#transform"><code class="computeroutput"><span class="identifier">transform</span></code></a>. 277 That gives us the opportunity to specify a function transforming this typelist 278 to some other value - the sum of the elements in our case. Initially let's 279 ignore how to summarise the elements in the vector. Let's assume that it 280 can be implemented by a lambda expression and use <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">lambda</span><span class="special"><...>::</span><span class="identifier">type</span></code> 281 representing that lambda expression. Here is an example using <a class="link" href="reference.html#transform"><code class="computeroutput"><span class="identifier">transform</span></code></a> and this lambda expression: 282 </p> 283<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">sum_parser</span> <span class="special">=</span> 284 <span class="identifier">transform</span><span class="special"><</span> 285 <span class="identifier">repeated</span><span class="special"><</span><span class="identifier">int_token</span><span class="special">>,</span> 286 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">lambda</span><span class="special"><...>::</span><span class="identifier">type</span> 287 <span class="special">>;</span> 288</pre> 289<p> 290 The <a class="link" href="reference.html#transform"><code class="computeroutput"><span class="identifier">transform</span></code></a><code class="computeroutput"><span class="special"><></span></code> parser combinator wraps the <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">></span></code> to build the parser we need. Here is 291 a diagram showing how it works: 292 </p> 293<p> 294 <span class="inlinemediaobject"><img src="../images/metaparse/repeated_diag2.png" width="70%"></span> 295 </p> 296<p> 297 As the diagram shows, the <a class="link" href="reference.html#transform"><code class="computeroutput"><span class="identifier">transform</span></code></a><code class="computeroutput"><span class="special"><</span></code><a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">>,</span> 298 <span class="special">...></span></code> parser parses the input 299 using <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">></span></code> and then does some processing on the 300 result of parsing. 301 </p> 302<p> 303 Let's implement the missing lambda expression that tells <a class="link" href="reference.html#transform"><code class="computeroutput"><span class="identifier">transform</span></code></a> how to change the result 304 coming from <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">></span></code>. We can summarise the numbers in a 305 typelist by using Boost.MPL's <code class="computeroutput"><span class="identifier">fold</span></code> 306 or <code class="computeroutput"><span class="identifier">accumulate</span></code>. Here is 307 an example doing that: 308 </p> 309<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">sum_op</span> <span class="special">=</span> <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">lambda</span><span class="special"><</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">plus</span><span class="special"><</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">_1</span><span class="special">,</span> <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">_2</span><span class="special">>>::</span><span class="identifier">type</span><span class="special">;</span> 310 311<span class="keyword">using</span> <span class="identifier">sum_parser</span> <span class="special">=</span> 312 <span class="identifier">transform</span><span class="special"><</span> 313 <span class="identifier">repeated</span><span class="special"><</span><span class="identifier">int_token</span><span class="special">>,</span> 314 <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">lambda</span><span class="special"><</span> 315 <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">fold</span><span class="special"><</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">_1</span><span class="special">,</span> <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">int_</span><span class="special"><</span><span class="number">0</span><span class="special">>,</span> <span class="identifier">sum_op</span><span class="special">></span> 316 <span class="special">>::</span><span class="identifier">type</span> 317 <span class="special">>;</span> 318</pre> 319<p> 320 Here is an extended version of the above diagram showing what happens here: 321 </p> 322<p> 323 <span class="inlinemediaobject"><img src="../images/metaparse/repeated_diag3.png" width="70%"></span> 324 </p> 325<p> 326 This example parses the input, builds the list of numbers and then loops 327 over it and summarises the values. It starts with the second argument of 328 <code class="computeroutput"><span class="identifier">fold</span></code>, <code class="computeroutput"><span class="identifier">int_</span><span class="special"><</span><span class="number">0</span><span class="special">></span></code> 329 and adds every item of the list of numbers (which is the result of the 330 parser <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">></span></code>) one by one. 331 </p> 332<div class="note"><table border="0" summary="Note"> 333<tr> 334<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 335<th align="left">Note</th> 336</tr> 337<tr><td align="left" valign="top"><p> 338 Note that <a class="link" href="reference.html#transform"><code class="computeroutput"><span class="identifier">transform</span></code></a> 339 wraps another parser, <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">int_token</span><span class="special">></span></code> here. It parses the input with that 340 parser, gets the result of that parsing and changes that result. <a class="link" href="reference.html#transform"><code class="computeroutput"><span class="identifier">transform</span></code></a> 341 itself will be a parser returning that updated result. 342 </p></td></tr> 343</table></div> 344<div class="section"> 345<div class="titlepage"><div><div><h5 class="title"> 346<a name="metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl"></a><a name="introducing-foldl"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl" title="Introducing foldl">Introducing 347 foldl</a> 348</h5></div></div></div> 349<p> 350 It works, however, this is rather inefficient: it has a loop parsing 351 the integers one by one, building a typelist and then it loops over this 352 typelist to summarise the result. Using template metaprograms in your 353 applications can have a serious impact on the compiler's memory usage 354 and the speed of the compilation, therefore I recommend being careful 355 with these things. 356 </p> 357<p> 358 Metaparse offers more efficient ways of achieving the same result. You 359 don't need two loops: you can merge them together and add every number 360 to your summary right after parsing it. Metaparse offers the <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> for this. 361 </p> 362<p> 363 With <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> 364 you specify: 365 </p> 366<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 367<li class="listitem"> 368 the parser to parse the individual elements of the list (which is 369 <code class="computeroutput"><span class="identifier">int_token</span></code> in our 370 example) 371 </li> 372<li class="listitem"> 373 the initial value used for folding (which is <code class="computeroutput"><span class="identifier">int_</span><span class="special"><</span><span class="number">0</span><span class="special">></span></code> in our example) 374 </li> 375<li class="listitem"> 376 the forward operation merging the sub-result we have so far and the 377 value coming from the last application of the parser (this was <code class="computeroutput"><span class="identifier">sum_op</span></code> in our example) 378 </li> 379</ul></div> 380<p> 381 Our parser can be implemented this way: 382 </p> 383<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">better_sum_parser</span> <span class="special">=</span> <span class="identifier">foldl</span><span class="special"><</span><span class="identifier">int_token</span><span class="special">,</span> <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">int_</span><span class="special"><</span><span class="number">0</span><span class="special">>,</span> <span class="identifier">sum_op</span><span class="special">>;</span> 384</pre> 385<p> 386 As you can see the implementation of the parser is more compact. Here 387 is a diagram showing what happens when you use this parser to parse some 388 input: 389 </p> 390<p> 391 <span class="inlinemediaobject"><img src="../images/metaparse/foldl_diag1.png" width="70%"></span> 392 </p> 393<p> 394 As you can see, not only the implementation of the parser is more compact, 395 but it achieves the same result by doing less as well. It parses the 396 input by applying <code class="computeroutput"><span class="identifier">int_token</span></code> 397 repeatedly, just like the previous solution. But it produces the final 398 result without building a typelist as an internal step. Here is how it 399 works internally: 400 </p> 401<p> 402 <span class="inlinemediaobject"><img src="../images/metaparse/foldl_diag2.png" width="70%"></span> 403 </p> 404<p> 405 It summarises the results of the repeated <code class="computeroutput"><span class="identifier">int_token</span></code> 406 application using <code class="computeroutput"><span class="identifier">sum_op</span></code>. 407 This implementation is more efficient. It accepts an empty string as 408 a valid input: the sum of it is <code class="computeroutput"><span class="number">0</span></code>. 409 It may be good for you, in which case you are done. If you don't wan 410 to accept it, you can use <a class="link" href="reference.html#foldl1"><code class="computeroutput"><span class="identifier">foldl1</span></code></a> 411 instead of <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a>. 412 This is the same, but it rejects empty input. (Metaparse offers <a class="link" href="reference.html#repeated1"><code class="computeroutput"><span class="identifier">repeated1</span></code></a> 413 as well if you choose the first approach and would like to reject empty 414 string) 415 </p> 416</div> 417<div class="section"> 418<div class="titlepage"><div><div><h5 class="title"> 419<a name="metaparse.user_manual.what_is_a_parser.repetition.introducing_foldr"></a><a name="introducing-foldr"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldr" title="Introducing foldr">Introducing 420 foldr</a> 421</h5></div></div></div> 422<div class="note"><table border="0" summary="Note"> 423<tr> 424<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 425<th align="left">Note</th> 426</tr> 427<tr><td align="left" valign="top"><p> 428 Note that if you are reading this manual for the first time, you probably 429 want to skip this section and proceed with <a class="link" href="user_manual.html#introducing-foldl_start_with_parser">Introducing 430 foldl_start_with_parser</a> 431 </p></td></tr> 432</table></div> 433<p> 434 You might have noticed that Metaparse offers <a class="link" href="reference.html#foldr"><code class="computeroutput"><span class="identifier">foldr</span></code></a> as well. The difference 435 between <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> 436 and <a class="link" href="reference.html#foldr"><code class="computeroutput"><span class="identifier">foldr</span></code></a> 437 is the direction in which the results are summarised. (<code class="computeroutput"><span class="identifier">l</span></code> stands for <span class="emphasis"><em>from the Left</em></span> 438 and <code class="computeroutput"><span class="identifier">r</span></code> stands for <span class="emphasis"><em>from 439 the Right</em></span>) Here is a diagram showing how <code class="computeroutput"><span class="identifier">better_sum_parser</span></code> 440 works if it is implemented using <a class="link" href="reference.html#foldr"><code class="computeroutput"><span class="identifier">foldr</span></code></a>: 441 </p> 442<p> 443 <span class="inlinemediaobject"><img src="../images/metaparse/foldr_diag1.png" width="70%"></span> 444 </p> 445<p> 446 As you can see this is very similar to using <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a>, but the results coming 447 out of the individual applications of <code class="computeroutput"><span class="identifier">int_token</span></code> 448 are summarised in a right-to-left order. As <code class="computeroutput"><span class="identifier">sum_op</span></code> 449 is addition, it does not affect the end result, but in other cases it 450 might. 451 </p> 452<div class="note"><table border="0" summary="Note"> 453<tr> 454<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 455<th align="left">Note</th> 456</tr> 457<tr><td align="left" valign="top"><p> 458 Note that the implementation of <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> is more efficient than 459 <a class="link" href="reference.html#foldr"><code class="computeroutput"><span class="identifier">foldr</span></code></a>. 460 Prefer <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> 461 whenever possible. 462 </p></td></tr> 463</table></div> 464<p> 465 As you might expect it, Metaparse offers <a class="link" href="reference.html#foldr1"><code class="computeroutput"><span class="identifier">foldr1</span></code></a> as well, which folds 466 from the right and rejects empty input. 467 </p> 468</div> 469<div class="section"> 470<div class="titlepage"><div><div><h5 class="title"> 471<a name="metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl_start_with_par"></a><a name="introducing-foldl_start_with_parser"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl_start_with_par" title="Introducing foldl_start_with_parser">Introducing 472 foldl_start_with_parser</a> 473</h5></div></div></div> 474<p> 475 Let's change the grammar of our little language. Instead of a list of 476 numbers, let's expect numbers separated by a <code class="computeroutput"><span class="special">+</span></code> 477 symbol. Our example input becomes the following: 478 </p> 479<pre class="programlisting"><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"11 + 13 + 3 + 21"</span><span class="special">)</span> 480</pre> 481<p> 482 Parsing it with <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> 483 or <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a> 484 is difficult: there has to be a <code class="computeroutput"><span class="special">+</span></code> 485 symbol before every element <span class="emphasis"><em>except</em></span> the first one. 486 None of the already introduced repetition constructs offer a way of treating 487 the first element in a different way. 488 </p> 489<p> 490 If we forget about the first number for a moment, the rest of the input 491 is <code class="computeroutput"><span class="string">"+ 13 + 3 + 21"</span></code>. 492 This can easily be parsed by <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> 493 (or <a class="link" href="reference.html#repeated"><code class="computeroutput"><span class="identifier">repeated</span></code></a>): 494 </p> 495<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">plus_token</span> <span class="special">=</span> <span class="identifier">token</span><span class="special"><</span><span class="identifier">lit_c</span><span class="special"><</span><span class="char">'+'</span><span class="special">>>;</span> 496<span class="keyword">using</span> <span class="identifier">plus_int</span> <span class="special">=</span> <span class="identifier">last_of</span><span class="special"><</span><span class="identifier">plus_token</span><span class="special">,</span> <span class="identifier">int_token</span><span class="special">>;</span> 497 498<span class="keyword">using</span> <span class="identifier">sum_parser2</span> <span class="special">=</span> <span class="identifier">foldl</span><span class="special"><</span><span class="identifier">plus_int</span><span class="special">,</span> <span class="identifier">int_</span><span class="special"><</span><span class="number">0</span><span class="special">>,</span> <span class="identifier">sum_op</span><span class="special">>;</span> 499</pre> 500<p> 501 It uses <code class="computeroutput"><span class="identifier">plus_int</span></code>, that 502 is <a class="link" href="reference.html#last_of"><code class="computeroutput"><span class="identifier">last_of</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">plus_token</span><span class="special">,</span> <span class="identifier">int_token</span><span class="special">></span></code> as the parser that is used repeatedly 503 to get the numbers. It does the following: 504 </p> 505<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 506<li class="listitem"> 507 Uses <code class="computeroutput"><span class="identifier">plus_token</span></code> to 508 parse the <code class="computeroutput"><span class="special">+</span></code> symbol and 509 any whitespace that might follow it. 510 </li> 511<li class="listitem"> 512 Uses then <code class="computeroutput"><span class="identifier">int_token</span></code> 513 to parse the number 514 </li> 515<li class="listitem"> 516 Combines the above two with <a class="link" href="reference.html#last_of"><code class="computeroutput"><span class="identifier">last_of</span></code></a> to use both parsers 517 in order and keep only the result of using the second one (the result 518 of parsing the <code class="computeroutput"><span class="special">+</span></code> symbol 519 is thrown away - we don't care about it). 520 </li> 521</ul></div> 522<p> 523 This way <a class="link" href="reference.html#last_of"><code class="computeroutput"><span class="identifier">last_of</span></code></a><code class="computeroutput"><span class="special"><</span><span class="identifier">plus_token</span><span class="special">,</span> <span class="identifier">int_token</span><span class="special">></span></code> returns the value of the number as 524 the result of parsing, just like our previous parser, <code class="computeroutput"><span class="identifier">int_token</span></code> 525 did. Because of this, it can be used as a drop-in replacement of <code class="computeroutput"><span class="identifier">int_token</span></code> in the previous example and 526 we get a parser for our updated language. Or at least for all number 527 except the first one. 528 </p> 529<p> 530 This <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> 531 can not parse the first element, because it expects a <code class="computeroutput"><span class="special">+</span></code> 532 symbol before every number. You might think of making the <code class="computeroutput"><span class="special">+</span></code> symbol optional in the above approach 533 - don't do that. It makes the parser accept <code class="computeroutput"><span class="string">"11 534 + 13 3 21"</span></code> as well as the <code class="computeroutput"><span class="special">+</span></code> 535 symbol is now optional <span class="emphasis"><em>everywhere</em></span>. 536 </p> 537<p> 538 What you could do is parsing the first element with <code class="computeroutput"><span class="identifier">int_token</span></code>, 539 the rest of the elements with the above <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a>-based solution and add 540 the result of the two. This is left as an exercise to the reader. 541 </p> 542<p> 543 Metaparse offers <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> to implement 544 this. <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> 545 is the same as <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a>. 546 The difference is that instead of an initial value to combine the list 547 elements with it takes an <span class="emphasis"><em>initial parser</em></span>: 548 </p> 549<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">plus_token</span> <span class="special">=</span> <span class="identifier">token</span><span class="special"><</span><span class="identifier">lit_c</span><span class="special"><</span><span class="char">'+'</span><span class="special">>>;</span> 550<span class="keyword">using</span> <span class="identifier">plus_int</span> <span class="special">=</span> <span class="identifier">last_of</span><span class="special"><</span><span class="identifier">plus_token</span><span class="special">,</span> <span class="identifier">int_token</span><span class="special">>;</span> 551 552<span class="keyword">using</span> <span class="identifier">sum_parser3</span> <span class="special">=</span> <span class="identifier">foldl_start_with_parser</span><span class="special"><</span><span class="identifier">plus_int</span><span class="special">,</span> <span class="identifier">int_token</span><span class="special">,</span> <span class="identifier">sum_op</span><span class="special">>;</span> 553</pre> 554<p> 555 <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> 556 starts with applying that initial parser and uses the result it returns 557 as the initial value for folding. It does the same as <a class="link" href="reference.html#foldl"><code class="computeroutput"><span class="identifier">foldl</span></code></a> after that. The following 558 diagram shows how it can be used to parse a list of numbers separated 559 by <code class="computeroutput"><span class="special">+</span></code> symbols: 560 </p> 561<p> 562 <span class="inlinemediaobject"><img src="../images/metaparse/foldl_start_with_parser_diag1.png" width="70%"></span> 563 </p> 564<p> 565 As the diagram shows, it start parsing the list of numbers with <code class="computeroutput"><span class="identifier">int_token</span></code>, uses its value as the starting 566 value for folding (earlier approaches were using the value <code class="computeroutput"><span class="identifier">int_</span><span class="special"><</span><span class="number">0</span><span class="special">></span></code> as 567 this starting value). Then it parses all elements of the list by using 568 <code class="computeroutput"><span class="identifier">plus_int</span></code> multiple times. 569 </p> 570</div> 571<div class="section"> 572<div class="titlepage"><div><div><h5 class="title"> 573<a name="metaparse.user_manual.what_is_a_parser.repetition.introducing_foldr_start_with_par"></a><a name="introducing-foldr_start_with_parser"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldr_start_with_par" title="Introducing foldr_start_with_parser">Introducing 574 foldr_start_with_parser</a> 575</h5></div></div></div> 576<div class="note"><table border="0" summary="Note"> 577<tr> 578<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 579<th align="left">Note</th> 580</tr> 581<tr><td align="left" valign="top"><p> 582 Note that if you are reading this manual for the first time, you probably 583 want to skip this section and try creating some parsers using <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> 584 instead. 585 </p></td></tr> 586</table></div> 587<p> 588 <a href="../foldl_start_with_parser.hpp" target="_top"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> 589 has its <span class="emphasis"><em>from the right</em></span> pair, <a class="link" href="reference.html#foldr_start_with_parser"><code class="computeroutput"><span class="identifier">foldr_start_with_parser</span></code></a>. It 590 uses the same elements as <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> but 591 in a different order. Here is a parser for our example language implemented 592 with <a class="link" href="reference.html#foldr_start_with_parser"><code class="computeroutput"><span class="identifier">foldr_start_with_parser</span></code></a>: 593 </p> 594<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">plus_token</span> <span class="special">=</span> <span class="identifier">token</span><span class="special"><</span><span class="identifier">lit_c</span><span class="special"><</span><span class="char">'+'</span><span class="special">>>;</span> 595<span class="keyword">using</span> <span class="identifier">int_plus</span> <span class="special">=</span> <span class="identifier">first_of</span><span class="special"><</span><span class="identifier">int_token</span><span class="special">,</span> <span class="identifier">plus_token</span><span class="special">>;</span> 596 597<span class="keyword">using</span> <span class="identifier">sum_parser4</span> <span class="special">=</span> <span class="identifier">foldr_start_with_parser</span><span class="special"><</span><span class="identifier">int_plus</span><span class="special">,</span> <span class="identifier">int_token</span><span class="special">,</span> <span class="identifier">sum_op</span><span class="special">>;</span> 598</pre> 599<p> 600 Note that it uses <code class="computeroutput"><span class="identifier">int_plus</span></code> 601 instead of <code class="computeroutput"><span class="identifier">plus_int</span></code>. 602 This is because the parser the initial value for folding comes from is 603 used after <code class="computeroutput"><span class="identifier">int_plus</span></code> has 604 parsed the input as many times as it could. It might sound strange for 605 the first time, but the following diagram should help you understand 606 how it works: 607 </p> 608<p> 609 <span class="inlinemediaobject"><img src="../images/metaparse/foldr_start_with_parser_diag1.png" width="70%"></span> 610 </p> 611<p> 612 As you can see, it starts with the parser that is applied repeatedly 613 on the input, thus instead of parsing <code class="computeroutput"><span class="identifier">plus_token</span> 614 <span class="identifier">int_token</span></code> repeatedly, we need 615 to parse <code class="computeroutput"><span class="identifier">int_token</span> <span class="identifier">plus_token</span></code> 616 repeatedly. The last number is not followed by <code class="computeroutput"><span class="special">+</span></code>, 617 thus <code class="computeroutput"><span class="identifier">int_plus</span></code> fails to 618 parse it and it stops the iteration. <a class="link" href="reference.html#foldr_start_with_parser"><code class="computeroutput"><span class="identifier">foldr_start_with_parser</span></code></a> then 619 uses the other parser, <code class="computeroutput"><span class="identifier">int_token</span></code> 620 to parse the input. It succeeds and the result it returns is used as 621 the starting value for folding from the right. 622 </p> 623<div class="note"><table border="0" summary="Note"> 624<tr> 625<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 626<th align="left">Note</th> 627</tr> 628<tr><td align="left" valign="top"><p> 629 Note that as the above description also suggests, the implementation 630 of <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> 631 is more efficient than <a class="link" href="reference.html#foldr_start_with_parser"><code class="computeroutput"><span class="identifier">foldr_start_with_parser</span></code></a>. Prefer 632 <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> 633 whenever possible. 634 </p></td></tr> 635</table></div> 636</div> 637<div class="section"> 638<div class="titlepage"><div><div><h5 class="title"> 639<a name="metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl_reject_incompl"></a><a name="introducing-foldl_reject_incomplete_start_with_parser"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.introducing_foldl_reject_incompl" title="Introducing foldl_reject_incomplete_start_with_parser">Introducing 640 foldl_reject_incomplete_start_with_parser</a> 641</h5></div></div></div> 642<p> 643 Using a parser built with <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> we can 644 parse the input when the input is correct. However, it is not always 645 the case. Consider the following input for example: 646 </p> 647<pre class="programlisting"><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"11 + 13 + 3 + 21 +"</span><span class="special">)</span> 648</pre> 649<p> 650 This is an invalid expression. However, if we parse it using the <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a>-based 651 parser presented earlier (<code class="computeroutput"><span class="identifier">sum_parser3</span></code>), 652 it accepts the input and the result is <code class="computeroutput"><span class="number">48</span></code>. 653 This is because <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> parses 654 the input <span class="emphasis"><em>as long as it can</em></span>. It parses the first<code class="computeroutput"><span class="identifier">int_token</span></code> (<code class="computeroutput"><span class="number">11</span></code>) 655 and then it starts parsing the <code class="computeroutput"><span class="identifier">plus_int</span></code> 656 elements (<code class="computeroutput"><span class="special">+</span> <span class="number">13</span></code>, 657 <code class="computeroutput"><span class="special">+</span> <span class="number">3</span></code>, 658 <code class="computeroutput"><span class="special">+</span> <span class="number">21</span></code>). 659 After parsing all of these, it tries to parse the remaining <code class="computeroutput"><span class="string">" +"</span></code> input using <code class="computeroutput"><span class="identifier">plus_int</span></code> which fails and therefore 660 <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a> 661 stops after <code class="computeroutput"><span class="special">+</span> <span class="number">21</span></code>. 662 </p> 663<p> 664 The problem is that the parser parses the longest sub-expression starting 665 from the beginning, that represents a valid expression. The rest is ignored. 666 The parser can be wrapped by <a class="link" href="reference.html#entire_input"><code class="computeroutput"><span class="identifier">entire_input</span></code></a> to make sure to 667 reject expressions with invalid extra characters at the end, however, 668 that won't make the error message useful. (<a class="link" href="reference.html#entire_input"><code class="computeroutput"><span class="identifier">entire_input</span></code></a> can only tell the 669 author of the invalid expression that after <code class="computeroutput"><span class="special">+</span> 670 <span class="number">21</span></code> is something wrong). 671 </p> 672<p> 673 Metaparse provides <a class="link" href="reference.html#foldl_reject_incomplete_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_reject_incomplete_start_with_parser</span></code></a>, 674 which does the same as <a class="link" href="reference.html#foldl_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_start_with_parser</span></code></a>, except 675 that once no further repetitions are found, it checks <span class="emphasis"><em>where</em></span> 676 the repeated parser (in our example <code class="computeroutput"><span class="identifier">plus_int</span></code>) 677 fails. When it can make any progress (eg. it finds a <code class="computeroutput"><span class="special">+</span></code> 678 symbol), then <a class="link" href="reference.html#foldl_reject_incomplete_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_reject_incomplete_start_with_parser</span></code></a> 679 assumes, that the expression's author intended to make the repetition 680 longer, but made a mistake and propagates the error message coming from 681 that last broken expression. 682 </p> 683<p> 684 <span class="inlinemediaobject"><img src="../images/metaparse/foldl_reject_incomplete_start_with_parser_diag1.png" width="70%"></span> 685 </p> 686<p> 687 The above diagram shows how <a class="link" href="reference.html#foldl_reject_incomplete_start_with_parser"><code class="computeroutput"><span class="identifier">foldl_reject_incomplete_start_with_parser</span></code></a> 688 parses the example invalid input and how it fails. This can be used for 689 better error reporting from the parsers. 690 </p> 691<p> 692 Other folding parsers also have their <code class="computeroutput"><span class="identifier">f</span></code> 693 version. (eg. <a class="link" href="reference.html#foldr_reject_incomplete"><code class="computeroutput"><span class="identifier">foldr_reject_incomplete</span></code></a>, 694 <a class="link" href="reference.html#foldl_reject_incomplete1"><code class="computeroutput"><span class="identifier">foldl_reject_incomplete1</span></code></a>, 695 etc). 696 </p> 697</div> 698<div class="section"> 699<div class="titlepage"><div><div><h5 class="title"> 700<a name="metaparse.user_manual.what_is_a_parser.repetition.finding_the_right_folding_parser"></a><a name="finding-the-right-folding-parser-combinator"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.repetition.finding_the_right_folding_parser" title="Finding the right folding parser combinator">Finding 701 the right folding parser combinator</a> 702</h5></div></div></div> 703<p> 704 As you might have noticed, there are a lot of different folding parser 705 combinators. To help you find the right one, the following naming convention 706 is used: 707 </p> 708<p> 709 <span class="inlinemediaobject"><img src="../images/metaparse/folds.png" width="70%"></span> 710 </p> 711<div class="note"><table border="0" summary="Note"> 712<tr> 713<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td> 714<th align="left">Note</th> 715</tr> 716<tr><td align="left" valign="top"><p> 717 Note that there is no <code class="computeroutput"><span class="identifier">foldr_reject_incomplete_start_with_parser</span></code>. 718 The <code class="computeroutput"><span class="identifier">p</span></code> version of the 719 right-folding parsers applies the special parser, whose result is the 720 initial value, after the repeated elements. Therefore, when the parser 721 parsing one repeated element fails, <code class="computeroutput"><span class="identifier">foldr_start_with_parser</span></code> 722 would apply that special final parser instead of checking how the repeated 723 element's parser failed. 724 </p></td></tr> 725</table></div> 726</div> 727</div> 728<div class="section"> 729<div class="titlepage"><div><div><h4 class="title"> 730<a name="metaparse.user_manual.what_is_a_parser.what_can_be_built_from_a_compile"></a><a name="result_types"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.what_can_be_built_from_a_compile" title="What can be built from a compile-time string?">What 731 can be built from a compile-time string?</a> 732</h4></div></div></div> 733<p> 734 Parsers built using Metaparse are template metaprograms parsing text (or 735 code) at compile-time. Here is a list of things that can be the "result" 736 of parsing: 737 </p> 738<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 739<li class="listitem"> 740 A <span class="emphasis"><em>type</em></span>. An example for this is a parser parsing 741 a <code class="computeroutput"><span class="identifier">printf</span></code> format string 742 and returning the typelist (eg. <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">vector</span></code>) 743 of the expected arguments. 744 </li> 745<li class="listitem"> 746 A <span class="emphasis"><em>constant value</em></span>. An example for this is the result 747 of a calculator language. See the <a class="link" href="getting_started_with_boost_metap.html#getting_started">Getting 748 Started</a> section for further details. 749 </li> 750<li class="listitem"> 751 A <span class="emphasis"><em>runtime object</em></span>. A static runtime object can 752 be generated that might be used at runtime. An example for this is 753 parsing regular expressions at compile-time and building <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">xpressive</span><span class="special">::</span><span class="identifier">sregex</span></code> objects. See the <code class="computeroutput"><span class="identifier">regex</span></code> example of Metaparse for an 754 example. 755 </li> 756<li class="listitem"> 757 A C++ <span class="emphasis"><em>function</em></span>, which might be called at runtime. 758 A C++ function can be generated that can be called at runtime. It is 759 good for generating native (and optimised) code from EDSLs. See the 760 <code class="computeroutput"><span class="identifier">compile_to_native_code</span></code> 761 example of Metaparse as an example for this. 762 </li> 763<li class="listitem"> 764 A <a class="link" href="reference.html#metafunction_class"><span class="emphasis"><em>template metafunction 765 class</em></span></a>. The result of parsing might be a type, which 766 is a <a class="link" href="reference.html#metafunction_class">template metafunction class</a>. 767 This is good for building an EDSL for template metaprogramming. See 768 the <code class="computeroutput"><span class="identifier">meta_hs</span></code> example 769 of Metaparse as an example for this. 770 </li> 771</ul></div> 772</div> 773<div class="section"> 774<div class="titlepage"><div><div><h4 class="title"> 775<a name="metaparse.user_manual.what_is_a_parser.grammars"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_is_a_parser.grammars" title="Grammars">Grammars</a> 776</h4></div></div></div> 777<p> 778 Metaparse provides a way to define grammars in a syntax that resembles 779 EBNF. The <a class="link" href="reference.html#grammar"><code class="computeroutput"><span class="identifier">grammar</span></code></a> 780 template can be used to define a grammar. It can be used the following 781 way: 782 </p> 783<pre class="programlisting"><span class="identifier">grammar</span><span class="special"><</span><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"plus_exp"</span><span class="special">)></span> 784 <span class="special">::</span><span class="identifier">import</span><span class="special"><</span><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"int_token"</span><span class="special">),</span> <span class="identifier">token</span><span class="special"><</span><span class="identifier">int_</span><span class="special">>>::</span><span class="identifier">type</span> 785 786 <span class="special">::</span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"ws ::= (' ' | '\n' | '\r' | '\t')*"</span><span class="special">)>::</span><span class="identifier">type</span> 787 <span class="special">::</span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"plus_token ::= '+' ws"</span><span class="special">),</span> <span class="identifier">front</span><span class="special"><</span><span class="identifier">_1</span><span class="special">>>::</span><span class="identifier">type</span> 788 <span class="special">::</span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">BOOST_METAPARSE_STRING</span><span class="special">(</span><span class="string">"plus_exp ::= int_token (plus_token int_token)*"</span><span class="special">),</span> <span class="identifier">plus_action</span><span class="special">>::</span><span class="identifier">type</span> 789</pre> 790<p> 791 The code above defines a parser from a grammar definition. The start symbol 792 of the grammar is <code class="computeroutput"><span class="identifier">plus_exp</span></code>. 793 The lines beginning with <code class="computeroutput"><span class="special">::</span><span class="identifier">rule</span></code> define rules. Rules optionally have 794 a semantic action, which is a metafunction class that transforms the result 795 of parsing after the rule has been applied. Existing parsers can be bound 796 to names and be used in the rules by importing them. Lines beginning with 797 <code class="computeroutput"><span class="special">::</span><span class="identifier">import</span></code> 798 bind existing parsers to names. 799 </p> 800<p> 801 The result of a grammar definition is a parser which can be given to other 802 parser combinators or be used directly. Given that grammars can import 803 existing parsers and build new ones, they are parser combinators as well. 804 </p> 805</div> 806</div> 807<div class="section"> 808<div class="titlepage"><div><div><h3 class="title"> 809<a name="metaparse.user_manual.parsing_based_on_constexpr"></a><a class="link" href="user_manual.html#metaparse.user_manual.parsing_based_on_constexpr" title="Parsing based on constexpr">Parsing 810 based on <code class="computeroutput"><span class="keyword">constexpr</span></code></a> 811</h3></div></div></div> 812<p> 813 Metaparse is based on template metaprogramming, however, C++11 provides 814 <code class="computeroutput"><span class="keyword">constexpr</span></code>, which can be used 815 for parsing at compile-time as well. While implementing parsers based on 816 <code class="computeroutput"><span class="keyword">constexpr</span></code> is easier for a C++ 817 developer, since its syntax resembles the regular syntax of the language, 818 the result of parsing has to be a <code class="computeroutput"><span class="keyword">constexpr</span></code> 819 value. Parsers based on template metaprogramming can build types as the result 820 of parsing. These types may be boxed <code class="computeroutput"><span class="keyword">constexpr</span></code> 821 values but can be metafunction classes, classes with static functions which 822 can be called at runtime, etc. 823 </p> 824<p> 825 When a parser built with Metaparse needs a sub-parser for processing a part 826 of the input text and generating a <code class="computeroutput"><span class="keyword">constexpr</span></code> 827 value as the result of parsing, one can implement the sub-parser based on 828 <code class="computeroutput"><span class="keyword">constexpr</span></code> functions. Metaparse 829 can be integrated with them and lift their results into C++ template metaprogramming. 830 An example demonstrating this feature can be found among the examples (<code class="computeroutput"><span class="identifier">constexpr_parser</span></code>). This capability makes 831 it possible to integrate Metaparse with parsing libraries based on <code class="computeroutput"><span class="keyword">constexpr</span></code>. 832 </p> 833</div> 834<div class="section"> 835<div class="titlepage"><div><div><h3 class="title"> 836<a name="metaparse.user_manual.what_types_of_grammars_can_be_us"></a><a class="link" href="user_manual.html#metaparse.user_manual.what_types_of_grammars_can_be_us" title="What types of grammars can be used?">What 837 types of grammars can be used?</a> 838</h3></div></div></div> 839<p> 840 It is possible to write parsers for <span class="emphasis"><em>context free grammars</em></span> 841 using Metaparse. However, this is not the most general category of grammars 842 that can be used. As Metaparse is a highly extendable framework, it is not 843 clear what should be considered to be the limit of Metaparse itself. For 844 example Metaparse provides the <a class="link" href="reference.html#accept_when"><code class="computeroutput"><span class="identifier">accept_when</span></code></a> <a class="link" href="reference.html#parser_combinator">parser 845 combinator</a>. It can be used to provide arbitrary predicates for enabled/disabling 846 a specific rule. One can go as far as providing the Turing machine (as a 847 <a class="link" href="reference.html#metafunction">metafunction</a>) of the entire grammar as 848 a predicate, so one can build parsers for <span class="emphasis"><em>unrestricted grammars</em></span> 849 that can be parsed using a Turing machine. Note that such a parser would 850 not be considered to be a parser built with Metaparse, however, it is not 851 clear how far a solution might go and still be considered using Metaparse. 852 </p> 853<p> 854 Metaparse assumes that the parsers are <span class="emphasis"><em>deterministic</em></span>, 855 as they have only "one" result. It is of course possible to write 856 parsers and combinators that return a set (or list or some other container) 857 of results as that "one" result, but that can be considered building 858 a new parser library. There is no clear boundary for Metaparse. 859 </p> 860<p> 861 Metaparse supports building <span class="emphasis"><em>top-down parsers</em></span> and <span class="emphasis"><em>left-recursion</em></span> 862 is not supported as it would lead to infinite recursion. <span class="emphasis"><em>Right-recursion</em></span> 863 is supported, however, in most cases the <a class="link" href="user_manual.html#repetition">iterative 864 parser combinators</a> provide better alternatives. 865 </p> 866</div> 867</div> 868<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 869<td align="left"></td> 870<td align="right"><div class="copyright-footer">Copyright © 2015 Abel Sinkovics<p> 871 Distributed under the Boost Software License, Version 1.0. (See accompanying 872 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>) 873 </p> 874</div></td> 875</tr></table> 876<hr> 877<div class="spirit-nav"> 878<a accesskey="p" href="getting_started_with_boost_metap.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../metaparse.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="versioning.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 879</div> 880</body> 881</html> 882
