Operator Precedence

Precedence is usually stated as a table of levels, and that framing hides the mechanism. What precedence actually decides is which operator ends up at the *root* of the subtree. For 1 + 2 * 3, the multiplication binds tighter, which means it is applied first, which means it is *further from the root* — the addition is the outermost operation and therefore the parent.

Say it as a rule and it becomes checkable: higher precedence, deeper in the tree. Every time you are unsure what a precedence table means, build the tree and read it back. A tree is unambiguous in a way that a table of numbers, half of which count up and half of which count down depending on the document, is not.

The tree below is what every mainstream language builds for 1 + 2 * 3, and it evaluates to 7. The alternative tree — the multiplication at the root — evaluates to 9, and it is what a flat grammar with no precedence produces about half the time depending on the parsing algorithm. That is [[ambiguous-grammars]]; this lesson is about the machinery that prevents it.

There are three ways a real implementation arranges that shape, and it is worth being able to recognise all three because you will read all three.

Grammar layering. One nonterminal per level, each referring to the level below: expression handles + and -, term handles * and /, factor handles literals and parentheses. The tighter operator is in the deeper rule, so the tighter operator ends up deeper in the tree — the structure of the grammar *is* the precedence table. Unambiguous by construction; a new precedence level means a new nonterminal and edits to its neighbours.

Declared precedence. Keep one flat rule, expr : expr OP expr, and put the levels in declarations: Bison's %left '+' '-' then %left '*' '/', with later declarations binding tighter. The generator uses them to resolve the conflicts the flat rule creates. One line per operator; the grammar alone no longer specifies the language.

Binding powers. A Pratt or precedence-climbing parser stores a numeric binding power per token and runs a loop: parse a left operand, then while the next token binds at least as tightly as the current minimum, consume it and recurse with a raised minimum. The table is data at run time, so operators can even be added dynamically — which is how Haskell's user-defined infixl 6 operators work. See [[pratt-parsing]].

Everyone learns that * binds tighter than +, and that much is stable across essentially every language with infix arithmetic. Almost nothing else is. The interesting bugs come from carrying a precedence intuition from one language to another, and there are three collisions common enough to be worth memorising.

The first is C's bitwise operators. &, | and ^ bind *looser* than the comparison operators, a decision Dennis Ritchie later called a mistake and which persists for compatibility. So x & mask == 0 parses as x & (mask == 0), which is almost never what the author meant, and both GCC and Clang warn about it under -Wparentheses.

The second is shift. In C, + binds tighter than <<, so a + b << c means (a + b) << c. In Go, the shift operators sit in the *same* precedence group as * and /, above +, so the same source means a + (b << c). Identical text, different tree, no diagnostic.

The third is unary minus against exponentiation. In Python, ** binds tighter than a unary minus on its left, so -2 ** 2 is -(2 ** 2) and evaluates to -4. JavaScript found this confusing enough that ES2016 made -2 ** 2 a syntax error outright, requiring the author to write the parentheses.

Parentheses are not an operator. They are the author's instruction to the parser to build a particular subtree regardless of the table, and in most languages they leave no trace at all in the AST — (1 + 2) * 3 and a hypothetical AST written directly as *(+(1,2), 3) are indistinguishable after parsing. That is usually what you want, and it is occasionally a problem: a formatter or a lint rule that wants to preserve redundant parentheses has to keep them explicitly, which is one of the reasons a [[concrete-syntax-tree]] exists as a separate artefact from the AST.

The corollary is the one to remember when reading generated code or a decompiler's output: parentheses in the *output* are re-derived from the tree and the precedence table, not recovered from the input. A printer that gets the table wrong emits parentheses that are correct-but-noisy, or — worse — omits ones that were needed, producing text that no longer round-trips to the same tree.