<html><head><link rel="stylesheet" href="resource://content-accessible/plaintext.css"><style media="screen" id="__markdown-viewer__md_css"></style><style media="print" id="__markdown-viewer__md_print_css"></style><style id="__markdown-viewer__hljs_css"></style><style id="__markdown-viewer__katex_css"></style><style id="__markdown-viewer__texmath_css"></style><style id="__markdown-viewer__menu_css"></style><style id="__markdown-viewer__custom_css"></style><meta name="viewport" content="width=device-width, initial-scale=1"><title>Appendix: Experimental Features</title></head><body><div id="__markdown-viewer__tools" class="floating"><input type="checkbox" id="__markdown-viewer__show-tools"><label for="__markdown-viewer__show-tools"></label><div id="__markdown-viewer__toc" class="toggleable"><ul><li><a href="#appendix-experimental-features">Appendix: Experimental Features</a><ul><li><a href="#the-wildcard-token">The Wildcard Token</a></li></ul></li></ul></div><p class="toggleable">Pick a markdown and code style:<br><select id="__markdown-viewer__mdselect"><option value="sss">default</option><option value="github">github</option></select><select id="__markdown-viewer__hlselect"><option value="a11y-dark">a11y-dark</option><option value="a11y-light">a11y-light</option><option value="a11y-auto">a11y-auto</option><option value="agate">agate</option><option value="androidstudio">androidstudio</option><option value="an-old-hope">an-old-hope</option><option value="arduino-light">arduino-light</option><option value="arta">arta</option><option value="ascetic">ascetic</option><option value="atelier-cave-dark">atelier-cave-dark</option><option value="atelier-cave-light">atelier-cave-light</option><option value="atelier-cave-auto">atelier-cave-auto</option><option value="atelier-dune-dark">atelier-dune-dark</option><option value="atelier-dune-light">atelier-dune-light</option><option value="atelier-dune-auto">atelier-dune-auto</option><option value="atelier-estuary-dark">atelier-estuary-dark</option><option value="atelier-estuary-light">atelier-estuary-light</option><option value="atelier-estuary-auto">atelier-estuary-auto</option><option value="atelier-forest-dark">atelier-forest-dark</option><option value="atelier-forest-light">atelier-forest-light</option><option value="atelier-forest-auto">atelier-forest-auto</option><option value="atelier-heath-dark">atelier-heath-dark</option><option value="atelier-heath-light">atelier-heath-light</option><option value="atelier-heath-auto">atelier-heath-auto</option><option value="atelier-lakeside-dark">atelier-lakeside-dark</option><option value="atelier-lakeside-light">atelier-lakeside-light</option><option value="atelier-lakeside-auto">atelier-lakeside-auto</option><option value="atelier-plateau-dark">atelier-plateau-dark</option><option value="atelier-plateau-light">atelier-plateau-light</option><option value="atelier-plateau-auto">atelier-plateau-auto</option><option value="atelier-savanna-dark">atelier-savanna-dark</option><option value="atelier-savanna-light">atelier-savanna-light</option><option value="atelier-savanna-auto">atelier-savanna-auto</option><option value="atelier-seaside-dark">atelier-seaside-dark</option><option value="atelier-seaside-light">atelier-seaside-light</option><option value="atelier-seaside-auto">atelier-seaside-auto</option><option value="atelier-sulphurpool-dark">atelier-sulphurpool-dark</option><option value="atelier-sulphurpool-light">atelier-sulphurpool-light</option><option value="atelier-sulphurpool-auto">atelier-sulphurpool-auto</option><option value="atom-one-dark">atom-one-dark</option><option value="atom-one-dark-reasonable">atom-one-dark-reasonable</option><option value="atom-one-light">atom-one-light</option><option value="brown-paper">brown-paper</option><option value="codepen-embed">codepen-embed</option><option value="color-brewer">color-brewer</option><option value="darcula">darcula</option><option value="dark">dark</option><option value="default">default</option><option value="docco">docco</option><option value="dracula">dracula</option><option value="far">far</option><option value="foundation">foundation</option><option value="github">github</option><option value="github-gist">github-gist</option><option value="gml">gml</option><option value="googlecode">googlecode</option><option value="gradient-dark">gradient-dark</option><option value="grayscale">grayscale</option><option value="gruvbox-dark">gruvbox-dark</option><option value="gruvbox-light">gruvbox-light</option><option value="gruvbox-auto">gruvbox-auto</option><option value="hopscotch">hopscotch</option><option value="hybrid">hybrid</option><option value="idea">idea</option><option value="ir-black">ir-black</option><option value="isbl-editor-dark">isbl-editor-dark</option><option value="isbl-editor-light">isbl-editor-light</option><option value="isbl-editor-auto">isbl-editor-auto</option><option value="kimbie">kimbie</option><option value="kimbie">kimbie</option><option value="lightfair">lightfair</option><option value="lioshi">lioshi</option><option value="magula">magula</option><option value="mono-blue">mono-blue</option><option value="monokai">monokai</option><option value="monokai-sublime">monokai-sublime</option><option value="night-owl">night-owl</option><option value="nnfx">nnfx</option><option value="nnfx-dark">nnfx-dark</option><option value="nord">nord</option><option value="obsidian">obsidian</option><option value="ocean">ocean</option><option value="paraiso-dark">paraiso-dark</option><option value="paraiso-light">paraiso-light</option><option value="paraiso-auto">paraiso-auto</option><option value="pojoaque">pojoaque</option><option value="purebasic">purebasic</option><option value="qtcreator_dark">qtcreator_dark</option><option value="qtcreator_light">qtcreator_light</option><option value="qtcreator_auto">qtcreator_auto</option><option value="railscasts">railscasts</option><option value="rainbow">rainbow</option><option value="routeros">routeros</option><option value="school-book">school-book</option><option value="shades-of-purple">shades-of-purple</option><option value="solarized-dark">solarized-dark</option><option value="solarized-light">solarized-light</option><option value="solarized-auto">solarized-auto</option><option value="srcery">srcery</option><option value="sunburst">sunburst</option><option value="tomorrow">tomorrow</option><option value="tomorrow-night">tomorrow-night</option><option value="tomorrow-night-blue">tomorrow-night-blue</option><option value="tomorrow-night-bright">tomorrow-night-bright</option><option value="tomorrow-night-eighties">tomorrow-night-eighties</option><option value="vs">vs</option><option value="vs2015">vs2015</option><option value="xcode">xcode</option><option value="xt256">xt256</option><option value="zenburn">zenburn</option></select></p><p class="toggleable"><a id="__markdown-viewer__download" download="markdown.html" style="display: none;">Download as HTML</a></p></div><div class="markdownRoot"><h2 id="appendix-experimental-features">Appendix: Experimental Features</h2>
<h3 id="the-wildcard-token">The Wildcard Token</h3>
<p>Rustlr version 0.2.9 introduced an experimental feature that allows users to write grammar productions that include a "wildcard" using <code>_</code> (underscore).
For example:</p>
<pre><code>E --> <span class="hljs-selector-tag">a</span> _* <span class="hljs-selector-tag">b</span>
</code></pre>
<p>The * symbol for zero or more repetitions was introduced in version 0.2.8 (along
with ? and +). Rustlr processes the above rule by adding a new non-terminal
symbol to represent the sequence:</p>
<pre><code>E <span class="hljs-comment">--> a T b</span>
T <span class="hljs-comment">--></span>
T <span class="hljs-comment">--> _</span>
</code></pre>
<p>However, the meaning of the <code>_</code> symbol is a bit intricate and requires an
understanding of how LR parsing works. At the heart of an LR parser
is a deterministic state machine (the "viable prefix automaton"). This
automaton <em>must stay deterministic</em>. This means that the correct way to
understand the underscore symbol is not as "any symbol" but as any <em>unexpected</em>
symbol. If a state defines a transition for symbol <code>b</code> as well as a transition
for the underscore, then these transitions must not render the machine
non-deterministic. In other words, the following should <strong>not</strong> cause
a "reduce-reduce" conflict:</p>
<pre><code><span class="hljs-selector-tag">F</span> <span class="hljs-selector-tag">--</span>> <span class="hljs-selector-tag">b</span> | <span class="hljs-selector-tag">_</span>
</code></pre>
<p>Rustlr works by treating <code>_</code> (represented internally as
<code>_WILDCARD_TOKEN_</code>) like any other terminal symbol when generating the
LR state machine. The wildcard role of the symbol is only signifcant
during parsing when a token is encountered that <strong>does not have a</strong>
regular transition defined for the current state. Normally, such a
situation results in a parsing error. However, if the state defines a
transition for <code>_</code>, then rustlr will follow the transition.
But the wildcard will never override a regular transition, if there is one.</p>
<p>What this means is that the intended meaning of the expression <code>a _* b</code> is <strong>not</strong> any sequence of symbols bracketed by a's and b's. The
above grammar (<code>E --> a _* b</code>) will fail to parse <code>"a b b b"</code> because
it cannot determine that the first two <code>b</code>'s are supposed to
recognized as wildcards and that only the last b is a "real b". That
is, it does not know which to apply to input <code>b</code> if the lookahead is also <code>b</code>.
It will parse <code>"a a a b"</code> because after the initial <code>a</code> is read, there are no
further conflicting transitions for <code>a</code>. To parse what we intend to, we have to modify the
grammar as follows:</p>
<pre><code><span class="hljs-selector-tag">F</span> <span class="hljs-selector-tag">--</span>> <span class="hljs-selector-tag">b</span> | <span class="hljs-selector-tag">_</span>
<span class="hljs-selector-tag">E</span> <span class="hljs-selector-tag">--</span>> <span class="hljs-selector-tag">a</span> <span class="hljs-selector-tag">F</span>* <span class="hljs-selector-tag">b</span>
</code></pre>
<p>This grammar does recognize any sequence of symbols bracketed by a and b.
The wildcard is thus much more subtle to use than one might like, but it
can still be useful, and thus it was decided to include it in Rustlr.</p>
</div></body></html>