Operator associativity
Encyclopedia
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. If an operand is both preceded and followed by operators (for example, "^ 4 ^"), and those operators have equal precedence, then the operand may be used as input to two different operations (i.e. the two operations indicated by the two operators). The choice of which operations to apply the operand to, is determined by the "associativity" of the operators. Operators may be left-associative (meaning the operations are grouped from the left), right-associative (meaning the operations are grouped from the right) or non-associative (meaning there is no defined grouping). The associativity and precedence of an operator is a part of the definition of the programming language; different programming languages may have different associativity and precedence for the same operator symbol.
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++.
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.
This can then be evaluated depth-first, starting at the top node (the first ^):
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 × 1016.
, 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
.
, the infix operator :- is non-associative because constructs such as "a :- b :- c" constitute syntax errors.
Another possibility distinct from left- or right-associativity is that the expression is legal but has different semantics. An example is the comparison operators (such as >, , and <=) in Python
: a < b < c is shorthand for (a < b) and (b < c), not equivalent to either (a < b) < c or a < (b < c).
See also
Mathematical notation
Mathematical notation is a system of symbolic representations of mathematical objects and ideas. Mathematical notations are used in mathematics, the physical sciences, engineering, and economics...
, the associativity (or fixity) of an operator
Operator (programming)
Programming languages typically support a set of operators: operations which differ from the language's functions in calling syntax and/or argument passing mode. Common examples that differ by syntax are mathematical arithmetic operations, e.g...
is a property that determines how operators of the same precedence
Order of operations
In mathematics and computer programming, the order of operations is a rule used to clarify unambiguously which procedures should be performed first in a given mathematical expression....
are grouped in the absence of parentheses. If an operand is both preceded and followed by operators (for example, "^ 4 ^"), and those operators have equal precedence, then the operand may be used as input to two different operations (i.e. the two operations indicated by the two operators). The choice of which operations to apply the operand to, is determined by the "associativity" of the operators. Operators may be left-associative (meaning the operations are grouped from the left), right-associative (meaning the operations are grouped from the right) or non-associative (meaning there is no defined grouping). The associativity and precedence of an operator is a part of the definition of the programming language; different programming languages may have different associativity and precedence for the same operator symbol.
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
Syntax error
In computer science, a syntax error refers to an error in the syntax of a sequence of characters or tokens that is intended to be written in a particular programming language....
, 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
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
, subtraction
Subtraction
In arithmetic, subtraction is one of the four basic binary operations; it is the inverse of addition, meaning that if we start with any number and add any number and then subtract the same number we added, we return to the number we started with...
, multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
, and division
Division (mathematics)
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
operators are left-associative, while the exponentiation
Exponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
, assignment
Assignment (computer science)
In computer programming, an assignment statement sets or re-sets the value stored in the storage location denoted by a variable name. In most imperative computer programming languages, assignment statements are one of the basic statements...
and conditional
?:
In computer programming, ?: is a ternary operator that is part of the syntax for a basic conditional expression in several programming languages...
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 reading the tokens from left to right would apply the associativity rule to a branch, because of the right-associativity of ^, in the following way:- Term 5 is read.
- Nonterminal ^ is read. Node: "5^".
- Term 4 is read. Node: "5^4".
- Nonterminal ^ is read, triggering the right-associativity rule. Associativity decides node: "5^(4^".
- Term 3 is read. Node: "5^(4^3".
- Nonterminal ^ is read, triggering the re-application of the right-associativity rule. Node "5^(4^(3^".
- Term 2 is read. Node "5^(4^(3^2".
- No tokens to read. Apply associativity to produce parse tree "5^(4^(3^2))".
This can then 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 ^ expression.
- It evaluates as: 32 = 9. The result replaces the expression branch as the second operand of the second ^.
- Evaluation continues one level up the parse treeParse treeA concrete syntax tree or parse tree or parsing treeis an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by non-terminals of the grammar, while the leaf nodes are labeled by terminals of the...
as: 49 = 262144. Again, the result replaces the expression branch as the second operand of the first ^. - Again, the evaluator steps up the tree to the root expression and evaluates as: 5262144 ≈ 6.2060699 × 10183230. The last remaining branch collapses and the result becomes the overall result, therefore completing overall evaluation.
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 × 1016.
Right-associativity of assignment operators
Assignment operators in imperative programming languages are usually defined to be right-associative. For example, in CC (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, 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
Statement (programming)
In computer programming a statement can be thought of as the smallest standalone element of an imperative programming language. A program written in such a language is formed by a sequence of one or more statements. A statement will have internal components .Many languages In computer programming...
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
Value (computer science)
In computer science, a value is an expression which cannot be evaluated any further . The members of a type are the values of that type. For example, the expression "1 + 2" is not a value as it can be reduced to the expression "3"...
.
Non-associative operators
Non-associative operators are operators that have no defined behavior when used in sequence in an expression. In PrologProlog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
, the infix operator :- is non-associative because constructs such as "a :- b :- c" constitute syntax errors.
Another possibility distinct from left- or right-associativity is that the expression is legal but has different semantics. An example is the comparison operators (such as >, , and <=) in Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
: a < b < c is shorthand for (a < b) and (b < c), not equivalent to either (a < b) < c or a < (b < c).
See also
- Order of operationsOrder of operationsIn mathematics and computer programming, the order of operations is a rule used to clarify unambiguously which procedures should be performed first in a given mathematical expression....
(in arithmetic and algebra) - Common operator notationCommon operator notationIn programming languages, common operator notation is one way of notating mathematical expressions as a linear sequence of tokens, or operators.In this model, tokens are divided into two classes: operators and operands....
(in programming languages) - AssociativityAssociativityIn mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...
(the mathematical property of associativity)