Ambiguity and How to Remove It

When one string has two trees

In guide 2 you learned that a parse tree is the real record of how a context-free grammar built a string, and that the order in which you replace variables — leftmost or rightmost — does not matter, because both leftmost and rightmost derivations describe the same tree. That promise quietly assumed there was only one tree to describe. A grammar is called ambiguous when some single string in its language has two genuinely different parse trees. Not two derivations that differ only in replacement order — those are harmless — but two trees with a different shape.

Why should you care, if the string is accepted either way? Because a parse tree is not just proof of membership — it is the skeleton of meaning. When you later walk the tree to compute a value, type-check, or translate to machine code, the shape of the tree decides the answer. Two shapes for one string means two meanings, and a compiler cannot quietly pick one. Membership asks 'is this string in the language?'; ambiguity asks 'does this string have exactly one structure?' — a strictly harder and more interesting question.

The textbook culprit is arithmetic. Take the over-simple grammar E -> E + E | E * E | a, which you might write on a first attempt because it clearly generates all the right strings. Now parse a + a * a. One tree adds first then multiplies, computing (a + a) * a; the other multiplies first, computing a + (a * a). Both are legal parse trees of the very same string under the very same grammar. The grammar has told you nothing about which one is meant — and for numbers those answers differ. The grammar is correct as a set of strings but useless as a guide to structure.

Two pictures of the same string

It is worth seeing the two trees side by side, because the shape is the bug. Below are both parse trees for a + a * a under E -> E + E | E * E | a. Read each one from the root down: the operator nearest the root is the one applied last (and therefore binds the loosest), and the deepest operator is applied first. The left tree puts + at the root, so multiplication happens inside and binds tighter; the right tree puts * at the root, so addition happens first. We want the first reading and not the second, but the grammar permits both.

string:  a + a * a        (grammar:  E -> E + E | E * E | a)

  Tree 1: a + (a * a)        Tree 2: (a + a) * a
  ------------------         ------------------
          E                          E
        / | \                      / | \
       E  +  E                    E  *  E
       |    /|\                   /|\    |
       a   E * E                 E + E   a
           |   |                 |   |
           a   a                 a   a

  root operator = applied LAST = binds loosest
  Tree 1 multiplies first (correct);  Tree 2 adds first (wrong)

The cure: encode precedence and associativity

The fix is to stop letting the grammar choose and instead bake the answer into its structure. Two facts are missing from the naive grammar, and we must encode both. First, precedence: multiplication should bind tighter than addition, so a + a * a must read as a + (a * a). Second, associativity: a - a - a should mean (a - a) - a, grouping left, not a - (a - a). The trick is to introduce one variable per precedence level and let lower-binding operators sit above higher-binding ones in the tree, forcing the shape we want.

Build it in layers, loosest operator outermost. An expression E is a chain of terms joined by +; a term T is a chain of factors joined by *; a factor F is the smallest unit, an a or a parenthesised expression. Because E can only break down into T (and never directly into a *-rule), every + necessarily ends up higher in the tree than every *, which is exactly precedence. To pin down associativity, make the recursion lean one way: write E -> E + T (left-recursive) so a + a + a forces (a + a) + a, grouping left. Now there is no choice left to make — exactly one tree survives.

Ambiguous (one level, free choice):
    E -> E + E | E * E | ( E ) | a

Unambiguous (layered: + loosest, * tighter, () tightest):
    E -> E + T | T          # + groups left, binds loosest
    T -> T * F | F          # * groups left, binds tighter
    F -> ( E ) | a          # parentheses / atoms bind tightest

Now a + a * a has ONLY this tree:
        E
      / | \
     E  +  T
     |    /|\
     T   T * F
     |   |   |
     F   F   a
     |   |
     a   a            => a + (a * a), as intended

Dangling else, and when you cannot win

Arithmetic is not the only offender. The most famous real-language case is the dangling else: with rules like S -> if C then S | if C then S else S | other, the string 'if C then if C then a else b' is ambiguous — does the else attach to the inner if or the outer one? Real languages decree a rule ('else binds to the nearest unmatched if') and then rewrite the grammar to enforce it, splitting statements into 'matched' and 'unmatched' kinds so that an else can never reach past a closer if. It is the same medicine as before: when the bare grammar offers a choice, restructure it so only the intended tree is derivable.

But here is the hard, honest truth this rung must tell. Sometimes you cannot win. A context-free language is called inherently ambiguous if every context-free grammar that generates it is ambiguous — the ambiguity is in the language, not just in a sloppy grammar. The classic example is the language of strings a^i b^j c^k where either i = j or j = k. Any grammar must handle both cases, and the strings where i = j = k can always be built two ways — one matching the a's to the b's, one matching the b's to the c's — and no rewriting ever erases that overlap. So no amount of cleverness produces a one-tree grammar.

How to actually do it

Pulling it together, here is the routine you reach for whenever a grammar you designed in guide 3 turns out to admit two trees. The aim is never to change the language — every step below preserves exactly which strings are generated — only to make each string's structure unique.

1. Find the ambiguity concretely. Look for a short string with two parse trees (or two distinct leftmost derivations). For operators it is almost always something like a + a * a or a - a - a; for statements it is the dangling else. A single witness string is enough to prove the grammar ambiguous.
2. Rank the operators by precedence — which should bind tightest? Then create one variable per level, from loosest at the top (the start variable) down to tightest at the bottom (atoms and parentheses).
3. Wire each level to break down only into the next-tighter level, never directly into a looser operator. That single discipline forces looser operators to sit higher in every tree, which IS precedence.
4. Choose associativity per operator by leaning the recursion. Left-recursive (E -> E + T) groups left; right-recursive (E -> T + E) groups right; pick whichever matches the operator's real meaning (- and / lean left, ^ leans right).
5. Re-test the witness string and a couple of mixed cases. Confirm exactly one tree now exists. Remember you can never fully automate this last check across all grammars, so reason it through by hand or rely on a parser-generator that rejects grammars outside its clean class.

That is the whole art of removing ambiguity: never widen or narrow the language, just sculpt its grammar until structure becomes a function of the string and nothing else. With a clean, unambiguous grammar in hand, you are ready for the next guide, where the very same layered shape reappears under an industrial name — BNF and EBNF — as the notation real language manuals use to publish exactly this kind of grammar.