/usr/share/doc/bison-doc/html/LR-Table-Construction.html

<!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: LR Table Construction</title>

<meta name="description" content="Bison 3.0.4: LR Table Construction">
<meta name="keywords" content="Bison 3.0.4: LR Table Construction">
<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="Default-Reductions.html#Default-Reductions" rel="next" title="Default Reductions">
<link href="Tuning-LR.html#Tuning-LR" rel="prev" title="Tuning LR">
<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="LR-Table-Construction"></a>
<div class="header">
<p>
Next: <a href="Default-Reductions.html#Default-Reductions" accesskey="n" rel="next">Default Reductions</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="LR-Table-Construction-1"></a>
<h4 class="subsection">5.8.1 LR Table Construction</h4>
<a name="index-Mysterious-Conflict"></a>
<a name="index-LALR-1"></a>
<a name="index-IELR-1"></a>
<a name="index-canonical-LR-1"></a>
<a name="index-_0025define-lr_002etype-1"></a>

<p>For historical reasons, Bison constructs LALR(1) parser tables by default.
However, LALR does not possess the full language-recognition power of LR.
As a result, the behavior of parsers employing LALR parser tables is often
mysterious.  We presented a simple example of this effect in <a href="Mysterious-Conflicts.html#Mysterious-Conflicts">Mysterious Conflicts</a>.
</p>
<p>As we also demonstrated in that example, the traditional approach to
eliminating such mysterious behavior is to restructure the grammar.
Unfortunately, doing so correctly is often difficult.  Moreover, merely
discovering that LALR causes mysterious behavior in your parser can be
difficult as well.
</p>
<p>Fortunately, Bison provides an easy way to eliminate the possibility of such
mysterious behavior altogether.  You simply need to activate a more powerful
parser table construction algorithm by using the <code>%define lr.type</code>
directive.
</p>
<dl>
<dt><a name="index-_0025define-lr_002etype-2"></a>Directive: <strong>%define lr.type</strong> <em><var>type</var></em></dt>
<dd><p>Specify the type of parser tables within the LR(1) family.  The accepted
values for <var>type</var> are:
</p>
<ul>
<li> <code>lalr</code> (default)
</li><li> <code>ielr</code>
</li><li> <code>canonical-lr</code>
</li></ul>

<p>(This feature is experimental. More user feedback will help to stabilize
it.)
</p></dd></dl>

<p>For example, to activate IELR, you might add the following directive to you
grammar file:
</p>
<div class="example">
<pre class="example">%define lr.type ielr
</pre></div>

<p>For the example in <a href="Mysterious-Conflicts.html#Mysterious-Conflicts">Mysterious Conflicts</a>, the mysterious
conflict is then eliminated, so there is no need to invest time in
comprehending the conflict or restructuring the grammar to fix it.  If,
during future development, the grammar evolves such that all mysterious
behavior would have disappeared using just LALR, you need not fear that
continuing to use IELR will result in unnecessarily large parser tables.
That is, IELR generates LALR tables when LALR (using a deterministic parsing
algorithm) is sufficient to support the full language-recognition power of
LR.  Thus, by enabling IELR at the start of grammar development, you can
safely and completely eliminate the need to consider LALR&rsquo;s shortcomings.
</p>
<p>While IELR is almost always preferable, there are circumstances where LALR
or the canonical LR parser tables described by Knuth
(see <a href="Bibliography.html#Bibliography">Knuth 1965</a>) can be useful.  Here we summarize the
relative advantages of each parser table construction algorithm within
Bison:
</p>
<ul>
<li> LALR

<p>There are at least two scenarios where LALR can be worthwhile:
</p>
<ul>
<li> GLR without static conflict resolution.

<a name="index-GLR-with-LALR"></a>
<p>When employing GLR parsers (see <a href="GLR-Parsers.html#GLR-Parsers">GLR Parsers</a>), if you do not resolve any
conflicts statically (for example, with <code>%left</code> or <code>%precedence</code>),
then
the parser explores all potential parses of any given input.  In this case,
the choice of parser table construction algorithm is guaranteed not to alter
the language accepted by the parser.  LALR parser tables are the smallest
parser tables Bison can currently construct, so they may then be preferable.
Nevertheless, once you begin to resolve conflicts statically, GLR behaves
more like a deterministic parser in the syntactic contexts where those
conflicts appear, and so either IELR or canonical LR can then be helpful to
avoid LALR&rsquo;s mysterious behavior.
</p>
</li><li> Malformed grammars.

<p>Occasionally during development, an especially malformed grammar with a
major recurring flaw may severely impede the IELR or canonical LR parser
table construction algorithm.  LALR can be a quick way to construct parser
tables in order to investigate such problems while ignoring the more subtle
differences from IELR and canonical LR.
</p></li></ul>

</li><li> IELR

<p>IELR (Inadequacy Elimination LR) is a minimal LR algorithm.  That is, given
any grammar (LR or non-LR), parsers using IELR or canonical LR parser tables
always accept exactly the same set of sentences.  However, like LALR, IELR
merges parser states during parser table construction so that the number of
parser states is often an order of magnitude less than for canonical LR.
More importantly, because canonical LR&rsquo;s extra parser states may contain
duplicate conflicts in the case of non-LR grammars, the number of conflicts
for IELR is often an order of magnitude less as well.  This effect can
significantly reduce the complexity of developing a grammar.
</p>
</li><li> Canonical LR

<a name="index-delayed-syntax-error-detection"></a>
<a name="index-LAC"></a>
<a name="index-_0025nonassoc-2"></a>
<p>While inefficient, canonical LR parser tables can be an interesting means to
explore a grammar because they possess a property that IELR and LALR tables
do not.  That is, if <code>%nonassoc</code> is not used and default reductions are
left disabled (see <a href="Default-Reductions.html#Default-Reductions">Default Reductions</a>), then, for every left context of
every canonical LR state, the set of tokens accepted by that state is
guaranteed to be the exact set of tokens that is syntactically acceptable in
that left context.  It might then seem that an advantage of canonical LR
parsers in production is that, under the above constraints, they are
guaranteed to detect a syntax error as soon as possible without performing
any unnecessary reductions.  However, IELR parsers that use LAC are also
able to achieve this behavior without sacrificing <code>%nonassoc</code> or
default reductions.  For details and a few caveats of LAC, see <a href="LAC.html#LAC">LAC</a>.
</p></li></ul>

<p>For a more detailed exposition of the mysterious behavior in LALR parsers
and the benefits of IELR, see <a href="Bibliography.html#Bibliography">Denny 2008 March</a>, and
<a href="Bibliography.html#Bibliography">Denny 2010 November</a>.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Default-Reductions.html#Default-Reductions" accesskey="n" rel="next">Default Reductions</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.4-1 / usr / share / doc / bison-doc / html / LR-Table-Construction.html
