bison-doc 1:3.0.4-1 / usr / share / doc / bison-doc / html / Why-Precedence.html

This file is indexed.

/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> &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="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 &lsquo;<samp>1&nbsp;<span class="nolinebreak">-</span>&nbsp;2&nbsp;*&nbsp;3</samp>&rsquo;<!-- /@w --> can be parsed in two different ways):
</p>
<div class="example">
<pre class="example">expr:
  expr '-' expr
| expr '*' expr
| expr '&lt;' expr
| '(' expr ')'
&hellip;
;
</pre></div>

<p>Suppose the parser has seen the tokens &lsquo;<samp>1</samp>&rsquo;, &lsquo;<samp>-</samp>&rsquo; and &lsquo;<samp>2</samp>&rsquo;;
should it reduce them via the rule for the subtraction operator?  It
depends on the next token.  Of course, if the next token is &lsquo;<samp>)</samp>&rsquo;, we
must reduce; shifting is invalid because no single rule can reduce the
token sequence &lsquo;<samp><span class="nolinebreak">-</span>&nbsp;2&nbsp;)</samp>&rsquo;<!-- /@w --> or anything starting with that.  But if
the next token is &lsquo;<samp>*</samp>&rsquo; or &lsquo;<samp>&lt;</samp>&rsquo;, 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) &lsquo;<samp>1&nbsp;<span class="nolinebreak">-</span>&nbsp;(2&nbsp;<var>op</var>&nbsp;3)</samp>&rsquo;<!-- /@w -->.  On the other
hand, if the subtraction is reduced before shifting <var>op</var>, the result
is &lsquo;<samp>(1&nbsp;<span class="nolinebreak">-</span>&nbsp;2)&nbsp;<var>op</var>&nbsp;3</samp>&rsquo;<!-- /@w -->.  Clearly, then, the choice of shift or
reduce should depend on the relative precedence of the operators
&lsquo;<samp>-</samp>&rsquo; and <var>op</var>: &lsquo;<samp>*</samp>&rsquo; should be shifted first, but not
&lsquo;<samp>&lt;</samp>&rsquo;.
</p>
<a name="index-associativity"></a>
<p>What about input such as &lsquo;<samp>1&nbsp;<span class="nolinebreak">-</span>&nbsp;2&nbsp;<span class="nolinebreak">-</span>&nbsp;5</samp>&rsquo;<!-- /@w -->; should this be
&lsquo;<samp>(1&nbsp;<span class="nolinebreak">-</span>&nbsp;2)&nbsp;<span class="nolinebreak">-</span>&nbsp;5</samp>&rsquo;<!-- /@w --> or should it be &lsquo;<samp>1&nbsp;<span class="nolinebreak">-</span>&nbsp;(2&nbsp;<span class="nolinebreak">-</span>&nbsp;5)</samp>&rsquo;<!-- /@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 &lsquo;<samp>1&nbsp;<span class="nolinebreak">-</span>&nbsp;2</samp>&rsquo;<!-- /@w --> and the lookahead token is &lsquo;<samp>-</samp>&rsquo;: 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> &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>

APT Browse - Built by Thomas Orozco.