| 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">) >> +</span><span class="identifier">digit_p</span><span class="special">) ] ]<br> ;<br><br> </span><span class="identifier">factor<br> </span><span class="special">= </span><span class="identifier">integer<br> </span><span class="special">| </span><span class="literal">'(' </span><span class="special">>> </span><span class="identifier">expression </span><span class="special">>> </span><span class="literal">')'<br> </span><span class="special">| (</span><span class="literal">'-' </span><span class="special">>> </span><span class="identifier">factor</span><span class="special">)<br> ;<br><br> </span><span class="identifier">term<br> </span><span class="special">= </span><span class="identifier">factor </span><span class="special"> |
|---|
| 45 | >> *( (</span><span class="literal">'*' </span><span class="special">>> </span><span class="identifier">factor</span><span class="special">)<br> | (</span><span class="literal">'/' </span><span class="special">>> </span><span class="identifier">factor</span><span class="special">)<br> )<br> ;<br><br> </span><span class="identifier">expression<br> </span><span class="special">= </span><span class="identifier">term<br> </span><span class="special">>> *( (</span><span class="literal">'+' </span><span class="special">>> </span><span class="identifier">term</span><span class="special">)<br> | (</span><span class="literal">'-' </span><span class="special">>> </span><span class="identifier">term</span><span class="special">)<br> )<br> ;</span></code></pre> |
|---|
| 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"><> </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"><< </span><span class="string">"parsing succeeded\n"</span><span class="special">;<br> </span><span class="identifier">cout </span><span class="special"><< </span><span class="string">"result = " </span><span class="special"><< </span><span class="identifier"><font color="#ff0000"><b>evaluate</b></font></span><span class="special">(</span><span class="identifier">info</span><span class="special">) << </span><span class="string">"\n\n"</span><span class="special">;<br> }</span></code></pre> |
|---|
| 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"><>& </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"><</span><span class="identifier">iterator_t</span><span class="special">> </span><span class="identifier"> parse_tree_match_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">parse_tree_match_t</span><span class="special">::</span><span class="identifier">const_tree_iterator 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"><>& </span><span class="identifier">info</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_factor</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br> </span><span class="keyword">long </span><span class="identifier">eval_integer</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">);<br><br> </span><span class="comment">// i should be pointing to a node created by the expression rule<br> </span><span class="keyword">long </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">iter_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">i</span><span class="special">)<br> {<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">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();<br> </span><span class="keyword">long </span><span class="identifier">lhs </span><span class="special">= </span><span class="identifier">eval_term</span><span class="special">(</span><span class="identifier">chi</span><span class="special">);<br> </span><span class="keyword">for </span><span class="special">(++</span><span class="identifier">chi</span><span class="special">; </span><span class="identifier">chi </span><span class="special">!= </span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">end</span><span class="special">(); ++</span><span class="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<char>)<br> </span><span class="keyword">char </span><span class="identifier">op </span><span class="special">= *(</span><span class="identifier">chi</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br> ++</span><span class="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">& </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">& </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">& </span><span class="identifier">i</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// use the range constructor for a string<br> </span><span class="identifier">string </span><span class="identifier">integer</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(), </span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">end</span><span class="special">());<br> </span><span class="comment">// convert the string to an integer<br> </span><span class="keyword">return </span><span class="identifier">strtol</span><span class="special">(</span><span class="identifier">integer</span><span class="special">.</span><span class="identifier">c_str</span><span class="special">(), </span><span class="number">0</span><span class="special">, </span><span class="number">10</span><span class="special">);<br> </span><span class="special">}<br></span></code></pre> |
|---|
| 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">) >> +</span><span class="identifier">digit_p</span><span class="special">) ] ]<br> ;<br><br> </span><span class="identifier">factor<br> </span><span class="special">= </span><span class="identifier">integer<br> </span><span class="special">| </span><span class="identifier"><font color="#ff0000"><b>inner_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'('</span><span class="special">) >> </span><span class="identifier">expression </span><span class="special">>> </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">')'</span><span class="special">)]<br> | (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">)] >> </span><span class="identifier">factor</span><span class="special">)<br> ;<br><br> </span><span class="identifier">term<br> </span><span class="special">= </span><span class="identifier">factor </span><span class="special"> |
|---|
| 73 | >> *( (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'*'</span><span class="special">)] >> </span><span class="identifier">factor</span><span class="special">)<br> | (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'/'</span><span class="special">)] >> </span><span class="identifier">factor</span><span class="special">)<br> )<br> ;<br><br> </span><span class="identifier">expression<br> </span><span class="special">= </span><span class="identifier">term<br> </span><span class="special">>> *( (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'+'</span><span class="special">)] >> </span><span class="identifier">term</span><span class="special">)<br> | (</span><span class="identifier"><font color="#ff0000"><b>root_node_d</b></font></span><span class="special">[</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'-'</span><span class="special">)] >> </span><span class="identifier">term</span><span class="special">)<br> )<br> ;</span></code></pre> |
|---|
| 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"><> </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">& </span><span class="identifier">i</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">integer</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="comment">// convert string to integer<br> </span><span class="identifier">string </span><span class="identifier">integer</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(), </span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">end</span><span class="special">());<br> </span><span class="keyword">return </span><span class="identifier">strtol</span><span class="special">(</span><span class="identifier">integer</span><span class="special">.</span><span class="identifier">c_str</span><span class="special">(), </span><span class="number">0</span><span class="special">, </span><span class="number">10</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">factor</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="comment">// factor can only be unary minus<br> </span><span class="keyword">return </span><span class="special">- </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">term</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'*'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">*<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'/'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">/<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">id</span><span class="special">() </span><span class="special">== </span><span class="identifier">parser_id</span><span class="special">(&</span><span class="identifier">expression</span><span class="special">))<br> </span><span class="special">{<br> </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'+'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">+<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="keyword">else </span><span class="keyword">if </span><span class="special">(*</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">value</span><span class="special">.</span><span class="identifier">begin</span><span class="special">() </span><span class="special">== </span><span class="literal">'-'</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="keyword">return </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()) </span><span class="special">-<br> </span><span class="identifier">eval_expression</span><span class="special">(</span><span class="identifier">i</span><span class="special">-></span><span class="identifier">children</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()+</span><span class="number">1</span><span class="special">);<br> </span><span class="special">}<br> </span><span class="special">}<br><br> </span><span class="keyword">return </span><span class="number">0</span><span class="special">;<br> </span><span class="special">}<br></span></code></pre> |
|---|
| 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><</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>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>IteratorT</span><span class=special>, </span><span class=identifier>FactoryT</span><span class=special>> <br> </span><span class=identifier>pt_parse</span><span class=special>( <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>first_</span><span class=special>, <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>last_</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>, <br> </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>skip_</span><span class=special>, |
|---|
| 95 | </span><span class="identifier">FactoryT</span><span class=special> </span><span class="keyword">const</span><span class=special> & </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><</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>IteratorT</span><span class=special>> <br> </span><span class=identifier>pt_parse</span><span class=special>( <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>first_</span><span class=special>, <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>last_</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>, <br> </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>skip_</span><span class=special>); <br> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>IteratorT</span><span class=special>> <br> </span><span class=identifier>pt_parse</span><span class=special>( <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>first_</span><span class=special>, <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>last_</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>); <br> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*> <br> </span><span class=identifier>pt_parse</span><span class=special>( <br> </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>* </span><span class=identifier>str</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>, <br> </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>skip</span><span class=special>); <br> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*> <br> </span><span class=identifier>pt_parse</span><span class=special>( <br> </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>* </span><span class=identifier>str</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>);<br></span></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><</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>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>IteratorT</span><span class=special>, </span><span class=identifier>FactoryT</span><span class=special>> <br> </span><span class=identifier>ast_parse</span><span class=special>( <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>first_</span><span class=special>, <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>last_</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>, <br> </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>skip_</span><span class=special>, |
|---|
| 101 | </span><span class="identifier"> FactoryT</span><span class=special> </span><span class="keyword">const</span><span class=special> & </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><</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>IteratorT</span><span class=special>> <br> </span><span class=identifier>ast_parse</span><span class=special>( <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>first_</span><span class=special>, <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>last_</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>, <br> </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>skip_</span><span class=special>); <br> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>IteratorT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>IteratorT</span><span class=special>> <br> </span><span class=identifier>ast_parse</span><span class=special>( <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>first_</span><span class=special>, <br> </span><span class=identifier>IteratorT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>last</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>); <br> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>SkipT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*> <br> </span><span class=identifier>ast_parse</span><span class=special>( <br> </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>* </span><span class=identifier>str</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>, <br> </span><span class=identifier>SkipT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>skip</span><span class=special>); <br> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>CharT</span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>ParserT</span><span class=special>> <br> </span><span class=identifier>tree_parse_info</span><span class=special><</span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>*> <br> </span><span class=identifier>ast_parse</span><span class=special>( <br> </span><span class=identifier>CharT </span><span class=keyword>const</span><span class=special>* </span><span class=identifier>str</span><span class=special>, <br> </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>ParserT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>parser</span><span class=special>);<br></span></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"><</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*><br> </span><span class="keyword">struct </span><span class="identifier">tree_parse_info<br> </span><span class="special">{<br> </span><span class="identifier">IteratorT </span><span class="identifier">stop</span><span class="special">;<br> </span><span class="keyword">bool </span><span class="identifier">match</span><span class="special">;<br> </span><span class="keyword">bool </span><span class="identifier">full</span><span class="special">;<br> </span><span class="keyword">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"><</span><span class="identifier">IteratorT</span><span class="special">>::</span><span class="identifier">container_t </span><span class="identifier">trees</span><span class="special">;<br> </span><span class="special">};<br></span></code></pre> |
|---|
| 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"><</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*, </span><span class="keyword">typename </span><span class="identifier">NodeFactoryT </span><span class="special">= </span><span class="identifier">node_val_data_factory</span><span class="special"><> </span><span class="special">><br> </span><span class="keyword">struct </span><span class="identifier">tree_match<br> </span><span class="special">{<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">NodeFactoryT</span><span class="special">::</span><span class="keyword">template </span><span class="identifier">factory</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">> </span><span class="identifier">node_factory_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">node_factory_t</span><span class="special">::</span><span class="identifier">node_t </span><span class="identifier">parse_node_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_node</span><span class="special"><</span><span class="identifier">parse_node_t</span><span class="special">> </span><span class="identifier">node_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">node_t</span><span class="special">::</span><span class="identifier">children_t </span><span class="identifier">container_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">tree_iterator</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_tree_iterator</span><span class="special">;<br><br> </span><span class="identifier">tree_match</span><span class="special">();<br> </span><span class="identifier">tree_match</span><span class="special">(</span><span class="keyword">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">& </span><span class="identifier">n</span><span class="special">);<br> </span><span class="identifier">tree_match</span><span class="special">(</span><span class="identifier">tree_match </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="keyword">explicit </span><span class="identifier">tree_match</span><span class="special">(</span><span class="identifier">match </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="identifier">tree_match</span><span class="special">& </span><span class="keyword">operator</span><span class="special">=(</span><span class="identifier">tree_match </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">tree_match</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="keyword">operator </span><span class="keyword">bool</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">int </span><span class="identifier">length</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br><br> </span><span class="identifier">container_t </span><span class="identifier">trees</span><span class="special">;<br> </span><span class="special">};</span></code></pre> |
|---|
| 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"><> </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<tree_node>. 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<tree_node<T> > which are |
|---|
| 172 | the node's children. The class looks like this:</p> |
|---|
| 173 | <pre> <code><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">T</span><span class="special">><br> </span><span class="keyword">struct </span><span class="identifier">tree_node<br> </span><span class="special">{<br> </span><span class="keyword">typedef </span><span class="identifier">T </span><span class="identifier">parse_node_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">tree_node</span><span class="special"><</span><span class="identifier">T</span><span class="special">> </span><span class="special">> </span><span class="identifier">children_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">children_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">tree_iterator</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">children_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_tree_iterator</span><span class="special">;<br><br> </span><span class="identifier">T </span><span class="identifier">value</span><span class="special">;<br> </span><span class="identifier">children_t </span><span class="identifier">children</span><span class="special">;<br><br> </span><span class="identifier">tree_node</span><span class="special">();<br> </span><span class="keyword">explicit </span><span class="identifier">tree_node</span><span class="special">(</span><span class="identifier">T </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">v</span><span class="special">);<br> </span><span class="identifier">tree_node</span><span class="special">(</span><span class="identifier">T </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">v</span><span class="special">, </span><span class="identifier">children_t </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">c</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">tree_node</span><span class="special"><</span><span class="identifier">T</span><span class="special">>& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="special">};</span></code></pre> |
|---|
| 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"><</span><span class="keyword">typename </span><span class="identifier">IteratorT </span><span class="special">= </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">*, </span><span class="keyword">typename </span><span class="identifier">ValueT </span><span class="special">= </span><span class="identifier">nil_t</span><span class="special">><br> </span><span class="keyword">struct </span><span class="identifier">node_val_data<br> </span><span class="special">{<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">IteratorT</span><span class="special">>::</span><span class="identifier">value_type </span><span class="identifier">value_type</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">value_type</span><span class="special">> </span><span class="identifier">container_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">iterator_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="keyword">typename </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">const_iterator_t</span><span class="special">;<br><br> </span><span class="identifier">node_val_data</span><span class="special">();<br> </span><span class="identifier">node_val_data</span><span class="special">(</span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_last</span><span class="special">);<br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">IteratorT2</span><span class="special">><br> </span><span class="identifier">node_val_data</span><span class="special">(</span><span class="identifier">IteratorT2 </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_first</span><span class="special">, </span><span class="identifier">IteratorT2 </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">_last</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">node_val_data</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br><br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">begin</span><span class="special">();<br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">begin</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">iterator </span><span class="identifier">end</span><span class="special">();<br> </span><span class="identifier">container_t</span><span class="special">::</span><span class="identifier">const_iterator </span><span class="identifier">end</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br><br> </span><span class="keyword">bool </span><span class="identifier">is_root</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">is_root</span><span class="special">(</span><span class="keyword">bool </span><span class="identifier">b</span><span class="special">);<br><br> </span><span class="identifier">parser_id </span><span class="identifier">id</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">id</span><span class="special">(</span><span class="identifier">parser_id </span><span class="identifier">r</span><span class="special">);<br><br> </span><span class="identifier">ValueT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">value</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">value</span><span class="special">(</span><span class="identifier">ValueT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">v</span><span class="special">);<br> </span><span class="special">};<br></span></code></pre> |
|---|
| 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">>> </span><span class="literal">',' </span><span class="special">>> </span><span class="special">*</span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'b'</span><span class="special">);<br> </span><span class="keyword">char </span><span class="keyword">const</span><span class="special">* </span><span class="identifier">input </span><span class="special">= </span><span class="string">"a,bb"</span><span class="special">;<br> </span><span class="identifier">scanner_t </span><span class="identifier">scanner</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">input </span><span class="special">+ </span><span class="identifier">strlen</span><span class="special">(</span><span class="identifier">input</span><span class="special">));<br> </span><span class="identifier">tree_match</span><span class="special"><> </span><span class="identifier">m </span><span class="special">= </span><span class="identifier">myrule</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">scanner</span><span class="special">);<br></span></code></pre> |
|---|
| 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"><> </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[] & 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> |
|---|
| 242 | directive is used, the enclosed parser will generate a tree using the |
|---|
| 243 | ast behavior. Note that you must pay attention to how your rules are declared |
|---|
| 244 | if you use a rule inside of these directives. The match policy of |
|---|
| 245 | the scanner will have to correspond to the desired behavior. If you |
|---|
| 246 | avoid rules and use primitive parsers or grammars, then you will not have |
|---|
| 247 | problems.</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>&&</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">>> </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">>> </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">>> </span><span class="special">*(</span><span class="literal">',' </span><span class="special">>> </span><span class="identifier">integer</span><span class="special">) </span><span class="special">];</span></code></pre> |
|---|
| 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">>> </span><span class="special">*(</span><span class="identifier">root_node_d</span><span class="special">[ </span><span class="identifier">ch_p</span><span class="special">(</span><span class="literal">'+'</span><span class="special">) </span><span class="special">] </span><span class="special">>> </span><span class="identifier">integer</span><span class="special">);</span></code></pre> |
|---|
| 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"><> </span><span class="identifier">i </span><span class="special">= </span><span class="identifier">pt_parse</span><span class="special">(</span><span class="identifier">input</span><span class="special">, </span><span class="identifier">myrule</span><span class="special">);<br><br> </span><span class="keyword">typedef </span><span class="identifier">parse_tree_iterator</span><span class="special"><</span><span class="identifier">tree_match</span><span class="special"><> </span><span class="special">> </span><span class="identifier">parse_tree_iterator_t</span><span class="special">;<br><br> </span><span class="comment">// create a first and last iterator to work off the tree<br> </span><span class="identifier">parse_tree_iterator_t </span><span class="identifier">first</span><span class="special">(</span><span class="identifier">i</span><span class="special">.</span><span class="identifier">trees</span><span class="special">, </span><span class="identifier">i</span><span class="special">.</span><span class="identifier">trees</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());<br> </span><span class="identifier">parse_tree_iterator_t </span><span class="identifier">last</span><span class="special">;<br><br> </span><span class="comment">// parse the tree<br> </span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">parse_tree_iterator_t</span><span class="special">> </span><span class="identifier">tree_parser </span><span class="special">=...<br> </span><span class="identifier">tree_parser</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">last</span><span class="special">);<br></span></code></pre> |
|---|
| 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">& </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><</span><span class=keyword>double</span><span class=special>> </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><</span><span class=identifier>iterator_t</span><span class=special>, </span><span class=identifier>factory_t</span><span class=special>> </span><span class=identifier>i </span><span class=special>= <br> </span><span class=identifier>ast_parse</span><span class=special><</span><span class=identifier>factory_t</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>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>()-></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><</span><span class=keyword>int</span><span class=special>> </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><</span><span class=identifier>iterator_t</span><span class=special>, </span><span class=identifier>factory_t</span><span class=special>> </span><span class=identifier>i </span><span class=special>= <br> </span><span class=identifier>ast_parse</span><span class=special><</span><span class=identifier>factory_t</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>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"><</span><span class="identifier">value_t</span><span class="special">> </span><span class="identifier">factory_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">ast_match_policy</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_policy_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">scanner</span><span class="special"><</span><span class="identifier">iterator_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> scanner_policies</span></code><code><span class="identifier"></span><span class="special"><</span></code><code><span class="identifier">iter_policy_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> match_policy_t</span><span class="special">></span></code><code><span class="identifier"></span><span class="special"> ></span></code><code><span class="special"> </span><span class="identifier">scanner_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">> </span><span class="identifier">rule_t</span><span class="special">;<br><br> </span><span class="identifier">rule_t </span><span class="identifier">r </span><span class="special">=...;<br><br></span></code><code><span class="special"> </span><span class="identifier">scanner_t </span><span class="identifier">scan </span><span class="special">= </span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">(</span><span class="identifier">first</span><span class="special">, </span><span class="identifier">last</span><span class="special"></span><span class="identifier"></span><span class="special">);<br></span></code><code><span class="special"></span></code><code><span class="special"> </span><span class="identifier">match_t </span><span class="identifier">hit </span><span class="special">= </span><span class="identifier">r</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier"></span><span class="special"></span><span class="identifier"></span><span class="special"></span><span class="identifier">scan</span><span class="special">);</span></code></pre> |
|---|
| 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"><</span><span class="keyword">typename </span><span class="identifier">IteratorT</span><span class="special">><br> </span><span class="keyword">class </span><span class="identifier">factory<br> </span><span class="special">{<br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="comment">// This is your node type<br> </span><span class="keyword">typedef </span><span class="identifier">my_node_type </span><span class="identifier">node_t</span><span class="special">;<br><br> </span><span class="keyword">static </span><span class="identifier">node_t </span><span class="identifier">create_node</span><span class="special">(<br> </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">first</span><span class="special">, </span><span class="identifier">IteratorT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">last</span><span class="special">, </span><span class="keyword">bool </span><span class="identifier">is_leaf_node</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// create a node and return it.<br> </span><span class="special">}<br><br> </span><span class="comment">// This function is used by the leaf_node and token_node directives.<br> // If you don't use them, then you can leave this function<br> // unimplemented.<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">ContainerT</span><span class="special">><br> </span><span class="keyword">static </span><span class="identifier">node_t </span><span class="identifier">group_nodes</span><span class="special">(</span><span class="identifier">ContainerT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">nodes</span><span class="special">)<br> </span><span class="special">{<br> </span><span class="comment">// Group all the nodes into one and return it.<br> </span><span class="special">}<br> </span><span class="special">};<br> </span><span class="special">};<br><br><br> </span><span class="comment">// Typedefs to use my_factory<br> </span><span class="keyword">typedef </span><span class="identifier">my_factory </span><span class="identifier">factory_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_match</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">tree_match_policy</span><span class="special"><</span><span class="identifier">iterator_t</span><span class="special">, </span><span class="identifier">factory_t</span><span class="special">> </span><span class="identifier">match_policy_t</span><span class="special">;<br></span></code><code><span class="special"><br> </span><span class="comment">// Typedefs if you are using rules instead of grammars<br></span></code><code><span class="special"> </span><span class="keyword">typedef </span><span class="identifier">scanner</span><span class="special"><</span><span class="identifier">iterator_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> scanner_policies</span></code><code><span class="identifier"></span><span class="special"><</span></code><code><span class="identifier">iter_policy_t</span></code><code><span class="special">,</span></code><code><span class="identifier"> match_policy_t</span><span class="special">></span></code><code><span class="identifier"></span><span class="special"> ></span></code><code><span class="special"> </span><span class="identifier">scanner_t</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">rule</span><span class="special"><</span><span class="identifier">scanner_t</span><span class="special"></span><span class="identifier"></span><span class="special">> </span><span class="identifier">rule_t</span><span class="special">;<br></span></code><code><span class="special"></span><span class="special"><br></span></code></pre><table border="0"><tbody><tr><td width="10"><br> |
|---|
| 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 © 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"> </p> |
|---|
| 414 | <br> |
|---|
| 415 | </body></html> |
|---|
