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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="Microsoft FrontPage 2.0">
<title>Geyacc: Operator Precedence</title>
</head>
<body bgcolor="#FFFFFF">
<table border="0" width="100%">
<tr>
<td><font size="6"><strong>Operator Precedence</strong></font></td>
<td align="right"><a href="algorithm.html"><img
src="../image/previous.gif" alt="Previous" border="0"
width="40" height="40"></a><a href="context.html"><img
src="../image/next.gif" alt="Next" border="0" width="40"
height="40"></a></td>
</tr>
</table>
<hr size="1">
<p>A situation where <a href="algorithm.html#shift_reduce">shift/reduce
conflicts</a> appear is in arithmetic expressions. Here shifting
is not always the preferred resolution; the <em>geyacc</em>
declarations for operator precedence allow you to specify when to
shift and when to reduce.</p>
<h2>When Precedence is Needed</h2>
<p>Consider the following ambiguous grammar fragment (ambiguous
because the input <font color="#808000"><tt>1 - 2 * 3</tt></font>
can be parsed in two different ways):</p>
<blockquote>
<pre><font color="#800080">expr</font><font color="#0000FF">:</font> <font
color="#800080">expr</font> <font color="#FF0000">'-'</font> <font
color="#800080">expr</font>
<font color="#0000FF">|</font> <font color="#800080">expr</font> <font
color="#FF0000">'*'</font> <font color="#800080">expr</font>
<font color="#0000FF">|</font> <font color="#800080">expr</font> <font
color="#FF0000">'<'</font> <font color="#800080">expr</font>
<font color="#0000FF">|</font> <font color="#FF0000">'('</font> <font
color="#800080">expr</font> <font color="#FF0000">')'</font>
...
<font color="#0000FF">;</font></pre>
</blockquote>
<p>Suppose the parser has seen the tokens <font color="#808000"><tt>1</tt></font>,
<font color="#808000"><tt>-</tt></font> and <font color="#808000"><tt>2</tt></font>;
should it reduce them via the rule for the addition operator? It
depends on the next token. Of course, if the next token is <font
color="#808000"><tt>)</tt></font>, we must reduce; shifting is
invalid because no single rule can reduce the token sequence <font
color="#808000"><tt>- 2 )</tt></font> or anything starting with
that. But if the next token is <font color="#808000" size="4"><tt>*</tt></font>
or <font color="#808000"><tt><</tt></font>, we have a choice:
either shifting or reduction would allow the parse to complete,
but with different results.</p>
<p>To decide which one <em>geyacc</em> should do, we must
consider the results. If the next operator token <font
color="#808000"><tt>OP</tt></font> is shifted, then it must be
reduced first in order to permit another opportunity to reduce
the sum. The result is (in effect) <font color="#808000"><tt>1 -
(2 OP 3)</tt></font>. On the other hand, if the subtraction is
reduced before shifting <font color="#808000"><tt>OP</tt></font>,
the result is <font color="#808000"><tt>(1 - 2) OP 3</tt></font>.
Clearly, then, the choice of shift or reduce should depend on the
relative precedence of the operators <font color="#808000"><tt>-</tt></font>
and <font color="#808000"><tt>OP</tt></font>: <font
color="#808000" size="4"><tt>*</tt></font> should be shifted
first, but not <font color="#808000"><tt><</tt></font>.</p>
<p>What about input such as <font color="#808000"><tt>1 - 2 - 5</tt></font>;
should this be <font color="#808000"><tt>(1 - 2) - 5</tt></font>
or should it be <font color="#808000"><tt>1 - (2 - 5)</tt></font>?
For most operators we prefer the former, which is called <em><strong>left
association</strong></em>. The latter alternative, <em><strong>right
association</strong></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 <font
color="#808000"><tt>1 - 2</tt></font> and the look-ahead token is
<font color="#808000"><tt>-</tt></font>: shifting makes
right-associativity.</p>
<h2>Specifying Operator Precedence</h2>
<p><em>Geyacc</em> allows you to specify these choices with the
operator precedence declarations <font color="#0000FF"><tt>%left</tt></font>
and <font color="#0000FF"><tt>%right</tt></font>. Each such
declaration contains a list of tokens, which are operators whose
precedence and associativity is being declared. The <font
color="#0000FF"><tt>%left</tt></font> declaration makes all those
operators left-associative and the <font color="#0000FF"><tt>%right</tt></font>
declaration makes them right-associative. A third alternative is <font
color="#0000FF"><tt>%nonassoc</tt></font>, which declares that it
is a syntax error to find the same operator twice "in a
row".</p>
<p>The relative precedence of different operators is controlled
by the order in which they are declared. The first <font
color="#0000FF"><tt>%left</tt></font> or <font color="#0000FF"><tt>%right</tt></font>
declaration in the file declares the operators whose precedence
is lowest, the next such declaration declares the operators whose
precedence is a little higher, and so on.</p>
<h2>Precedence Examples</h2>
<p>In our example, we would want the following declarations:</p>
<blockquote>
<pre><font color="#0000FF">%left</font> <font color="#FF0000">'<'</font>
<font color="#0000FF">%left</font> <font color="#FF0000">'-'</font>
<font color="#0000FF">%left</font> <font color="#FF0000">'*'</font></pre>
</blockquote>
<p>In a more complete example, which supports other operators as
well, we would declare them in groups of equal precedence. For
example,<font color="#FF0000" size="2" face="Courier New"> </font><font
color="#FF0000"><tt>'+'</tt></font> is declared with <font
color="#FF0000"><tt>'-'</tt></font>:</p>
<blockquote>
<pre><font color="#0000FF">%left </font><font color="#FF0000">'<' '>' '=' NE LE GE</font><font
color="#0000FF">
%left </font><font color="#FF0000">'+' '-'</font><font
color="#0000FF">
%left </font><font color="#FF0000">'*' '/'</font></pre>
</blockquote>
<p>Here <font color="#FF0000"><tt>NE</tt></font> and so on stand
for the operators for "not equal" and so on. We assume
that these tokens are more than one character long and therefore
are represented by names, not character literals.</p>
<h2>How Precedence Works</h2>
<p>The first effect of the precedence declarations is to assign
precedence levels to the terminal symbols declared. The second
effect is to assign precedence levels to certain rules: each rule
gets its precedence from the last terminal symbol mentioned in
the components. (You can also specify explicitly the <a
href="#context">precedence of a rule</a>.)</p>
<p>Finally, the resolution of conflicts works by comparing the
precedence of the rule being considered with that of the
look-ahead token. If the token's precedence is higher, the choice
is to shift. If the rule's precedence is higher, the choice is to
reduce. If they have equal precedence, the choice is made based
on the associativity of that precedence level. The verbose output
file made by <a href="options.html#-v"><font color="#800000"><tt>-v</tt></font></a>
says how each conflict was resolved.</p>
<p>Not all rules and not all tokens have precedence. If either
the rule or the look-ahead token has no precedence, then the
default is to shift.</p>
<h2><a name="context">Context-Dependent Precedence</a></h2>
<p>Often the precedence of an operator depends on the context.
This sounds outlandish at first, but it is really very common.
For example, a minus sign typically has a very high precedence as
a unary operator, and a somewhat lower precedence (lower than
multiplication) as a binary operator.</p>
<p>The <em>geyacc</em> precedence declarations, <font
color="#0000FF"><tt>%left</tt></font>, <font color="#0000FF"><tt>%right</tt></font>
and <font color="#0000FF"><tt>%nonassoc</tt></font>, can only be
used once for a given token; so a token has only one precedence
declared in this way. For context-dependent precedence, you need
to use an additional mechanism: the <font color="#0000FF"><tt>%prec</tt></font>
modifier for rules. The <font color="#0000FF"><tt>%prec</tt></font>
modifier declares the precedence of a particular rule by
specifying a terminal symbol whose precedence should be used for
that rule. It's not necessary for that symbol to appear otherwise
in the rule. The modifier's syntax is:</p>
<blockquote>
<pre><font color="#0000FF">%prec</font> TERMINAL-SYMBOL</pre>
</blockquote>
<p>and it is written after the components of the rule. Its effect
is to assign the rule the precedence of <font size="2"
face="Courier New">TERMINAL-SYMBOL</font>, overriding the
precedence that would be deduced for it in the ordinary way. The
altered rule precedence then affects how conflicts involving that
rule are resolved.</p>
<p>Here is how <font color="#0000FF"><tt>%prec</tt></font> solves
the problem of unary minus. First, declare a precedence for a
fictitious terminal symbol named <font color="#FF0000"><tt>UMINUS</tt></font>.
There are no tokens of this type, but the symbol serves to stand
for its precedence:</p>
<blockquote>
<pre>...
<font color="#0000FF">%left </font><font color="#FF0000">'+' '-'</font><font
color="#0000FF">
%left </font><font color="#FF0000">'*'</font><font
color="#0000FF">
%left</font> <font color="#FF0000">UMINUS</font></pre>
</blockquote>
<p>Now the precedence of <font color="#FF0000"><tt>UMINUS</tt></font>
can be used in specific rules:</p>
<blockquote>
<pre><font color="#800080">exp</font><font color="#0000FF">:</font> ...
<font color="#0000FF">|</font> <font color="#800080">exp</font> <font
color="#FF0000">'-'</font> <font color="#800080">exp</font>
...
<font color="#0000FF">|</font> <font color="#FF0000">'-'</font> <font
color="#800080">exp</font> <font color="#0000FF">%prec</font> <font
color="#FF0000">UMINUS</font></pre>
</blockquote>
<hr size="1">
<table border="0" width="100%">
<tr>
<td><address>
<font size="2"><b>Copyright 1998</b></font><font
size="1"><b>, </b></font><font size="2"><strong>Eric
Bezault</strong></font><strong> </strong><font
size="2"><br>
<strong>mailto:</strong></font><a
href="mailto://www.gobosoft.com"><font size="2">ericb@gobosoft.com</font></a><font
size="2"><br>
<strong>http:</strong></font><a
href="http://www.gobosoft.com"><font size="2">//www.gobosoft.com</font></a><font
size="2"><br>
<strong>Last Updated:</strong> 9 August 1998</font><br>
<!--webbot bot="PurpleText"
preview="
$Date: 1999/06/12 18:57:04 $
$Revision: 1.7 $"
-->
</address>
</td>
<td align="right" valign="top"><a
href="http://www.gobosoft.com"><img
src="../image/home.gif" alt="Home" border="0" width="40"
height="40"></a><a href="index.html"><img
src="../image/toc.gif" alt="Toc" border="0" width="40"
height="40"></a><a href="algorithm.html"><img
src="../image/previous.gif" alt="Previous" border="0"
width="40" height="40"></a><a href="context.html"><img
src="../image/next.gif" alt="Next" border="0" width="40"
height="40"></a></td>
</tr>
</table>
</body>
</html>
|
