Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/spirit/doc/introduction.html @ 33

Last change on this file since 33 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 11.7 KB
Line 
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>
Note: See TracBrowser for help on using the repository browser.