Editing Operator associativity

{{Short description|Property determining how equal-precedence operators are grouped}}{{for|the mathematical concept of associativity|Associative property}}

In [[programming language theory]], the '''associativity''' of an [[Operator (programming)|operator]] is a property that determines how operators of the same [[order of operations|precedence]] are grouped in the absence of [[Bracket (mathematics)|parentheses]].  If an [[operand]] is both preceded and followed by operators (for example, <code>^ 3 ^</code>), 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 '''associative''' (meaning the operations can be grouped arbitrarily), '''left-associative''' (meaning the operations are grouped from the left), '''right-associative''' (meaning the operations are grouped from the right) or '''non-associative''' (meaning operations cannot be chained, often because the output type is incompatible with the input types). 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 type of operator.

{{anchor|rightAssociative}}Consider the expression <code>a ~ b ~ c</code>. If the operator <code>~</code> has left associativity, this expression would be interpreted as <code>(a ~ b) ~ c</code>. If the operator has right associativity, the expression would be interpreted as <code>a ~ (b ~ c)</code>. If the operator is non-associative, the expression might be a [[syntax error]], or it might have some special meaning. Some mathematical operators have inherent associativity. For example, subtraction and division, as used in conventional math notation, are inherently left-associative. Addition and multiplication, by contrast, are both left and right associative.  (e.g. <code>(a * b) * c = a * (b * c)</code>).

Many programming language manuals provide a table of operator precedence and associativity; see, for example, [[Operators in C and C++#Operator precedence|the table for C and C++]].

The concept of notational associativity described here is related to, but different from, the mathematical [[associativity]]. An operation that is mathematically associative, by definition requires no notational associativity. (For example, addition has the associative property, therefore it does not have to be either left associative or right associative.) An operation that is not mathematically associative, however, must be notationally left-, right-, or non-associative. (For example, subtraction does not have the associative property, therefore it must have notational associativity.)

== Examples ==

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

In order to reflect normal usage, [[addition]], [[subtraction]], [[multiplication]], and [[Division (mathematics)|division]] operators are usually left-associative,<ref>Education Place: [http://eduplace.com/math/mathsteps/4/a/index.html The Order of Operations]</ref><ref>[[Khan Academy]]: [https://www.khanacademy.org/math/pre-algebra/pre-algebra-arith-prop/pre-algebra-order-of-operations/v/introduction-to-order-of-operations The Order of Operations], timestamp [https://www.youtube.com/watch?v=ClYdw4d4OmA&t=5m40s 5m40s]</ref><ref>Virginia Department of Education: [http://www.doe.virginia.gov/instruction/mathematics/middle/algebra_readiness/curriculum_companion/order-operations.pdf#page=3 Using Order of Operations and Exploring Properties], section 9</ref> while for an [[exponentiation]] operator (if present)<ref name="Codeplea_2016">[https://codeplea.com/exponentiation-associativity-options Exponentiation Associativity and Standard Math Notation] Codeplea. 23 Aug 2016. Retrieved 20 Sep 2016.</ref>{{Better source needed|reason=A [[WP:RSSELF|blog isn't a reliable source]].|date=May 2024}} there is no general agreement. Any [[assignment (computer science)|assignment]] operators are typically 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 <code>5^4^3^2</code>, in which <code>^</code> is taken to be a right-associative exponentiation operator. A parser reading the tokens from left to right would apply the associativity rule to a branch, because of the right-associativity of <code>^</code>, in the following way:
# Term <code>5</code> is read.
# Nonterminal  <code>^</code> is read. Node: "<code>5^</code>".
# Term <code>4</code> is read. Node: "<code>5^4</code>".
# Nonterminal <code>^</code> is read, triggering the right-associativity rule. Associativity decides node: "<code>5^(4^</code>".
# Term <code>3</code> is read. Node: "<code>5^(4^3</code>".
# Nonterminal <code>^</code> is read, triggering the re-application of the right-associativity rule. Node "<code>5^(4^(3^</code>".
# Term <code>2</code> is read. Node "<code>5^(4^(3^2</code>". 
# No tokens to read.  Apply associativity to produce parse tree "<code>5^(4^(3^2))</code>".
This can then be evaluated depth-first, starting at the top node (the first <code>^</code>):
# The evaluator walks down the tree, from the first, over the second, to the third <code>^</code> expression.
# It evaluates as: 3{{sup|2}} = 9. The result replaces the expression branch as the second operand of the second <code>^</code>.
# Evaluation continues one level up the [[parse tree]] as: 4{{sup|9}} = {{formatnum:262144}}. Again, the result replaces the expression branch as the second operand of the first <code>^</code>. 
# Again, the evaluator steps up the tree to the root expression and evaluates as: 5{{sup|262144}} ≈ {{val|6.2060699|e=183230}}. 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  <code>((5^4)^3)^2</code> and the completely different result (625{{sup|3}}){{sup|2}} = {{formatnum:244140625}}{{sup|2}} ≈ {{val|5.9604645|e=16}}.

== Right-associativity of assignment operators ==

In many [[imperative programming language]]s, the [[assignment operator]] is defined to be right-associative, and assignment is defined to be an expression (which evaluates to a value), not just a statement. This allows [[Assignment (computer science)#Chained assignment|chained assignment]] by using the value of one assignment expression as the right operand of the next assignment expression.

In [[C (programming language)|C]], the assignment <code>a = b</code> is an expression that evaluates to the same value as the expression <code>b</code> converted to the type of <code>a</code>, with the [[Side effect (computer science)|side effect]] of storing the [[Value (computer science)#lrvalue|R-value]] of <code>b</code> into the [[Value (computer science)#lrvalue|L-value]] of <code>a</code>.{{efn|1=An expression can be made into a [[Statement (programming)|statement]] by following it with a semicolon; i.e. <code>a = b</code> is an expression but <code>a = b;</code> is a statement.}} Therefore the expression <code>a = (b = c)</code> can be interpreted as <code>b = c; a = b;</code>. The alternative expression <code>(a = b) = c</code> raises an error because <code>a = b</code> is not an L-value expression, i.e. it has an R-value but not an L-value where to store the R-value of <code>c</code>. The right-associativity of the <code>=</code> operator allows expressions such as <code>a = b = c</code> to be interpreted as <code>a = (b = c)</code>.

In [[C++]], the assignment <code>a = b</code> is an expression that evaluates to the same value as the expression <code>a</code>, with the side effect of storing the R-value of <code>b</code> into the L-value of <code>a</code>. Therefore the expression <code>a = (b = c)</code> can still be interpreted as <code>b = c; a = b;</code>. And the alternative expression <code>(a = b) = c</code> can be interpreted as <code>a = b; a = c;</code> instead of raising an error. The right-associativity of the <code>=</code> operator allows expressions such as <code>a = b = c</code> to be interpreted as <code>a = (b = c)</code>.

== Non-associative operators ==
Non-associative operators are operators that have no defined behavior when used in sequence in an expression. In [[Prolog]] the infix operator <code>:-</code> is '''non-associative''' because constructs such as "<code>a :- b :- c</code>" constitute syntax errors.

Another possibility is that sequences of certain operators are interpreted in some other way, which cannot be expressed as associativity. This generally means that syntactically, there is a special rule for sequences of these operations, and semantically the behavior is different. A good example is in [[Python (programming language)|Python]], which has several such constructs.<ref>''[https://docs.python.org/3/reference/ The Python Language Reference],'' "[https://docs.python.org/3/reference/expressions.html 6. Expressions]"</ref> Since assignments are statements, not operations, the assignment operator does not have a value and is not associative. [[Assignment (computer science)#Chained assignment|Chained assignment]] is instead implemented by having a grammar rule for sequences of assignments <code>a = b = c</code>, which are then assigned left-to-right. Further, combinations of assignment and augmented assignment, like <code>a = b += c</code> are not legal in Python, though they are legal in C. Another example are comparison operators, such as <code>&gt;</code>, <code>==</code>, and <code>&lt;=</code>. A chained comparison like <code>a &lt; b &lt; c</code> is interpreted as <code>(a &lt; b) and (b &lt; c)</code>, not equivalent to either <code>(a &lt; b) &lt; c</code> or <code>a &lt; (b &lt; c)</code>.<ref>''[https://docs.python.org/3/reference/ The Python Language Reference],'' "[https://docs.python.org/3/reference/expressions.html 6. Expressions]": [https://docs.python.org/3/reference/expressions.html#comparisons 6.9. Comparisons]</ref>

== See also ==
* [[Order of operations]] (in arithmetic and algebra)
* [[Common operator notation]] (in programming languages)
* [[Associativity]] (the mathematical property of associativity)

== Notes ==
{{notelist}}

== References ==
{{reflist}}

[[Category:Parsing]]
[[Category:Programming language topics]]
[[Category:Operators (programming)]]