ceph/src/boost/libs/spirit/classic/doc/introduction.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html>
   3   <head>
   4     <meta content=
   5     "HTML Tidy for Windows (vers 1st February 2003), see www.w3.org"
   6           name="generator">
   7     <title>
   8       Introduction
   9     </title>
  10     <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
  11     <link rel="stylesheet" href="theme/style.css" type="text/css">
  12   </head>
  13   <body>
  14     <table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
  15       <tr>
  16         <td width="10" height="49"></td>
  17         <td width="85%" height="49">
  18           <font size="6" face=
  19           "Verdana, Arial, Helvetica, sans-serif"><b>Introduction</b></font>
  20         </td>
  21         <td width="112" height="49">
  22           <a href="http://spirit.sf.net"><img src="theme/spirit.gif"
  23                width="112" height="48" align="right" border="0"></a>
  24         </td>
  25       </tr>
  26     </table><br>
  27     <table border="0">
  28       <tr>
  29         <td width="10"></td>
  30         <td width="30">
  31           <a href="../index.html"><img src="theme/u_arr.gif" border="0"></a>
  32         </td>
  33         <td width="30">
  34           <a href="preface.html"><img src="theme/l_arr.gif" width="20"
  35                height="19" border="0"></a>
  36         </td>
  37         <td width="30">
  38           <a href="quick_start.html"><img src="theme/r_arr.gif" border="0"></a>
  39         </td>
  40       </tr>
  41     </table>
  42     <p>
  43       Spirit is an object-oriented recursive-descent parser generator framework
  44       implemented using template meta-programming techniques. Expression
  45       templates allow us to approximate the syntax of Extended Backus-Normal
  46       Form (EBNF) completely in C++.
  47     </p>
  48     <p>
  49       The Spirit framework enables a target grammar to be written exclusively
  50       in C++. Inline EBNF grammar specifications can mix freely with other C++
  51       code and, thanks to the generative power of C++ templates, are
  52       immediately executable. In retrospect, conventional compiler-compilers or
  53       parser-generators have to perform an additional translation step from the
  54       source EBNF code to C or C++ code.
  55     </p>
  56     <p>
  57       A simple EBNF grammar snippet:
  58     </p>
  59
  60 <pre><code><font color="#000000">    </font></code><code><font color="#000000"><span class="identifier">group      </span> <span class="special">::=</span> <span class="literal">'('</span> <span class="identifier">expression</span> <span class="literal">')'
  61 </span>    <span class="identifier">factor     </span> <span class=
  62 "special">::=</span> <span class="identifier">integer</span> <span class=
  63 "special">|</span> <span class="identifier">group
  64 </span>    <span class="identifier">term       </span> <span class=
  65 "special">::=</span> <span class="identifier">factor</span> <span class=
  66 "special">((</span><span class="literal">'*'</span> <span class=
  67 "identifier">factor</span><span class="special">)</span> <span class=
  68 "special">|</span> <span class="special">(</span><span class=
  69 "literal">'/'</span> <span class="identifier">factor</span><span class=
  70 "special">))*
  71 </span>    <span class="identifier">expression </span> <span class=
  72 "special">::=</span> <span class="identifier">term</span> <span class=
  73 "special">((</span><span class="literal">'+'</span> <span class=
  74 "identifier">term</span><span class="special">)</span> <span class=
  75 "special">|</span> <span class="special">(</span><span class=
  76 "literal">'-'</span> <span class="identifier">term</span><span class=
  77 "special">))*</span></font></code></pre>
  78     <p>
  79       is approximated using Spirit's facilities as seen in this code snippet:
  80     </p>
  81
  82 <pre><code><font color="#000000">    </font></code><code><font color="#000000"><span class=
  83 "identifier">group      </span> <span class=
  84       "special">=</span> <span class="literal">'('</span> <span class=
  85       "special">&gt;&gt;</span> <span class=
  86       "identifier">expression</span> <span class=
  87       "special">&gt;&gt;</span> <span class="literal">')'</span><span class=
  88       "special">;
  89 </span>    <span class="identifier">factor     </span> <span class=
  90 "special">=</span> <span class="identifier">integer</span> <span class=
  91 "special">|</span> <span class="identifier">group</span><span class="special">;
  92 </span>    <span class="identifier">term       </span> <span class=
  93 "special">=</span> <span class="identifier">factor</span> <span class=
  94 "special">&gt;&gt;</span> <span class="special">*((</span><span class=
  95 "literal">'*'</span> <span class="special">&gt;&gt;</span> <span class=
  96 "identifier">factor</span><span class="special">)</span> <span class=
  97 "special">|</span> <span class="special">(</span><span class=
  98 "literal">'/'</span> <span class="special">&gt;&gt;</span> <span class=
  99 "identifier">factor</span><span class="special">));
 100 </span>    <span class="identifier">expression </span> <span class=
 101 "special">=</span> <span class="identifier">term</span> <span class=
 102 "special">&gt;&gt;</span> <span class="special">*((</span><span class=
 103 "literal">'+'</span> <span class="special">&gt;&gt;</span> <span class=
 104 "identifier">term</span><span class="special">)</span> <span class=
 105 "special">|</span> <span class="special">(</span><span class=
 106 "literal">'-'</span> <span class="special">&gt;&gt;</span> <span class=
 107 "identifier">term</span><span class="special">));</span></font></code>
 108 </pre>
 109 <p>
 110       Through the magic of expression templates, this is perfectly valid and
 111       executable C++ code. The production rule <tt>expression</tt> is in fact
 112       an object that has a member function parse that does the work given a
 113       source code written in the grammar that we have just declared. Yes, it's
 114       a calculator. We shall simplify for now by skipping the type declarations
 115       and the definition of the rule <tt>integer</tt> invoked by
 116       <tt>factor</tt>. The production rule <tt>expression</tt> in our grammar
 117       specification, traditionally called the start symbol, can recognize
 118       inputs such as:
 119     </p>
 120
 121 <pre><code><font color="#000000">    </font></code><span class="number">12345
 122 </span><code><font color="#000000">    </font></code><span class="special">-</span><span class="number">12345
 123 </span><code><font color="#000000">    </font></code><span class="special">+</span><span class="number">12345
 124 </span><code><font color="#000000">    </font></code><span class="number">1</span> <span class=
 125 "special">+</span> <span class="number">2
 126 </span><code><font color="#000000">    </font></code><span class="number">1</span> <span class=
 127 "special">*</span> <span class="number">2
 128 </span><code><font color="#000000">    </font></code><span class="number">1</span><span class=
 129      "special">/</span><span class="number">2</span> <span class=
 130      "special">+</span> <span class="number">3</span><span class=
 131      "special">/</span><span class="number">4
 132 </span><code><font color="#000000">    </font></code><span class="number">1</span> <span class=
 133 "special">+</span> <span class="number">2</span> <span class=
 134 "special">+</span> <span class="number">3</span> <span class=
 135 "special">+</span> <span class="number">4
 136 </span><code><font color="#000000">    </font></code><span class="number">1</span> <span class=
 137 "special">*</span> <span class="number">2</span> <span class=
 138 "special">*</span> <span class="number">3</span> <span class=
 139 "special">*</span> <span class="number">4
 140 </span><code><font color="#000000">    </font></code><span class="special">(</span><span class=
 141      "number">1</span> <span class="special">+</span> <span class=
 142      "number">2</span><span class="special">)</span> <span class=
 143      "special">*</span> <span class="special">(</span><span class=
 144      "number">3</span> <span class="special">+</span> <span class=
 145      "number">4</span><span class="special">)
 146 </span><code><font color="#000000">    </font></code><span class="special">(-</span><span class=
 147 "number">1</span> <span class="special">+</span> <span class=
 148 "number">2</span><span class="special">)</span> <span class=
 149 "special">*</span> <span class="special">(</span><span class=
 150 "number">3</span> <span class="special">+</span> <span class=
 151 "special">-</span><span class="number">4</span><span class="special">)
 152 </span><code><font color="#000000">    </font></code><span class="number">1</span> <span class=
 153 "special">+</span> <span class="special">((</span><span class=
 154 "number">6</span> <span class="special">*</span> <span class=
 155 "number">200</span><span class="special">)</span> <span class=
 156 "special">-</span> <span class="number">20</span><span class=
 157 "special">)</span> <span class="special">/</span> <span class="number">6
 158 </span><code><font color="#000000">    </font></code><span class="special">(</span><span class=
 159      "number">1</span> <span class="special">+</span> <span class=
 160      "special">(</span><span class="number">2</span> <span class=
 161      "special">+</span> <span class="special">(</span><span class=
 162      "number">3</span> <span class="special">+</span> <span class=
 163      "special">(</span><span class="number">4</span> <span class=
 164      "special">+</span> <span class="number">5</span><span class=
 165      "special">))))</span>
 166 </pre>
 167 <p>
 168       Certainly we have done some modifications to the original EBNF syntax.
 169       This is done to conform to C++ syntax rules. Most notably we see the
 170       abundance of shift <tt>&gt;&gt;</tt> operators. Since there are no
 171       'empty' operators in C++, it is simply not possible to write something
 172       like:
 173     </p>
 174
 175 <pre><code><font color="#000000">    </font></code><span class=
 176      "identifier">a</span> <span class="identifier">b</span>
 177 </pre>
 178 <p>
 179       as seen in math syntax, for example, to mean multiplication or, in our
 180       case, as seen in EBNF syntax to mean sequencing (b should follow a). The
 181       framework uses the shift <tt class="operators">&gt;&gt;</tt> operator
 182       instead for this purpose. We take the <tt class="operators">&gt;&gt;</tt>
 183       operator, with arrows pointing to the right, to mean "is followed by".
 184       Thus we write:
 185     </p>
 186
 187 <pre><code><font color="#000000">    </font></code><span class=
 188 "identifier">a</span> <span class="special">&gt;&gt;</span> <span class=
 189 "identifier">b</span>
 190 </pre>
 191 <p>
 192       The alternative operator <tt class="operators">|</tt> and the parentheses
 193       <tt class="operators">()</tt> remain as is. The assignment operator
 194       <tt class="operators">=</tt> is used in place of EBNF's <tt class=
 195       "operators">::=</tt>. Last but not least, the Kleene star <tt class=
 196       "operators">*</tt> which used to be a postfix operator in EBNF becomes a
 197       prefix. Instead of:
 198     </p>
 199
 200 <pre><code><font color="#000000">    </font></code><span class="identifier">a</span><span class=
 201      "special">*</span> <span class="comment">//... in EBNF syntax,</span>
 202 </pre>
 203 <p>
 204       we write:
 205     </p>
 206
 207 <pre><code><font color="#000000">    </font></code><span class="special">*</span><span class=
 208      "identifier">a</span> <span class="comment">//... in Spirit.</span>
 209 </pre>
 210 <p>
 211       since there are no postfix stars, "<tt class="operators">*</tt>", in
 212       C/C++. Finally, we terminate each rule with the ubiquitous semi-colon,
 213       "<tt>;</tt>".
 214     </p>
 215     <table border="0">
 216       <tr>
 217         <td width="10"></td>
 218         <td width="30">
 219           <a href="../index.html"><img src="theme/u_arr.gif" border="0"></a>
 220         </td>
 221         <td width="30">
 222           <a href="preface.html"><img src="theme/l_arr.gif" width="20"
 223                height="19" border="0"></a>
 224         </td>
 225         <td width="30">
 226           <a href="quick_start.html"><img src="theme/r_arr.gif" border="0"></a>
 227         </td>
 228       </tr>
 229     </table><br>
 230     <hr size="1">
 231     <p class="copyright">
 232       Copyright &copy; 1998-2003 Joel de Guzman<br>
 233       <br>
 234        <font size="2">Use, modification and distribution is subject to the
 235       Boost Software License, Version 1.0. (See accompanying file
 236       LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)</font>
 237     </p>
 238     <p>&nbsp;
 239
 240     </p>
 241   </body>
 242 </html>