Common operator notation: Difference between revisions

Revision as of 15:19, 22 February 2010

Latest revision as of 18:04, 7 July 2023

(27 intermediate revisions by 18 users not shown)

Line 1:

{{about|the concept of operator precedence|operator precedence parsing|operator-precedence parser}}

{{Unreferencedrefimprove|date=August 2009}}

In [[programming languages]], [[scientific calculator]]s and similar '''common operator notation''' or '''operator grammar''' 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: [[operator (programming)|operator]]s and operands.

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

In [[programming languages]], '''common operator notation''' is just one way of notating mathematical expressions as a linear sequence of tokens, or [[operator]]s, but this is not the only way. 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. <!-- speculation... Can it be demonstrated that this is the only sensible way? I do not know, but any such demonstration would be welcome. --> A generalized version of this model (in which each operator can be given independent left and right precedences) can be found at [http://compilers.iecc.com/comparch/article/01-07-068].

Operands are mathematical objects upon which the operators operate. These include literal [[number]]s suchand other constants as 3well oras 1001,identifiers [[truth(names) value]]swhich suchmay asrepresent trueanything orfrom false,simple structuresscalar suchvariables asto vectorscomplex aggregated structures and objects, ordepending anyon otherthe mathematicalcomplexity objectand capability of the language at hand as well as usage context. 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 '''operator precedence''' is a number (from high to low or vice versa) that defines which operator takes an operand that is surrounded by two operators of different precedence (or priority). Multiplication normally has higher precedence than addition,<ref name="Bronstein_1987">{{cite book |title=Taschenbuch der Mathematik |title-link=Bronstein and Semendjajew |author-first1=Ilja Nikolaevič<!-- Nikolajewitsch --> |author-last1=Bronstein<!-- 1903–1976 --> |author-first2=Konstantin Adolfovič<!-- Adolfowitsch --> |author-last2=Semendjajew<!-- 1908–1988 --> |editor-first1=Günter |editor-last1=Grosche |editor-first2=Viktor |editor-last2=Ziegler<!-- 1922–1980--> |editor-first3=Dorothea |editor-last3=Ziegler |others=Weiß, Jürgen<!-- lector --> |translator-first=Viktor |translator-last=Ziegler |volume=1 |date=1987 |edition=23 |orig-year=1945 |publisher=[[Verlag Harri Deutsch]] (and [[B. G. Teubner Verlagsgesellschaft]], Leipzig) |___location=Thun and Frankfurt am Main |language=German |chapter=2.4.1.1. |pages=115–120 |isbn=3-87144-492-8}}</ref> for example, so 3+4×5 = 3+(4×5) ≠ (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.

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! for instance. An [[infix operator]] is positioned in between a left and a right operand, as in x+y. Some languages, most notably the C-syntax family, stretches this conventional terminology and speaks also of ''[[ternary operator|ternary]]'' infix operators (a?b:c). Theoretically it would even be possible (but not necessarily practical) to define parenthesization as a unary 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 ==

[[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".

{{Main|Operator associativity}}

Operator associativity determines what happens when an operand is surrounded by operators of the same precedence, as in 1-2-3: An operator can be [[left-associative]], [[right-associative]], or [[non-associative]]. Left-associative operators are applied to operands in left-to-right order while right-associative operators are the other way round. The basic arithmetic operators are normally all left-associative,<ref name="Bronstein_1987" /> which means that 1-2-3 = (1-2)-3 ≠ 1-(2-3), for instance. This does not hold true for higher operators. For example, [[exponentiation]] is normally right-associative in mathematics,<ref name="Bronstein_1987" /> but is implemented as left-associative in some computer applications like Excel. In programming languages where assignment is implemented as an operator, that operator is often right-associative. If so, a statement like {{mono|1=a := b := c}} would be equivalent to {{mono|1=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 {{mono|1=:-}} is non-associative, so constructs such as {{mono|1=a :- b :- c}} are syntax errors.

Unary prefix operators such as − (negation) or sin (trigonometric function) 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. So −sin x = −(sin x), and sin -x = sin(-x).

Mathematically oriented languages (such as on [[scientific calculator]]s) sometimes allow implicit multiplication with higher priority than prefix operators (such as sin), so that sin 2x+1 = (sin(2x))+1, for instance.{{citation needed|date=November 2015|reason=While this may be correct for some languages, it is not correct mathematically. This needs to be discussed in much better details. See also [[Order of operations]].}}

[[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,

However, prefix (and postfix) operators do not ''necessarily'' have higher precedence than all infix operators. Some (hypothetical) programming language may well have an operator called sin with a precedence lower than × but higher than + for instance. In such a language, sin 2·x+1 = sin(2·x)+1 would be true, instead of (sin 2)·x+1, as would normally be the case.

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

The rules for expression evaluation are simpleusually three-fold:

If an operator is right-associative, the operators are applied in right-to-left order. In the [[Java (programming language)|Java programming language]], the assignment operator "<tt>=</tt>" is right-associative. That is, the Java statement "<tt>a = b = c;</tt>" is equivalent to "<tt>(a = (b = c));</tt>". It first assigns the value of c to

# Treat any sub-expression in parentheses as a single recursively-evaluated operand (there may be different kinds of parentheses though, with different semantics).

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

# AssociateBind operands withto operators of higher precedence before those of lower precedence.

# Among operators ofFor equal precedence, associatebind operands withto operators according to the associativity of the operators.

Some more examples:

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 all associative prefix operators. The unary postfix operator '!' and, in the [[C (programming language)|C]] language, the post-increment and post-decrement 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)) and, in [[C (programming language)|C]], the expression "<tt>x++--</tt>" is equivalent to "<tt>(x++)--</tt>". When prefix and postfix operators of equal precedence coexist, the order of association is undefined.

:<tt> {{mono|1= + 1-2 + 3 * /4 * 5 + 6 + 7 = ((((1 + -2) + ((3 * /4) * 5)) + 6) + 7)</tt>}}

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 '×',

:<math>\sin {{mono|1= 4 \cdot+ -x 3+2 3 = ((\sin(4 \cdot+ 3(-x)) + 2)</math>3}}

==Generalizations of Common Operator Notation==

not

In [[programming languages]], '''common operator notation''' is just one way of notating mathematical expressions as a linear sequence of tokens, or [[operator]]s, but this is not the only way. 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. <!-- speculation... Can it be demonstrated that this is the only sensible way? I do not know, but any such demonstration would be welcome. --> A generalized version of this model (in which each operator can be given independent left and right precedences) can be found at [http://compilers.iecc.com/comparch/article/01-07-068].

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

or

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

The rules for expression evaluation are simple:

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

# Associate operands with operators of higher precedence before those of lower precedence.

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

:<tt>4 + -x + 3 = ((4 + (-x)) + 3)</tt>

:<tt>4 * 3! = (4 * (3!))</tt>

:<tt>a++-- = (a++)--</tt>

:<tt>-3! = -(3!)</tt>

==See also==

*[[Order of operations]]

*[[Relational operator]]

*[[Operator (computer programming)]]

*[[Operators in C and C++]]

==References==

{{Reflist}}

{{DEFAULTSORT:Common Operator Notation}}

[[Category:Computer arithmetic]]

[[Category:ProgrammingOperators constructs(programming)]]

[[Category:Programming language topics]]