Bell 32V development

[unix-history] / usr / doc / yacc / ss6

.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.