/usr/share/doc/bison-doc/html/Reduce

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- 
This manual (22 January 2015) is for GNU Bison (version
3.0.4), the GNU parser generator.

Copyright (C) 1988-1993, 1995, 1998-2015 Free Software
Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License,
Version 1.3 or any later version published by the Free Software
Foundation; with no Invariant Sections, with the Front-Cover texts
being "A GNU Manual," and with the Back-Cover Texts as in
(a) below.  A copy of the license is included in the section entitled
"GNU Free Documentation License."

(a) The FSF's Back-Cover Text is: "You have the freedom to copy and
modify this GNU manual.  Buying copies from the FSF
supports it in developing GNU and promoting software
freedom." -->
<!-- Created by GNU Texinfo 6.0, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Bison 3.0.4: Reduce/Reduce</title>

<meta name="description" content="Bison 3.0.4: Reduce/Reduce">
<meta name="keywords" content="Bison 3.0.4: Reduce/Reduce">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Index-of-Terms.html#Index-of-Terms" rel="index" title="Index of Terms">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Algorithm.html#Algorithm" rel="up" title="Algorithm">
<link href="Mysterious-Conflicts.html#Mysterious-Conflicts" rel="next" title="Mysterious Conflicts">
<link href="Parser-States.html#Parser-States" rel="prev" title="Parser States">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
blockquote.smallindentedblock {margin-right: 0em; font-size: smaller}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smalllisp {margin-left: 3.2em}
kbd {font-style: oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space: nowrap}
span.nolinebreak {white-space: nowrap}
span.roman {font-family: serif; font-weight: normal}
span.sansserif {font-family: sans-serif; font-weight: normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en">
<a name="Reduce_002fReduce"></a>
<div class="header">
<p>
Next: <a href="Mysterious-Conflicts.html#Mysterious-Conflicts" accesskey="n" rel="next">Mysterious Conflicts</a>, Previous: <a href="Parser-States.html#Parser-States" accesskey="p" rel="prev">Parser States</a>, Up: <a href="Algorithm.html#Algorithm" accesskey="u" rel="up">Algorithm</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index-of-Terms.html#Index-of-Terms" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Reduce_002fReduce-Conflicts"></a>
<h3 class="section">5.6 Reduce/Reduce Conflicts</h3>
<a name="index-reduce_002freduce-conflict"></a>
<a name="index-conflicts_002c-reduce_002freduce"></a>

<p>A reduce/reduce conflict occurs if there are two or more rules that apply
to the same sequence of input.  This usually indicates a serious error
in the grammar.
</p>
<p>For example, here is an erroneous attempt to define a sequence
of zero or more <code>word</code> groupings.
</p>
<div class="example">
<pre class="example">sequence:
  %empty         { printf (&quot;empty sequence\n&quot;); }
| maybeword
| sequence word  { printf (&quot;added word %s\n&quot;, $2); }
;
</pre><pre class="example">
</pre><pre class="example">maybeword:
  %empty    { printf (&quot;empty maybeword\n&quot;); }
| word      { printf (&quot;single word %s\n&quot;, $1); }
;
</pre></div>

<p>The error is an ambiguity: there is more than one way to parse a single
<code>word</code> into a <code>sequence</code>.  It could be reduced to a
<code>maybeword</code> and then into a <code>sequence</code> via the second rule.
Alternatively, nothing-at-all could be reduced into a <code>sequence</code>
via the first rule, and this could be combined with the <code>word</code>
using the third rule for <code>sequence</code>.
</p>
<p>There is also more than one way to reduce nothing-at-all into a
<code>sequence</code>.  This can be done directly via the first rule,
or indirectly via <code>maybeword</code> and then the second rule.
</p>
<p>You might think that this is a distinction without a difference, because it
does not change whether any particular input is valid or not.  But it does
affect which actions are run.  One parsing order runs the second rule&rsquo;s
action; the other runs the first rule&rsquo;s action and the third rule&rsquo;s action.
In this example, the output of the program changes.
</p>
<p>Bison resolves a reduce/reduce conflict by choosing to use the rule that
appears first in the grammar, but it is very risky to rely on this.  Every
reduce/reduce conflict must be studied and usually eliminated.  Here is the
proper way to define <code>sequence</code>:
</p>
<div class="example">
<pre class="example">sequence:
  %empty         { printf (&quot;empty sequence\n&quot;); }
| sequence word  { printf (&quot;added word %s\n&quot;, $2); }
;
</pre></div>

<p>Here is another common error that yields a reduce/reduce conflict:
</p>
<div class="example">
<pre class="example">sequence:
  %empty
| sequence words
| sequence redirects
;
</pre><pre class="example">
</pre><pre class="example">words:
  %empty
| words word
;
</pre><pre class="example">
</pre><pre class="example">redirects:
  %empty
| redirects redirect
;
</pre></div>

<p>The intention here is to define a sequence which can contain either
<code>word</code> or <code>redirect</code> groupings.  The individual definitions of
<code>sequence</code>, <code>words</code> and <code>redirects</code> are error-free, but the
three together make a subtle ambiguity: even an empty input can be parsed
in infinitely many ways!
</p>
<p>Consider: nothing-at-all could be a <code>words</code>.  Or it could be two
<code>words</code> in a row, or three, or any number.  It could equally well be a
<code>redirects</code>, or two, or any number.  Or it could be a <code>words</code>
followed by three <code>redirects</code> and another <code>words</code>.  And so on.
</p>
<p>Here are two ways to correct these rules.  First, to make it a single level
of sequence:
</p>
<div class="example">
<pre class="example">sequence:
  %empty
| sequence word
| sequence redirect
;
</pre></div>

<p>Second, to prevent either a <code>words</code> or a <code>redirects</code>
from being empty:
</p>
<div class="example">
<pre class="example">sequence:
  %empty
| sequence words
| sequence redirects
;
</pre><pre class="example">
</pre><pre class="example">words:
  word
| words word
;
</pre><pre class="example">
</pre><pre class="example">redirects:
  redirect
| redirects redirect
;
</pre></div>

<p>Yet this proposal introduces another kind of ambiguity!  The input
&lsquo;<samp>word word</samp>&rsquo; can be parsed as a single <code>words</code> composed of two
&lsquo;<samp>word</samp>&rsquo;s, or as two one-<code>word</code> <code>words</code> (and likewise for
<code>redirect</code>/<code>redirects</code>).  However this ambiguity is now a
shift/reduce conflict, and therefore it can now be addressed with precedence
directives.
</p>
<p>To simplify the matter, we will proceed with <code>word</code> and <code>redirect</code>
being tokens: <code>&quot;word&quot;</code> and <code>&quot;redirect&quot;</code>.
</p>
<p>To prefer the longest <code>words</code>, the conflict between the token
<code>&quot;word&quot;</code> and the rule &lsquo;<samp>sequence: sequence words</samp>&rsquo; must be resolved
as a shift.  To this end, we use the same techniques as exposed above, see
<a href="Non-Operators.html#Non-Operators">Using Precedence For Non Operators</a>.  One solution
relies on precedences: use <code>%prec</code> to give a lower precedence to the
rule:
</p>
<div class="example">
<pre class="example">%precedence &quot;word&quot;
%precedence &quot;sequence&quot;
%%
</pre><pre class="example">sequence:
  %empty
| sequence word      %prec &quot;sequence&quot;
| sequence redirect  %prec &quot;sequence&quot;
;
</pre><pre class="example">
</pre><pre class="example">words:
  word
| words &quot;word&quot;
;
</pre></div>

<p>Another solution relies on associativity: provide both the token and the
rule with the same precedence, but make them right-associative:
</p>
<div class="example">
<pre class="example">%right &quot;word&quot; &quot;redirect&quot;
%%
</pre><pre class="example">sequence:
  %empty
| sequence word      %prec &quot;word&quot;
| sequence redirect  %prec &quot;redirect&quot;
;
</pre></div>

<hr>
<div class="header">
<p>
Next: <a href="Mysterious-Conflicts.html#Mysterious-Conflicts" accesskey="n" rel="next">Mysterious Conflicts</a>, Previous: <a href="Parser-States.html#Parser-States" accesskey="p" rel="prev">Parser States</a>, Up: <a href="Algorithm.html#Algorithm" accesskey="u" rel="up">Algorithm</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Index-of-Terms.html#Index-of-Terms" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>
bison-doc 1:3.0.4-1 / usr / share / doc / bison-doc / html / Reduce_002fReduce.html
