.SH6: Precedence.PPThere is one common situationwhere 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 naturallydescribed by the notion of.I precedencelevels for operators, together with information about leftor right associativity.It turns out that ambiguous grammars with appropriate disambiguating rulescan be used to create parsers that are faster and easier towrite than parsers constructed from unambiguous grammars.The basic notion is to write grammar rulesof the form.DSexpr  :  expr  OP  expr.DEand.DSexpr  :  UNARY  expr.DEfor 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 bindingstrength, of all the operators, and the associativityof the binary operators.This information is sufficient to allow Yacc to resolve the parsing conflictsin accordance with these rules, and construct a parser that realizes the desiredprecedences and associativities..PPThe 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 leveland associativity; the lines are listed inorder of increasing precedence or binding strength.Thus,.DS%left  \'+\'  \'\-\'%left  \'*\'  \'/\'.DEdescribes the precedence and associativity of the four arithmetic operators.Plus and minus are left associative, and have lower precedence thanstar 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, likethe operator .LT. in Fortran, that may not associate with themselves; thus,.DSA  .LT.  B  .LT.  C.DEis 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	;.DEmight be used to structure the input.DSa  =  b  =  c*d  \-  e  \-  f*g.DEas follows:.DSa = ( b = ( ((c*d)\-e) \- (f*g) ) ).DEWhen this mechanism is used,unary operators must, in general, be given a precedence.Sometimes a unary operator and a binary operatorhave the same symbolic representation, but different precedences.An example is unary and binary \'\-\'; unary minus may be given the samestrength as multiplication, or even higher, while binary minus has a lower strength thanmultiplication.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.Itcauses 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.PPA token declaredby %left, %right, and %nonassoc need not be, but may be, declared by %token as well..PPThe precedences and associativities are used by Yacc toresolve 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 literalsthat have them..IP 2.A precedence and associativity is associated with each grammar rule; it is the precedenceand 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 conflictand 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 characterhave precedence and associativity associated with them, then the conflict is resolvedin favor of the action (shift or reduce) associated with the higher precedence.If the precedences are the same, then the associativity is used; leftassociative implies reduce, right associative implies shift, and nonassociatingimplies error..PPConflicts resolved by precedence are not counted in the number of shift/reduce and reduce/reduceconflicts reported by Yacc.This means that mistakes in the specification of precedences maydisguise errors in the input grammar; it is a good idea to be sparingwith precedences, and use them in an essentially ``cookbook'' fashion,until some experience has been gained.The.I y.outputfileis very useful in deciding whether the parser is actually doingwhat was intended.