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">>></span> <span class= 86 "identifier">expression</span> <span class= 87 "special">>></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">>></span> <span class="special">*((</span><span class= 95"literal">'*'</span> <span class="special">>></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">>></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">>></span> <span class="special">*((</span><span class= 103"literal">'+'</span> <span class="special">>></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">>></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>>></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">>></tt> operator 182 instead for this purpose. We take the <tt class="operators">>></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">>></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 © 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> 239 240 </p> 241 </body> 242</html> 243
