Operator associativity
From Seo Wiki - Search Engine Optimization and Programming Languages
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++.
Contents |
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:
- 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)), 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} ≈ 6.2060699 × 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 and the completely different results 625, 244140625 and finally ~5.9604645 × 10^{16}.
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<tt> to be interpreted as <tt>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^{[1]} 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)de:Operatorassoziativität