Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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

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

updated boost from 1_33_1 to 1_34_1
File size: 94.4 KB
RevLine 
[29]1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title>Trees</title>
2
3<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
4<link rel="stylesheet" href="theme/style.css" type="text/css"></head>
5<body>
6<table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2">
7  <tbody><tr>
8    <td width="10">
9    <br>
10</td>
11    <td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Trees</b></font>
12    </td>
13    <td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td>
14  </tr>
15</tbody></table>
16<br>
17<table border="0">
18  <tbody><tr>
19    <td width="10"><br>
20</td>
21    <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
22    <td width="30"><a href="symbols.html"><img src="theme/l_arr.gif" border="0"></a></td>
23    <td width="30"><a href="multi_pass.html"><img src="theme/r_arr.gif" border="0"></a></td>
24   </tr>
25</tbody></table>
26<h2>Why use parse trees</h2>
27<p> Parse trees are an in-memory representation of the input with a structure
28  that conforms to the grammar.</p>
29<p> The advantages of using parse trees instead of semantic actions:</p>
30<ul>
31  <li>You can make multiple passes over the data without having to re-parse the
32    input.</li>
33  <li>You can perform transformations on the tree.</li>
34  <li>You can evaluate things in any order you want, whereas with attribute schemes
35    you have to process in a begin to end fashion.</li>
36  <li>You do not have to worry about backtracking and action side effects that
37    may occur with an ambiguous grammar.</li>
38</ul>
39<p> <b>Example</b></p>
40<p> Now that you think you may want to use trees, I'll give an example of how
41  to use them and you can see how easy they are to use. So, following with tradition
42  (and the rest of the documentation) we'll do a calculator. Here's the grammar:</p>
43<pre>    <code><span class="identifier">integer </span><span class="special">
44        =   </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">) &gt;&gt; +</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">&gt;&gt; </span><span class="identifier">expression </span><span class="special">&gt;&gt; </span><span class="literal">')'<br>        </span><span class="special">|   (</span><span class="literal">'-' </span><span class="special">&gt;&gt; </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">
45            &gt;&gt; *(   (</span><span class="literal">'*' </span><span class="special">&gt;&gt; </span><span class="identifier">factor</span><span class="special">)<br>                |   (</span><span class="literal">'/' </span><span class="special">&gt;&gt; </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">&gt;&gt; *(   (</span><span class="literal">'+' </span><span class="special">&gt;&gt; </span><span class="identifier">term</span><span class="special">)<br>                |   (</span><span class="literal">'-' </span><span class="special">&gt;&gt; </span><span class="identifier">term</span><span class="special">)<br>                )<br>        ;</span></code></pre>
46<p> Now, you'll notice the only thing different in this grammar is the <tt>token_node_d</tt>
47  directive. This causes the integer rule to group all the input into one node.
48  Without <tt>token_node_d</tt>, each character would get it's own node. As you'll
49  soon see, it's easier to convert the input into an int when all the characters
50  are in one node. Here is how the parse is done to create a tree:</p>
51<pre>    <code><span class="identifier">tree_parse_info</span><span class="special">&lt;&gt; </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>
52<p> <tt>pt_parse()</tt> is similar to <tt>parse()</tt>. There are four overloads:
53  two for pairs of first and last iterators and two for character strings. Two
54  of the functions take a skipper parser and the other two do not.</p>
55<p> The <tt>tree_parse_info</tt> struct contains the same information as a <tt>parse_info</tt>
56  struct as well as one extra data member called trees. When the parse finishes,
57  trees will contain the parse tree.</p>
58<p> Here is how you can use the tree to evaluate the input:</p>
59<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">&lt;&lt; </span><span class="string">"parsing succeeded\n"</span><span class="special">;<br>        </span><span class="identifier">cout </span><span class="special">&lt;&lt; </span><span class="string">"result = " </span><span class="special">&lt;&lt; </span><span class="identifier"><font color="#ff0000"><b>evaluate</b></font></span><span class="special">(</span><span class="identifier">info</span><span class="special">) &lt;&lt; </span><span class="string">"\n\n"</span><span class="special">;<br>    }</span></code></pre>
60<p> Now you ask, where did <tt>evaluate()</tt> come from? Is it part of spirit?
61  Unfortunately, no, <tt>evaluate()</tt> is only a part of the sample. Here it
62  is:</p>
63<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">&lt;&gt;&amp; </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>
64<p> So here you see evaluate() simply calls <tt>eval_expression()</tt> passing
65  the begin() iterator of info.trees. Now here's the rest of the example:</p>
66<pre>    <code><span class="comment">// Here's some typedefs to simplify things<br>    </span><span class="keyword">typedef char 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">tree_match</span><span class="special">&lt;</span><span class="identifier">iterator_t</span><span class="special">&gt;             </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  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>    // grammar 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">&lt;&gt;&amp; </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">&amp; </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">&amp; </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">&amp; </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">&amp; </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">&amp; </span><span class="identifier">i</span><span class="special">)<br>    {<br>        </span><span class="comment">// first child points to a term, so call eval_term on it<br>        </span><span class="identifier">iter_t chi </span><span class="special">= </span><span class="identifier">i</span><span class="special">-&gt;</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">-&gt;</span><span class="identifier">children</span><span class="special">.</span><span class="identifier">end</span><span class="special">(); ++</span><span class="identifier">chi</span><span class="special">)<br>        {<br>            </span><span class="comment">// next node points to the operator.  The text of the operator is<br>            // stored in value (a vector&lt;char&gt;)<br>            </span><span class="keyword">char </span><span class="identifier">op </span><span class="special">= *(</span><span class="identifier">chi</span><span class="special">-&gt;</span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br>            ++</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 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>        }<br>        </span><span class="keyword">return </span><span class="identifier">lhs</span><span class="special">;<br>    }<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">&amp; </span><span class="identifier">i</span><span class="special">)<br>    {<br>        </span><span class="comment">//  ... see <a href="../example/fundamental/parse_tree_calc1.cpp">parse_tree_calc1.cpp</a> 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">&amp; </span><span class="identifier">i</span><span class="special">)<br>    {<br>        </span><span class="comment">//  ... again, see <a href="../example/fundamental/parse_tree_calc1.cpp">parse_tree_calc1.cpp</a> 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">&amp; </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">-&gt;</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">-&gt;</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>
67<p>  <img height="16" width="15" src="theme/lens.gif"> The full source code can be <a href="../example/fundamental/parse_tree_calc1.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
68<p>So, you like what you see, but maybe you think that the parse tree is too
69    hard to process? With a few more directives you can generate an abstract syntax
70    tree (ast) and cut the amount of evaluation code by at least <b>50%</b>. So
71    without any delay, here's the ast calculator grammar:</p>
72<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">) &gt;&gt; +</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">) &gt;&gt; </span><span class="identifier">expression </span><span class="special">&gt;&gt; </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">)] &gt;&gt; </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">
73            &gt;&gt; *(  (</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">)] &gt;&gt; </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">)] &gt;&gt; </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">&gt;&gt; *(  (</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">)] &gt;&gt; </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">)] &gt;&gt; </span><span class="identifier">term</span><span class="special">)<br>                )<br>        ;</span></code></pre>
74<p> The differences from the parse tree grammar are hi-lighted in <b><font color="#ff0000">bold-red</font></b>.
75  The <tt>inner_node_d</tt> directive causes the first and last nodes generated
76  by the enclosed parser to be discarded, since we don't really care about the
77  parentheses when evaluating the expression. The <tt>root_node_d</tt> directive
78  is the key to ast generation. A node that is generated by the parser inside
79  of <tt>root_node_d</tt> is marked as a root node. When a root node is created,
80  it becomes a root or parent node of the other nodes generated by the same rule.</p>
81<p> To start the parse and generate the ast, you must use the ast_parse functions,
82  which are similar to the pt_parse functions.</p>
83<pre>    <code><span class="identifier">tree_parse_info</span><span class="special">&lt;&gt; </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>
84<p> Here is the eval_expression function (note that to process the ast we only
85  need one function instead of four):</p>
86<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">&amp; </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">-&gt;</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">(&amp;</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">-&gt;</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">-&gt;</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">-&gt;</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">(&amp;</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">-&gt;</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">-&gt;</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">(&amp;</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">-&gt;</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">-&gt;</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">-&gt;</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">-&gt;</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">-&gt;</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">-&gt;</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">-&gt;</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">(&amp;</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">-&gt;</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">-&gt;</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">-&gt;</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">-&gt;</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">-&gt;</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">-&gt;</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>
87<p> <img src="theme/lens.gif" width="15" height="16"> An entire working example is <a href="../example/fundamental/ast_calc.cpp">ast_calc.cpp</a>. Hopefully this example has been enough to whet your appetite for
88  trees. For more nitty-gritty details, keep on reading the rest of this chapter.</p>
89<a name="usage"></a>
90<h2>Usage</h2>
91<a name="pt_parse"></a>
92<h3>pt_parse</h3>
93<p> To create a parse tree, you can call one of the five free functions:</p>
94<pre>    <span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>FactoryT</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>, </span><span class=identifier>FactoryT</span><span class=special>&gt;    <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>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>,
95        </span><span class="identifier">FactoryT</span><span class=special> </span><span class="keyword">const</span><span class=special> &amp;        </span><span class="identifier">factory_</span><span class=special> = </span><span class="identifier">FactoryT</span><span class=special>());    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <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>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <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>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <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>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <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>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);<br></span></pre>
96<a name="ast_parse"></a>
97<h3>ast_parse</h3>
98<p> To create an abstract syntax tree (ast for short) you call one of the five
99  free functions:</p>
100<pre>    <span class=keyword>template </span><span class=special>&lt;</span><span class=keyword>typename </span><span class=identifier>FactoryT</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>, </span><span class=identifier>FactoryT</span><span class=special>&gt;    <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>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>,
101       </span><span class="identifier"> FactoryT</span><span class=special> </span><span class="keyword">const</span><span class=special> &amp;        </span><span class="identifier">factory_</span><span class=special> = </span><span class="identifier">FactoryT</span><span class=special>()</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <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>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last_</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip_</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>IteratorT</span><span class=special>&gt;    <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>&amp;        </span><span class=identifier>first_</span><span class=special>,        <br>        </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>&amp;        </span><span class=identifier>last</span><span class=special>,        <br>        </span><span class=identifier>parser</span><span class=special>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <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>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>,        <br>        </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>&amp;            </span><span class=identifier>skip</span><span class=special>);    <br>    </span><span class=keyword>template </span><span class=special>&lt;</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>&gt;    <br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*&gt;    <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>&lt;</span><span class=identifier>ParserT</span><span class=special>&gt; </span><span class=keyword>const</span><span class=special>&amp;  </span><span class=identifier>parser</span><span class=special>);<br></span></pre>
102<a name="tree_parse_info"></a> 
103<h3>tree_parse_info</h3>
104<p> The <tt>tree_parse_info</tt> struct returned from pt_parse and ast_parse contains
105  information about the parse:</p>
106<pre>    <code><span class="keyword">template </span><span class="special">&lt;</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">*&gt;<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">std::size_t </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">&lt;</span><span class="identifier">IteratorT</span><span class="special">&gt;::</span><span class="identifier">container_t </span><span class="identifier">trees</span><span class="special">;<br>    </span><span class="special">};<br></span></code></pre>
107<table width="90%" border="0" align="center">
108  <tbody><tr>
109    <td class="table_title" colspan="10"> tree_parse_info </td>
110  </tr>
111  <tr>
112  </tr><tr>
113    <td class="table_cells"><b>stop</b></td>
114    <td class="table_cells">points to the final parse position (i.e. parsing processed
115      the input up to this point).</td>
116  </tr>
117  <tr><td class="table_cells"><b>match</b></td>
118  <td class="table_cells">true if parsing is successful. This may be full (the
119    parser consumed all the input), or partial (the parser consumed only a portion
120    of the input.)</td>
121  </tr>
122  <tr><td class="table_cells"><b>full</b></td>
123  <td class="table_cells">true when we have a full match (when the parser consumed
124    all the input).</td>
125  </tr>
126  <tr><td class="table_cells"><b>length</b></td>
127  <td class="table_cells">The number of characters consumed by the parser. This
128    is valid only if we have a successful match (either partial or full).</td>
129  </tr>
130  <tr><td class="table_cells"><b>trees</b></td>
131  <td class="table_cells">Contains the root node(s) of the tree.</td>
132  </tr>
133</tbody></table>
134<a name="tree_match"></a>
135<h3>tree_match</h3>
136<p> When Spirit is generating a tree, the parser's parse() member function will
137  return a tree_match object, instead of a match object. tree_match has three
138  template parameters. The first is the Iterator type which defaults to <tt>char
139  const*</tt>. The second is the node factory, which defaults to <a href="#node_val_data_factory">node_val_data_factory</a>.
140  The third is the attribute type stored in the match. A tree_match has a member
141  variable which is a container (a <tt>std::vector</tt>) of <a href="#tree_node">tree_node</a> 
142  objects named trees. For efficiency reasons, when a tree_match is copied, the
143  trees are <b>not</b> copied, they are moved to the new object, and the source
144  object is left with an empty tree container. tree_match supports the same interface
145  as the match class: it has an operator bool() so you can test it for a sucessful
146  match: if (matched), and you can query the match length via the length() function.
147  The class has this interface:</p>
148<pre>    <code><span class="keyword">template </span><span class="special">&lt;</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">&lt;&gt; </span><span class="special">&gt;<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">&lt;</span><span class="identifier">IteratorT</span><span class="special">&gt; </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">&lt;</span><span class="identifier">parse_node_t</span><span class="special">&gt;                   </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">std::size_t </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">&amp; </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">&amp; </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">&amp; </span><span class="identifier">x</span><span class="special">);<br>        </span><span class="identifier">tree_match</span><span class="special">&amp; </span><span class="keyword">operator</span><span class="special">=(</span><span class="identifier">tree_match </span><span class="keyword">const</span><span class="special">&amp; </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">&amp; </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>
149<p> When a parse has sucessfully completed, the trees data member will contain
150  the root node of the tree. </p>
151<table width="80%" border="0" align="center">
152  <tbody><tr> 
153    <td class="note_box"><img src="theme/lens.gif" width="15" height="16"> <b>vector?</b><br>
154      <br>
155      You may wonder, why is it a vector then? The answer is that it is partly
156      for implementation purposes, and also if you do not use any rules in your
157      grammar, then trees will contain a sequence of nodes that will not have
158      any children.</td>
159  </tr>
160</tbody></table>
161<p> Having spirit create a tree is similar to how a normal parse is done:</p>
162<pre>    <code><span class="identifier">tree_match</span><span class="special">&lt;&gt; </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>
163<a name="tree_node"></a>
164<h3>tree_node</h3>
165<p> Once you have created a tree by calling <a href="#pt_parse">pt_parse</a>
166  or <a href="#ast_parse">ast_parse</a>, you have a <a href="#tree_parse_info">tree_parse_info</a>
167  which contains the root node of the tree, and now you need to do something with
168  the tree. The data member trees of <a href="#tree_parse_info">tree_parse_info</a>
169  is a std::vector&lt;tree_node&gt;. tree_node provides the tree structure. The
170  class has one template parameter named T. tree_node contains an instance of
171  type T. It also contains a std::vector&lt;tree_node&lt;T&gt; &gt; which are
172  the node's children. The class looks like this:</p>
173<pre>    <code><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">T</span><span class="special">&gt;<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">&lt;</span><span class="identifier">tree_node</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt; </span><span class="special">&gt; </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">&amp; </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">&amp; </span><span class="identifier">v</span><span class="special">, </span><span class="identifier">children_t </span><span class="keyword">const</span><span class="special">&amp; </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">&lt;</span><span class="identifier">T</span><span class="special">&gt;&amp; </span><span class="identifier">x</span><span class="special">);<br>    </span><span class="special">};</span></code></pre>
174<p> This class is simply used to separate the tree framework from the data stored
175  in the tree. It is a generic node and any type can be stored inside it and acessed
176  via the data member value. The default type for T is <tt>node_val_data</tt>.</p>
177<a name="node_val_data"></a>
178<h3>node_val_data</h3>
179<p> The <tt>node_val_data</tt> class contains the actual information about each
180  node. This includes the text or token sequence that was parsed, an <tt>id</tt> 
181  that indicates which rule created the node, a boolean flag that indicates whether
182  the node was marked as a root node, and an optional user-specified value. This
183  is the interface:</p>
184<pre>    <code><span class="keyword">template </span><span class="special">&lt;</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">&gt;<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">&lt;</span><span class="identifier">IteratorT</span><span class="special">&gt;::</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">&lt;</span><span class="identifier">value_type</span><span class="special">&gt; </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">&amp; </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">&amp; </span><span class="identifier">_last</span><span class="special">);<br>        </span><span class="keyword">template </span><span class="special">&lt;</span><span class="keyword">typename </span><span class="identifier">IteratorT2</span><span class="special">&gt;<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">&amp; </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT2 </span><span class="keyword">const</span><span class="special">&amp; </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">&amp; </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">&amp; </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">&amp; </span><span class="identifier">v</span><span class="special">);<br>    </span><span class="special">};<br></span></code></pre>
185<a name="parser_id__checking_and_setting"></a>
186<h3>parser_id, checking and setting</h3>
187<p> If a node is generated by a rule, it will have an <tt>id</tt> set. Each rule
188  has an id that it sets of all nodes generated by that rule. The id is of type
189  <tt><a href="rule.html#tag">parser_id</a></tt>. The default id of each rule
190  is set to the address of that rule (converted to an integer). This is not always
191  the most convenient, since the code that processes the tree may not have access
192  to the rules, and may not be able to compare addresses. So, you can override
193  the default id used by each rule by <a href="rule.html#tag">giving it a specific
194  ID</a>. Then, when processing the tree you can call <tt>node_val_data::id()</tt> 
195  to see which rule created that node.</p>
196<a name="structure_layout_of_a_parse_tree"></a>
197<h2>structure/layout of a parse tree</h2>
198<a name="parse_tree_layout"></a>
199<h3>parse tree layout</h3>
200<p> The tree is organized by the rules. Each rule creates a new level in the tree.
201  All parsers attached to a rule create a node when a sucessful match is made.
202  These nodes become children of a node created by the rule. So, the following
203  code:</p>
204<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">&gt;&gt; </span><span class="literal">',' </span><span class="special">&gt;&gt; </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">&lt;&gt; </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>
205<p> When executed, this code would return a tree_match, m. <tt>m.trees[0]</tt> 
206  would contain a tree like this:</p>
207<table border="0" align="center">
208  <tbody><tr>
209    <td><img src="theme/trees1.png" width="253" height="151"></td>
210  </tr>
211</tbody></table>
212<p> The root node would not contain any text, and it's id would be set to the
213  address of myrule. It would have four children. Each child's id would be set
214  to the address of myrule, would contain the text as shown in the diagram, and
215  would have no children.</p>
216<a name="ast_layout"></a>
217<h2>ast layout</h2>
218<p> When calling <a href="#ast_parse">ast_parse</a>, the tree gets generated differently.
219  It mostly works the same as when generating a parse tree. The difference happens
220  when a rule only generated one sub-node. Instead of creating a new level, <a href="#ast_parse">ast_parse</a>
221  will not create a new level, it will just leave the existing node. So, this
222  code:</p>
223<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">&lt;&gt; </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>
224<p> will generate a single node that contains 'a'. If <tt>tree_match_policy</tt> 
225  had been used instead of <tt>ast_match_policy</tt>, the tree would have looked
226  like this:</p>
227<table border="0" align="center">
228  <tbody><tr>
229    <td><img src="theme/trees2.png" width="139" height="151"></td>
230  </tr>
231</tbody></table>
232<p> ast_match_policy has the effect of eliminating intermediate rule levels which
233  are simply pass-through rules. This is not enough to generate abstract syntax
234  trees, <a href="#root_node_d_and_ast_generation">root_node_d</a> is also needed. <a href="#root_node_d_and_ast_generation">root_node_d</a>
235  will be explained later.</p>
236<a name="switching__gen_pt_node_d____amp__gen_ast_node_d__"></a>
237<h2>switching: gen_pt_node_d[] &amp; gen_ast_node_d[]</h2>
238<p> If you want to mix and match the parse tree and ast behaviors in your application,
239  you can use the <tt>gen_pt_node_d[]</tt> and <tt>gen_ast_node_d[]</tt> directives.
240  When parsing passes through the <tt>gen_pt_node_d</tt> directive, parse tree
241  creation behavior is turned on. When the <tt>gen_ast_node_d</tt>
242directive is    used, the enclosed parser will generate a tree using the
243ast behavior. Note    that you must pay attention to how your rules are declared
244if you use a rule inside of these    directives. &nbsp;The match policy of
245the scanner will have to correspond to the desired behavior. &nbsp;If you
246avoid rules and use primitive parsers or grammars, then you will not have
247problems.</p>
248<a name="directives"></a>
249<h2>Directives</h2>
250<p> There are a few more directives that can be used to control the generation
251  of trees. These directives only effect tree generation. Otherwise, they have
252  no effect.<br>
253</p>
254<a name="no_node_d"></a>
255<h3>no_node_d</h3>
256<p> This directive is similar to <tt>gen_pt_node_d</tt> and <tt>gen_ast_node_d</tt>,
257  in that is modifies the scanner's match policy used by the enclosed parser. As it's name
258  implies, it does no tree generation, it turns it off completely. This is useful
259  if there are parts of your grammar which are not needed in the tree. For instance:
260  keywords, operators (<tt>*</tt>, <tt>-</tt>, <tt>&amp;&amp;</tt>, etc.) By eliminating
261  these from the tree, both memory usage and parsing time can be lowered. This
262  directive has the same requirements with respect to rules as <tt>gen_pt_node_d</tt> 
263  and <tt>gen_ast_node_d</tt> do. See the example file xml_grammar.hpp (in libs/spirit/example/application/xml
264  directory) for example
265  usage of <tt>no_node_d[]</tt>.</p>
266<a name="discard_node_d"></a>
267<h3>discard_node_d</h3>
268<p> This directive has a similar purpose to <tt>no_node_d</tt>, but works differently.
269  It does not switch the scanner's match policy, so the enclosed parser still generates
270  nodes. The generated nodes are discarded and do not appear in the tree. Using
271  <tt>discard_node_d</tt> is slower than <tt>no_node_d</tt>, but it does not suffer
272  from the drawback of having to specify a different rule type for any rule inside
273  it.</p>
274<a name="leaf_node_d_token_node_d"></a>
275<h3>leaf_node_d/token_node_d</h3>
276<p> Both <tt>leaf_node_d</tt> and <tt>token_node_d</tt> work the same. They group
277  together all the nodes generated by the enclosed parser. Note that a rule should
278  not be used inside these directives.</p>
279<p> This rule:</p>
280<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">&gt;&gt; </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>
281<p> would generate a root node with the id of integer and a child node for each
282  character parsed</p>
283<p> This:</p>
284<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">&gt;&gt; </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>
285<p> would generate a root node with only one child node that contained the entire
286  integer.</p>
287<a name="infix_node_d"></a>
288<h3>infix_node_d</h3>
289<p> This is useful for removing separators from lists. It discards all the nodes
290  in even positions. Thus this rule:</p>
291<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">&gt;&gt; </span><span class="special">*(</span><span class="literal">',' </span><span class="special">&gt;&gt; </span><span class="identifier">integer</span><span class="special">) </span><span class="special">];</span></code></pre>
292<p> would discard all the comma nodes and keep all the integer nodes.</p>
293<a name="discard_first_node_d"></a>
294<h3>discard_first_node_d</h3>
295<p> This discards the first node generated.</p>
296<a name="discard_last_node_d"></a>
297<h3>discard_last_node_d</h3>
298<p> This discards the last node generated.</p>
299<a name="inner_node_d"></a>
300<h3>inner_node_d</h3>
301<p> This discards the first and last node generated.</p>
302<a name="root_node_d_and_ast_generation"></a> 
303<h2>root_node_d and ast generation</h2>
304<p> The <tt>root_node_d</tt> directive is used to help out ast generation. It
305  has no effect when generating a parse tree. When a parser is enclosed in <tt>root_node_d</tt>,
306  the node it generates is marked as a root. This affects the way it is treated
307  when it's added to the list of nodes being generated. Here's an example:</p>
308<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">&gt;&gt; </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">&gt;&gt; </span><span class="identifier">integer</span><span class="special">);</span></code></pre>
309<p> When parsing 5+6 the following tree will be generated:</p>
310<table border="0" align="center">
311  <tbody><tr>
312    <td><img src="theme/trees3.png"></td>
313  </tr>
314</tbody></table>
315<p> When parsing 1+2+3 the following will be generated:</p>
316<table border="0" align="center">
317  <tbody><tr>
318    <td><img src="theme/trees4.png"></td>
319  </tr>
320</tbody></table>
321<p> When a new node is created the following rules are used to determine how the
322  tree will be generated:</p>
323<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>
324<p> After parsing leaves the current rule, the root node flag on the top node
325  is turned off. This means that the root_node_d directive only affects the current
326  rule.</p>
327<p> <img height="16" width="15" src="theme/lens.gif"> The example <a href="../example/fundamental/ast_calc.cpp">ast_calc.cpp</a>  demonstrates the use of root_node_d and <a href="#ast_parse">ast_parse</a>. The full source code can be <a href="../example/fundamental/ast_calc.cpp">viewed here</a>. This is part of the Spirit distribution.</p>
328<a name="parse_tree_iterator"></a>
329<h2>parse_tree_iterator</h2>
330<p> The <tt>parse_tree_iterator</tt> class allows you to parse a tree using spirit.
331  The class iterates over the tokens in the leaf nodes in the same order they
332  were created. The <tt>parse_tree_iterator</tt> is templated on <tt>ParseTreeMatchT</tt>.
333  It is constructed with a container of trees, and a position to start. Here is
334  an example usage:</p>
335<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">&lt;&gt; </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">&lt;</span><span class="identifier">tree_match</span><span class="special">&lt;&gt; </span><span class="special">&gt; </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">&lt;</span><span class="identifier">parse_tree_iterator_t</span><span class="special">&gt; </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>
336<p> <a name="advanced_tree_generation"></a>
337</p>
338<h2>advanced tree generation</h2>
339<a name="node_value"></a>
340<h3>node value</h3>
341<p> The <tt>node_val_data</tt> can contain a value. By default it contains a <tt>void_t</tt>,
342  which is an empty class. You can specify the type, using a template parameter,
343  which will then be stored in every node. The type must be default constructible,
344  and assignable. You can get and set the value using</p>
345<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>
346<p> and</p>
347<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">&amp; </span><span class="identifier">value</span><span class="special">);</span></code></pre>
348<p> To specify the value type, you must use a different <a href="#node_val_data">node_val_data
349  </a>factory than the default. The following example shows how to modify the factory to store and retrieve a double inside each <span class="identifier">node_val_data</span>.
350<pre>    <span class=keyword>typedef </span><span class=identifier>node_val_data_factory</span><span class=special>&lt;</span><span class=keyword>double</span><span class=special>&gt; </span><span class=identifier>factory_t</span><span class=special>;<br>    </span><span class=identifier>my_grammar </span><span class=identifier>gram</span><span class=special>;<br>    </span><span class=identifier>my_skip_grammar </span><span class=identifier>skip</span><span class=special>;<br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>iterator_t</span><span class=special>, </span><span class=identifier>factory_t</span><span class=special>&gt; </span><span class=identifier>i </span><span class=special>= <br>        </span><span class=identifier>ast_parse</span><span class=special>&lt;</span><span class=identifier>factory_t</span><span class=special>&gt;(</span><span class=identifier>first</span><span class=special>, </span><span class=identifier>last</span><span class=special>, </span><span class=identifier>gram</span><span class=special>, </span><span class=identifier>skip</span><span class=special>);<br>    // 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>i</span><span class=special>.</span><span class=identifier>trees</span><span class=special>.</span><span class=identifier>begin</span><span class=special>()-&gt;</span><span class=identifier>value</span><span class=special>;<br></span></pre>
351</p>
352<a name="access_node_d"></a>
353<h3>access_node_d</h3>
354<p> Now, you may be wondering, "What good does it do to have a value I can
355  store in each node, but not to have any way of setting it?" Well, that's
356  what <tt>access_node_d</tt> is for. <tt>access_node_d</tt> is a directive. It
357  allows you to attach an action to it, like this:</p>
358<pre>    <code><span class="identifier">access_node_d</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>
359<p> The attached action will be passed 3 parameters: A reference to the root node
360  of the tree generated by the parser, and the current first and last iterators.
361  The action can set the value stored in the node.</p>
362<a name="tree_node_factories"></a>
363<h3>Tree node factories</h3>
364<p> By setting the factory, you can control what type of nodes are created and
365  how they are created. There are 3 predefined factories: <tt>node_val_data_factory</tt>,
366  <tt>node_all_val_data_factory</tt>, and <tt>node_iter_data_factory</tt>. You
367  can also create your own factory to support your own node types.</p>
368<p> Using factories with grammars is quite easy, you just need to specify the factory type as explicit template parameter to the free ast_parse function:</p>
369<pre>    <span class=keyword>typedef </span><span class=identifier>node_iter_data_factory</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt; </span><span class=identifier>factory_t</span><span class=special>;<br>    </span><span class=identifier>my_grammar </span><span class=identifier>gram</span><span class=special>;<br>    </span><span class=identifier>my_skip_grammar </span><span class=identifier>skip</span><span class=special>;<br>    </span><span class=identifier>tree_parse_info</span><span class=special>&lt;</span><span class=identifier>iterator_t</span><span class=special>, </span><span class=identifier>factory_t</span><span class=special>&gt; </span><span class=identifier>i </span><span class=special>= <br>        </span><span class=identifier>ast_parse</span><span class=special>&lt;</span><span class=identifier>factory_t</span><span class=special>&gt;(</span><span class=identifier>first</span><span class=special>, </span><span class=identifier>last</span><span class=special>, </span><span class=identifier>gram</span><span class=special>, </span><span class=identifier>skip</span><span class=special>);<br></span></pre>
370<p> Instead, using the factory directly with rules is slightly harder because the
371  factory is a template parameter to the scanner match policy, so you must use a
372  custom scanner:</p>
373<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">&lt;</span><span class="identifier">value_t</span><span class="special">&gt; </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">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </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">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </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">&lt;</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">&lt;</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">&gt;</span></code><code><span class="identifier"></span><span class="special"> &gt;</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">&lt;</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">&gt; </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>
374<a name="node_val_data_factory"></a>
375<h3>node_val_data_factory</h3>
376<p> This is the default factory. It creates <tt>node_val_data</tt> nodes. Leaf
377  nodes contain a copy of the matched text, and intermediate nodes don't. <tt>node_val_data_factory</tt> 
378  has one template parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type
379  of value that will be stored in the <tt>node_val_data</tt>.</p>
380<a name="node_val_data_factory"></a>
381<h3>node_all_val_data_factory</h3>
382<p> This factory also creates <tt>node_val_data</tt>. The difference between it
383  and <tt>node_val_data_factory</tt> is that <b>every</b> node contains all the
384  text that spans it. This means that the root node will contain a copy of the
385  entire parsed input sequence. <tt>node_all_val_data_factory</tt> has one template
386  parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type of value that
387  will be stored in the <tt>node_val_data</tt>.</p>
388<a name="node_iter_data_factory"></a>
389<h3>node_iter_data_factory</h3>
390<p> This factory creates the <tt>parse_tree_iter_node</tt>. This node stores iterators
391  into the input sequence instead of making a copy. It can use a lot less memory.
392  However, the input sequence must stay valid for the life of the tree, and it's
393  not a good idea to use the <tt>multi_pass</tt> iterator with this type of node.
394  All levels of the tree will contain a begin and end iterator. <tt>node_iter_data_factory</tt> 
395  has one template parameter: <tt>ValueT</tt>. <tt>ValueT</tt> specifies the type
396  of value that will be stored in the node_val_data.</p>
397<a name="custom"></a>
398<h3>custom</h3>
399<p> You can create your own factory. It should look like this:</p>
400<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">&lt;</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">&gt;<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">&amp; </span><span class="identifier">first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">&amp; </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">&lt;</span><span class="keyword">typename </span><span class="identifier">ContainerT</span><span class="special">&gt;<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">&amp; </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">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </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">&lt;</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">&gt; </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">&lt;</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">&lt;</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">&gt;</span></code><code><span class="identifier"></span><span class="special"> &gt;</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">&lt;</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">&gt; </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>
401</td>
402    <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td>
403    <td width="30"><a href="symbols.html"><img src="theme/l_arr.gif" border="0"></a></td>
404    <td width="30"><a href="multi_pass.html"><img src="theme/r_arr.gif" border="0"></a></td>
405  </tr>
406</tbody></table>
407<hr size="1">
408<p class="copyright">Copyright &copy; 2001-2002 Daniel C. Nuffer<br>
409  <br>
410  <font size="2">Use, modification and distribution is subject to the Boost Software
411    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
412    http://www.boost.org/LICENSE_1_0.txt)</font></p>
413<p class="copyright">&nbsp;</p>
414<br>
415</body></html>
Note: See TracBrowser for help on using the repository browser.