Who defines C operator precedence and associativity?

Question

Introduction

In every textbook on C/C++, you'll find an operator precedence and associativity table such as the following:

http://en.cppreference.com/w/cpp/language/operator_precedence

One of the questions on StackOverflow asked something like this:

What order do the following functions execute:

f1() * f2() + f3();
f1() + f2() * f3();

Referring to the previous chart I confidently replied that functions have left-to-right associativity so in the previous statements the are evaluated like this in both cases:

f1() -> f2() -> f3()

After the functions are evaluated you finish the evaluation like this:

(a1 * a2) + a3
a1 + (a2 * a3)

To my surprise, many people told me I was flat out wrong. Determined to prove them wrong, I decided to turn to the ANSI C11 standard. I was once again surprised to find out that very little is mentioned on operator precedence and associativity.

Questions

1. If my belief that functions are always evaluated from left-to-right is wrong, what does the table referring to function precedence and associativity really mean?
2. Who defines operator precedence and associativity if it's not ANSI? If it is ANSI who makes the definition, why is little mentioned about operator precedence and associativity? Is operator precedence and associativity inferred from the ANSI C standard or is it defined in Mathematics?

Solution 1

Operator precedence is defined in the appropriate standard. The standards for C and C++ are the One True Definition of what exactly C and C++ are. So if you look closely, the details are there. In fact, the details are in the grammar of the language. For example, take a look at the grammar production rule for + and - in C++ (collectively, additive-expressions):

additive-expression:
  multiplicative-expression
  additive-expression + multiplicative-expression
  additive-expression - multiplicative-expression

As you can see, a multiplicative-expression is a subrule of an additive-expression. This means that if you have something like x + y * z, the y * z expression is a subexpression of x + y * z. This defines the precedence between these two operators.

We can also see that the left operand of an additive-expression expands to another additive-expression, which means that with x + y + z, x + y is a subexpression of it. This defines the associativity.

Associativity determines how adjacent uses of the same operator will be grouped. For example, + is left-to-right associative, which means that x + y + z will be grouped like so: (x + y) + z.

Don't mistake this for order of evaluation. There is absolutely no reason why the value of z could not be computed before x + y is. What matters is that it is x + y that is computed and not y + z.

For the function call operator, left-to-right associativity means that f()() (which could happen if f returned a function pointer, for example) is grouped like so: (f())() (of course, the other direction wouldn't make any sense).

Now let's consider the example you were looking at:

f1() + f2() * f3()

The * operator has higher precedence than the + operator, so the expressions are grouped like so:

f1() + (f2() * f3())

We don't even have to consider associativity here, because we don't have any of the same operator adjacent to each other.

Evaluation of the functions call expressions is, however, completely unsequenced. There's no reason f3 couldn't be called first, then f1, and then f2. The only requirement in this case is that operands of an operator are evaluated before the operator is. So that would mean f2 and f3 have to be called before the * is evaluated and the * must be evaluated and f1 must be called before the + is evaluated.

Some operators do, however, impose a sequencing on the evaluation of their operands. For example, in x || y, x is always evaluated before y. This allows for short-circuiting, where y does not need to be evaluated if x is known already to be true.

The order of evaluation was previously defined in C and C++ with the use of sequence points, and both have changed terminology to define things in terms of a sequenced before relationship. For more information, see Undefined Behaviour and Sequence Points.

Solution 2

The precedence of operators in the C Standard is indicated by the syntax.

(C99, 6.5p3) "The grouping of operators and operands is indicated by the syntax. 74)"

74) "The syntax specifies the precedence of operators in the evaluation of an expression"

C99 Rationale also says

"The rules of precedence are encoded into the syntactic rules for each operator."

and

"The rules of associativity are similarly encoded into the syntactic rules."

Also note that associativity has nothing to do with evaluation order. In:

f1() * f2() + f3()

function calls are evaluated in any order. The C syntactic rules says that f1() * f2() + f3() means (f1() * f2()) + f3() but the evaluation order of the operands in the expression is unspecified.

Solution 3

One way to think about precedence and associativity is to imagine that the language only allows statements containing an assignment and one operator, rather than multiple operators. So a statement like:

a = f1() * f2() + f3();

would not be allowed, since it has 5 operators: 3 function calls, multiplication, and addition. In this simplified language, you would have to assign everything to temporaries and then combine them:

temp1 = f1();
temp2 = f2();
temp3 = temp1 * temp2;
temp4 = f3();
a = temp3 + temp4;

Associativity and precedence specify that the last two statements must be performed in that order, since multiplication has higher precedence than addition. But it doesn't specify the relative order of the first 3 statements; it would be just as valid to do:

temp4 = f3();
temp2 = f2();
temp1 = f1();
temp3 = temp1 * temp2;
a = temp3 + temp4;

sftrabbit gave an example where associativity of function call operators is relevant:

a = f()();

When simplifying it as above, this becomes:

temp = f();
a = temp();

Solution 4

Precedence and associativity are defined in the standard, and they decide how to build the syntax tree. Precedence works by operator type(1+2*3 is 1+(2*3) and not (1+2)*3) and associativity works by operator position(1+2+3 is (1+2)+3 and not 1+(2+3)).

Order of evaluation is different - it does not define how to build the syntax tree - it defines how to evaluate the nodes of operators in the syntax tree. Order of evaluation is defined not to be defined - you can never rely on it because compilers are free to choose any order they see fit. This is done so compilers could try to optimize the code. The idea is that programmers write code that shouldn't be affected by order of evaluation, and yield the same results no matter the order.

Solution 5

Left-to-right associativity means that f() - g() - h() means (f() - g()) - h(), nothing more. Suppose f returns 1. Suppose g returns 2. Suppose h returns 3. Left-to-right associativity means the result is (1 - 2) - 3, or -4: a compiler is still permitted to first call g and h, that has nothing to do with associativity, but it is not allowed to give a result of 1 - (2 - 3), which would be something completely different.

View more solutions

Comments

[ThiefMaster]

10 + 10 * 10 - from left to right that's 10 + 10 = 20, 20 * 10 = 200. with proper precedence it's 10 + (10 * 10) = 110. I'm not sure if those operators add a sequence point, so the order of the function execution might be arbitrary.

[yngccc]

operator associative only group things to avoid ambiguity, they have nothing to do with evaluation order.

[Raymond Chen]

Precedence and associativity are independent of evaluation order. See Eric Lippert's discussion.

[Ed Heal]

It is call maths. Remember Mr sentence from grange hill

[Fiddling Bits]

@yngum Thank you, I understand now.

[Fiddling Bits]

@RaymondChen Thank you, I understand now.

[AnT stands with Russia]

It is also worth noting that, firstly, C and C++ languages differ in relative precedence of = operator inside ?: operator, which means that precedence rules of C and C++ are different. Any table that claims to apply to both C and C++ is inaccurate. And secondly, the precedence properties of ?: operator can't generally be linearized, meaning that any linear table will always be inaccurate with regard to ?: operator.

[Fiddling Bits]

@AndreyT Thank you. Those are things you don't learn in a book.

[Cubbi]

@AndreyT Precedence rules of C and C++ are indeed different (thanks to newfound lvalueness of some operators), but could you illustrate the supposed inaccuracy w.r.t ?: in C++?

[AnT stands with Russia]

@Cubbi: One classic example is a ? b : c = d, which is grouped as (a ? b : c) = d in C (leading to a compile error) and as a ? b : (c = d) in C++.

[Cubbi]

@AndreyT To be pedantic, it isn't grouped that way in C except as compiler extension, but I am more interested in a justification for "any linear table will always be inaccurate with regard to ?:". Unless you were simply referring to the middle expression between ? and :.

[AnT stands with Russia]

@Cubbi: That's not true. Yes, it is actually grouped that way in C. And no, it is not a compiler extension, but rather a requirement of C grammar that has been there from the beginning of times. The issue is well-known and has been covered on SO as well (stackoverflow.com/questions/1082655/…). Even if such grouping were non-standard calling it an "extension" would certainly be incorrect. It would certainly break compliant code. And non-standard compiler features that break compliant code cannot be called "extensions".

[AnT stands with Russia]

When I say that linear table is inaccurate I mean that different "segments" of ?: operator actually have different relative precedence with regard to other operators. In case of C the example with assignment operator in the middle segment illustrates it. In C++ the the example with assignment operator in the last segment illustrates it. I.e. assignment in the first segment always has lower precedence, while assignment in the middle and/or last segment seems to have higher precedence.

[Cubbi]

@AndreyT I believe stackoverflow.com/a/13515505/273767 gives more correct treatment of the grammar involved.

[AnT stands with Russia]

@Cubbi: I'm not sure what you mean by "more correct" since I don't see the contradiction between the two. More specifically, how did it make you conclude that a ? b : c = d is not grouped as (a ? b : c) = d in C?

[Cubbi]

@AndreyT a ? b : c = d does not match any C grammar rule. It is not an expression. Those compilers that use non-standard grammar, have to group it that way to make sure the resulting expression is ill-formed under C's semantics, which also assigns ?: higher precedence. I said I was being pedantic there.

[AnT stands with Russia]

@Cubbi: Good point. Indeed, looking at the actual C grammar I don't see how it can possibly support such grouping...

[StarPinkER]

Take a look at sequence point.

[Fiddling Bits]

What do you mean by Left-to-right associativity means that f() + g() + h() means (f() + g()) + h() and a compiler is permitted to first call g and h? Aren't this statements contradictory?

[Pascal Cuoq]

As an example, the grammar rule that says that multiplicative-expression can be written as cast-expression or as multiplicative-expression * cast-expression defines casts as having precedence over multiplication and multiplication as associating to the left.

[Admin]

@FiddlingBits No, they're not. My answer is overly complicated, I'll simplify.

[Admin]

@FiddlingBits Does this help?

[Fiddling Bits]

When you say "[l]eft-to-right associativity means the result is (1 - 2) - 3, or -4", this is referring the associativity of the difference operator (-). I understand this, however, this is independent of the associativity and evaluation of function calls. If functions are associative from left-to-right, why can they be called right-to-left, for example? Sorry if I'm being dumb and making you repeat yourself.

[Fiddling Bits]

In the case of something like 10 * 2 / 5, it is evaluated like (10 * 2) / 5, right? It must, because if associativity was not obeyed, the answers would be completely different. Aren't statements evaluated from the top down as far as precedence are concerned however associativity is defined? Sorry if I'm making you repeat yourself?

[Fiddling Bits]

Can you include an example when function call associativity does apply?

[Pascal Cuoq]

This is a refreshingly direct answer to the question.

[Joseph Mansfield]

@FiddlingBits Both * and / are multiplicative operators and are basically considered to be the same for the sake of operator precedence and association. Since they associate left-to-right, you are right that the grouping is (10 * 2) / 5.

[Joseph Mansfield]

@FiddlingBits The point is that 5 can be evaluated before 10 * 2. The only ordering here is that the division must happen after the evaluation of its operands.

[Barmar]

@FiddlingBits Added the function call associativity example.

[Fiddling Bits]

Okay, I think I get it now. What's happening here, f()(), is that first f() is called and it returns a pointer to another function, then the function that is returned is called. Is that right?

[Fiddling Bits]

Thank you. I understand now.

[Fiddling Bits]

Thank you, I understand now.

[Barmar]

Right. Although this also is based on a simpler rule: you always have to compute a value before you can use it. E.g. it wouldn't make sense to do temp1 = f1() after temp3 = temp1 * temp2.

[Admin]

@FiddlingBits Ah, now I sort of get what you mean. Left-to-right associativity for function calls can be taken to mean that a(b)(c) is (a(b))(c), never a((b)(c)), even though both are potentially valid expressions. (Remember, a function can return a pointer to another function.) It's still independent of evaluation order.

[Fiddling Bits]

Thank you. I understand now.

[Keith Thompson]

A good answer -- but you might expand it a bit to mention that some operators (&&, ||, ?:, ,) do impose a particular evaluation order on their operands.

[Admin]

The && should be a || to make sense. Adding as a comment since I cannot edit only two characters.