Common operator notation: Difference between revisions

Revision as of 17:45, 15 November 2012

Revision as of 18:54, 15 November 2012

Line 2:

{{Unreferenced|date=August 2009}}

{{Cleanup-reorganize|date=July 2007}}

In [[programming languages]], [[scientific calculator]]s and similar '''common operator notation''' is onea way ofto notatingdefine and analyse mathematical and other formal expressions. asIn this model a linear sequence of tokens, orare divided into two classes: [[operator (programming)|operator]]s and operands.

Operands are mathematical objects upon which the operators operate. These include literal [[number]]s suchand asother 3constants oras 1001,well [[truthas value]]sidentifiers such(names) aswhich truemay orrepresent false,anything structuresfrom suchsimple asscalar vectors,variables orto anycomplex otheraggregated mathematicalstructures objectand objects. One special type of operand is the parenthesis group. An expression enclosed in parentheses is evaluatedtypically recursively andevaluated treated,to forbe operator association purposes,treated as a single operand on the next evaluation level.

In this model, tokens are divided into two classes: operators and operands.

Each operator is given a position, precedence, and an associativity. The precedence is a number, and '''operator precedence''' is usuallya orderednumber with(from thehigh correspondingto numberlow order,or althoughvice someversa) implementationsthat givedefines higherwhich precedencesoperator lowerthat numbers.takes an Inoperand casessurrounded in whichby two operators of different precedencesprecedence compete(or forpriority). theMultiplication samenormally operand, the operator with thehas higher precedence wins.than addition, Forfor example, '×' has a higher precedence than '+', so 3+4×5 = (3+(4×5)), not≠ ((3+4)×5).

Operands are mathematical objects upon which the operators operate. These include [[number]]s such as 3 or 1001, [[truth value]]s such as true or false, structures such as vectors, or any other mathematical object. One special type of operand is the parenthesis group. An expression enclosed in parentheses is evaluated recursively and treated, for operator association purposes, as a single operand.

[[Operator position]] indicates where, in the sequence, the operator appears. 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.

Each operator is given a position, precedence, and an associativity. The precedence is a number, and '''operator precedence''' is usually ordered with the corresponding number order, although some implementations give higher precedences lower numbers. In cases in which two operators of different precedences compete for the same operand, the operator with the higher precedence wins. For example, '×' has a higher precedence than '+', so 3+4×5 = (3+(4×5)), not ((3+4)×5).

[[Operator associativity]], loosely speaking, describes what operatorshappens arewhen allowedan tooperand associateis beforesurrounded associatingby withoperators of the operatorsame inprecedence; question.subtraction is Innormally thoseleft cases in which operators of equal precedence competeassociative, for common operandsexample, operatorso associativity1-2-3 describes= the(1-2)-3 order≠ of operator association1-(2-3). An infix operator can be left-associative, right-associative, or non-associative. A prefix or postfix operator can be either associative or non-associative. If an operator is left-associative, the operators are applied in left-to-right order. The basic arithmetic operators '+', '−', '×', and '÷', for example, are normally all left-associative. That is,

[[Operator position]] indicates where, in the sequence, the operator appears. 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".

[[Operator associativity]], loosely speaking, describes what operators are allowed to associate before associating with the operator in question. In those cases in which operators of equal precedence compete for common operands, operator associativity describes the order of operator association. An infix operator can be left-associative, right-associative, or non-associative. A prefix or postfix operator can be either associative or non-associative. If an operator is left-associative, the operators are applied in left-to-right order. The arithmetic operators '+', '−', '×', and '÷', for example, are all left-associative. That is,

:<math>3+4+5-6-7 = ((((3+4)+5)-6)-7).</math>

If an operator is rightRight-associative, the operators are applied in right-to-left order. In the [[Java (programming language)|Javalanguages programmingwhere language]],assignment theis assignmentan operator, "<tt>=</tt>"that operatior is often right-associative. If That isso, the Java statement "<tt>a := b := c;</tt>" is equivalent to "<tt>(a := (b := c));</tt>"., Itwhich firstmeans assignsthat 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.

b, then assigns the value of b to a. An operator which is non-associative cannot compete for operands with operators of equal precedence. For example, in [[Prolog]], the infix operator "<tt>:-</tt>" is non-associative, so constructs such as "<tt>a :- b :- c</tt>" constitute syntax errors. There may nonetheless be a use for such constructs as "<tt>a =|> b =|> c</tt>".

A prefix or postfix operator is associative if and only if it may compete for operands with operators of equal precedence. The unary prefix operators '+', '−', and 'sin', for example, are alltypically associative prefix operators. When Themore unarythan one associative prefix or postfix operator '!'of equal precedence andprecedes or succeeds an operand, inthe operators closest to the [[Coperand (programminggoes language)|C]]first. language For example, the−sin post-incrementx and= post-decrement−(sin(x)). operators

"<tt>++</tt>" and "<tt>--</tt>" are examples of associative postfix operators. When more than one associative prefix or postfix operator of equal precedence precedes or succeeds an operand, the operators closer to the operand associate first. For example, −sin x = −(sin(x)). When prefix and postfix operators of equal precedence coexist, the order of association is undefined.

Note that, contrary to popular belief, prefix and postfix operators do not necessarily have higher precedence than all infix operators. For example, if the prefix operator 'sin' is given a precedence between that of '+' and '×',

Note that, contrary to popular belief, prefixPrefix and postfix operators do not necessarily have higher precedence than all infix operators. For example, <u>if</u> the prefix operator 'sin' iswas given a precedence between that of '+' and '×', then

:<math>\sin 4 \cdot 3+2 = ((\sin(4 \cdot 3)) + 2)</math>

not

:<math>(((\sin 4) \cdot 3) + 2)</math>

or

:<math>\sin(((4 \cdot 3)+2))</math>

The rules for expression evaluation are simpleusually 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.

# Treat any sub-expression in parentheses as a single recursively-evaluated operand.

# AssociateFor equal precedence, bind operands withto operators ofaccording higherto precedencethe before thoseassociativity of lowerthe precedenceoperators.

# Among operators of equal precedence, associate operands with operators according to the associativity of the operators.

Note that an infix operator need not be binary. [[C (programming language)|C]], for example, has a ternary infix operator "<tt>[[?:]]</tt>". <!-- speculation Would it, then, be accurate to call parenthesization an n-ary bifix operation? :) -->

Examples:

:<tt>1 + 2 + 3 * 4 * 5 + 6 + 7 = ((((1 + 2) + ((3 * 4) * 5)) + 6) + 7)</tt>