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
|
.\" $OpenBSD: ss6,v 1.1 2002/12/03 21:36:35 mickey Exp $
.\"
.\" Copyright (C) Caldera International Inc. 2001-2002.
.\" All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code and documentation must retain the above
.\" copyright notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\" notice, this list of conditions and the following disclaimer in the
.\" documentation and/or other materials provided with the distribution.
.\" 3. All advertising materials mentioning features or use of this software
.\" must display the following acknowledgement:
.\" This product includes software developed or owned by Caldera
.\" International, Inc.
.\" 4. Neither the name of Caldera International, Inc. nor the names of other
.\" contributors may be used to endorse or promote products derived from
.\" this software without specific prior written permission.
.\"
.\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
.\" INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
.\" IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
.\" INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
.\" (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
.\" SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
.\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
.\" @(#)ss6 8.1 (Berkeley) 6/8/93
.\"
.SH
6: Precedence
.PP
There is one common situation
where the rules given above for resolving conflicts are not sufficient;
this is in the parsing of arithmetic expressions.
Most of the commonly used constructions for arithmetic expressions can be naturally
described by the notion of
.I precedence
levels for operators, together with information about left
or right associativity.
It turns out that ambiguous grammars with appropriate disambiguating rules
can be used to create parsers that are faster and easier to
write than parsers constructed from unambiguous grammars.
The basic notion is to write grammar rules
of the form
.DS
expr : expr OP expr
.DE
and
.DS
expr : UNARY expr
.DE
for all binary and unary operators desired.
This creates a very ambiguous grammar, with many parsing conflicts.
As disambiguating rules, the user specifies the precedence, or binding
strength, of all the operators, and the associativity
of the binary operators.
This information is sufficient to allow Yacc to resolve the parsing conflicts
in accordance with these rules, and construct a parser that realizes the desired
precedences and associativities.
.PP
The precedences and associativities are attached to tokens in the declarations section.
This is done by a series of lines beginning with a Yacc keyword: %left, %right,
or %nonassoc, followed by a list of tokens.
All of the tokens on the same line are assumed to have the same precedence level
and associativity; the lines are listed in
order of increasing precedence or binding strength.
Thus,
.DS
%left \'+\' \'\-\'
%left \'*\' \'/\'
.DE
describes the precedence and associativity of the four arithmetic operators.
Plus and minus are left associative, and have lower precedence than
star and slash, which are also left associative.
The keyword %right is used to describe right associative operators,
and the keyword %nonassoc is used to describe operators, like
the operator .LT. in Fortran, that may not associate with themselves; thus,
.DS
A .LT. B .LT. C
.DE
is illegal in Fortran, and such an operator would be described with the keyword
%nonassoc in Yacc.
As an example of the behavior of these declarations, the description
.DS
%right \'=\'
%left \'+\' \'\-\'
%left \'*\' \'/\'
%%
expr : expr \'=\' expr
| expr \'+\' expr
| expr \'\-\' expr
| expr \'*\' expr
| expr \'/\' expr
| NAME
;
.DE
might be used to structure the input
.DS
a = b = c*d \- e \- f*g
.DE
as follows:
.DS
a = ( b = ( ((c*d)\-e) \- (f*g) ) )
.DE
When this mechanism is used,
unary operators must, in general, be given a precedence.
Sometimes a unary operator and a binary operator
have the same symbolic representation, but different precedences.
An example is unary and binary \'\-\'; unary minus may be given the same
strength as multiplication, or even higher, while binary minus has a lower strength than
multiplication.
The keyword, %prec, changes the precedence level associated with a particular grammar rule.
%prec appears immediately after the body of the grammar rule, before the action or closing semicolon,
and is followed by a token name or literal.
It
causes the precedence of the grammar rule to become that of the following token name or literal.
For example, to make unary minus have the same precedence as multiplication the rules might resemble:
.DS
%left \'+\' \'\-\'
%left \'*\' \'/\'
%%
expr : expr \'+\' expr
| expr \'\-\' expr
| expr \'*\' expr
| expr \'/\' expr
| \'\-\' expr %prec \'*\'
| NAME
;
.DE
.PP
A token declared
by %left, %right, and %nonassoc need not be, but may be, declared by %token as well.
.PP
The precedences and associativities are used by Yacc to
resolve parsing conflicts; they give rise to disambiguating rules.
Formally, the rules work as follows:
.IP 1.
The precedences and associativities are recorded for those tokens and literals
that have them.
.IP 2.
A precedence and associativity is associated with each grammar rule; it is the precedence
and associativity of the last token or literal in the body of the rule.
If the %prec construction is used, it overrides this default.
Some grammar rules may have no precedence and associativity associated with them.
.IP 3.
When there is a reduce/reduce conflict, or there is a shift/reduce conflict
and either the input symbol or the grammar rule has no precedence and associativity,
then the two disambiguating rules given at the beginning of the section are used,
and the conflicts are reported.
.IP 4.
If there is a shift/reduce conflict, and both the grammar rule and the input character
have precedence and associativity associated with them, then the conflict is resolved
in favor of the action (shift or reduce) associated with the higher precedence.
If the precedences are the same, then the associativity is used; left
associative implies reduce, right associative implies shift, and nonassociating
implies error.
.PP
Conflicts resolved by precedence are not counted in the number of shift/reduce and reduce/reduce
conflicts reported by Yacc.
This means that mistakes in the specification of precedences may
disguise errors in the input grammar; it is a good idea to be sparing
with precedences, and use them in an essentially ``cookbook'' fashion,
until some experience has been gained.
The
.I y.output
file
is very useful in deciding whether the parser is actually doing
what was intended.
|
