associativity question

[fdmfdmfdm]

Associativity in C takes two forms: left to right and right to left. I
think the K&R book lacks something...

For example, *p++, since the associativity is from right to left, do
this expression means *(p++)? I think I am wrong. (so, associativity
is not for operand?)

But for *++p, right to left associativity means *(++p) is correct.

So by definition of associativity, I guess it only applys on grouped
operators but not on operand. Right? A more complicated example will
be char* const *(*next++)()

 

[Richard Heathfield]

(e-mail address removed) said:

Associativity in C takes two forms: left to right and right to left. I
think the K&R book lacks something...

For example, *p++, since the associativity is from right to left, do
this expression means *(p++)?
Yes.

But for *++p, right to left associativity means *(++p) is correct.

Yes, except for the "But", which should be "And".

 

[CBFalconer]

(e-mail address removed) said:


Yes, except for the "But", which should be "And".

In both cases the OP should think about the value of the beast
encased in parentheses.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Andrey Tarasevich]

Associativity in C takes two forms: left to right and right to left. I
think the K&R book lacks something...

OK. Although the syntax (and semantics) of expressions in C is officially
described by the language grammar, in most cases it can be described in
simplified terms of operator "associativity" and "precedence".

For example, *p++, since the associativity is from right to left,
do
this expression means *(p++)? I think I am wrong. (so, associativity
is not for operand?)

There's no associativity involved in this case. Associativity is only applicable
to binary operators. In this case it is about precedence only. Postfix operators
normally take precedence over prefix operators. That's why it means '*(p++)'.

But for *++p, right to left associativity means *(++p) is correct.

Once again, no associativity involved here. Moreover, in this particular case
there's no need to involve either associativity or precedence.

Associativity and/or precedence come into play when the meaning of the
expression is potentially ambiguous, i.e. there are several ways to assign
precedences and associate operands with operators. In order to be ambiguous it
has to involve multiple binary/ternary operators, or a mix of prefix and postfix
unary operators applied to the same operand, or a mix of unary and
binary/ternary operators.

There's nothing like that in case of '*++p'. There's only one way to parse it.
It's *(++p)'. No need (and no way) to involve precedence or associativity at all.

So by definition of associativity, I guess it only applys on grouped
operators but not on operand. Right?

Associativity applies when you have a long "chain" of binary operators of equal
precedence. It's associativity that tells you that 'a - b + c' means '(a - b) +
c' and not 'a - (b + c)'.

A more complicated example will
be char* const *(*next++)()

This just doesn't make sense in C. At the first sight it looks like a
declaration, but you can't have a '++' in a declaration (at least not the way
you used it above).

 

[Ben Bacarisse]

OK. Although the syntax (and semantics) of expressions in C is officially
described by the language grammar, in most cases it can be described in
simplified terms of operator "associativity" and "precedence".


There's no associativity involved in this case. Associativity is
only applicable to binary operators.

Associativity (or something very like it) is applicable in expressions
with unary operators if pre- and postfix operators are mixed.

*p++ could be ((*p)++) or (*(p++))

In their operator table K&R list * and ++ as right associative so the
above is interpreted as we all know it is.

In this case it is about precedence only. Postfix operators
normally take precedence over prefix operators.

Not according to K&R. They list them in the same row -- i.e. as
having the same precedence. As you say, non of this is "official",
but it is the source of the OP's question. In fact on page 91[1] they
explain that to increment what p points to you must write (*p)++
because "unary operations like * and ++ are evaluated right to left".

[1] My copy is K&R 1978(!).

 

[Chris Torek]

Simplified for humans, anyway. Computers can do it either way.

More specifically, the task at hand is to bind operators to operands,
so as to build a "parse tree" (see, e.g.,
<http://en.wikipedia.org/wiki/Parsing>, which has a little graphic
of how to bind "1 + 2 * 3" in the usual manner). If one uses an
"operator precedence grammar", to simplify the idea for humans,
one must specify the "precedence" of the various operators, hence
the name "operator precedence grammar".

As Andrey Tarasevich noted, the C standards (C89 and C99 both) use
a different method, so that Standard C does not need to talk about
precedence and associativity at all. (It still uses those words
anyway, since the grammar in the standard has an implied equivalent
operator-precedence grammar. In fact, it actually has multiple
implied equivalents, as we shall see.)

Well, sort of:

Associativity (or something very like it) is applicable in expressions
with unary operators if pre- and postfix operators are mixed.

Only if they are given the same "precedence", though.

The problem with a simple precedence grammar is that it does not
tell us what to do when all the operators have the *same* precedence.
In particular, given something like:

x op y op z

does this mean:

op
/ \
(x op y) op z op z
/ \
x y

or does it mean:

op
/ \
x op (y op z) x op
/ \
y z

? It could be either one -- so to "break the tie", we add a
complication to the already-complicated[%] "operator precedence"
grammar, where "precedence" tells us which operator(s) to bind
first[*]. We add "associativity" too; it tells us which operator(s)
to bind first in case "precedence" failed to tell us. It *only*
applies *after* precedence fails, though!
-----
% Yes, complicated: just less-so than the *really* complicated
fully-factored grammar in the C standards.
* Note that this is all about binding operators at *compile*
time. Actual evaluation order at runtime is another matter
entirely.
-----

*p++ could be ((*p)++) or (*(p++))

If we give "++" higher precedence than unary "*", then it can only
be the latter; we need not look for any associativity.

If the standard's grammar is mechanically transformed into an
operator-precedence grammar, the resulting grammar does in fact
give (postfix) "++" higher precedence than unary "*". (It gives
prefix "++" the same precedence, but operators bind to operands,
not to additional operators, so interpreting *++p as (*++)p is
right out.)

In their operator table K&R list * and ++ as right associative so the
above is interpreted as we all know it is.

Hence, K&R use a *different* grammar -- but one that achieves the
same result.

It is OK to change the grammar if the result is the same. Compiler
writers do this all the time, for various reasons. The C standards
require only that one get the correct answer; the method by which
this "right answer" is obtained is infinitely changeable.