Precedence and associativity

Parsers that evaluate expressions usually have to establish the order in which various operations are carried out. For example, parsers for arithmetic expressions usually carry out multiplications before additions. Two factors affect order of operation: precedence and associativity.

Precedence dictates which of two different operations is to be carried out first. For example, in:

A + B * C

the standard arithmetic rules of precedence dictate that the multiplication is to take place before the addition. Operations that are to be carried out first are said to have a higher precedence than operations that are to be performed later.

Different operators can sometimes have the same precedence. In C, for example, addition and subtraction are similar enough to share the same precedence.

Associativity indicates which of two similar operations is to be carried out first. By similar, we mean operations with the same precedence (for example, addition and subtraction in C). For example, C chooses to parse

A - B - C

(A - B) - C

whereas such languages as APL or FORTRAN use:

A - (B - C)

If the first operation is evaluated before the second (as C does), the operation is left associative. If the second operation is evaluated before the first (as APL does), the operation is right associative.

Occasionally, a compiler may have operations that are not associative. For example, FORTRAN regards:

A .GT. B .GT. C

as invalid. In this case, the operation is nonassociative.

You can declare the precedence and associativity of operator tokens in the declarations section by using the keywords:

%left
%right
%nonassoc

For example:

%left '+' '-'

indicates that the + and - operations have the same precedence and are left associative.

Associativity declarations should be given in order of precedence. Operations with lowest precedence are listed first, and those with highest precedence are listed last. Operations with equal precedence are listed on the same line. For example,

%right '='
%left  '+' '-'
%left  '*' '/' '%'

says that = has a lower precedence than + and -, which in turn have a lower precedence than *, /, and %. = is also right associative, so that

A = B = C

is parsed as

A = (B = C)

Because of the way yacc specifies precedence and associativity, operators with equal precedence always have the same associativity. For example, if A and B have equal precedence, their precedence must have been set with one of

%left A B
%right A B
%nonassoc A B

which means A and B must have the same associativity.

The names supplied with %right, %left, and %nonassoc can be literals or yacc identifiers. If they are identifiers, they are regarded as token names. yacc generates a %token directive for such names if they have not already been declared. For example, in:

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

UMINUS is taken to be a token identifier. There is no need to define UMINUS as a token identifier; a %token directive is generated automatically if necessary. It is perfectly valid to have an explicit:

%token UMINUS

if you want; however, it must precede the %left declaration.

For a more technical discussion of how precedence and associativity rules affect a parser, see Ambiguities.