<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title>Trees</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<link rel="stylesheet" href="theme/style.css" type="text/css"></head>
<body>
<table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
<tbody><tr>
<td width="10">
<br>
</td>
<td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Trees</b></font>
</td>
<td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td>
</tr>
</tbody></table>
<br>
<table border="0">
<tbody><tr>
<td width="10"><br>
</td>
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
<td width="30"><a href="symbols.html"><img src="theme/l_arr.gif" border="0"></a></td>
<td width="20"><a href="multi_pass.html"><img src="theme/r_arr.gif" border="0"></a></td>
</tr>
</tbody></table>
<h2>Why use parse trees</h2>
<p> Parse trees are an in-memory representation of the input with a structure
that conforms to the grammar.</p>
<p> The advantages of using parse trees instead of semantic actions:</p>
<ul>
<li>You can make multiple passes over the data without having to re-parse the
input.</li>
<li>You can perform transformations on the tree.</li>
<li>You can evaluate things in any order you want, whereas with attribute schemes
you have to process in a begin to end fashion.</li>
<li>You do not have to worry about backtracking and action side effects that
may occur with an ambiguous grammar.</li>
</ul>
<p> <b>Example</b></p>
<p> Now that you think you may want to use trees, I'll give an example of how
to use them and you can see how easy they are to use. So, following with tradition
(and the rest of the documentation) we'll do a calculator. Here's the grammar:</p>
<pre> <code><span class="identifier">integer </span><span class="special">
= </span><span class="identifier">lexeme_d</span><span class="special">[ </span><span class="identifier"><font color="#ff0000"><b>token_node_d</b></font></span><span class="special">[ (!</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">) >> +</span><span class="identifier">digit_p</span><span class="special">) ] ]<br> ;<br><br> </span><span class="identifier">factor<br> </span><span class="special">= </span><span class="identifier">integer<br> </span><span class="special">| </span><span class="literal">'(' </span><span class="special">>> </span><span class="identifier">expression </span><span class="special">>> </span><span class="literal">')'<br> </span><span class="special">| (</span><span class="literal">'-' </span><span class="special">>> </span><span class="identifier">factor</span><span class="special">)<br> ;<br><br> </span><span class="identifier">term<br> </span><span class="special">= </span><span class="identifier">factor </span><span class="special">
>> *( (</span><span class="literal">'*' </span><span class="special">>> </span><span class="identifier">factor</span><span class="special">)<br> | (</span><span class="literal">'/' </span><span class="special">>> </span><span class="identifier">factor</span><span class="special">)<br> )<br> ;<br><br> </span><span class="identifier">expression<br> </span><span class="special">= </span><span class="identifier">term<br> </span><span class="special">>> *( (</span><span class="literal">'+' </span><span class="special">>> </span><span class="identifier">term</span><span class="special">)<br> | (</span><span class="literal">'-' </span><span class="special">>> </span><span class="identifier">term</span><span class="special">)<br> )<br> ;</span></code></pre>
<p> Now, you'll notice the only thing different in this grammar is the <tt>token_node_d</tt>
directive. This causes the integer rule to group all the input into one node.
Without <tt>token_node_d</tt>, each character would get it's own node. As you'll
soon see, it's easier to convert the input into an int when all the characters
are in one node. Here is how the parse is done to create a tree:</p>
<pre> <code><span class="identifier">tree_parse_info</span><span class="special"><> </span><span class="identifier">info </span><span class="special">= </span><span class="identifier"><font color="#ff0000"><b>pt_parse</b></font></span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">expression</span><span class="special">);</span></code></pre>
<p> <tt>pt_parse()</tt> is similar to <tt>parse()</tt>, there are a total of four.
Two for pairs of first and last iterators and two for character strings. Two
of the functions take a skipper parser and the other two do not.</p>
<p> The <tt>tree_parse_info</tt> struct contains the same information as a <tt>parse_info</tt>
struct as well as one extra data member called trees. When the parse finishes,
trees will contain the parse tree.</p>
<p> Here is how you can use the tree to evaluate the input:</p>
<pre> <code><span class="keyword">if </span><span class="special">(</span><span class="identifier">info</span><span class="special">.</span><span class="identifier">full</span><span class="special">)<br> {<br> </span><span class="identifier">cout </span><span class="special"><< </span><span class="string">"parsing succeeded\n"</span><span class="special">;<br> </span><span class="identifier">cout </span><span class="special"><< </span><span class="string">"result = " </span><span class="special"><< </span><span class="identifier"><font color="#ff0000"><b>evaluate</b></font></span><span class="special">(</span><span class="identifier">info</span><span class="special">) << </span><span class="string">"\n\n"</span><span class="special">;<br> }</span></code></pre>
<p> Now you ask, where did <tt>evaluate()</tt> come from? Is it part of spirit?
Unfortunately, no, <tt>evaluate()</tt> is only a part of the sample. Here it
is:</p>
<pre> <code><span class="keyword">long </span><span class="identifier">evaluate</span><span class="special">(</span><span class="keyword">const </span><span class="identifier">tree_parse_info</span><span class="special"><>& </span><span class="identifier">info</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">info</span><span class="special">.</span><span class="identifier">trees</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br> </span><span class="special">}</span></code></pre>
<p> So here you see evaluate() simply calls <tt>eval_expression()</tt> passing
the begin() iterator of info.trees. Now here's the rest of the example:</p>
<pre> <code><span class="comment">// Here's some typedefs to simplify things<br> </span><span class="keyword">typedef </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">iterator_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">parse_tree_match</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">> </span><span class="identifier">parse_tree_match_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">parse_tree_match_t</span><span class="special">::</span><span class="identifier">const_tree_iterator </span><span class="identifier">iter_t</span><span class="special">;<br><br> </span><span class="comment">// Here's the function prototypes that we'll use. One function for each<br> </span><span class="identifier">grammar </span><span class="identifier">rule</span><span class="special">.<br> </span><span class="keyword">long </span><span class="identifier">evaluate</span><span class="special">(</span><span class="keyword">const </span><span class="identifier">tree_parse_info</span><span class="special"><>& </span><span class="identifier">info</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_factor</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_integer</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br><br> </span><span class="comment">// i should be pointing to a node created by the expression rule<br> </span><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// first child points to a term, so call eval_term on it<br> </span><span class="identifier">iter_t </span><span class="identifier">chi </span><span class="special">= </span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();<br> </span><span class="keyword">long </span><span class="identifier">lhs </span><span class="special">= </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">chi</span><span class="special">);<br> </span><span class="keyword">for </span><span class="special">(++</span><span class="identifier">chi</span><span class="special">; </span><span class="identifier">chi </span><span class="special">!= </span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">end</span><span class="special">(); </span><span class="special">++</span><span class="identifier">chi</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// next node points to the operator. The text of the operator is<br> // stored in value (a vector<char>)<br> </span><span class="keyword">char </span><span class="identifier">op </span><span class="special">= </span><span class="special">*(</span><span class="identifier">chi</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br> </span><span class="special">++</span><span class="identifier">chi</span><span class="special">;<br> </span><span class="keyword">long </span><span class="identifier">rhs </span><span class="special">= </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">chi</span><span class="special">);<br> </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">op </span><span class="special">== </span><span class="literal">'+'</span><span class="special">)<br> </span><span class="identifier">lhs </span><span class="special">+= </span><span class="identifier">rhs</span><span class="special">;<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">op </span><span class="special">== </span><span class="literal">'-'</span><span class="special">)<br> </span><span class="identifier">lhs </span><span class="special">-= </span><span class="identifier">rhs</span><span class="special">;<br> </span><span class="keyword">else<br> </span><span class="identifier">assert</span><span class="special">(</span><span class="number">0</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="keyword">return </span><span class="identifier">lhs</span><span class="special">;<br> </span><span class="special">}<br><br> </span><span class="keyword">long </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// ... see parse_tree_calc1.cpp for complete example<br> // (it's rather similar to eval_expression() ) ...<br> </span><span class="special">}<br><br> </span><span class="keyword">long </span><span class="identifier">eval_factor</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// ... again, see parse_tree_calc1.cpp if you want all the details ...<br> </span><span class="special">}<br><br> </span><span class="keyword">long </span><span class="identifier">eval_integer</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// use the range constructor for a string<br> </span><span class="identifier">string </span><span class="identifier">integer</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(), </span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">end</span><span class="special">());<br> </span><span class="comment">// convert the string to an integer<br> </span><span class="keyword">return </span><span class="identifier">strtol</span><span class="special">(</span><span class="identifier">integer</span><span class="special">.</span><span class="identifier">c_str</span><span class="special">(), </span><span class="number">0</span><span class="special">, </span><span class="number">10</span><span class="special">);<br> </span><span class="special">}<br></span></code></pre>
<p> So, you like what you see, but maybe you think that the parse tree is too
hard to process? With a few more directives you can generate an abstract syntax
tree (ast) and cut the amount of evaluation code by at least <b>50%</b>. So
without any delay, here's the ast calculator grammar:</p>
<pre> <code><span class="identifier">integer<br> </span><span class="special">= </span><span class="identifier">leaf_node_d</span><span class="special">[ </span><span class="identifier">lexeme_d</span><span class="special">[ (!</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">) >> +</span><span class="identifier">digit_p</span><span class="special">) ] ]<br> ;<br><br> </span><span class="identifier">factor<br> </span><span class="special">= </span><span class="identifier">integer<br> </span><span class="special">| </span><span class="identifier"><font color="#ff0000"><b>inner_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'('</span><span class="special">) >> </span><span class="identifier">expression </span><span class="special">>> </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">')'</span><span class="special">)]<br> | (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">)] >> </span><span class="identifier">factor</span><span class="special">)<br> ;<br><br> </span><span class="identifier">term<br> </span><span class="special">= </span><span class="identifier">factor </span><span class="special">
>> *( (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'*'</span><span class="special">)] >> </span><span class="identifier">factor</span><span class="special">)<br> | (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'/'</span><span class="special">)] >> </span><span class="identifier">factor</span><span class="special">)<br> )<br> ;<br><br> </span><span class="identifier">expression<br> </span><span class="special">= </span><span class="identifier">term<br> </span><span class="special">>> *( (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'+'</span><span class="special">)] >> </span><span class="identifier">term</span><span class="special">)<br> | (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">)] >> </span><span class="identifier">term</span><span class="special">)<br> )<br> ;</span></code></pre>
<p> The differences from the parse tree grammar are hi-lighted in <b><font color="#ff0000">bold-red</font></b>.
The <tt>inner_node_d</tt> directive causes the first and last nodes generated
by the enclosed parser to be discarded, since we don't really care about the
parentheses when evaluating the expression. The <tt>root_node_d</tt> directive
is the key to ast generation. A node that is generated by the parser inside
of <tt>root_node_d</tt> is marked as a root node. When a root node is created,
it becomes a root or parent node of the other nodes generated by the same rule.</p>
<p> To start the parse and generate the ast, you must use the ast_parse functions,
which are similar to the pt_parse functions.</p>
<pre> <code><span class="identifier">tree_parse_info</span><span class="special"><> </span><span class="identifier">info </span><span class="special">= </span><span class="identifier">ast_parse</span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">expression</span><span class="special">);</span></code></pre>
<p> Here is the eval_expression function (note that to process the ast we only
need one function instead of four):</p>
<pre> <code><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">integer</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="comment">// convert string to integer<br> </span><span class="identifier">string </span><span class="identifier">integer</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(), </span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">end</span><span class="special">());<br> </span><span class="keyword">return </span><span class="identifier">strtol</span><span class="special">(</span><span class="identifier">integer</span><span class="special">.</span><span class="identifier">c_str</span><span class="special">(), </span><span class="number">0</span><span class="special">, </span><span class="number">10</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">factor</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="comment">// factor can only be unary minus<br> </span><span class="keyword">return </span><span class="special">- </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">term</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'*'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">*<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'/'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">/<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">expression</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'+'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">+<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'-'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">-<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="special">}<br><br> </span><span class="keyword">return </span><span class="number">0</span><span class="special">;<br> </span><span class="special">}<br></span></code></pre>
<p> An entire working example is ast_calc.cpp (in libs/spirit/example/fundamental/calc
directory). Hopefully this example has been enough to whet your appetite for
trees. For more nitty-gritty details, keep on reading the rest of this chapter.</p>
<a name="usage"></a>
<h2>Usage</h2>
<a name="pt_parse"></a>
<h3>pt_parse</h3>
<p> To create a parse tree, you can call one of the four free functions:</p>
<pre> <code><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">SkipT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">><br> </span><span class="identifier">pt_parse</span><span class="special">(<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">first_</span><span class="special">,<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">last_</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">,<br> </span><span class="identifier">SkipT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">skip_</span><span class="special">);<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">><br> </span><span class="identifier">pt_parse</span><span class="special">(<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">first_</span><span class="special">,<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">last</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">);<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">CharT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">SkipT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">*><br> </span><span class="identifier">pt_parse</span><span class="special">(<br> </span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">str</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">,<br> </span><span class="identifier">SkipT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">skip</span><span class="special">);<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">CharT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">*><br> </span><span class="identifier">pt_parse</span><span class="special">(<br> </span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">str</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">);<br></span></code></pre>
<a name="ast_parse"></a>
<h3>ast_parse</h3>
<p> To create an abstract syntax tree (ast for short) you call one of the four
free functions:</p>
<pre> <code><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">SkipT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">><br> </span><span class="identifier">ast_parse</span><span class="special">(<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">first_</span><span class="special">,<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">last_</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">,<br> </span><span class="identifier">SkipT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">skip_</span><span class="special">);<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">><br> </span><span class="identifier">ast_parse</span><span class="special">(<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">first_</span><span class="special">,<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">last</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">);<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">CharT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">SkipT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">*><br> </span><span class="identifier">ast_parse</span><span class="special">(<br> </span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">str</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">,<br> </span><span class="identifier">SkipT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">skip</span><span class="special">);<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">CharT</span><span class="special">, </span><span class="keyword">typename </span><span class="identifier">ParserT</span><span class="special">><br> </span><span class="identifier">tree_parse_info</span><span class="special"><</span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">*><br> </span><span class="identifier">ast_parse</span><span class="special">(<br> </span><span class="identifier">CharT </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">str</span><span class="special">,<br> </span><span class="identifier">parser</span><span class="special"><</span><span class="identifier">ParserT</span><span class="special">> </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">parser</span><span class="special">);<br></span></code></pre>
<a name="tree_parse_info"></a>
<h3>tree_parse_info</h3>
<p> The <tt>tree_parse_info</tt> struct returned from pt_parse and ast_parse contains
information about the parse:</p>
<pre> <code><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*><br> </span><span class="keyword">struct </span><span class="identifier">tree_parse_info<br> </span><span class="special">{<br> </span><span class="identifier">IteratorT </span><span class="identifier">stop</span><span class="special">;<br> </span><span class="keyword">bool </span><span class="identifier">match</span><span class="special">;<br> </span><span class="keyword">bool </span><span class="identifier">full</span><span class="special">;<br> </span><span class="keyword">unsigned </span><span class="identifier">length</span><span class="special">;<br><br> </span><span class="keyword">typename </span><span class="identifier">tree_match</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">>::</span><span class="identifier">container_t </span><span class="identifier">trees</span><span class="special">;<br> </span><span class="special">};<br></span></code></pre>
<table width="90%" border="0" align="center">
<tbody><tr>
<td class="table_title" colspan="10"> tree_parse_info </td>
</tr>
<tr>
</tr><tr>
<td class="table_cells"><b>stop</b></td>
<td class="table_cells">points to the final parse position (i.e. parsing processed
the input up to this point).</td>
</tr>
<tr><td class="table_cells"><b>match</b></td>
<td class="table_cells">true if parsing is successful. This may be full (the
parser consumed all the input), or partial (the parser consumed only a portion
of the input.)</td>
</tr>
<tr><td class="table_cells"><b>full</b></td>
<td class="table_cells">true when we have a full match (when the parser consumed
all the input).</td>
</tr>
<tr><td class="table_cells"><b>length</b></td>
<td class="table_cells">The number of characters consumed by the parser. This
is valid only if we have a successful match (either partial or full).</td>
</tr>
<tr><td class="table_cells"><b>trees</b></td>
<td class="table_cells">Contains the root node(s) of the tree.</td>
</tr>
</tbody></table>
<a name="tree_match"></a>
<h3>tree_match</h3>
<p> When Spirit is generating a tree, the parser's parse() member function will
return a tree_match object, instead of a match object. tree_match has three
template parameters. The first is the Iterator type which defaults to <tt>char
const*</tt>. The second is the node factory, which defaults to <a href="#node_val_data_factory">node_val_data_factory</a>.
The third is the attribute type stored in the match. A tree_match has a member
variable which is a container (a <tt>std::vector</tt>) of <a href="#tree_node">tree_node</a>
objects named trees. For efficiency reasons, when a tree_match is copied, the
trees are <b>not</b> copied, they are moved to the new object, and the source
object is left with an empty tree container. tree_match supports the same interface
as the match class: it has an operator bool() so you can test it for a sucessful
match: if (matched), and you can query the match length via the length() function.
The class has this interface:</p>
<pre> <code><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*, </span><span class="keyword">typename </span><span class="identifier">NodeFactoryT </span><span class="special">= </span><span class="identifier">node_val_data_factory</span><span class="special"><> </span><span class="special">><br> </span><span class="keyword">struct </span><span class="identifier">tree_match<br> </span><span class="special">{<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">NodeFactoryT</span><span class="special">::</span><span class="keyword">template </span><span class="identifier">factory</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">> </span><span class="identifier">node_factory_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">node_factory_t</span><span class="special">::</span><span class="identifier">node_t </span><span class="identifier">parse_node_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_node</span><span class="special"><</span><span class="identifier">parse_node_t</span><span class="special">> </span><span class="identifier">node_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">node_t</span><span class="special">::</span><span class="identifier">children_t </span><span class="identifier">container_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">tree_iterator</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_tree_iterator</span><span class="special">;<br><br> </span><span class="identifier">tree_match</span><span class="special">();<br> </span><span class="identifier">tree_match</span><span class="special">(</span><span class="keyword">unsigned </span><span class="identifier">length</span><span class="special">, </span><span class="identifier">parse_node_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">n</span><span class="special">);<br> </span><span class="identifier">tree_match</span><span class="special">(</span><span class="identifier">tree_match </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="keyword">explicit </span><span class="identifier">tree_match</span><span class="special">(</span><span class="identifier">match </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="identifier">tree_match</span><span class="special">& </span><span class="keyword">operator</span><span class="special">=(</span><span class="identifier">tree_match </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">tree_match</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="keyword">operator </span><span class="keyword">bool</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">int </span><span class="identifier">length</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br><br> </span><span class="identifier">container_t </span><span class="identifier">trees</span><span class="special">;<br> </span><span class="special">};</span></code></pre>
<p> When a parse has sucessfully completed, the trees data member will contain
the root node of the tree. </p>
<table width="80%" border="0" align="center">
<tbody><tr>
<td class="note_box"><img src="theme/lens.gif" width="15" height="16"> <b>vector?</b><br>
<br>
You may wonder, why is it a vector then? The answer is that it is partly
for implementation purposes, and also if you do not use any rules in your
grammar, then trees will contain a sequence of nodes that will not have
any children.</td>
</tr>
</tbody></table>
<p> Having spirit create a tree is similar to how a normal parse is done:</p>
<pre> <code><span class="identifier">tree_match</span><span class="special"><> </span><span class="identifier">hit </span><span class="special">= </span><span class="identifier">expression</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">tree_scanner</span><span class="special">);<br><br> </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">hit</span><span class="special">)<br> </span><span class="identifier">process_tree_root</span><span class="special">(</span><span class="identifier">hit</span><span class="special">.</span><span class="identifier">trees</span><span class="special">[</span><span class="number">0</span><span class="special">]); </span><span class="comment">// do something with the tree</span></code></pre>
<a name="tree_node"></a>
<h3>tree_node</h3>
<p> Once you have created a tree by calling <a href="#pt_parse">pt_parse</a>
or <a href="#ast_parse">ast_parse</a>, you have a <a href="#tree_parse_info">tree_parse_info</a>
which contains the root node of the tree, and now you need to do something with
the tree. The data member trees of <a href="#tree_parse_info">tree_parse_info</a>
is a std::vector<tree_node>. tree_node provides the tree structure. The
class has one template parameter named T. tree_node contains an instance of
type T. It also contains a std::vector<tree_node<T> > which are
the node's children. The class looks like this:</p>
<pre> <code><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">T</span><span class="special">><br> </span><span class="keyword">struct </span><span class="identifier">tree_node<br> </span><span class="special">{<br> </span><span class="keyword">typedef </span><span class="identifier">T </span><span class="identifier">parse_node_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">tree_node</span><span class="special"><</span><span class="identifier">T</span><span class="special">> </span><span class="special">> </span><span class="identifier">children_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">children_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">tree_iterator</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">children_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_tree_iterator</span><span class="special">;<br><br> </span><span class="identifier">T </span><span class="identifier">value</span><span class="special">;<br> </span><span class="identifier">children_t </span><span class="identifier">children</span><span class="special">;<br><br> </span><span class="identifier">tree_node</span><span class="special">();<br> </span><span class="keyword">explicit </span><span class="identifier">tree_node</span><span class="special">(</span><span class="identifier">T </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">v</span><span class="special">);<br> </span><span class="identifier">tree_node</span><span class="special">(</span><span class="identifier">T </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">v</span><span class="special">, </span><span class="identifier">children_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">c</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">tree_node</span><span class="special"><</span><span class="identifier">T</span><span class="special">>& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="special">};</span></code></pre>
<p> This class is simply used to separate the tree framework from the data stored
in the tree. It is a generic node and any type can be stored inside it and acessed
via the data member value. The default type for T is <tt>node_val_data</tt>.</p>
<a name="node_val_data"></a>
<h3>node_val_data</h3>
<p> The <tt>node_val_data</tt> class contains the actual information about each
node. This includes the text or token sequence that was parsed, an <tt>id</tt>
that indicates which rule created the node, a boolean flag that indicates whether
the node was marked as a root node, and an optional user-specified value. This
is the interface:</p>
<pre> <code><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*, </span><span class="keyword">typename </span><span class="identifier">ValueT </span><span class="special">= </span><span class="identifier">nil_t</span><span class="special">><br> </span><span class="keyword">struct </span><span class="identifier">node_val_data<br> </span><span class="special">{<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">>::</span><span class="identifier">value_type </span><span class="identifier">value_type</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">value_type</span><span class="special">> </span><span class="identifier">container_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">iterator_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_iterator_t</span><span class="special">;<br><br> </span><span class="identifier">node_val_data</span><span class="special">();<br> </span><span class="identifier">node_val_data</span><span class="special">(</span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_last</span><span class="special">);<br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT2</span><span class="special">><br> </span><span class="identifier">node_val_data</span><span class="special">(</span><span class="identifier">IteratorT2 </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT2 </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_last</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">node_val_data</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br><br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">begin</span><span class="special">();<br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">begin</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">end</span><span class="special">();<br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">end</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br><br> </span><span class="keyword">bool </span><span class="identifier">is_root</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">is_root</span><span class="special">(</span><span class="keyword">bool </span><span class="identifier">b</span><span class="special">);<br><br> </span><span class="identifier">parser_id </span><span class="identifier">id</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">id</span><span class="special">(</span><span class="identifier">parser_id </span><span class="identifier">r</span><span class="special">);<br><br> </span><span class="identifier">ValueT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">value</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">value</span><span class="special">(</span><span class="identifier">ValueT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">v</span><span class="special">);<br> </span><span class="special">};<br></span></code></pre>
<a name="parser_id__checking_and_setting"></a>
<h3>parser_id, checking and setting</h3>
<p> If a node is generated by a rule, it will have an <tt>id</tt> set. Each rule
has an id that it sets of all nodes generated by that rule. The id is of type
<tt>parser_id</tt>. The default id of each rule is set to the address of that
rule (converted to an integer). This is not always the most convenient, since
the code that processes the tree may not have access to the rules, and may not
be able to compare addresses. So, you can override the default id used by each
rule by calling <tt>set_id(parser_id)</tt> on a rule. Then, when processing
the tree you can call <tt>node_val_data::id()</tt> to see which rule created
that node.</p>
<a name="structure_layout_of_a_parse_tree"></a>
<h2>structure/layout of a parse tree</h2>
<a name="parse_tree_layout"></a>
<h3>parse tree layout</h3>
<p> The tree is organized by the rules. Each rule creates a new level in the tree.
All parsers attached to a rule create a node when a sucessful match is made.
These nodes become children of a node created by the rule. So, the following
code:</p>
<pre> <code><span class="identifier">rule_t </span><span class="identifier">myrule </span><span class="special">= </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'a'</span><span class="special">) </span><span class="special">>> </span><span class="literal">',' </span><span class="special">>> </span><span class="special">*</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'b'</span><span class="special">);<br> </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">input </span><span class="special">= </span><span class="string">"a,bb"</span><span class="special">;<br> </span><span class="identifier">scanner_t </span><span class="identifier">scanner</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">input </span><span class="special">+ </span><span class="identifier">strlen</span><span class="special">(</span><span class="identifier">input</span><span class="special">));<br> </span><span class="identifier">tree_match</span><span class="special"><> </span><span class="identifier">m </span><span class="special">= </span><span class="identifier">myrule</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">scanner</span><span class="special">);<br></span></code></pre>
<p> When executed, this code would return a tree_match, m. <tt>m.trees[0]</tt>
would contain a tree like this:</p>
<table border="0" align="center">
<tbody><tr>
<td><img src="theme/trees1.png" width="253" height="151"></td>
</tr>
</tbody></table>
<p> The root node would not contain any text, and it's id would be set to the
address of myrule. It would have four children. Each child's id would be set
to the address of myrule, would contain the text as shown in the diagram, and
would have no children.</p>
<a name="ast_layout"></a>
<h2>ast layout</h2>
<p> When calling <a href="#ast_parse">ast_parse</a>, the tree gets generated differently.
It mostly works the same as when generating a parse tree. The difference happens
when a rule only generated one sub-node. Instead of creating a new level, <a href="#ast_parse">ast_parse</a>
will not create a new level, it will just leave the existing node. So, this
code:</p>
<pre> <code><span class="identifier">rule_t </span><span class="identifier">myrule </span><span class="special">= </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'a'</span><span class="special">);<br> </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">input </span><span class="special">= </span><span class="string">"a"</span><span class="special">;<br> </span><span class="identifier">ast_scanner_t </span><span class="identifier">scanner</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">input</span><span class="special">+</span><span class="identifier">strlen</span><span class="special">(</span><span class="identifier">input</span><span class="special">));<br> </span><span class="identifier">tree_match</span><span class="special"><> </span><span class="identifier">m </span><span class="special">= </span><span class="identifier">myrule</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">scanner</span><span class="special">);<br></span></code></pre>
<p> will generate a single node that contains 'a'. If <tt>tree_match_policy</tt>
had been used instead of <tt>ast_match_policy</tt>, the tree would have looked
like this:</p>
<table border="0" align="center">
<tbody><tr>
<td><img src="theme/trees2.png" width="139" height="151"></td>
</tr>
</tbody></table>
<p> ast_match_policy has the effect of eliminating intermediate rule levels which
are simply pass-through rules. This is not enough to generate abstract syntax
trees, <a href="#root_node">root_node_d</a> is also needed. <a href="#root_node">root_node_d</a>
will be explained later.</p>
<a name="switching__gen_pt_node_d____amp__gen_ast_node_d__"></a>
<h2>switching: gen_pt_node_d[] & gen_ast_node_d[]</h2>
<p> If you want to mix and match the parse tree and ast behaviors in your application,
you can use the <tt>gen_pt_node_d[]</tt> and <tt>gen_ast_node_d[]</tt> directives.
When parsing passes through the <tt>gen_pt_node_d</tt> directive, parse tree
creation behavior is turned on. When the <tt>gen_ast_node_d</tt>
directive is used, the enclosed parser will generate a tree using the
ast behavior. Note that you must pay attention to how your rules are declared
if you use a rule inside of these directives. The match policy of
the scanner will have to correspond to the desired behavior. If you
avoid rules and use primitive parsers or grammars, then you will not have
problems.</p>
<a name="directives"></a>
<h2>Directives</h2>
<p> There are a few more directives that can be used to control the generation
of trees. These directives only effect tree generation. Otherwise, they have
no effect.<br>
</p>
<a name="no_node_d"></a>
<h3>no_node_d</h3>
<p> This directive is similar to <tt>gen_pt_node_d</tt> and <tt>gen_ast_node_d</tt>,
in that is modifies the scanner's match policy used by the enclosed parser. As it's name
implies, it does no tree generation, it turns it off completely. This is useful
if there are parts of your grammar which are not needed in the tree. For instance:
keywords, operators (<tt>*</tt>, <tt>-</tt>, <tt>&&</tt>, etc.) By eliminating
these from the tree, both memory usage and parsing time can be lowered. This
directive has the same requirements with respect to rules as <tt>gen_pt_node_d</tt>
and <tt>gen_ast_node_d</tt> do. See the example file xml_grammar.hpp (in libs/spirit/example/application/xml
directory) for example
usage of <tt>no_node_d[]</tt>.</p>
<a name="discard_node_d"></a>
<h3>discard_node_d</h3>
<p> This directive has a similar purpose to <tt>no_node_d</tt>, but works differently.
It does not switch the scanner's match policy, so the enclosed parser still generates
nodes. The generated nodes are discarded and do not appear in the tree. Using
<tt>discard_node_d</tt> is slower than <tt>no_node_d</tt>, but it does not suffer
from the drawback of having to specify a different rule type for any rule inside
it.</p>
<a name="leaf_node_d_token_node_d"></a>
<h3>leaf_node_d/token_node_d</h3>
<p> Both <tt>leaf_node_d</tt> and <tt>token_node_d</tt> work the same. They group
together all the nodes generated by the enclosed parser. Note that a rule should
not be used inside these directives.</p>
<p> This rule:</p>
<pre> <code><span class="identifier">rule_t </span><span class="identifier">integer </span><span class="special">= </span><span class="special">!</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">) </span><span class="special">>> </span><span class="special">*(</span><span class="identifier">range_p</span><span class="special">(</span><span class="literal">'0'</span><span class="special">, </span><span class="literal">'9'</span><span class="special">));</span></code></pre>
<p> would generate a root node with the id of integer and a child node for each
character parsed</p>
<p> This:</p>
<pre> <code><span class="identifier">rule_t </span><span class="identifier">integer </span><span class="special">= </span><span class="identifier">token_node_d</span><span class="special">[ </span><span class="special">!</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">) </span><span class="special">>> </span><span class="special">*(</span><span class="identifier">range_p</span><span class="special">(</span><span class="literal">'0'</span><span class="special">, </span><span class="literal">'9'</span><span class="special">)) </span><span class="special">];</span></code></pre>
<p> would generate a root node with only one child node that contained the entire
integer.</p>
<a name="infix_node_d"></a>
<h3>infix_node_d</h3>
<p> This is useful for removing separators from lists. It discards all the nodes
in even positions. Thus this rule:</p>
<pre> <code><span class="identifier">rule_t </span><span class="identifier">intlist </span><span class="special">= </span><span class="identifier">infix_node_d</span><span class="special">[ </span><span class="identifier">integer </span><span class="special">>> </span><span class="special">*(</span><span class="literal">',' </span><span class="special">>> </span><span class="identifier">integer</span><span class="special">) </span><span class="special">];</span></code></pre>
<p> would discard all the comma nodes and keep all the integer nodes.</p>
<a name="discard_first_node_d"></a>
<h3>discard_first_node_d</h3>
<p> This discards the first node generated.</p>
<a name="discard_last_node_d"></a>
<h3>discard_last_node_d</h3>
<p> This discards the last node generated.</p>
<a name="inner_node_d"></a>
<h3>inner_node_d</h3>
<p> This discards the first and last node generated.</p>
<a name="root_node_d_and_ast_generation"></a>
<h2>root_node_d and ast generation</h2>
<p> The <tt>root_node_d</tt> directive is used to help out ast generation. It
has no effect when generating a parse tree. When a parser is enclosed in <tt>root_node_d</tt>,
the node it generates is marked as a root. This affects the way it is treated
when it's added to the list of nodes being generated. Here's an example:</p>
<pre> <code><span class="identifier">rule_t </span><span class="identifier">add </span><span class="special">= </span><span class="identifier">integer </span><span class="special">>> </span><span class="special">*(</span><span class="identifier">root_node_d</span><span class="special">[ </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'+'</span><span class="special">) </span><span class="special">] </span><span class="special">>> </span><span class="identifier">integer</span><span class="special">);</span></code></pre>
<p> When parsing 5+6 the following tree will be generated:</p>
<table border="0" align="center">
<tbody><tr>
<td><img src="theme/trees3.png"></td>
</tr>
</tbody></table>
<p> When parsing 1+2+3 the following will be generated:</p>
<table border="0" align="center">
<tbody><tr>
<td><img src="theme/trees4.png"></td>
</tr>
</tbody></table>
<p> When a new node is created the following rules are used to determine how the
tree will be generated:</p>
<pre><code> Let a be the previously generated node. <br> Let b be the new node.<br><br> If b is a root node then<br><br> b's children become a + b's previous children. <br> a is the new first child of b.<br><br> else if a is a root node and b is not, then<br><br> b becomes the last child of a.<br><br> else<br><br> a and b become siblings.</code></pre>
<p> After parsing leaves the current rule, the root node flag on the top node
is turned off. This means that the root_node_d directive only affects the current
rule.</p>
<p> The example ast_calc.cpp (in libs/spirit/example/fundamental/calc
directory) demonstrates the use of root_node_d and <a href="#ast_parse">ast_parse</a>.<br>
</p>
<a name="parse_tree_iterator"></a>
<h2>parse_tree_iterator</h2>
<p> The <tt>parse_tree_iterator</tt> class allows you to parse a tree using spirit.
The class iterates over the tokens in the leaf nodes in the same order they
were created. The <tt>parse_tree_iterator</tt> is templated on <tt>ParseTreeMatchT</tt>.
It is constructed with a container of trees, and a position to start. Here is
an example usage:</p>
<pre> <code><span class="identifier">rule_t </span><span class="identifier">myrule </span><span class="special">= </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'a'</span><span class="special">);<br> </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">input </span><span class="special">= </span><span class="string">"a"</span><span class="special">;<br><br> </span><span class="comment">// generate parse tree<br> </span><span class="identifier">tree_parse_info</span><span class="special"><> </span><span class="identifier">i </span><span class="special">= </span><span class="identifier">pt_parse</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">myrule</span><span class="special">);<br><br> </span><span class="keyword">typedef </span><span class="identifier">parse_tree_iterator</span><span class="special"><</span><span class="identifier">tree_match</span><span class="special"><> </span><span class="special">> </span><span class="identifier">parse_tree_iterator_t</span><span class="special">;<br><br> </span><span class="comment">// create a first and last iterator to work off the tree<br> </span><span class="identifier">parse_tree_iterator_t </span><span class="identifier">first</span><span class="special">(</span><span class="identifier">i</span><span class="special">.</span><span class="identifier">trees</span><span class="special">, </span><span class="identifier">i</span><span class="special">.</span><span class="identifier">trees</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br> </span><span class="identifier">parse_tree_iterator_t </span><span class="identifier">last</span><span class="special">();<br><br> </span><span class="comment">// parse the tree<br> </span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">parse_tree_iterator_t</span><span class="special">> </span><span class="identifier">tree_parser </span><span class="special">=...<br> </span><span class="identifier">tree_parser</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">last</span><span class="special">);<br></span></code></pre>
<p> For a concrete example of the usage of the parse_tree_iterator, see the cpp
example files: cpp_expression_grammar.cpp and cpp_macromap.cpp</p>
<a name="advanced_tree_generation"></a>
<h2>advanced tree generation</h2>
<a name="node_value"></a>
<h3>node value</h3>
<p> The <tt>node_val_data</tt> can contain a value. By default it contains a <tt>void_t</tt>,
which is an empty class. You can specify the type, using a template parameter,
which will then be stored in every node. The type must be default constructible,
and assignable. You can get and set the value using</p>
<pre> <code><span class="identifier">ValueT </span><span class="identifier">node_val_data</span><span class="special">::</span><span class="identifier">value</span><span class="special">();</span></code></pre>
<p> and</p>
<pre> <code><span class="keyword">void </span><span class="identifier">node_val_data</span><span class="special">::</span><span class="identifier">value</span><span class="special">(</span><span class="identifier">Value </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">value</span><span class="special">);</span></code></pre>
<p> In order to specify the value type, you must use a different <a href="#node_val_data">node_val_data
</a>factory than the default. Since the <tt>node_val_data</tt> factory is a
template parameter to the scanner match policy, you must use a custom scanner.
Since <tt>pt_parse</tt> and <tt>ast_parse</tt> use preconfigured scanners,
you must specify your own. Here's an example of how to store and access a double in each node_val_data.</p>
<pre> <code><span class="keyword">typedef </span><span class="identifier">node_val_data_factory</span><span class="special"><</span><span class="keyword">double</span><span class="special">> </span><span class="identifier">factory_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">ast_match_policy</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_policy_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">scanner</span><span class="special"><</span><span class="identifier">iterator_t</span></code><code><span class="identifier"></span><span class="special">,</span></code><code><span class="identifier"> scanner_policies</span></code><code><span class="special"><</span></code><code><span class="identifier">iter_policy_t</span></code><code><span class="identifier"></span><span class="special">,</span></code><code><span class="identifier"> match_policy_t</span><span class="special"></span></code><code><span class="special">></span></code><code><span class="special"> ></span></code><code><span class="special"> </span><span class="identifier">scanner_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">> </span><span class="identifier">rule_t</span><span class="special">;<br><br> </span><span class="identifier">rule_t </span><span class="identifier">r </span><span class="special">=...;<br><br></span></code><code><span class="special"> </span><span class="identifier">scanner_t </span><span class="identifier">scan </span><span class="special">= </span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">last</span><span class="special"></span><span class="identifier"></span><span class="special">);<br></span></code><code><span class="special"> </span><span class="identifier">match_t </span><span class="identifier">hit </span><span class="special">= </span><span class="identifier">r</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier"></span><span class="special"></span><span class="identifier"></span><span class="special"></span><span class="identifier">scan</span><span class="special">);<br><br> </span><span class="comment">// access the double in the root node:<br> </span><span class="keyword">double </span><span class="identifier">d </span><span class="special">= </span><span class="identifier">hit</span><span class="special">.</span><span class="identifier">trees</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">value</span><span class="special">();</span></code></pre>
<a name="access_node_d"></a>
<h3>access_node_d</h3>
<p> Now, you may be wondering, "What good does it do to have a value I can
store in each node, but I don't have any way of setting it?" Well, that's
what <tt>access_node_d</tt> is for. <tt>access_node_d</tt> is a directive. It
allows you to attach an action to it, like this:</p>
<pre> <code><span class="identifier">access_node</span><span class="special">[...</span><span class="identifier">some </span><span class="identifier">parsers</span><span class="special">...][</span><span class="identifier">my_action</span><span class="special">()]</span></code></pre>
<p> The attached action will be passed 3 parameters: A reference to the root node
of the tree generated by the parser, and the current first and last iterators.
The action can set the value stored in the node.</p>
<a name="tree_node_factories"></a>
<h3>Tree node factories</h3>
<p> By setting the factory, you can control what type of nodes are created and
how they are created. There are 3 predefined factories: <tt>node_val_data_factory</tt>,
<tt>node_all_val_data_factory</tt>, and <tt>node_iter_data_factory</tt>. You
can also create your own factory to support your own node types.</p>
<p> Here's an example of how to use a factory:</p>
<pre> <code><span class="keyword">typedef </span><span class="identifier">spirit</span><span class="special">::</span><span class="identifier">void_t </span><span class="identifier">value_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">node_val_data_factory</span><span class="special"><</span><span class="identifier">value_t</span><span class="special">> </span><span class="identifier">factory_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">ast_match_policy</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_policy_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">scanner</span><span class="special"><</span><span class="identifier">iterator_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> scanner_policies</span></code><code><span class="identifier"></span><span class="special"><</span></code><code><span class="identifier">iter_policy_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> match_policy_t</span><span class="special">></span></code><code><span class="identifier"></span><span class="special"> ></span></code><code><span class="special"> </span><span class="identifier">scanner_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">> </span><span class="identifier">rule_t</span><span class="special">;<br><br> </span><span class="identifier">rule_t </span><span class="identifier">r </span><span class="special">=...;<br><br></span></code><code><span class="special"> </span><span class="identifier">scanner_t </span><span class="identifier">scan </span><span class="special">= </span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">last</span><span class="special"></span><span class="identifier"></span><span class="special">);<br></span></code><code><span class="special"></span></code><code><span class="special"> </span><span class="identifier">match_t </span><span class="identifier">hit </span><span class="special">= </span><span class="identifier">r</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier"></span><span class="special"></span><span class="identifier"></span><span class="special"></span><span class="identifier">scan</span><span class="special">);</span></code></pre>
<a name="node_val_data_factory"></a>
<h3>node_val_data_factory</h3>
<p> This is the default factory. It creates <tt>node_val_data</tt> nodes. Leaf
nodes contain a copy of the matched text, and intermediate nodes don't. <tt>node_val_data_factory</tt>
has one template parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type
of value that will be stored in the <tt>node_val_data</tt>.</p>
<a name="node_val_data_factory"></a>
<h3>node_all_val_data_factory</h3>
<p> This factory also creates <tt>node_val_data</tt>. The difference between it
and <tt>node_val_data_factory</tt> is that <b>every</b> node contains all the
text that spans it. This means that the root node will contain a copy of the
entire parsed input sequence. <tt>node_all_val_data_factory</tt> has one template
parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type of value that
will be stored in the <tt>node_val_data</tt>.</p>
<a name="node_iter_data_factory"></a>
<h3>node_iter_data_factory</h3>
<p> This factory creates the <tt>parse_tree_iter_node</tt>. This node stores iterators
into the input sequence instead of making a copy. It can use a lot less memory.
However, the input sequence must stay valid for the life of the tree, and it's
not a good idea to use the <tt>multi_pass</tt> iterator with this type of node.
All levels of the tree will contain a begin and end iterator. <tt>node_iter_data_factory</tt>
has one template parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type
of value that will be stored in the node_val_data.</p>
<a name="custom"></a>
<h3>custom</h3>
<p> You can create your own factory. It should look like this:</p>
<pre> <code><span class="keyword">class </span><span class="identifier">my_factory<br> </span><span class="special">{<br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="comment">// This inner class is so that the factory can simulate<br> // a template template parameter<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">><br> </span><span class="keyword">class </span><span class="identifier">factory<br> </span><span class="special">{<br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="comment">// This is your node type<br> </span><span class="keyword">typedef </span><span class="identifier">my_node_type </span><span class="identifier">node_t</span><span class="special">;<br><br> </span><span class="keyword">static </span><span class="identifier">node_t </span><span class="identifier">create_node</span><span class="special">(<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">last</span><span class="special">, </span><span class="keyword">bool </span><span class="identifier">is_leaf_node</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// create a node and return it.<br> </span><span class="special">}<br><br> </span><span class="comment">// This function is used by the leaf_node and token_node directives.<br> // If you don't use them, then you can leave this function<br> // unimplemented.<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">ContainerT</span><span class="special">><br> </span><span class="keyword">static </span><span class="identifier">node_t </span><span class="identifier">group_nodes</span><span class="special">(</span><span class="identifier">ContainerT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">nodes</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// Group all the nodes into one and return it.<br> </span><span class="special">}<br> </span><span class="special">};<br> </span><span class="special">};<br><br><br> </span><span class="comment">// Typedefs to use my_factory<br> </span><span class="keyword">typedef </span><span class="identifier">my_factory </span><span class="identifier">factory_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_match_policy</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_policy_t</span><span class="special">;<br></span></code><code><span class="special"><br> </span><span class="comment">// Typedefs if you are using rules instead of grammars<br></span></code><code><span class="special"> </span><span class="keyword">typedef </span><span class="identifier">scanner</span><span class="special"><</span><span class="identifier">iterator_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> scanner_policies</span></code><code><span class="identifier"></span><span class="special"><</span></code><code><span class="identifier">iter_policy_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> match_policy_t</span><span class="special">></span></code><code><span class="identifier"></span><span class="special"> ></span></code><code><span class="special"> </span><span class="identifier">scanner_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">> </span><span class="identifier">rule_t</span><span class="special">;<br></span></code><code><span class="special"></span><span class="special"><br></span></code></pre><table border="0"><tbody><tr><td width="10"><br>
</td>
<td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
<td width="30"><a href="symbols.html"><img src="theme/l_arr.gif" border="0"></a></td>
<td width="20"><a href="multi_pass.html"><img src="theme/r_arr.gif" border="0"></a></td>
</tr>
</tbody></table>
<hr size="1">
<p class="copyright">Copyright © 2001-2002 Daniel C. Nuffer<br>
<br>
<font size="2">Permission to copy, use, modify, sell and distribute this document
is granted provided this copyright notice appears in all copies. This document
is provided "as is" without express or implied warranty, and with
no claim as to its suitability for any purpose.</font></p>
<p class="copyright"> </p>
<br>
</body></html>
