Who defines operator precedence and associativity, and how does it relate to order of evaluation?

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:

In 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?

Comyns

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. – Crosscheck

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

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

It is call maths. Remember Mr sentence from grange hill – Awake

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. – Daltondaltonism

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

@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++? – Furie

@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++. – Daltondaltonism

@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 :. – Furie

@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 (#1083155). 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". – Daltondaltonism

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. – Daltondaltonism

@AndreyT I believe https://mcmap.net/q/451027/-does-the-c-c-ternary-operator-actually-have-the-same-precedence-as-assignment-operators gives more correct treatment of the grammar involved. – Furie

@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? – Daltondaltonism

@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. – Furie

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

Take a look at sequence point. – Daunt

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

Whimsey

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? – Comyns

@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. – Whimsey

@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. – Whimsey

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

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

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

Italy

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. – Suffrage

Answer 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();

Japanese

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? – Comyns

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. – Japanese

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

Bromleigh

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

Tuner

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? – Comyns

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

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. – Comyns

@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. – Tuner

Answer 6

Firstly, you're conflating operator precedence/associativity and order of evaluation. These are two different concepts.

• Operator precedence tells you which operations take place between what operands.
• Order of evaluation tells you in what order these operands are evaluated, prior to the operator.

Overall, operator precedence tells us that the following operations take place:

x1 = f1()
x2 = f2()
x3 = f3()
xm = x2 * x3
xa = x1 + xm

The only ordering requirement (due to dependencies) is that x2 and x3 must be computed before xm, and x1 and xm must be computed before xa. Other than that, the compiler is free to do things in any order it wants.

Operator precedence is governed by the language grammar

Operator precedence is a consequence of the grammar of the language. For example, both C and C++ languages have the rule:

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

According to this rule, the expression f1() + f2() * f3() is parsed as:

                  additive-expression
                          │
           ┌──────────────┼──────────────┐
           │              │              │
   additive-expression   '+'   multiplicative-expression
           │                   ┌─────────┼─────────┐
 multiplicative-expression     │         │         │
           │                  ...       '*'       ...
          ...                  │                   │
           │            postfix-expression  postfix-expression
    postfix-expression         │                   │
           │                  f2()                f3()
          f1()

Note: The ... indicates that there are many rules which are expanded until arriving at postfix-expression.

In other words, the operands are grouped like:

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

Precedence, arity, and associativity are all consequences of grammatical rules:

• + has lower precedence than * because it appears at a shallower level in the grammar
• + is left-to-right associative because additive-expression is left-recursive
• + is a binary operator because there are two rules additive-expression and multiplicative-expression expanded to its sides

Order of evaluation is governed by sequencing rules

As already stated, order of evaluation is separate from precedence. Precedence can only tell you that a multiplication f2() * f3() takes place, but it does not tell you whether f2() or f3() are executed first.

[intro.execution] p10 states:

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced.

Note that [intro.execution] p11 also states that function calls cannot be interleaved, so functions behave as if they were indeterminately sequenced, not unsequenced. In other words, f2() and f3() cannot be executed in parallel/interleaved, but it is unspecified whether f2() or f3() is executed first.

Some operators do have sequencing; for example, in f4() << f5(), f4() is always executed before f5(), because of the sequencing in [expr.shift] p4:

[For E1 << E2,] the expression E1 is sequenced before the expression E2.

Toluene