Operator precedence.

[BartC]

[Repost of lost message. Hopefully this won't contradict that one if it ever
turns up..]

"BartC" <[email protected]> writes:

In short, I don't think C would be logical with fewer than 11 levels,
and once you have 11, does it matter if the distinctions between
operators are emphasized by having 15? Would the degree of
arbitrariness required to reduce the number eliminate the benefit of
having fewer?

You've got it wrong; you need more arbitrariness to increase the number of
levels. You need to justify one operator having a higher or lower precedence
than another. At the same level, there is little to decide!

The difference between add/subtract, and multiple/divide, most people know
about. That's two. There's a few more levels that are obvious (compare, and
logical and/or). But none of the rest have an obvious precedence, or no
reason to for them to have their own dedicated precedence level.

(In a UK general discussion forum, the value of 48÷2(9+3) was recently
discussed. After 2500 posts, there was still no agreement! And a poll showed
that 55% thought the answer was 2, and 45% thought it was 288. Someone even
posted this explanation:

.

So a lot of people have trouble even dealing with just two precedence
levels. And C has a dozen more! Admittedly that was a not technical forum.)

 

[James Kuyper]

For unary operators, I think hierarchy matches execution order.

Yes, if you only consider the unary operators, it's simple. However, the
minute you throw in binary operators, the issue does comes up. C deals
with that issue by specifying a grammar that gives the postfix operators
(both unary and binary) the highest precedence and left-to-right
associativity, and gives the unary prefix operators the next-highest
precedence, with right-to-left associativity. All other operators (most
of them binary) have a lower precedence.

....

Do they? In the K&R table, they seem to occupy one level.

The relevant grammar rules are 6.5.2p1:
postfix-expression:
primary-expression
postfix-expression [ expression ]
postfix-expression ( argument-expression-listopt )
postfix-expression . identifier
postfix-expression -> identifier
postfix-expression ++
postfix-expression --
( type-name ) { initializer-list }
( type-name ) { initializer-list , }

and 6.5.3p1:
unary-expression:
postfix-expression
++ unary-expression
-- unary-expression
unary-operator cast-expression
sizeof unary-expression
sizeof ( type-name )
_Alignof ( type-name )

The aspect of the grammar which can be described by precedence tables is
encoded in the grammar by the fact that a postfix-expression can be
parsed as a unary-expression, but a unary-expression cannot be parsed as
a postfix-expression.

Because you might have thought it a typo otherwise. K&R says unary ops
associate from right to left. So op4 first.

Sorry - I misunderstood. I thought you were choosing a bizarre way of
expressing the correct parse, which is (A op3) op4.

There are only two unary postfix operators, the other postfix operators
are all binary. According to the grammar, a++-- can only be parsed as
(a++)--, not as (a--)++. It hardly matters, though: postfix ++ and --
both require modifiable lvalues for their left operand (6.5.3.1p2), and
neither one has a result which is an lvalue. Therefore, after correctly
parsing any consecutive pair of unary postfix operators, an
implementation must diagnose a constraint violation. As a result,
associativity is pretty much irrelevant for unary postfix operators.

The associativity of postfix operators only comes up in combination with
the binary postfix operators. It's encoded in the grammar by the fact
that every grammar production for a postfix-expression that also
contains a postfix-expression contains it only on the left side of the
production, not on the right. In other words, they associate from left
to right. For instance, a.b++ is parsed as (a.b)++, not as a.(b++),
because the right operand of the member-selection operator must be an
identifier, while the left operand of postfix ++ can be another
postfix-expression.
If the grammar had mandated the second parse, rather than the first, the
result would have been a constraint violation, but it would first have
had to be correctly parsed before it could be recognized as one.

In contrast, every grammar production for unary-expression that contains
a unary-expression, contains it on the right end of the production.
That's why the prefix unary operators can be correctly described as
associating from right to left.

....

Yes, you can think of it as an extra level, but it can just be the grammar.

Well yes, in C, it's all grammar; precedence and associativity are
merely descriptions of important features of that grammar. The process
of deriving a precedence and associativity table for C naturally starts
with the postfix operators and ends with the comma operator. Starting it
with || and ending it with the multiplicative operators is rather
arbitrary. You could just as easily have chosen to start it at the
additive operators.

The three-way ?: is too weird to even have as operator. How would you even
parenthesise it so that ?: is done before the assignment? Besides, according
to the precedence table, ?: comes before assignment!

Yes, that's the one way in which precedence tables necessarily fail to
correctly describe the C grammar. Take out the ?: operator, and a
correctly written precedence table could be a perfectly accurate
description of one aspect of the grammar.

 

[Ike Naar]

Because you might have thought it a typo otherwise. K&R says unary ops
associate from right to left. So op4 first.

Right-to-left associativity only holds for the prefix unary operators.
Postfix unary operators associate from left to right.
In your example,

op1 op2 A op4 op4

should be calculated as

op1 (op2 ((A op4) op3))

 

[Ike Naar]

Right-to-left associativity only holds for the prefix unary operators.
Postfix unary operators associate from left to right.
In your example,

op1 op2 A op4 op4

should be calculated as

op1 (op2 ((A op4) op3))

Sorry for adding to the confusion, that should, of course, be

op1 op2 A op3 op4

and

op1 (op2 ((A op3) op4))

 

[Ben Bacarisse]

[Repost of lost message. Hopefully this won't contradict that one if it ever
turns up..]

"BartC" <[email protected]> writes:

In short, I don't think C would be logical with fewer than 11 levels,
and once you have 11, does it matter if the distinctions between
operators are emphasized by having 15? Would the degree of
arbitrariness required to reduce the number eliminate the benefit of
having fewer?

You've got it wrong; you need more arbitrariness to increase the number of
levels. You need to justify one operator having a higher or lower precedence
than another. At the same level, there is little to decide!

Most of my post did try to explain why it's not arbitrary!

The difference between add/subtract, and multiple/divide, most people know
about. That's two. There's a few more levels that are obvious (compare, and
logical and/or). But none of the rest have an obvious precedence, or no
reason to for them to have their own dedicated precedence level.

I don't want = and , to share precedence with any of these.

(In a UK general discussion forum, the value of 48÷2(9+3) was recently
discussed. After 2500 posts, there was still no agreement! And a poll showed
that 55% thought the answer was 2, and 45% thought it was 288. Someone even
posted this explanation:

.

So a lot of people have trouble even dealing with just two precedence
levels. And C has a dozen more! Admittedly that was a not technical
forum.)

I can't see what the number of precedence levels has to do with this
example. The only possible ambiguity (as evidenced by the two answers
you give) is about associativity, not precedence.

 

[BartC]

Most of my post did try to explain why it's not arbitrary!

You tried to justify why every new operator seems to need it's own
precedence level. But OK:

Because of the strong mathematical the connection between &/| and */+ it
is natural to separate these pairs by precedence.

It also makes it natural to group them together.

Once you have 11, it seems to me you may as well have 15.

Now you seem to be saying there are so many, that you need to keep a table
to hand anyway, so it doesn't matter how many levels there are!

Putting ^ in
with, say, |; or putting the shift operators in with * would probably be
as confusing as giving them their own level.

Shift operators effectively multiply and divide; so why *not* lump them with
* and /? As it as, some are obliged to use parentheses as they will not know
off-hand where they actually are in the hierarchy.

And separating == and !=
from < and friends has strong arguments in its favour, which there is no
reason to ignore once you already have so many levels.

Again, adding levels for it's own sake. And, should be == be higher then >,
or the other way? And, what are the arguments for not having the same level
for all of them? I can't see a reason to favour (a==b)<c over a==(b<c) or
vice versa.

I don't want = and , to share precedence with any of these.

Well, OK, in C, "=" is classed as an operator, although a low priority one.
So actually when you take out the obvious ones, such as "=" and ".", there's
a bit less than 15 to remember. But still too many..

I can't see what the number of precedence levels has to do with this
example. The only possible ambiguity (as evidenced by the two answers
you give) is about associativity, not precedence.

That's true; I tend to lump the two together. Ultimately what's being
decided is order of evaluation**. The point was, the general public seem to
have a real problem with this stuff; I can fare a bit better, but still have
trouble remembering beyond about six levels (and that only because they are
in two groups: arithmetic, and compare/logical).

Did the designers of C actually seek to minimise precedence levels? Did they
think that having many of them would be better than having too few? Having
too few levels means extra parentheses. Having too many also means extra
parentheses when you can't remember the priorities!

(** And yes I know the right terminology is a bit different. Sometimes there
is a choice of evaluation order without affecting the result.)

 

[BartC]

So my book is wrong (K&R2 p. 53); it says *all* unary operators associate
right to left.

op1 op2 A op3 op4
[should be]

op1 (op2 ((A op3) op4))

So, all the ones on the right first, innermost first out, then all those on
the left, also innermost first?

 

[Ike Naar]

So my book is wrong (K&R2 p. 53); it says *all* unary operators associate
right to left.

Perhaps it's a matter of terminology.
I don't have K&R2 available to check it, but perhaps
the term "unary operator" does not apply to postfix ++ and postfix --.

 

[BartC]

Yes, if you only consider the unary operators, it's simple. However, the
minute you throw in binary operators, the issue does comes up. C deals
with that issue by specifying a grammar that gives the postfix operators
(both unary and binary)

I'm not too well up on the right terminology, but wouldn't any binary
operator just be 'infix'?

The relevant grammar rules are 6.5.2p1:

....

Actually, I've made use of C-style postfix ++,-- operators in my own
projects. They are parsed as they are in C. (But I don't any special concept
of precedence, and a much simpler grammar.)

There are only two unary postfix operators, the other postfix operators
are all binary. According to the grammar, a++-- can only be parsed as
(a++)--, not as (a--)++. It hardly matters, though: postfix ++ and --
both require modifiable lvalues for their left operand (6.5.3.1p2), and
neither one has a result which is an lvalue.

(Yes, well, I worry about lvalues in a later pass. My parser only deals
with 'shape'.)

Therefore, after correctly
parsing any consecutive pair of unary postfix operators, an
implementation must diagnose a constraint violation. As a result,
associativity is pretty much irrelevant for unary postfix operators.

to right. For instance, a.b++ is parsed as (a.b)++, not as a.(b++),

(That's a good point; just needed a quicker check my parser does the same,
which fortunately it did. But then, I don't treat "." (or "->") as an
operator at all; it can't be an operator because the right operand can't be
a conventional expression.)

Yes, that's the one way in which precedence tables necessarily fail to
correctly describe the C grammar. Take out the ?: operator, and a
correctly written precedence table could be a perfectly accurate
description of one aspect of the grammar.

So the issue is really K&R over-simplifying matters in their operator table,
by including constructs which are not conventional operators in syntax or
semantics (such as "()" and "[]").

 

[James Kuyper]

I'm not too well up on the right terminology, but wouldn't any binary
operator just be 'infix'?

That's a reasonable point of view, but the C standard calls a, a(b),
a.b, a->b, and (a){b} postfix-expressions, even though they're all
binary, and the parts of those expressions that are left after you
remove 'a' and 'b' are considered by the C standard to be postfix
operators. I think that's may be because they are highly asymmetric
operators, so 'b' was considered to be part of the operator, rather than
an operand fully comparable to 'a' itself.

....

Actually, I've made use of C-style postfix ++,-- operators in my own
projects. They are parsed as they are in C. (But I don't any special concept
of precedence, and a much simpler grammar.)


(Yes, well, I worry about lvalues in a later pass. My parser only deals
with 'shape'.)

That's entirely appropriate - constraint violations are to be diagnosed
based upon what you have as a result of parsing; they shouldn't
influence the parsing itself (though people have argued to the contrary
with respect to function-like macros with no arguments). What "shape"
does your language consider a++-- to have?

....

which fortunately it did. But then, I don't treat "." (or "->") as an
operator at all; it can't be an operator because the right operand can't be
a conventional expression.)

The C standard considers it an operator, operating on an expression and
and identifier. Similarly, (a){b} is an operator even though 'a' has to
be a type name, not an expression.

....

So the issue is really K&R over-simplifying matters in their operator table,
by including constructs which are not conventional operators in syntax or
semantics (such as "()" and "[]").

They are operators as far as the C standard is concerned, however
unconventional they might be.

 

[Joe keane]

Once you have 11, it seems to me you may as well have 15.

They have structure:

function call
arithmetic
power root (**)
multiply divide
plus minus
bitwise
not
and
or
compare
logical
not
and
or
compare (.EQV.)
assignment

 

[Ben Bacarisse]

<snip>

I think we're likely to continue to disagree here so I'll just answer
your question:

Again, adding levels for it's own sake. And, should be == be higher
then >, or the other way? And, what are the arguments for not having
the same level for all of them? I can't see a reason to favour
(a==b)<c over a==(b<c) or vice versa.

All of these operators produce 0 or 1. The < and <= relation between
such values crop up very must less often than == and != do. For example

a < 0 == b < 0

asserts that a and b have the same sign. != is logical XOR.

I am not saying that this will convince you that another precedence
level is needed, but it might persuade you that it's not pointless (as
you seemed to be suggesting).

<snip>

 

[Ben Bacarisse]

They have structure:

function call
arithmetic
power root (**)
multiply divide
plus minus
bitwise
not
and
or
compare
logical
not
and
or
compare (.EQV.)
assignment

To what are you referring? This is not C and it's not Fortran (as
..EQV. might suggest).

 

[Keith Thompson]

Not all of the choices made for operator precedence were good ones;
IIRC, Ritchie himself acknowledged that fact. In a new language where
backwards compatibility was not an issue, they should be done
differently. But I don't think that fewer precedence levels is the way
to go.

Here's what Dennis Ritchie said about it in net.lang.c, this group's
predecessor, on 1982-10-22, Message-ID: <bnews.research.310>:

The priorities of && || vs. == etc. came about in the following way.
Early C had no separate operators for & and && or | and ||. (Got
that?) Instead it used the notion (inherited from B and BCPL) of
"truth-value context": where a Boolean value was expected, after
"if" and "while" and so forth, the & and | operators were
interpreted as && and || are now; in ordinary expressions, the
bitwise interpretations were used. It worked out pretty well, but
was hard to explain. (There was the notion of "top-level operators"
in a truth-value context.)

The precedence of & and | were as they are now.

Primarily at the urging of Alan Snyder, the && and || operators were
added. This successfully separated the concepts of bitwise
operations and short-circuit Boolean evaluation. However, I had
cold feet about the precedence problems. For example, there were
lots of programs with things like
if (a==b & c==d) ...
In retrospect it would have been better to go ahead and change the
precedence of & to higher than ==, but it seemed safer just to split
& and && without moving & past an existing operator. (After all, we
had several hundred kilobytes of source code, and maybe 3
installations....)
Dennis Ritchie

Backward compatibility is not a new problem.

 

[Joe keane]

To what are you referring?

programming languages

I know BASIC, Pascal, Java, and they're all pretty much the same.

Why doesn't C have a '**' operator?
Well it just doesn't.
Why doesn't C have a '^^' operator?
Well it just doesn't.

I can work with Lisp or HP-41 but, obviously a lot of people thought it
useful to AFAP copy math notation (translating formulas).

 

[BartC]

<0.38da0585be4c06b336ce.20120512001744BST.871umqux2f.fsf@bsb.me.uk>,

Why doesn't C have a '**' operator?
Well it just doesn't.

It has a pow() function that does almost the same thing (with fewer
overloading possibilities).

Why doesn't C have a '^^' operator?
Well it just doesn't.

What is ^^ supposed to be? Up-arrow notation?

 

[Keith Thompson]

They have structure:

function call
arithmetic
power root (**)
multiply divide
plus minus
bitwise
not
and
or
compare
logical
not
and
or
compare (.EQV.)
assignment

As you've been asked several times before, what language are you talking
about?

 

[Joe keane]

As you've been asked several times before, what language are you
talking about?

a language that has operator precedence

Although you may find languages without operator precedence,
the ones that do have it are more similar than different.

 

[Keith Thompson]

a language that has operator precedence

Although you may find languages without operator precedence,
the ones that do have it are more similar than different.

So it's not any specific language? You've been posting very specific
information about something that doesn't actually exist -- when
there are *plenty* of examples of real-world languages with well
defined operator precedence rules that would have made perfectly
good examples.

And you didn't feel the need to tell us what you were doing.

Please consider making some additional effort to let people know
what you're talking about rather than wasting our time.

 

[Kaz Kylheku]

a language that has operator precedence

Although you may find languages without operator precedence,
the ones that do have it are more similar than different.

Fortran has operator precedence.
Haskell has operator precedence.
Regular expressions have operator precedence.
....