Avoiding confusion about precedence

Question

When mentioning operator precedence for AND / OR, I explained it wrongly. I re-explained it properly using the idea of binding: the operator "binds tightly" to the two expressions immediately on either side.

My incorrect explanation was based on me thinking of a complex expression as a tree, with AND as the root. For example, this fake expression:

expr1 OR expr2 AND expr3

behaves as if there are parentheses around expr2 AND expr3, but the "tree view of precedence" with AND being "more" would put the parentheses around the OR expression. I didn't explain my wrong idea to the students, but it is an error that I sometimes make in my thinking - it makes sense to me!

Is there a better way of explaining precedence to avoid this ambiguity than to say "it binds tightly"?

I encountered this when teaching SQL, but the question is not really about Boolean operators or Math, it is about Precedence in general as implemented in many languages. (If I had been showing a math example I would have unconsciously followed the rules of Algebra, but Booleans are not as common in my life.) A common synonym for Precedence is "Order Of Operations", but in SQL there is not supposed to be an 'order'. This is especially so with Booleans, because they just yield T/F and so there is no sense of left-to-right or anything.

Answer 1

Actually, your tree explanation is fine, except that it is the low precedence operators closer to the root. In Java, the "." operator is the strongest/highest and the assignment operators are the lowest precedence. The arithmetic operators are all higher precedence (bind tighter) than the booleans, with && having higher precedence than ||

A semi-official list is here: http://operator-precedence.com/java

In fact many compilers will translate an expression (the entire program, in fact) into a tree structure either explicitly or implicitly.

But, "binding tightly" is pretty traditional for an explanation also. The scope of an operator is limited by the end of the expression or the occurrence of a lower precedence operator. Therefore the RHS of the OR in your example is the end of the expression, but the LHS of the AND is bounded by the OR operator.

In the tree explanation work from lower to higher. In the "binding tightly" work from the higher to the lower precedence operator.

---

Odd historical note: To a logician, AND is logical "multiplication" and OR is logical "addition", hence the typical relationship in programming languages.

However, Pascal took that idea a bit too far and OR had the same precedence as addition with AND having the same precedence as multiplication, requiring parentheses in many more expressions than you would like.

On the other hand, having to write things explicitly in a programming language is usually a good thing as it lessens the likelihood of an oversight error.

Answer 2

You can use an analogy of priority queues (maybe a hospital, if it isn't too gruesome; perhaps a queue for ordering work tasks)

A nurse doesn't need a patient to have some indicator that they are supposed to be treated before some other patients (these indicators are the parenthesis). There's simply a known treatment order, based on the urgency of the treatment.

If all patients need equally urgent treatment, then they are treated according to the order of their appearances (the ones who "check in" first are the ones treated first).

Nurses know how urgent a new patient's treatment is, and so does the compiler. For java, it goes like this:

1. postfix    expr++ expr--
2. unary  ++expr --expr +expr -expr ~ !
3. multiplicative * / %
4. additive   + -
5. shift  << >> >>>
6. relational < > <= >= instanceof
7. equality   == !=
8. bitwise AND    &
9. bitwise exclusive OR   ^
10. bitwise inclusive OR  |
11. logical AND   &&
12. logical OR    ||
13. ternary   ? :
14. assignment    = += -= *= /= %= &= ^= |= <<= >>= >>>=

(Taken from the Oracle Docs, numbering is mine. Originally has table)

In effect, the function and member call are before all other operators. So . is of precedence 0.

The nurse (compiler) knows in which order to actually treat (execute\write to bytecode) the various levels or urgency.

Different languages might have different ordering, but the analogy of a nurse ordering the treatment based on urgency would still hold. In the example you gave, it's more "urgent" to deal with the AND than it is with OR.

So in SQL, some operators are dealt with before others. Some operators require expressions on both sides, and some don't (select only needs from the right, while AND needs from both sides).

Answer 3

1st remind pupils of BIDMAS, they learn this is arithmetic class, around the age of 11years old. Though in programming it is usually BIMDAS. Though this only makes a difference when there are rounding errors.

When teaching boolean algebra, use a+b (or), a.b (and), as opposed to a∨b (or), a∧b (and). The second makes much more sense when relating boolean logic to set theory. However the first makes more sense when relating to algebra. The precedence is the same. All of the algebraic manipulations are the same, except 1+1=1. Now show that all of the rules in the book can be derived from these. Back this up by creating truth tables. Then practice. Then add de Morgan’s Theorem. Then practice.

When mixing logic, and arithmetic or any other complex combination (if you are not 100% sure, Or think that other will not be, or other languages do it differently, or you suspect that the may do, or just because you want to), then use parenthesis.

Answer 4

Is there a better way of explaining precedence to avoid this ambiguity than to say "it binds tightly"?

The most unambiguous way to think about and explain precedence is by a context-free grammar (also known as a Backus–Naur form). The language of Boolean expression in the form of a context-free grammar follows.

expr0 ::= expr0 'OR' expr1 | expr1;
expr1 ::= expr1 'AND' expr2 | expr2;
expr2 ::= predicate | '(' expr0 ')';

expr0 is a Boolean expression; predicate is an atomic formula, an application of a predicate like “less than”. You see that the arguments of AND may be an AND-expression, a predicate application, or a bracketed expression, but never an OR-expression. The only way to insert an OR-expression inside an AND-expression is the way expr1 → expr2 → brackets → expr0. Hence AND binds more tightly than OR. This defines precedence. Notice that this grammar also defines associativity; OR and AND are left-associative.

It is not possible to convey the whole theory of formal grammars in an answer. Any introductory textbook on automata theory, programming language semantics or implementation should contain this topic.

A common synonym for Precedence is "Order Of Operations", but in SQL there is not supposed to be an 'order'.

The fact that there is no order of operations in SQL is related to the semantics of SQL, while the question of precedence and associativity is related to syntax.