projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <html> |
| 2 | <head> | |
| 3 | <title>Epsilon</title> | |
| 4 | <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> | |
| 5 | <link rel="stylesheet" href="theme/style.css" type="text/css"> | |
| 6 | </head> | |
| 7 | ||
| 8 | <body> | |
| 9 | <table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2"> | |
| 10 | <tr> | |
| 11 | <td width="10"> | |
| 12 | </td> | |
| 13 | <td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>Epsilon</b></font> | |
| 14 | </td> | |
| 15 | <td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td> | |
| 16 | </tr> | |
| 17 | </table> | |
| 18 | <br> | |
| 19 | <table border="0"> | |
| 20 | <tr> | |
| 21 | <td width="10"></td> | |
| 22 | <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> | |
| 23 | <td width="30"><a href="rule.html"><img src="theme/l_arr.gif" border="0"></a></td> | |
| 24 | <td width="30"><a href="directives.html"><img src="theme/r_arr.gif" border="0"></a></td> | |
| 25 | </tr> | |
| 26 | </table> | |
| 27 | <p>The <strong>Epsilon</strong> (<tt>epsilon_p</tt> and <tt>eps_p</tt>) is a multi-purpose | |
| 28 | parser that returns a zero length match. </p> | |
| 29 | <h3>Simple Form</h3> | |
| 30 | <p>In its simplest form, epsilon_p matches the null string and always returns | |
| 31 | a match of zero length:</p> | |
| 32 | <pre><code><span class=special> </span><span class="identifier">epsilon_p </span><span class="comment">// always returns a zero-length match</span></code></pre> | |
| 33 | <p>This form is usually used to trigger a <a href="semantic_actions.html">semantic | |
| 34 | action</a> unconditionally. For example, it is useful in triggering error messages | |
| 35 | when a set of alternatives fail:</p> | |
| 36 | <pre><code><span class=special> </span><span class="identifier">r</span><span class="special"> = </span><span class="identifier">A</span><span class="special"> | </span><span class="identifier">B</span><span class="special"> | </span><span class="identifier">C</span><span class="special"> | </span><span class="identifier">eps_p</span><span class="special">[</span><span class="identifier">error</span><span class="special">];</span><span class="identifier"></span><span class="comment"> // error if A, B, or C fails to match</span></code></pre> | |
| 37 | <h3>Semantic Predicate</h3> | |
| 38 | <p>Semantic predicates allow you to attach a function anywhere in the grammar. | |
| 39 | In this role, the epsilon takes a 0-ary (nullary) function/functor. The run-time | |
| 40 | function/functor is typically a test that is called upon to resolve ambiguity | |
| 41 | in the grammar. A parse failure will be reported when the function/functor result | |
| 42 | evaluates to false. Otherwise an empty match will be reported. The general form | |
| 43 | is:</p> | |
| 44 | <pre> eps_p<span class="special">(</span>f<span class="special">) >></span> rest<span class="special">;</span> | |
| 45 | </pre> | |
| 46 | <p>The nullary function <tt>f</tt> is called to do a semantic test (say, checking | |
| 47 | if a symbol is in the <a href="symbols.html">symbol table</a>). If test returns | |
| 48 | <tt>true</tt>, <tt>rest</tt> will be evaluated. Otherwise, the production will | |
| 49 | return early with a no-match without ever touching <tt>rest</tt>.</p> | |
| 50 | <h3>Syntactic Predicate</h3> | |
| 51 | <p>Similar to Semantic predicates, Syntactic predicates assert a certain conditional | |
| 52 | syntax to be satisfied before evaluating another production. This time, epsilon_p | |
| 53 | accepts a (conditional) parser. The general form is:</p> | |
| 54 | <pre> eps_p<span class="special">(</span>p<span class="special">) >></span> rest<span class="special">;</span> | |
| 55 | </pre> | |
| 56 | <p>If <tt>p</tt> is matched on the input stream then attempt to recognize <tt>rest</tt>. | |
| 57 | The parser <tt>p </tt>is called to do a syntax check. Regardless of <tt>p</tt>'s | |
| 58 | success, <tt>eps_p(p)</tt> will always return a zero length match (i.e. the | |
| 59 | input is not consumed). If test returns <tt>true</tt>, <tt>rest</tt> will be | |
| 60 | evaluated. Otherwise, the production will return early with a no-match without | |
| 61 | ever touching <tt>rest</tt>.</p> | |
| 62 | <p>Example:</p> | |
| 63 | <pre><code><span class=special> </span><span class="identifier">eps_p</span><span class="special">(</span><span class="literal">'0'</span><span class="special">) >> </span><span class="identifier">oct_p </span><span class="comment">// note that '0' is actually a ch_p('0')</span><span class="identifier"> </span></code></pre> | |
| 64 | <p>Epsilon here is used as a syntactic predicate. <tt>oct_p</tt> (see <a href="numerics.html">numerics</a>) | |
| 65 | is parsed only if we see a leading <tt>'0'</tt>. Wrapping the leading <tt>'0'</tt> | |
| 66 | inside an epsilon makes the parser not consume anything from the input. If a | |
| 67 | <tt>'0'</tt> is seen, <tt>epsilon_p</tt> reports a successful match with zero | |
| 68 | length. </p> | |
| 69 | <table width="80%" border="0" align="center"> | |
| 70 | <tr> | |
| 71 | <td class="note_box"><div align="justify"><img src="theme/note.gif" width="16" height="16"> | |
| 72 | <b>Primitive arguments</b> <br> | |
| 73 | <br> | |
| 74 | Epsilon allows primitive type arguments such as <tt>char</tt>, <tt>int</tt>, | |
| 75 | <tt>wchar_t</tt>, <tt>char const<span class="operators">*</span></tt>, | |
| 76 | <tt>wchar_t const<span class="operators">*</span></tt> and so on. Examples: | |
| 77 | <tt><br> | |
| 78 | <br> | |
| 79 | </tt><code><span class="identifier">eps_p</span><tt><span class=special>(</span><span class=string>"hello"</span><span class=special>)</span><span class=comment> | |
| 80 | // same as eps_p(str_p("hello"))</span></tt><span class=identifier><br> | |
| 81 | eps_p</span><span class=special>(</span><span class=literal>'x'</span><span class="special">) | |
| 82 | </span><span class=comment>// same as eps_p(ch_p('x'))</span></code></div></td> | |
| 83 | </tr> | |
| 84 | </table> | |
| 85 | <h3><img src="theme/alert.gif" width="16" height="16"> Inhibiting Semantic Actions</h3> | |
| 86 | <p>In a syntactic predicate <tt>eps_p(p)</tt>, any semantic action directly or | |
| 87 | indirectly attached to the conditional parser <tt>p</tt> will not be called. | |
| 88 | However, semantic actions attached to epsilon itself will always be called. | |
| 89 | The following code snippets illustrates the behavior:</p> | |
| 90 | <pre> eps_p<span class="special">(</span>c<span class="special">[</span>f<span class="special">])</span> <span class="comment">// f not called</span><br> eps_p<span class="special">(</span>c<span class="special">)[</span>f<span class="special">]</span> <span class="comment">// f is called</span><br> eps_p<span class="special">[</span>f<span class="special">]</span> <span class="comment">// f is called</span></pre> | |
| 91 | <p>Actually, the conditional parser <tt>p</tt> is implicitly wrapped in a <tt><a href="scanner.html#no_actions_scanner">no_actions_d</a></tt> | |
| 92 | directive:</p> | |
| 93 | <pre><code><span class=special> </span>no_actions_d<span class="special">[</span>p<span class="special">]</span></code></pre> | |
| 94 | <p>The conditional parser is required to be free from side-effects (semantic actions). | |
| 95 | <code></code>The conditional parser's purpose is to resolve ambiguity by looking | |
| 96 | ahead in the input stream for a certain pattern. Ambiguity and semantic actions | |
| 97 | do not mix well. On an ambiguous grammar, backtracking happens. And when it | |
| 98 | happens, we cannot undo the effects of triggered semantic actions. </p> | |
| 99 | <h3>Negation</h3> | |
| 100 | <p>Operator <tt>~</tt> is defined for parsers constructed by <tt>epsilon_p</tt>/<tt>eps_p</tt>. | |
| 101 | It performs negation by complementing the results reported. <tt>~~eps_p(x)</tt> | |
| 102 | is identical to <tt>eps_p(x)</tt>.</p> | |
| 103 | <table border="0"> | |
| 104 | <tr> | |
| 105 | <td width="10"></td> | |
| 106 | <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> | |
| 107 | <td width="30"><a href="rule.html"><img src="theme/l_arr.gif" border="0"></a></td> | |
| 108 | <td width="30"><a href="directives.html"><img src="theme/r_arr.gif" border="0"></a></td> | |
| 109 | </tr> | |
| 110 | </table> | |
| 111 | <br> | |
| 112 | <hr size="1"> | |
| 113 | <p class="copyright">Copyright © 1998-2003 Joel de Guzman<br> | |
| 114 | Copyright © 2003 Martin Wille<br> | |
| 115 | <br> | |
| 116 | <font size="2">Use, modification and distribution is subject to the Boost Software | |
| 117 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
| 118 | http://www.boost.org/LICENSE_1_0.txt) </font> </p> | |
| 119 | <p> </p> | |
| 120 | </body> | |
| 121 | </html> |