Common operator notation
 |
 | This article may be in need of reorganization to comply with Wikipedia's layout guidelines. (July 2007) |
In programming languages, scientific calculators and similar common operator notation is a way to define and analyse mathematical and other formal expressions. In this model a linear sequence of tokens are divided into two classes: operators and operands.
Operands are objects upon which the operators operate. These include literal numbers and other constants as well as identifiers (names) which may represent anything from simple scalar variables to complex aggregated structures and objects. One special type of operand is the parenthesis group. An expression enclosed in parentheses is typically recursively evaluated to be treated as a single operand on the next evaluation level.
Each operator is given a position, precedence, and an associativity. The operator precedence is a number (from high to low or vice versa) that defines which operator that takes an operand surrounded by two operators of different precedence (or priority). Multiplication normally has higher precedence than addition, for example, so 3+4×5 = 3+(4×5) ≠ (3+4)×5.
In terms of operator position, an operator may be prefix, postfix, or infix. A prefix operator immediately precedes its operand, as in "−x". A postfix operator immediately succeeds its operand, as in "x!". An infix operator exists between its left and right operands, as in "A + B". Some languages, most notably the C-syntax family, stretches this convention and speaks also of ternary infix operators (a?b:c). Theoretically it would even be possible (but not nessecarily practical) to define parenthesization as an n-ary bifix operation.
Operator associativity, describes what happens when an operand is surrounded by operators of the same precedence; subtraction is normally left associative, for example, so 1-2-3 = (1-2)-3 ≠ 1-(2-3). An operator can be left-associative, right-associative, or non-associative. If an operator is left-associative, the operators are applied in left-to-right order. The basic arithmetic operators for example, are normally all left-associative. That is,
Right-associative operators are applied in right-to-left order. In programming languages where assignment is an operator, that operatior is often right-associative. If so, the statement a := b := c is equivalent to a := (b := c), which means that the value of c is copied to b which is then copied to a. An operator which is non-associative cannot compete for operands with operators of equal precedence. In Prolog for example, the infix operator :- is non-associative, so constructs such as a :- b :- c are syntax errors. There may nonetheless be constructs like a =|> b =|> c.
The unary prefix operators '+', '−', and 'sin', for example, are typically associative prefix operators. When more than one associative prefix or postfix operator of equal precedence precedes or succeeds an operand, the operators closest to the operand goes first. For example, −sin x = −(sin(x)).
Prefix and postfix operators do not necessarily have higher precedence than all infix operators. For example, if the prefix operator sin was given a precedence between that of + and ×, then
not
or
The rules for expression evaluation are usually three-fold:
- Treat any sub-expression in parentheses as a single recursively-evaluated operand (there may be different kinds of parentheses though, with different semantics).
- Bind operands to operators of higher precedence before those of lower precedence.
- For equal precedence, bind operands to operators according to the associativity of the operators.
Examples:
- 1 + 2 + 3 * 4 * 5 + 6 + 7 = ((((1 + 2) + ((3 * 4) * 5)) + 6) + 7)
- 4 + -x + 3 = ((4 + (-x)) + 3)
Generalizations of Common Operator Notation
The use of operator precedence classes and associativities is just one way. However, it is not the most general way: this model cannot give an operator more precedence when competing with '−' than it can when competing with '+', while still giving '+' and '−' equivalent precedences and associativities. A generalized version of this model (in which each operator can be given independent left and right precedences) can be found at [1].