Operator associativity

For the mathematical concept of associativity, see Associativity.

In programming languages and mathematical notation, the associativity (or fixity) of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses. Operators may be left-associative, right-associative or non-associative. The associativity and precedence of an operator depends on the programming language in question.

Consider the expression a ~ b ~ c. If the operator ~ has left associativity, this expression would be interpreted as (a ~ b) ~ c and evaluated left-to-right. If the operator has right associativity, the expression would be interpreted as a ~ (b ~ c) and evaluated right-to-left. If the operator is non-associative, the expression might be a syntax error, or it might have some special meaning.

Many programming language manuals provide a table of operator precedence and associativity; see, for example, the table for C and C++.

Examples

Associativity is only needed when the operators in an expression have the same precedence. Usually + and - have the same precedence. Consider the expression 7 − 4 + 2. The result could be either (7 − 4) + 2 = 5 or 7 − (4 + 2) = 1. The former result corresponds to the case when + and − are left-associative, the latter to when + and - are right-associative.

Usually the addition, subtraction, multiplication, and division operators are left-associative, while the exponentiation, assignment and conditional operators are right-associative. To prevent cases where operands would be associated with two operators, or no operator at all, operators with the same precedence must have the same associativity.

A detailed example

Consider the expression 5^4^3^2. A parser always reads the tokens from left to right. But because of the right-associativity of ^, the following would happen in a simple parser:

1. 5 gets read.
2. The first ^ gets read. 5 gets associated to it.
3. 4 gets read. It gets associated to the only ^ read until now.
4. The second ^ gets read. 4 gets re-associated to it because of the right-associativity. Then that construct gets associated to the first ^ as the right operand.
5. 3 gets read. It gets associated to the second ^.
6. The third ^ gets read. 3 gets re-associated to it because of the right-associativity. Then that construct gets associated to the second ^ as the right operand.
7. 2 gets read. It gets associated to the third ^.

Resulting in the parse tree 5^(4^(3^2)), which can be evaluated depth-first, starting at the top node (the first ^):

1. The evaluator walks down the tree, from the first, over the second, to the third ^.
2. It evaluates it: 3² = 9. Then it puts the result in place of that expression branch, as the second operand of the above (second) ^.
3. It goes one up, and evaluates resulted expression: 4⁹ = 262144. Then it puts the result in place of that expression branch, as the second operand of the above (first) ^.
4. Again, it goes one up, and evaluates resulted expression: 5²⁶²¹⁴⁴ ≈ 6.2060699 × 10¹⁸³²³⁰. This then becomes the remaining result, and therefore, the evaluation finished successfully.

A left-associative evaluation would have resulted in the parse tree ((5^4)^3)^2 and the completely different results 625, 244140625 and finally ~5.9604645 × 10¹⁶.

Right-associativity of assignment operators

Assignment operators in imperative programming languages are usually defined to be right-associative. For example, in C, the assignment a = b is an expression that returns a value (namely, b converted to the type of a) with the side effect of setting a to this value. An assignment can be performed in the middle of an expression. (An expression can be made into a statement by following it with a semicolon; i.e. a = b is an expression but a = b; is a statement). The right-associativity of the = operator allows expressions such as a = b = c to be interpreted as a = (b = c), thereby setting both a and b to the value of c. The alternative (a = b) = c does not make sense because a = b is not an lvalue.

Non-associative operators

Non-associative operators are operators that have no defined behavior when used together in an expression. In Prolog, the infix operator :- is non-associative because constructs such as "a :- b :- c" constitute syntax errors. In Python, comparison operators (such as >, ==, and <=) are non-associative because expressions such as a < b < c have a meaning distinct from (a < b) < c or a < (b < c). In this case, the expression is shorthand for (a < b) and (b < c).

References

See also

• Order of operations (in arithmetic and algebra)
• Common operator notation (in programming languages)
• Associativity (the mathematical property of associativity)