]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <html> |
2 | <head> | |
3 | <title> Loops</title> | |
4 | <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> | |
5 | <link rel="stylesheet" href="theme/style.css" type="text/css"> | |
6 | </head> | |
7 | ||
8 | <body> | |
9 | <table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2"> | |
10 | <tr> | |
11 | <td width="10"> | |
12 | </td> | |
13 | <td width="85%"> | |
14 | <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b> Loops</b></font> | |
15 | </td> | |
16 | <td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td> | |
17 | </tr> | |
18 | </table> | |
19 | <br> | |
20 | <table border="0"> | |
21 | <tr> | |
22 | <td width="10"></td> | |
23 | <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> | |
24 | <td width="30"><a href="escape_char_parser.html"><img src="theme/l_arr.gif" border="0"></a></td> | |
25 | <td width="30"><a href="character_sets.html"><img src="theme/r_arr.gif" border="0"></a></td> | |
26 | </tr> | |
27 | </table> | |
28 | <p>So far we have introduced a couple of EBNF operators that deal with looping. | |
29 | We have the <tt>+</tt> positive operator, which matches the preceding symbol | |
30 | one (1) or more times, as well as the Kleene star <tt>*</tt> which matches the | |
31 | preceding symbol zero (0) or more times.</p> | |
32 | <p>Taking this further, we may want to have a generalized loop operator. To some | |
33 | this may seem to be a case of overkill. Yet there are grammars that are impractical | |
34 | and cumbersome, if not impossible, for the basic EBNF iteration syntax to specify. | |
35 | Examples:</p> | |
36 | <blockquote> | |
37 | <p><img src="theme/bullet.gif" width="12" height="12"> A file name may have | |
38 | a maximum of 255 characters only.<br> | |
39 | <img src="theme/bullet.gif" width="12" height="12"> A specific bitmap file | |
40 | format has exactly 4096 RGB color information. <br> | |
41 | <img src="theme/bullet.gif" width="12" height="12"> A 32 bit binary string | |
42 | (1..32 1s or 0s).</p> | |
43 | </blockquote> | |
44 | <p>Other than the Kleene star <tt>*</tt>, the Positive closure <tt>+</tt>, and | |
45 | the optional <tt>!</tt>, a more flexible mechanism for looping is provided for | |
46 | by the framework. <br> | |
47 | </p> | |
48 | <table width="80%" border="0" align="center"> | |
49 | <tr> | |
50 | <td colspan="2" class="table_title">Loop Constructs</td> | |
51 | </tr> | |
52 | <tr> | |
53 | <td class="table_cells" width="26%"><b>repeat_p (n) [p]</b></td> | |
54 | <td class="table_cells" width="74%">Repeat <b>p</b> exactly <b>n</b> times</td> | |
55 | </tr> | |
56 | <tr> | |
57 | <td class="table_cells" width="26%"><b>repeat_p (n1, n2) [p]</b></td> | |
58 | <td class="table_cells" width="74%">Repeat <b>p</b> at least <b>n1</b> times | |
59 | and at most <b>n2</b> times</td> | |
60 | </tr> | |
61 | <tr> | |
62 | <td class="table_cells" width="26%"><b>repeat_p (n, more) [p] </b></td> | |
63 | <td class="table_cells" width="74%">Repeat <b>p</b> at least <b>n</b> times, | |
64 | continuing until <b>p</b> fails or the input is consumed</td> | |
65 | </tr> | |
66 | </table> | |
67 | <p>Using the <tt>repeat_p</tt> parser, we can now write our examples above:</p> | |
68 | <p>A file name with a maximum of 255 characters:<br> | |
69 | </p> | |
70 | <pre> <span class=identifier>valid_fname_chars </span><span class=special>= </span><span class=comment>/*..*/</span><span class=special>; | |
71 | </span><span class=identifier>filename </span><span class=special>= </span><span class=identifier>repeat_p</span><span class=special>(</span><span class=number>1</span><span class=special>, </span><span class=number>255</span><span class=special>)[</span><span class=identifier>valid_fname_chars</span><span class=special>];</span></pre> | |
72 | <p>A specific bitmap file format which has exactly 4096 RGB color information:<span class=special><br> | |
73 | </span></p> | |
74 | <pre> <span class=identifier>uint_parser</span><span class=special><</span><span class=keyword>unsigned</span><span class=special>, </span><span class=number>16</span><span class=special>, </span><span class=number>6</span><span class=special>, </span><span class=number>6</span><span class=special>> </span><span class=identifier>rgb_p</span><span class=special>; | |
75 | </span><span class=identifier>bitmap </span><span class=special>= </span><span class=identifier>repeat_p</span><span class=special>(</span><span class=number>4096</span><span class=special>)[</span><span class=identifier>rgb_p</span><span class=special>];</span></pre> | |
76 | <p>As for the 32 bit binary string (1..32 1s or 0s), of course we could have easily | |
77 | used the <tt>bin_p</tt> numeric parser instead. For the sake of demonstration | |
78 | however:<span class=special><br> | |
79 | </span></p> | |
80 | <pre> <span class=identifier>bin</span><span class=number>32</span> <span class=special>= </span><span class=identifier>lexeme_d</span><span class=special>[</span><span class=identifier>repeat_p</span><span class=special>(</span>1, <span class=number>32</span><span class=special>)[</span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'1'</span><span class=special>) </span><span class=special>| </span><span class=literal>'0'</span><span class=special>]];</span></pre> | |
81 | <table width="80%" border="0" align="center"> | |
82 | <tr> | |
83 | <td class="note_box"><img src="theme/note.gif" width="16" height="16"> Loop | |
84 | parsers are run-time <a href="parametric_parsers.html">parametric</a>.</td> | |
85 | </tr> | |
86 | </table> | |
87 | <p>The Loop parsers can be dynamic. Consider the parsing of a binary file of Pascal-style | |
88 | length prefixed string, where the first byte determines the length of the incoming | |
89 | string. Here's a sample input: | |
90 | <blockquote> | |
91 | <table width="363" border="0" cellspacing="0" cellpadding="0"> | |
92 | <tr> | |
93 | <td class="dk_grey_bkd"> | |
94 | <table width="100%" border="0" cellspacing="2" cellpadding="2"> | |
95 | <tr> | |
96 | <td class="white_bkd" width=8%"> | |
97 | <div align="center">11</div> | |
98 | </td> | |
99 | <td class="white_bkd" width="8%"> | |
100 | <div align="center">h</div> | |
101 | </td> | |
102 | <td class="white_bkd" width="8%"> | |
103 | <div align="center">e</div> | |
104 | </td> | |
105 | <td class="white_bkd" width="8%"> | |
106 | <div align="center">l</div> | |
107 | </td> | |
108 | <td class="white_bkd" width="8%"> | |
109 | <div align="center">l</div> | |
110 | </td> | |
111 | <td class="white_bkd" width="8%"> | |
112 | <div align="center">o</div> | |
113 | </td> | |
114 | <td class="white_bkd" width="8%"> | |
115 | <div align="center"> _</div> | |
116 | </td> | |
117 | <td class="white_bkd" width="8%"> | |
118 | <div align="center">w</div> | |
119 | </td> | |
120 | <td class="white_bkd" width="8%"> | |
121 | <div align="center">o</div> | |
122 | </td> | |
123 | <td class="white_bkd" width="8%"> | |
124 | <div align="center">r</div> | |
125 | </td> | |
126 | <td class="white_bkd" width="8%"> | |
127 | <div align="center">l</div> | |
128 | </td> | |
129 | <td class="white_bkd" width="8%"> | |
130 | <div align="center">d</div> | |
131 | </td> | |
132 | </tr> | |
133 | </table> | |
134 | </td> | |
135 | </tr> | |
136 | </table> | |
137 | ||
138 | </blockquote> | |
139 | <p>This trivial example cannot be practically defined in traditional EBNF. Although | |
140 | some EBNF syntax allow more powerful repetition constructs other than the Kleene | |
141 | star, we are still limited to parsing fixed strings. The nature of EBNF forces | |
142 | the repetition factor to be a constant. On the other hand, Spirit allows the | |
143 | repetition factor to be variable at run time. We could write a grammar that | |
144 | accepts the input string above:</p> | |
145 | <pre><span class=identifier> </span><span class=keyword>int </span><span class=identifier>c</span><span class=special>; | |
146 | </span><span class=identifier>r </span><span class=special>= </span><span class=identifier>anychar_p</span><span class=special>[</span><span class=identifier>assign_a</span><span class=special>(</span><span class=identifier>c</span><span class=special>)] </span><span class=special>>> </span><span class=identifier>repeat_p</span><span class=special>(</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>ref</span><span class=special>(</span><span class=identifier>c</span><span class=special>))[</span><span class=identifier>anychar_p</span><span class=special>];</span></pre> | |
147 | <p>The expression</p> | |
148 | <pre> <span class=identifier>anychar_p</span><span class=special>[</span><span class=identifier>assign_a</span><span class=special>(</span><span class=identifier>c</span><span class=special>)]</span></pre> | |
149 | <p>extracts the first character from the input and puts it in <tt>c</tt>. What | |
150 | is interesting is that in addition to constants, we can also use variables as | |
151 | parameters to <tt>repeat_p</tt>, as demonstrated in </p> | |
152 | <pre> <span class=identifier>repeat_p</span><span class=special>(</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>ref</span><span class=special>(</span><span class=identifier>c</span><span class=special>)</span><span class=special>)</span><span class=special>[</span><span class=identifier>anychar_p</span><span class=special>]</span></pre> | |
153 | <p>Notice that <tt>boost::ref</tt> is used to reference the integer <tt>c</tt>. | |
154 | This usage of <tt>repeat_p</tt> makes the parser defer the evaluation of the | |
155 | repetition factor until it is actually needed. Continuing our example, since | |
156 | the value 11 is already extracted from the input, <tt>repeat_p</tt> is is now | |
157 | expected to loop exactly 11 times.</p> | |
158 | <table border="0"> | |
159 | <tr> | |
160 | <td width="10"></td> | |
161 | <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> | |
162 | <td width="30"><a href="escape_char_parser.html"><img src="theme/l_arr.gif" border="0"></a></td> | |
163 | <td width="30"><a href="character_sets.html"><img src="theme/r_arr.gif" border="0"></a></td> | |
164 | </tr> | |
165 | </table> | |
166 | <br> | |
167 | <hr size="1"> | |
168 | <p class="copyright">Copyright © 1998-2003 Joel de Guzman<br> | |
169 | <br> | |
170 | <font size="2">Use, modification and distribution is subject to the Boost Software | |
171 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
172 | http://www.boost.org/LICENSE_1_0.txt) </font> </p> | |
173 | </body> | |
174 | </html> |