ON COMMON OPERATOR NOTATION
There are many ways of encoding a mathematical expression as a
linear sequence of tokens. The use of operator precedence classes
and associativities is just one way. Therefore, it is not the most
general way. By way of support, 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. QED. Can it be demonstrated that this is the only
sensible way? I do not know, but any such demonstration would be
welcome.
In this model, tokens are divided into two classes: operators and
operands.
Operands are mathematical objects upon which the operators operate.
These include numbers, like 3 or 1001, truth values, like true or
false, structures, like vectors, or any other mathematical object.
One special type of operand is the parenthesis group. An expression
enclosed in perenthesis is evaluated recursively and treated, for
operator association purposes, as a single operand.
Each operator is given a position, precedence, and an associativity.
The precedence is a number, and operator precedence is ordered
homomorphically with number order. (Some implementations give
higher precedences lower numbers.) In cases it 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 position indicates where the operator is, in the sequence,
the operator appears. In terms of operator position, an operator
may be prefix, postfix, or infix. A prefix operator immediately
preceeds 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, 3+4+5-6-7 =
((((3+4)+5)-6)-7). If an operator is right-associative, the
operators are applied in right-to-left order. In the Java
programming language, the assignment operator "=" is
right-associative. That is, the Java statement "a = b = c;" is
equivalent to "(a = (b = c));". (It first assigns the value of c to
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 operator ':-' is
non-associative, so constructs such as "a :- b :- c" constitute
syntax errors. There would, nonetheless, be a use for such
constructs as a -->> b -->> c, but how such would be used, in
Prolog, I do not know.
The rules for expression evaluation are simple:
(1) Treat any sub-expression in parenthesis as a single
(recursively-evaluated) operand.
(2) Associate operands with operators of higher precedence before
those of lower precedence.
(3) 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. The C programming
language, for example, has a ternary infix operator "? :". Would
it, then, be accurate to call parenthisization an n-ary bifix
operation? :)
Examples:
1 + 2 + 3 * 4 * 5 + 6 + 7 = ((((1+2)+((3*4)*5))+6)+7)
