Associativity

Suppose we have the expression 5 - 3 + 2. Should it parse as 5 - (3 + 2) or (5 - 3) + 2? Does it matter which way it parses?

The parsing order does matter. Precedence tells us that + is just as greedy as -, so it's no help here. To break precedence ties, we examine the associativity of the operators. Mathematical convention says the additive operators + and - are left-associative, which means whichever operator is leftmost is greediest. For this expression, the - operator is leftmost and is the greediest. It will appear lower in the parse tree.

The vast majority of operators are left-associative, but there are a few exceptions. By mathematical convention, exponentiation is right-associative, which means whichever operator is rightmost is greediest.

The assignment operators are also right-associative. Assignment operators can only match precedence with other assignment operators since they are the only operators at their precedence level. Therefore, their associativity only matters when an expression contains multiple assignment operators, as in a = b = 8. This parses as a = (b = 8). Both a and b end up bound to 8.

Haskell doesn't treat assignment as an expression and doesn't support nested assignments. An operator that doesn't nest with itself is non-associative. The Java operator ++ is non-associative. We can't write (x++)++. The inner ++ evaluates to a numeric rvalue. The second ++ fails because it expects an lvalue receiver.

In the Lisp family of languages, associativity is unimportant, since each operation is explicitly surrounded by parentheses, as shown in this Racket expression:

(+ (- 5 3) 2)

(+ (- 5 3) 2)

As with precedence, an operator's associativity is an artifact of the grammar. This non-terminal recurses in its left operand:

additive 
  = additive PLUS multiplicative
  | additive MINUS multiplicative
  | multiplicative

additive 
  = additive PLUS multiplicative
  | additive MINUS multiplicative
  | multiplicative

Because the recursion happens on the left, the leftmost + or - will be lowest in the tree, making these operators left-associative. The production for a right-associative operator will recurse in its right operand.