/usr/share/doc/bison-doc/html/Default-Reductions.html

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

Copyright (C) 1988-1993, 1995, 1998-2013 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 5.2, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Bison 3.0.2: Default Reductions</title>

<meta name="description" content="Bison 3.0.2: Default Reductions">
<meta name="keywords" content="Bison 3.0.2: Default Reductions">
<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="Tuning-LR.html#Tuning-LR" rel="up" title="Tuning LR">
<link href="LAC.html#LAC" rel="next" title="LAC">
<link href="LR-Table-Construction.html#LR-Table-Construction" rel="prev" title="LR Table Construction">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
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" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Default-Reductions"></a>
<div class="header">
<p>
Next: <a href="LAC.html#LAC" accesskey="n" rel="next">LAC</a>, Previous: <a href="LR-Table-Construction.html#LR-Table-Construction" accesskey="p" rel="prev">LR Table Construction</a>, Up: <a href="Tuning-LR.html#Tuning-LR" accesskey="u" rel="up">Tuning LR</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="Default-Reductions-1"></a>
<h4 class="subsection">5.8.2 Default Reductions</h4>
<a name="index-default-reductions"></a>
<a name="index-_0025define-lr_002edefault_002dreduction-1"></a>
<a name="index-_0025nonassoc-3"></a>

<p>After parser table construction, Bison identifies the reduction with the
largest lookahead set in each parser state.  To reduce the size of the
parser state, traditional Bison behavior is to remove that lookahead set and
to assign that reduction to be the default parser action.  Such a reduction
is known as a <em>default reduction</em>.
</p>
<p>Default reductions affect more than the size of the parser tables.  They
also affect the behavior of the parser:
</p>
<ul>
<li> Delayed <code>yylex</code> invocations.

<a name="index-delayed-yylex-invocations"></a>
<a name="index-consistent-states"></a>
<a name="index-defaulted-states"></a>
<p>A <em>consistent state</em> is a state that has only one possible parser
action.  If that action is a reduction and is encoded as a default
reduction, then that consistent state is called a <em>defaulted state</em>.
Upon reaching a defaulted state, a Bison-generated parser does not bother to
invoke <code>yylex</code> to fetch the next token before performing the reduction.
In other words, whether default reductions are enabled in consistent states
determines how soon a Bison-generated parser invokes <code>yylex</code> for a
token: immediately when it <em>reaches</em> that token in the input or when it
eventually <em>needs</em> that token as a lookahead to determine the next
parser action.  Traditionally, default reductions are enabled, and so the
parser exhibits the latter behavior.
</p>
<p>The presence of defaulted states is an important consideration when
designing <code>yylex</code> and the grammar file.  That is, if the behavior of
<code>yylex</code> can influence or be influenced by the semantic actions
associated with the reductions in defaulted states, then the delay of the
next <code>yylex</code> invocation until after those reductions is significant.
For example, the semantic actions might pop a scope stack that <code>yylex</code>
uses to determine what token to return.  Thus, the delay might be necessary
to ensure that <code>yylex</code> does not look up the next token in a scope that
should already be considered closed.
</p>
</li><li> Delayed syntax error detection.

<a name="index-delayed-syntax-error-detection-1"></a>
<p>When the parser fetches a new token by invoking <code>yylex</code>, it checks
whether there is an action for that token in the current parser state.  The
parser detects a syntax error if and only if either (1) there is no action
for that token or (2) the action for that token is the error action (due to
the use of <code>%nonassoc</code>).  However, if there is a default reduction in
that state (which might or might not be a defaulted state), then it is
impossible for condition 1 to exist.  That is, all tokens have an action.
Thus, the parser sometimes fails to detect the syntax error until it reaches
a later state.
</p>
<a name="index-LAC-1"></a>
<p>While default reductions never cause the parser to accept syntactically
incorrect sentences, the delay of syntax error detection can have unexpected
effects on the behavior of the parser.  However, the delay can be caused
anyway by parser state merging and the use of <code>%nonassoc</code>, and it can
be fixed by another Bison feature, LAC.  We discuss the effects of delayed
syntax error detection and LAC more in the next section (see <a href="LAC.html#LAC">LAC</a>).
</p></li></ul>

<p>For canonical LR, the only default reduction that Bison enables by default
is the accept action, which appears only in the accepting state, which has
no other action and is thus a defaulted state.  However, the default accept
action does not delay any <code>yylex</code> invocation or syntax error detection
because the accept action ends the parse.
</p>
<p>For LALR and IELR, Bison enables default reductions in nearly all states by
default.  There are only two exceptions.  First, states that have a shift
action on the <code>error</code> token do not have default reductions because
delayed syntax error detection could then prevent the <code>error</code> token
from ever being shifted in that state.  However, parser state merging can
cause the same effect anyway, and LAC fixes it in both cases, so future
versions of Bison might drop this exception when LAC is activated.  Second,
GLR parsers do not record the default reduction as the action on a lookahead
token for which there is a conflict.  The correct action in this case is to
split the parse instead.
</p>
<p>To adjust which states have default reductions enabled, use the
<code>%define lr.default-reduction</code> directive.
</p>
<dl>
<dt><a name="index-_0025define-lr_002edefault_002dreduction-2"></a>Directive: <strong>%define lr.default-reduction</strong> <em><var>where</var></em></dt>
<dd><p>Specify the kind of states that are permitted to contain default reductions.
The accepted values of <var>where</var> are:
</p><ul>
<li> <code>most</code> (default for LALR and IELR)
</li><li> <code>consistent</code>
</li><li> <code>accepting</code> (default for canonical LR)
</li></ul>

<p>(The ability to specify where default reductions are permitted is
experimental.  More user feedback will help to stabilize it.)
</p></dd></dl>

<hr>
<div class="header">
<p>
Next: <a href="LAC.html#LAC" accesskey="n" rel="next">LAC</a>, Previous: <a href="LR-Table-Construction.html#LR-Table-Construction" accesskey="p" rel="prev">LR Table Construction</a>, Up: <a href="Tuning-LR.html#Tuning-LR" accesskey="u" rel="up">Tuning LR</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.2-1 / usr / share / doc / bison-doc / html / Default-Reductions.html
