| <html> |
| <head> |
| <title>Techniques</title> |
| <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> |
| <link rel="stylesheet" href="theme/style.css" type="text/css"> |
| </head> |
| |
| <body> |
| <table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2"> |
| <tr> |
| <td width="10"> |
| </td> |
| <td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Techniques</b></font></td> |
| <td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td> |
| </tr> |
| </table> |
| <br> |
| <table border="0"> |
| <tr> |
| <td width="10"></td> |
| <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> |
| <td width="30"><a href="style_guide.html"><img src="theme/l_arr.gif" border="0"></a></td> |
| <td width="30"><a href="faq.html"><img src="theme/r_arr.gif" border="0"></a></td> |
| </tr> |
| </table> |
| <ul> |
| <li><a href="#templatized_functors">Templatized Functors</a></li> |
| <li><a href="#multiple_scanner_support">Rule With Multiple Scanners</a></li> |
| <li><a href="#no_rules">Look Ma' No Rules!</a></li> |
| <li><a href="#typeof">typeof</a></li> |
| <li><a href="#nabialek_trick">Nabialek trick</a></li> |
| </ul> |
| <h3><a name="templatized_functors"></a> Templatized Functors</h3> |
| <p>For the sake of genericity, it is often better to make the functor's member |
| <tt>operator()</tt> a template. That way, we do not have to concern ourselves |
| with the type of the argument to expect as long as the behavior is appropriate. |
| For instance, rather than hard-coding <tt>char const*</tt> as the argument of |
| a generic semantic action, it is better to make it a template member function. |
| That way, it can accept any type of iterator:</p> |
| <pre><code><font color="#000000"><span class=special> </span><span class=keyword>struct </span><span class=identifier>my_functor |
| </span><span class=special>{ |
| </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>void </span><span class=keyword>operator</span><span class=special>()(</span><span class=identifier>IteratorT </span><span class=identifier>first</span><span class=special>, </span><span class=identifier>IteratorT </span><span class=identifier>last</span><span class=special>) </span><span class=keyword>const</span><span class=special>; |
| </span><span class=special>};</span></font></code></pre> |
| <p>Take note that this is only possible with functors. It is not possible to pass |
| in template functions as semantic actions unless you cast it to the correct |
| function signature; in which case, you <em>monomorphize</em> the function. This |
| clearly shows that functors are superior to plain functions.</p> |
| <h3><b><a name="multiple_scanner_support" id="multiple_scanner_support"></a> Rule |
| With Multiple Scanners</b></h3> |
| <p>As of v1.8.0, rules can use one or more scanner types. There are cases, for |
| instance, where we need a rule that can work on the phrase and character levels. |
| Rule/scanner mismatch has been a source of confusion and is the no. 1 <a href="faq.html#scanner_business">FAQ</a>. |
| To address this issue, we now have <a href="rule.html#multiple_scanner_support">multiple |
| scanner support</a>. </p> |
| <p>Here is an example of a grammar with a rule <tt>r</tt> that can be called with |
| 3 types of scanners (phrase-level, lexeme, and lower-case). See the <a href="rule.html">rule</a>, |
| <a href="grammar.html">grammar</a>, <a href="scanner.html#lexeme_scanner">lexeme_scanner</a> |
| and <a href="scanner.html#as_lower_scanner">as_lower_scanner </a>for more information. |
| </p> |
| <p>Here's the grammar (see <a href="../example/techniques/multiple_scanners.cpp">multiple_scanners.cpp</a>): |
| </p> |
| <pre><span class=special> </span><span class=keyword>struct </span><span class=identifier>my_grammar </span><span class=special>: </span><span class=identifier>grammar</span><span class=special><</span><span class=identifier>my_grammar</span><span class=special>> |
| </span><span class=special>{ |
| </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>> |
| </span><span class=keyword>struct </span><span class=identifier>definition |
| </span><span class=special>{ |
| </span><span class=identifier>definition</span><span class=special>(</span><span class=identifier>my_grammar </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>self</span><span class=special>) |
| </span><span class=special>{ |
| </span><span class=identifier>r </span><span class=special>= </span><span class=identifier>lower_p</span><span class=special>; |
| </span><span class=identifier>rr </span><span class=special>= </span><span class=special>+(</span><span class=identifier>lexeme_d</span><span class=special>[</span><span class=identifier>r</span><span class=special>] </span><span class=special>>> </span><span class=identifier>as_lower_d</span><span class=special>[</span><span class=identifier>r</span><span class=special>] </span><span class=special>>> </span><span class=identifier>r</span><span class=special>); |
| </span><span class=special>} |
| |
| </span><span class=keyword>typedef </span><span class=identifier>scanner_list</span><span class=special>< |
| </span><span class=identifier>ScannerT |
| </span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>lexeme_scanner</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>>::</span><span class=identifier>type |
| </span><span class=special>, </span><span class=keyword>typename </span><span class=identifier>as_lower_scanner</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>>::</span><span class=identifier>type |
| </span><span class=special>> </span><span class=identifier>scanners</span><span class=special>; |
| |
| </span><span class=identifier>rule</span><span class=special><</span><span class=identifier>scanners</span><span class=special>> </span><span class=identifier>r</span><span class=special>; |
| </span><span class=identifier>rule</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>> </span><span class=identifier>rr</span><span class=special>; |
| </span><span class=identifier>rule</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>start</span><span class=special>() </span><span class=keyword>const </span><span class=special>{ </span><span class=keyword>return </span><span class=identifier>rr</span><span class=special>; </span><span class=special>} |
| </span><span class=special>}; |
| </span><span class=special>};</span></pre> |
| <p>By default support for multiple scanners is disabled. The macro |
| <tt>BOOST_SPIRIT_RULE_SCANNERTYPE_LIMIT</tt> must be defined to the |
| maximum number of scanners allowed in a scanner_list. The value must |
| be greater than 1 to enable multiple scanners. Given the |
| example above, to define a limit of three scanners for the list, the |
| following line must be inserted into the source file before the |
| inclusion of Spirit headers: |
| </p> |
| <pre><span class=special> </span><span class=preprocessor>#define </span><span class=identifier>BOOST_SPIRIT_RULE_SCANNERTYPE_LIMIT</span> <span class=literal>3</span></pre> |
| <h3><span class=special></span><b> <a name="no_rules" id="no_rules"></a> Look |
| Ma' No Rules</b></h3> |
| <p>You use grammars and you use lots of 'em? Want a fly-weight, no-cholesterol, |
| super-optimized grammar? Read on...</p> |
| <p>I have a love-hate relationship with rules. I guess you know the reasons why. |
| A lot of problems stem from the limitation of rules. Dynamic polymorphism and |
| static polymorphism in C++ do not mix well. There is no notion of virtual template |
| functions in C++; at least not just yet. Thus, the <strong>rule is tied to a |
| specific scanner type</strong>. This results in problems such as the <a href="faq.html#scanner_business">scanner |
| business</a>, our no. 1 FAQ. Apart from that, the virtual functions in rules |
| slow down parsing, kill all meta-information, and kills inlining, hence bloating |
| the generated code, especially for very tiny rules such as:</p> |
| <pre> r <span class="special">=</span> ch_p<span class="special">(</span><span class="quotes">'x'</span><span class="special">) >></span> uint_p<span class="special">;</span></pre> |
| <p> The rule's limitation is the main reason why the grammar is designed the way |
| it is now, with a nested template definition class. The rule's limitation is |
| also the reason why subrules exists. But do we really need rules? Of course! |
| Before C++ adopts some sort of auto-type deduction, such as that proposed by |
| David Abrahams in clc++m:</p> |
| <pre> |
| <code><span class=keyword>auto </span><span class=identifier>r </span><span class=special>= ...</span><span class=identifier>definition </span><span class=special>...</span></code></pre> |
| <p> we are tied to the rule as RHS placeholders. However.... in some occasions |
| we can get by without rules! For instance, rather than writing:</p> |
| <pre> |
| <code><span class=identifier>rule</span><span class=special><> </span><span class=identifier>x </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'x'</span><span class=special>);</span></code></pre> |
| <p> It's better to write:</p> |
| <pre> |
| <code><span class=identifier>chlit</span><span class=special><> </span><span class=identifier>x </span><span class=special>= </span><span class=identifier>ch_p</span><span class=special>(</span><span class=literal>'x'</span><span class=special>);</span></code></pre> |
| <p> That's trivial. But what if the rule is rather complicated? Ok, let's proceed |
| stepwise... I'll investigate a simple skip_parser based on the C grammar from |
| Hartmut Kaiser. Basically, the grammar is written as (see <a href="../example/techniques/no_rules/no_rule1.cpp">no_rule1.cpp</a>):</p> |
| <pre><code> <span class=keyword>struct </span><span class=identifier>skip_grammar </span><span class=special>: </span><span class=identifier>grammar</span><span class=special><</span><span class=identifier>skip_grammar</span><span class=special>> |
| { |
| </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>> |
| </span><span class=keyword>struct </span><span class=identifier>definition |
| </span><span class=special>{ |
| </span><span class=identifier>definition</span><span class=special>(</span><span class=identifier>skip_grammar </span><span class=keyword>const</span><span class=special>& /*</span><span class=identifier>self</span><span class=special>*/) |
| { |
| </span><span class=identifier>skip |
| </span><span class=special>= </span><span class=identifier>space_p |
| </span><span class=special>| </span><span class=string>"//" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=literal>'\n'</span><span class=special>) >> </span><span class=literal>'\n' |
| </span><span class=special>| </span><span class=string>"/*" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=string>"*/"</span><span class=special>) >> </span><span class=string>"*/" |
| </span><span class=special>; |
| } |
| |
| </span><span class=identifier>rule</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>> </span><span class=identifier>skip</span><span class=special>; |
| |
| </span><span class=identifier>rule</span><span class=special><</span><span class=identifier>ScannerT</span><span class=special>> </span><span class=keyword>const</span><span class=special>& |
| </span><span class=identifier>start</span><span class=special>() </span><span class=keyword>const </span><span class=special>{ </span><span class=keyword>return </span><span class=identifier>skip</span><span class=special>; } |
| }; |
| };</span></code></pre> |
| <p> Ok, so far so good. Can we do better? Well... since there are no recursive |
| rules there (in fact there's only one rule), you can expand the type of rule's |
| RHS as the rule type (see <a href="../example/techniques/no_rules/no_rule2.cpp">no_rule2.cpp</a>):</p> |
| <pre><code><span class=special> </span><span class=keyword>struct </span><span class=identifier>skip_grammar </span><span class=special>: </span><span class=identifier>grammar</span><span class=special><</span><span class=identifier>skip_grammar</span><span class=special>> |
| { |
| </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>> |
| </span><span class=keyword>struct </span><span class=identifier>definition |
| </span><span class=special>{ |
| </span> <span class=identifier>definition</span><span class=special>(</span><span class=identifier>skip_grammar </span><span class=keyword>const</span><span class=special>& /*</span><span class=identifier>self</span><span class=special>*/) |
| : </span><span class=identifier>skip</span><span class=special> |
| ( </span><span class=identifier>space_p |
| </span><span class=special>| </span><span class=string>"//" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=literal>'\n'</span><span class=special>) >> </span><span class=literal>'\n' |
| </span><span class=special>| </span><span class=string>"/*" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=string>"*/"</span><span class=special>) >> </span><span class=string>"*/" |
| </span><span class=special>) |
| { |
| } |
| |
| </span><span class=keyword>typedef |
| </span><span class=identifier>alternative</span><span class=special><</span><span class=identifier>alternative</span><span class=special><</span><span class=identifier>space_parser</span><span class=special>, </span><span class=identifier>sequence</span><span class=special><</span><span class=identifier>sequence</span><span class=special>< |
| </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*>, </span><span class=identifier>kleene_star</span><span class=special><</span><span class=identifier>difference</span><span class=special><</span><span class=identifier>anychar_parser</span><span class=special>, |
| </span><span class=identifier>chlit</span><span class=special><</span><span class=keyword>char</span><span class=special>> > > >, </span><span class=identifier>chlit</span><span class=special><</span><span class=keyword>char</span><span class=special>> > >, </span><span class=identifier>sequence</span><span class=special><</span><span class=identifier>sequence</span><span class=special>< |
| </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*>, </span><span class=identifier>kleene_star</span><span class=special><</span><span class=identifier>difference</span><span class=special><</span><span class=identifier>anychar_parser</span><span class=special>, |
| </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*> > > >, </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*> > > |
| </span><span class=identifier>skip_t</span><span class=special>; |
| </span><span class=special> </span><span class=identifier>skip_t </span><span class=identifier>skip</span><span class=special>; |
| |
| </span><span class=identifier>skip_t </span><span class=keyword>const</span><span class=special>& |
| </span><span class=identifier>start</span><span class=special>() </span><span class=keyword>const </span><span class=special>{ </span><span class=keyword>return </span><span class=identifier>skip</span><span class=special>; } |
| }; |
| };</span></code></pre> |
| <p> Ughhh! How did I do that? How was I able to get at the complex typedef? Am |
| I insane? Well, not really... there's a trick! What you do is define the typedef |
| <tt>skip_t</tt> first as int:</p> |
| <pre> |
| <code><span class=keyword>typedef </span><span class=keyword>int </span><span class=identifier>skip_t</span><span class=special>;</span></code></pre> |
| <p> Try to compile. Then, the compiler will generate an obnoxious error message |
| such as:</p> |
| <pre> |
| <code><span class=string>"cannot convert boost::spirit::alternative<... blah blah...to int"</span><span class=special>.</span></code></pre> |
| <p> <strong>THERE YOU GO!</strong> You got it's type! I just copy and paste the |
| correct type (removing explicit qualifications, if preferred).</p> |
| <p> Can we still go further? Yes. Remember that the grammar was designed for rules. |
| The nested template definition class is needed to get around the rule's limitations. |
| Without rules, I propose a new class called <tt>sub_grammar</tt>, the grammar's |
| low-fat counterpart:</p> |
| <pre><code><span class=special> </span><span class=keyword>namespace </span><span class=identifier>boost </span><span class=special>{ </span><span class=keyword>namespace </span><span class=identifier>spirit |
| </span><span class=special>{ |
| </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>DerivedT</span><span class=special>> |
| </span><span class=keyword>struct </span><span class=identifier>sub_grammar </span><span class=special>: </span><span class=identifier>parser</span><span class=special><</span><span class=identifier>DerivedT</span><span class=special>> |
| { |
| </span><span class=keyword>typedef </span><span class=identifier>sub_grammar </span><span class=identifier>self_t</span><span class=special>; |
| </span><span class=keyword>typedef </span><span class=identifier>DerivedT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>embed_t</span><span class=special>; |
| |
| </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>> |
| </span><span class=keyword>struct </span><span class=identifier>result |
| </span><span class=special>{ |
| </span><span class=keyword>typedef </span><span class=keyword>typename </span><span class=identifier>parser_result</span><span class=special>< |
| </span><span class=keyword>typename </span><span class=identifier>DerivedT</span><span class=special>::</span><span class=identifier>start_t</span><span class=special>, </span><span class=identifier>ScannerT</span><span class=special>>::</span><span class=identifier>type |
| </span><span class=identifier>type</span><span class=special>; |
| }; |
| |
| </span><span class=identifier>DerivedT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>derived</span><span class=special>() </span><span class=keyword>const |
| </span><span class=special>{ </span><span class=keyword>return </span><span class=special>*</span><span class=keyword>static_cast</span><span class=special><</span><span class=identifier>DerivedT </span><span class=keyword>const</span><span class=special>*>(</span><span class=keyword>this</span><span class=special>); } |
| |
| </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>ScannerT</span><span class=special>> |
| </span><span class=keyword>typename </span><span class=identifier>parser_result</span><span class=special><</span><span class=identifier>self_t</span><span class=special>, </span><span class=identifier>ScannerT</span><span class=special>>::</span><span class=identifier>type |
| </span><span class=identifier>parse</span><span class=special>(</span><span class=identifier>ScannerT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>scan</span><span class=special>) </span><span class=keyword>const |
| </span><span class=special>{ |
| </span><span class=keyword>return </span><span class=identifier>derived</span><span class=special>().</span><span class=identifier>start</span><span class=special>.</span><span class=identifier>parse</span><span class=special>(</span><span class=identifier>scan</span><span class=special>); |
| } |
| }; |
| }}</span></code></pre> |
| <p>With the <tt>sub_grammar</tt> class, we can define our skipper grammar this |
| way (see <a href="../example/techniques/no_rules/no_rule3.cpp">no_rule3.cpp</a>):</p> |
| <pre><code><span class=special> </span><span class=keyword>struct </span><span class=identifier>skip_grammar </span><span class=special>: </span><span class=identifier>sub_grammar</span><span class=special><</span><span class=identifier>skip_grammar</span><span class=special>> |
| { |
| </span><span class=keyword>typedef |
| </span><span class=identifier>alternative</span><span class=special><</span><span class=identifier>alternative</span><span class=special><</span><span class=identifier>space_parser</span><span class=special>, </span><span class=identifier>sequence</span><span class=special><</span><span class=identifier>sequence</span><span class=special>< |
| </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*>, </span><span class=identifier>kleene_star</span><span class=special><</span><span class=identifier>difference</span><span class=special><</span><span class=identifier>anychar_parser</span><span class=special>, |
| </span><span class=identifier>chlit</span><span class=special><</span><span class=keyword>char</span><span class=special>> > > >, </span><span class=identifier>chlit</span><span class=special><</span><span class=keyword>char</span><span class=special>> > >, </span><span class=identifier>sequence</span><span class=special><</span><span class=identifier>sequence</span><span class=special>< |
| </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*>, </span><span class=identifier>kleene_star</span><span class=special><</span><span class=identifier>difference</span><span class=special><</span><span class=identifier>anychar_parser</span><span class=special>, |
| </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*> > > >, </span><span class=identifier>strlit</span><span class=special><</span><span class=keyword>const </span><span class=keyword>char</span><span class=special>*> > > |
| </span><span class=identifier>start_t</span><span class=special>; |
| |
| </span><span class=identifier>skip_grammar</span><span class=special>() |
| : </span><span class=identifier>start |
| </span><span class=special>( |
| </span><span class=identifier>space_p |
| </span><span class=special>| </span><span class=string>"//" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=literal>'\n'</span><span class=special>) >> </span><span class=literal>'\n' |
| </span><span class=special>| </span><span class=string>"/*" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=string>"*/"</span><span class=special>) >> </span><span class=string>"*/" |
| </span><span class=special>) |
| {} |
| |
| </span><span class=identifier>start_t </span><span class=identifier>start</span><span class=special>; |
| };</span></code></pre> |
| <p>But what for, you ask? You can simply use the <tt>start_t</tt> type above as-is. |
| It's already a parser! We can just type:</p> |
| <pre> |
| <code><span class=identifier>skipper_t </span><span class=identifier>skipper </span><span class=special>= |
| </span><span class=identifier>space_p |
| </span><span class=special>| </span><span class=string>"//" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=literal>'\n'</span><span class=special>) >> </span><span class=literal>'\n' </span><br> <span class=special>| </span><span class=string>"/*" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=string>"*/"</span><span class=special>) >> </span><span class=string>"*/"</span> |
| <span class=special> ;</span></code></pre> |
| <p> and use <tt>skipper</tt> just as we would any parser? Well, a subtle difference |
| is that <tt>skipper</tt>, used this way will be embedded <strong>by value </strong>when<strong> |
| </strong>you compose more complex parsers using it. That is, if we use <tt>skipper</tt> |
| inside another production, the whole thing will be stored in the composite. |
| Heavy!</p> |
| <p> The proposed <tt>sub_grammar</tt> OTOH will be held by reference. Note:</p> |
| <pre><code> <span class=keyword>typedef </span><span class=identifier>DerivedT </span><span class=keyword>const</span><span class=special>& </span><span class=identifier>embed_t</span><span class=special>;</span></code></pre> |
| <p>The proposed <tt>sub_grammar</tt> does not have the inherent limitations of |
| rules, is very lighweight, and should be blazingly fast (can be fully inlined |
| and does not use virtual functions). Perhaps this class will be part of a future |
| spirit release. </p> |
| <table width="80%" border="0" align="center"> |
| <tr> |
| <td class="note_box"><img src="theme/note.gif" width="16" height="16"> <strong>The |
| no-rules result</strong><br> <br> |
| So, how much did we save? On MSVCV7.1, the original code: <a href="../example/techniques/no_rules/no_rule1.cpp">no_rule1.cpp</a> |
| compiles to <strong>28k</strong>. Eliding rules, <a href="../example/techniques/no_rules/no_rule2.cpp">no_rule2.cpp</a>, |
| we got <strong>24k</strong>. Not bad, we shaved off 4k amounting to a 14% |
| reduction. But you'll be in for a surprise. The last version, using the |
| sub-grammar: <a href="../example/techniques/no_rules/no_rule3.cpp">no_rule3.cpp</a>, |
| compiles to <strong>5.5k</strong>! That's a whopping 80% reduction.<br> |
| <br> |
| <table width="100%" border="1"> |
| <tr> |
| <td><a href="../example/techniques/no_rules/no_rule1.cpp">no_rule1.cpp</a></td> |
| <td><strong>28k</strong></td> |
| <td>standard rule and grammar</td> |
| </tr> |
| <tr> |
| <td><a href="../example/techniques/no_rules/no_rule2.cpp">no_rule2.cpp</a></td> |
| <td><strong>24k</strong></td> |
| <td>standard grammar, no rule</td> |
| </tr> |
| <tr> |
| <td><a href="../example/techniques/no_rules/no_rule3.cpp">no_rule3.cpp</a></td> |
| <td><strong>5.5k</strong></td> |
| <td>sub_grammar, no rule, no grammar</td> |
| </tr> |
| </table> </td> |
| </tr> |
| </table> |
| <h3><b> <a name="typeof" id="typeof"></a> typeof</b></h3> |
| <p>Some compilers already support the <tt>typeof</tt> keyword. Examples are g++ |
| and Metrowerks CodeWarrior. Someday, <tt>typeof</tt> will become commonplace. |
| It is worth noting that we can use <tt>typeof</tt> to define non-recursive rules |
| without using the rule class. To give an example, we'll use the skipper example |
| above; this time using <tt>typeof</tt>. First, to avoid redundancy, we'll introduce |
| a macro <tt>RULE</tt>: </p> |
| <pre><code> <span class=preprocessor>#define </span><span class=identifier>RULE</span><span class=special>(</span><span class=identifier>name</span><span class=special>, </span><span class=identifier>definition</span><span class=special>) </span><span class="keyword">typeof</span><span class=special>(</span><span class=identifier>definition</span><span class=special>) </span><span class=identifier>name </span><span class=special>= </span><span class=identifier>definition</span></code></pre> |
| <p>Then, simply:</p> |
| <pre><code><span class=identifier> </span><span class=identifier>RULE</span><span class=special>( |
| </span><span class=identifier>skipper</span><span class=special>, |
| ( </span><span class=identifier>space_p |
| </span><span class=special>| </span><span class=string>"//" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=literal>'\n'</span><span class=special>) >> </span><span class=literal>'\n' |
| </span><span class=special>| </span><span class=string>"/*" </span><span class=special>>> *(</span><span class=identifier>anychar_p </span><span class=special>- </span><span class=string>"*/"</span><span class=special>) >> </span><span class=string>"*/" |
| </span><span class=special>) |
| );</span></code></pre> |
| <p>(see <a href="../example/techniques/typeof.cpp">typeof.cpp</a>)</p> |
| <p>That's it! Now you can use skipper just as you would any parser. Be reminded, |
| however, that <tt>skipper</tt> above will be embedded by value when<strong> |
| </strong>you compose more complex parsers using it (see <tt>sub_grammar</tt> rationale above). You can use the <tt>sub_grammar</tt> class to avoid this problem.</p> |
| <h3><a name="nabialek_trick"></a> Nabialek trick</h3> |
| <p>This technique, I'll call the <strong><em>"Nabialek trick" </em></strong>(from the name of its inventor, Sam Nabialek), can improve the rule dispatch from linear non-deterministic to deterministic. The trick applies to grammars where a keyword (operator, etc), precedes a production. There are lots of grammars similar to this:</p> |
| <pre> <span class=identifier>r </span><span class=special>= |
| </span><span class=identifier>keyword1 </span><span class=special>>> </span><span class=identifier>production1 |
| </span><span class=special>| </span><span class=identifier>keyword2 </span><span class=special>>> </span><span class=identifier>production2 |
| </span><span class=special>| </span><span class=identifier>keyword3 </span><span class=special>>> </span><span class=identifier>production3 |
| </span><span class=special>| </span><span class=identifier>keyword4 </span><span class=special>>> </span><span class=identifier>production4 |
| </span><span class=special>| </span><span class=identifier>keyword5 </span><span class=special>>> </span><span class=identifier>production5 |
| </span><span class=comment>/*** etc ***/ |
| </span><span class=special>;</span></pre> |
| <p>The cascaded alternatives are tried one at a time through trial and error until something matches. The Nabialek trick takes advantage of the <a href="symbols.html">symbol table</a>'s search properties to optimize the dispatching of the alternatives. For an example, see <a href="../example/techniques/nabialek.cpp">nabialek.cpp</a>. The grammar works as follows. There are two rules (<tt>one</tt> and <tt>two</tt>). When "one" is recognized, rule <tt>one</tt> is invoked. When "two" is recognized, rule <tt>two</tt> is invoked. Here's the grammar:</p> |
| <pre><span class=special> </span><span class=identifier>one </span><span class=special>= </span><span class=identifier>name</span><span class=special>; |
| </span><span class=identifier>two </span><span class=special>= </span><span class=identifier>name </span><span class=special>>> </span><span class=literal>',' </span><span class=special>>> </span><span class=identifier>name</span><span class=special>; |
| |
| </span><span class=identifier>continuations</span><span class=special>.</span><span class=identifier>add |
| </span><span class=special>(</span><span class=string>"one"</span><span class=special>, &</span><span class=identifier>one</span><span class=special>) |
| </span><span class=special>(</span><span class=string>"two"</span><span class=special>, &</span><span class=identifier>two</span><span class=special>) |
| </span><span class=special>; |
| |
| </span><span class=identifier>line </span><span class=special>= </span><span class=identifier>continuations</span><span class=special>[</span><span class=identifier>set_rest</span><span class=special><</span><span class=identifier>rule_t</span><span class=special>>(</span><span class=identifier>rest</span><span class=special>)] </span><span class=special>>> </span><span class=identifier>rest</span><span class=special>;</span></pre> |
| <p>where continuations is a <a href="symbols.html">symbol table</a> with pointer to rule_t slots. one, two, name, line and rest are rules:</p> |
| <pre><span class=special> </span><span class=identifier>rule_t </span><span class=identifier>name</span><span class=special>; |
| </span><span class=identifier>rule_t </span><span class=identifier>line</span><span class=special>; |
| </span><span class=identifier>rule_t </span><span class=identifier>rest</span><span class=special>; |
| </span><span class=identifier>rule_t </span><span class=identifier>one</span><span class=special>; |
| </span><span class=identifier>rule_t </span><span class=identifier>two</span><span class=special>; |
| |
| </span><span class=identifier>symbols</span><span class=special><</span><span class=identifier>rule_t</span><span class=special>*> </span><span class=identifier>continuations</span><span class=special>;</span></pre> |
| <p>set_rest, the semantic action attached to continuations is:</p> |
| <pre><span class=special> </span><span class=keyword>template </span><span class=special><</span><span class=keyword>typename </span><span class=identifier>Rule</span><span class=special>> |
| </span><span class=keyword>struct </span><span class=identifier>set_rest |
| </span><span class=special>{ |
| </span><span class=identifier>set_rest</span><span class=special>(</span><span class=identifier>Rule</span><span class=special>& </span><span class=identifier>the_rule</span><span class=special>) |
| </span><span class=special>: </span><span class=identifier>the_rule</span><span class=special>(</span><span class=identifier>the_rule</span><span class=special>) </span><span class=special>{} |
| |
| </span><span class=keyword>void </span><span class=keyword>operator</span><span class=special>()(</span><span class=identifier>Rule</span><span class=special>* </span><span class=identifier>newRule</span><span class=special>) </span><span class=keyword>const |
| </span><span class=special>{ </span><span class=identifier>m_theRule </span><span class=special>= </span><span class=special>*</span><span class=identifier>newRule</span><span class=special>; </span><span class=special>} |
| |
| </span><span class=identifier>Rule</span><span class=special>& </span><span class=identifier>the_rule</span><span class=special>; |
| </span><span class=special>};</span></pre> |
| <p>Notice how the rest <tt>rule</tt> gets set dynamically when the set_rule action is called. The dynamic grammar parses inputs such as:</p> |
| <p> "one only"<br> |
| "one again"<br> |
| "two first, second"</p> |
| <p>The cool part is that the <tt>rest</tt> rule is set (by the <tt>set_rest</tt> action) depending on what the symbol table got. If it got a <em>"one"</em> then rest = one. If it got <em>"two"</em>, then rest = two. Very nifty! This technique should be very fast, especially when there are lots of keywords. It would be nice to add special facilities to make this easy to use. I imagine:</p> |
| <pre><span class=special> </span><span class=identifier>r </span><span class=special>= </span><span class=identifier>keywords </span><span class=special>>> </span><span class=identifier>rest</span><span class=special>;</span></pre> |
| <p>where <tt>keywords</tt> is a special parser (based on the symbol table) that automatically sets its RHS (rest) depending on the acquired symbol. This, I think, is mighty cool! Someday perhaps... </p> |
| <p><img src="theme/note.gif" width="16" height="16"> Also, see the <a href="switch_parser.html">switch parser</a> for another deterministic parsing trick for character/token prefixes. </p> |
| <span class=special></span> |
| <table border="0"> |
| <tr> |
| <td width="10"></td> |
| <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> |
| <td width="30"><a href="style_guide.html"><img src="theme/l_arr.gif" border="0"></a></td> |
| <td width="30"><a href="faq.html"><img src="theme/r_arr.gif" border="0"></a></td> |
| </tr> |
| </table> |
| <br> |
| <hr size="1"> |
| <p class="copyright">Copyright © 1998-2003 Joel de Guzman<br> |
| <br> |
| <font size="2">Use, modification and distribution is subject to the Boost Software |
| License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt)</font></p> |
| <p class="copyright"> </p> |
| </body> |
| </html> |
