Operator 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. Many programming language manuals provide a table of operator precedence and associativity.

What is associativity

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 result corresponds to the case when + and - are right-associative. To prevent cases where operands would be associated with two operators, or no operator at all, operators with the same precedence always have the same associativity. Usually the operators +, −, * and / are left-associative, while the exponentiation, assignment and conditional operators are right-associative.

To understand the intuition behind these names, think of the operators (of the same precedence) concurring for the operands. Left-associative means that operands are associated to the operator on their left side. Likewise, right-associative means, the operands are associated to the operator on their right side. This results in the evaluation of left-associative expressions with multiple operands to be carried out left-to-right, and right-associative ones right-to-left.

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:

5 gets read.
The first ^ gets read. 5 gets associated to it.
4 gets read. It gets associated to the only ^ read until now.
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.
3 gets read. It gets associated to the second ^.
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.
2 gets read. It gets associated to the third ^.

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

The evaluator walks down the tree, from the first, over the second, to the third ^.
It evaluates it: $3^{2}=9$ . Then it puts the result in place of that expression branch, as the second operand of the above (second) ^.
It goes one up, and evaluates resulted expression: $4^{9}=262144$ . Then it puts the result in place of that expression branch, as the second operand of the above (first) ^.
Again, it goes one up, and evaluates resulted expression: $5^{262144}\approx 6.2060699\times 10^{183230}$ . 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 (in mathematical notation $((5^{4})^{3})^{2}$ ), and the completely different results 625, 244140625 and finally ~ $5.9604645\times 10^{16}$ .

Note about right-associative operators

It may seem counter-intuitive that assignment operators such as =, and also +=, -=, etc, have an associativity if you are unfamiliar with the idea of treating an assignment as an expression, having a side effect, or resulting in a value (in functional programming languages). In languages such as C, the assignment a=b is an expression that returns the value b converted to the type of a, with the side effect of setting a to this value. Thus an assignment can be performed in the middle of an expression. Note that an expression with side effects 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 = allows statements such as a=b=c; which means a=(b=c); which sets both a and b to the value of c (at least if the variables are all of the same type). The alternative (a=b)=c; does not make sense because a=b is not an lvalue.

Exponentiation makes perfect sense as a right-associative operator. In Python, exponentiation is denoted by the ** operator. The expression a ** b ** c means a ** (b ** c). The alternative (a ** b) ** c would usually be equivalent to a ** (b * c) by the mathematical identity $(a^{b})^{c}=a^{bc}$ , but calculated less efficiently^{[citation needed]}.

Non-associative operatorsNon-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^{[citation needed]} 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).See alsoOrder of operations (in arithmetic and algebra) Common operator notation (in programming languages) Associativity (the mathematical property of associativity)