yacc

Precedence

The disambiguating rules given above are not sufficient in resolving the conflicts that arise in the parsing of arithmetic expressions. These situations require that the parser be given some information about ``precedence'' and ``associativity''. Most of the commonly-used constructions for arithmetic expressions can be described naturally by the notion of precedence levels for operators, together with left and 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 those constructed from unambiguous grammars.

Grammar rules for binary operators are typically written in the form:

   expr  :  expr  OP  expr

Rules for unary operators typically look like:

   expr  :  UNARYOP  expr

These create a very ambiguous grammar with many parsing conflicts. To avoid ambiguity, the user can specify the precedence of all the operators and the associativities of the binary operators. This information is sufficient in allowing yacc to resolve the parsing conflicts and construct a parser that implements the precedences and associativities.

In an expression where there is a choice of two operators to evaluate, ``precedence'' determines which of the two is evaluated. For example, the following expression could be evaluated to 23 or 35, depending on whether '+' or '*' is evaluated first:

   3+4*5

The operator evaluated first is said to have higher precedence.

``Associativity'' determines which side of an expression involving a particular operator should be evaluated first. The following example could be evaluated to 2 or 4:

   6-3-1

The result depends on whether the logical grouping is:

   (6-3)-1

or:

   6-(3-1)

If an operator is ``left associative'', then the expression to the left of the operator is evaluated first, as in the first case above. If it is ``right associative'', then the right side is evaluated first, as in the second case above.

The precedences and associativities are attached to tokens in the declarations section of the yacc specification. This is done with a series of lines starting with one of the yacc keywords %left, %right, or %nonassoc, followed by a list of tokens. All of the tokens on the same line have the same precedence level and associativity; the lines occur in order of increasing precedence. The following lines describe the precedence and associativity of the four arithmetic operators:

   %left  '+'  '-'
   %left  '*'  '/'

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 indicate right-associative operators, and the keyword %nonassoc is used to describe operators like .LT. in FORTRAN that may not associate with themselves. The following statement is illegal in FORTRAN, and therefore the .LT. operator should be described with the keyword %nonassoc:

   A .LT. B .LT. C

Here is a yacc specification for expressions involving operators:

   %right  ´=´
   %left  ´+´  ´-´
   %left  ´´  ´/´
   
   %%
   

   expr   :   expr  ´=´  expr
          |   expr  ´+´  expr
          |   expr  ´-´  expr
          |   expr  ´´  expr
          |   expr  ´/´  expr
          |   NAME
          ;

Now consider the following input tokens:

   a  =  b  =  cd  -  e  -  fg

A parser that follows the specification just given structures the input as follows:

   a = ( b = ( ((cd)-e) - (fg) ) )