/usr/share/doc/bison-doc/html/Why-Precedence.html is in bison-doc 1:3.0.4-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | <!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: Why Precedence</title>
<meta name="description" content="Bison 3.0.4: Why Precedence">
<meta name="keywords" content="Bison 3.0.4: Why Precedence">
<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="Precedence.html#Precedence" rel="up" title="Precedence">
<link href="Using-Precedence.html#Using-Precedence" rel="next" title="Using Precedence">
<link href="Precedence.html#Precedence" rel="prev" title="Precedence">
<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="Why-Precedence"></a>
<div class="header">
<p>
Next: <a href="Using-Precedence.html#Using-Precedence" accesskey="n" rel="next">Using Precedence</a>, Up: <a href="Precedence.html#Precedence" accesskey="u" rel="up">Precedence</a> [<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="When-Precedence-is-Needed"></a>
<h4 class="subsection">5.3.1 When Precedence is Needed</h4>
<p>Consider the following ambiguous grammar fragment (ambiguous because the
input ‘<samp>1 <span class="nolinebreak">-</span> 2 * 3</samp>’<!-- /@w --> can be parsed in two different ways):
</p>
<div class="example">
<pre class="example">expr:
expr '-' expr
| expr '*' expr
| expr '<' expr
| '(' expr ')'
…
;
</pre></div>
<p>Suppose the parser has seen the tokens ‘<samp>1</samp>’, ‘<samp>-</samp>’ and ‘<samp>2</samp>’;
should it reduce them via the rule for the subtraction operator? It
depends on the next token. Of course, if the next token is ‘<samp>)</samp>’, we
must reduce; shifting is invalid because no single rule can reduce the
token sequence ‘<samp><span class="nolinebreak">-</span> 2 )</samp>’<!-- /@w --> or anything starting with that. But if
the next token is ‘<samp>*</samp>’ or ‘<samp><</samp>’, we have a choice: either
shifting or reduction would allow the parse to complete, but with
different results.
</p>
<p>To decide which one Bison should do, we must consider the results. If
the next operator token <var>op</var> is shifted, then it must be reduced
first in order to permit another opportunity to reduce the difference.
The result is (in effect) ‘<samp>1 <span class="nolinebreak">-</span> (2 <var>op</var> 3)</samp>’<!-- /@w -->. On the other
hand, if the subtraction is reduced before shifting <var>op</var>, the result
is ‘<samp>(1 <span class="nolinebreak">-</span> 2) <var>op</var> 3</samp>’<!-- /@w -->. Clearly, then, the choice of shift or
reduce should depend on the relative precedence of the operators
‘<samp>-</samp>’ and <var>op</var>: ‘<samp>*</samp>’ should be shifted first, but not
‘<samp><</samp>’.
</p>
<a name="index-associativity"></a>
<p>What about input such as ‘<samp>1 <span class="nolinebreak">-</span> 2 <span class="nolinebreak">-</span> 5</samp>’<!-- /@w -->; should this be
‘<samp>(1 <span class="nolinebreak">-</span> 2) <span class="nolinebreak">-</span> 5</samp>’<!-- /@w --> or should it be ‘<samp>1 <span class="nolinebreak">-</span> (2 <span class="nolinebreak">-</span> 5)</samp>’<!-- /@w -->? For most
operators we prefer the former, which is called <em>left association</em>.
The latter alternative, <em>right association</em>, is desirable for
assignment operators. The choice of left or right association is a
matter of whether the parser chooses to shift or reduce when the stack
contains ‘<samp>1 <span class="nolinebreak">-</span> 2</samp>’<!-- /@w --> and the lookahead token is ‘<samp>-</samp>’: shifting
makes right-associativity.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Using-Precedence.html#Using-Precedence" accesskey="n" rel="next">Using Precedence</a>, Up: <a href="Precedence.html#Precedence" accesskey="u" rel="up">Precedence</a> [<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>
|