Ambiguity, Precedence and Associativity

A parse tree fixes the meaning of a program, because later phases read the tree, not the raw text. So a grammar that assigns two trees to one string is a grammar that assigns two meanings — a genuine catastrophe for a compiler, which must be deterministic about what your code does. A grammar with that flaw is ambiguous.

The cure is not to throw the language away but to rewrite the grammar so that exactly one tree survives — and to choose which tree survives so it matches the arithmetic everyone already expects.

The classic culprit: a flat expression grammar

Collapse our careful three layers into one seductive line:

E \;\to\; E + E \;\mid\; E * E \;\mid\; (\,E\,) \;\mid\; \mathbf{id}.

It generates precisely the same language as the layered grammar — every sum and product of identifiers — but it is ambiguous. Take the single string \mathbf{id} + \mathbf{id} * \mathbf{id}. Because E may combine with E under either + or * with no rule about which binds first, two different trees are legal:

Tree A — + at the root, so * happens first: \mathbf{id} + (\mathbf{id} * \mathbf{id}). This is what we want.

Tree B — * at the root, so + happens first: (\mathbf{id} + \mathbf{id}) * \mathbf{id}. Arithmetically wrong.

Both are valid derivations under the flat grammar, and nothing in the grammar prefers one. If the parser picks Tree B, then 2 + 3 * 4 evaluates to 20 instead of 14. The grammar, not the parser, is to blame.

Encoding precedence into the grammar's layers

Precedence is the rule that * binds tighter than +. The trick that removes the ambiguity is to give each precedence level its own nonterminal, stacked so that the tighter-binding operator lives lower (nearer the leaves) in every tree. That is exactly the layered grammar from the CFG page:

\begin{aligned} E &\;\to\; E + T \;\mid\; T &&\text{(sums live at the top)}\\ T &\;\to\; T * F \;\mid\; F &&\text{(products one level down)}\\ F &\;\to\; (\,E\,) \;\mid\; \mathbf{id} &&\text{(atoms at the bottom)} \end{aligned}

Now a + can only be introduced by E \to E + T, whose operands are already-complete terms; a * can only appear inside a term. So a product is always gathered into a single T before any surrounding + can touch it — Tree B becomes underivable, and only the *-first shape (Tree A) remains. There is now exactly one parse tree for \mathbf{id} + \mathbf{id} * \mathbf{id}. Adding more levels (comparison, logical-or, …) is just more layers in the same stack.

Associativity: which way does \mathbf{id} - \mathbf{id} - \mathbf{id} lean?

Precedence separates different operators; associativity settles operators of the same precedence. Subtraction must be left-associative: a - b - c means (a - b) - c, not a - (b - c). The direction of the recursion in the production decides this:

Production shapeRecursionTree leansMeaning of a\,\theta\,b\,\theta\,c
E \to E - Tleft-recursiveleft(a - b) - c — left-associative
E \to T - Eright-recursiverighta - (b - c) — right-associative

So E \to E + T is not merely a stylistic choice — the left recursion is what makes + and - group to the left, as arithmetic demands. Right-associative operators, like exponentiation (2 \wedge 2 \wedge 3 = 2 \wedge (2 \wedge 3)) and the assignment operator = in C, get right-recursive productions instead. Same precedence trick, opposite lean.

The dangling else

The most famous ambiguity in language design has nothing to do with arithmetic. Consider the natural statement grammar

S \;\to\; \mathbf{if}\ E\ \mathbf{then}\ S \;\mid\; \mathbf{if}\ E\ \mathbf{then}\ S\ \mathbf{else}\ S \;\mid\; \text{other}.

Now parse \mathbf{if}\ E_1\ \mathbf{then}\ \mathbf{if}\ E_2\ \mathbf{then}\ S_1\ \mathbf{else}\ S_2. Whose \mathbf{else} is it? It could bind to the outer \mathbf{if} (execute S_2 when E_1 is false) or to the inner \mathbf{if} (execute S_2 when E_1 is true but E_2 is false). Two trees, two behaviours. Every mainstream language resolves it by fiat — an \mathbf{else} matches the nearest unmatched \mathbf{if} — and this can be baked into the grammar by splitting statements into "matched" (fully-elsed) and "open" nonterminals so that the string between a \mathbf{then} and its \mathbf{else} is forced to be matched. It is the precedence trick again: rewrite the grammar until only the intended tree survives.

Practicality. Rewriting a grammar to be unambiguous can double its size and blur its readability — the layered expression grammar is already less obvious than E \to E + E \mid E * E. So tools like yacc/bison let you keep the short, ambiguous grammar and instead declare how to break ties: %left '+' '-' then %left '*' '/' tells the generator that both are left-associative and that * outranks +. A per-rule %prec handles oddities like unary minus. Under the hood the generator still resolves every shift/reduce conflict deterministically — you have simply moved the precedence declaration out of the grammar's shape and into a compact directive. The dangling \mathbf{else} is conventionally resolved by the default "prefer shift", which happens to attach the \mathbf{else} to the nearest \mathbf{if} — exactly the rule we wanted.

Two traps. First, never say "this language is ambiguous" when you mean the grammar — almost every ambiguous grammar has an unambiguous sibling for the same language, and rewriting is the standard fix. (A rare few languages are inherently ambiguous, with no unambiguous grammar at all, but no programming language is one of them.) Second, and more sobering: there is no algorithm that decides, for an arbitrary CFG, whether it is ambiguous — the problem is undecidable, provably reducible to Post's Correspondence Problem. That is why parser generators cannot simply warn "your grammar is ambiguous"; instead they report concrete conflicts (shift/reduce, reduce/reduce) that they hit while building their tables, which are a decidable, conservative proxy. A grammar can be unambiguous yet still provoke conflicts in a particular parsing method — the two notions are related but not the same.