Operator associativity

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. 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++.

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 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:

  1. Term 5 is read.
  2. Nonterminal ^ is read. Node: "5^".
  3. Term 4 is read. Node: "5^4".
  4. Nonterminal ^ is read, triggering the right-associativity rule. Associativity decides node: "5^(4^".
  5. Term 3 is read. Node: "5^(4^3".
  6. Nonterminal ^ is read, triggering the re-application of the right-associativity rule. Node "5^(4^(3^".
  7. Term 2 is read. Node "5^(4^(3^2".
  8. 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 ^):

  1. The evaluator walks down the tree, from the first, over the second, to the third ^ expression.
  2. It evaluates as: 32 = 9. The result replaces the expression branch as the second operand of the second ^.
  3. Evaluation continues one level up the parse tree as: 49 = 262144. Again, the result replaces the expression branch as the second operand of the first ^.
  4. 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 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 in sequence in an expression. In Prolog, 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).[1]

See also

References

  1. ^ http://docs.python.org/reference/expressions.html#comparisons

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Operator (programming) — Programming languages generally support a set of operators that are similar to operations in mathematics. A language may contain a fixed number of built in operators (e.g. + * = in C and C++), or it may allow the creation of programmer defined… …   Wikipedia

  • Common operator notation — This article is about the concept of operator precedence. For operator precedence parsing, see operator precedence parser. In programming languages, common operator notation is one way of notating mathematical expressions as a linear sequence of… …   Wikipedia

  • Hyper operator — Articleissues OR=September 2008The hyper operators forming the hyper n family are related to Knuth s up arrow notation and Conway chained arrow notation as follows: extrm{hyper} n (a, b) = extrm{hyper}(a,n,b) = a uparrow^{n 2} b = a o b o (n 2)… …   Wikipedia

  • Assignment operator (C++) — In the C++ programming language, the assignment operator, = , is the operator used for assignment. Like most other operators in C++, it can be overloaded. The copy assignment operator, often just called the assignment operator , is a special case …   Wikipedia

  • Vertex operator algebra — In mathematics, a vertex operator algebra (VOA) is an algebraic structure that plays an important role in conformal field theory and related areas of physics. They have proven useful in purely mathematical contexts such as monstrous moonshine and …   Wikipedia

  • Associative property — This article is about associativity in mathematics. For associativity in the central processor unit memory cache, see CPU cache. For associativity in programming languages, see operator associativity. In mathematics, associativity is a property… …   Wikipedia

  • Order of operations — In mathematics and computer programming, the order of operations (sometimes called operator precedence) is a rule used to clarify unambiguously which procedures should be performed first in a given mathematical expression. For example, in… …   Wikipedia

  • List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… …   Wikipedia

  • List of basic discrete mathematics topics — Discrete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally , in the sense of not supporting or requiring the notion of continuity. Most, if not all, of the objects studied in finite… …   Wikipedia

  • Outline of discrete mathematics — The following outline is presented as an overview of and topical guide to discrete mathematics: Discrete mathematics – study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have… …   Wikipedia

Фильмы

  • The Mighty Power Of the Commowealth., 1984 — The film tells about the activity of the Council for Mutual Economic Assistance (CMEA).
  • Eleventh Five-Year Period: Time And People., 1986 — About improvement of economic mechanism basing on examples of definite enterprises: "Rostselmash" ["Rostov Agriculture Machinery Plant"}, the collective farm named after Frunze (a Russian revolutionary) in the Belgorod Region, the collective farm "Krasnaya Zarya" ["Red Dawn"] of the Pskov Region and others.
  • The Man In the City., 1991 — About the problem of waste products recycling in large cities, about the ecological situation in Moscow.

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”