Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 61 ยท Context-Free Grammars

Ambiguity, Precedence and Associativity

Learn why ambiguous grammars break compilers, how to layer rules for operator precedence and associativity, and fix the dangling else, with a Python tree counter.

What is the value of 2 + 3 * 4? Everyone says 14, because multiplication goes first. What is 8 - 4 - 2? Everyone says 2, because subtraction works from the left. These rules feel obvious, but a grammar does not know them. A grammar only says which token sequences are legal. If it is written carelessly, one sentence can have two different parse trees, and the compiler has no way to know which one you meant.

This problem is called ambiguity. In this lesson you will see exactly what it is, why it matters for real programs, and how grammar writers remove it: by layering rules to encode precedence and associativity, and by fixing the famous dangling else. You will also run a small program that counts the parse trees of a sentence, which turns the abstract idea of ambiguity into a number you can print. If you need a refresher on trees and derivations, read Context-Free Grammars first.

What is an ambiguous grammar?

A grammar is ambiguous if at least one sentence has more than one parse tree (equivalently, more than one leftmost derivation). Here is the shortest possible example:

TEXT
E -> E + E | E * E | ( E ) | n

It looks harmless, and it is easy to read. But consider n + n * n. The grammar is happy to build either of these trees:

flowchart TD
    subgraph A["Tree A: (n + n) * n"]
        A1["E"] --> A2["E"]
        A1 --> A3["*"]
        A1 --> A4["E: n"]
        A2 --> A5["E: n"]
        A2 --> A6["+"]
        A2 --> A7["E: n"]
    end
    subgraph B["Tree B: n + (n * n)"]
        B1["E"] --> B2["E: n"]
        B1 --> B3["+"]
        B1 --> B4["E"]
        B4 --> B5["E: n"]
        B4 --> B6["*"]
        B4 --> B7["E: n"]
    end

Two valid parse trees for the same sentence. Tree A adds first, tree B multiplies first.

With n = 2, 3, 4 the two trees evaluate to 20 and 14. A compiler built on this grammar could generate different code depending on an arbitrary choice. Ambiguity is therefore not a style problem; it is a bug in the language specification. Parser generators also reject or warn about it (it shows up as conflicts in the parse table, which you will meet in LL(1) parsing and LR parsing).

There are two ways to deal with it. The grammar can be rewritten to be unambiguous (the topic of this lesson), or the ambiguous grammar can be kept and paired with extra disambiguating rules such as precedence declarations. Both are common; Pratt parsing is the second approach in hand-written form.

Counting parse trees

How do you check ambiguity on a concrete sentence? Count the parse trees. The function below uses dynamic programming: count(symbol, i, j) is the number of ways the symbol can derive tokens i to j. For a production, it tries every way to split that span between the symbols on the right side. It works for grammars without empty (epsilon) productions and without cycles like A -> B, B -> A, which is plenty for our examples.

Run it on the ambiguous grammar and on a layered grammar for the same language (we explain the second one in a moment). The count for a layered grammar is always 1.

Python An ambiguity counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the numbers. n + n * n has two trees (precedence problem), n + n + n also has two (associativity problem: does it group left or right?), and n + n + n + n has five. Those counts are Catalan numbers, and they grow quickly: ambiguity is not an occasional curiosity but an explosion. Parentheses remove ambiguity entirely, which is why ( n + n ) * n has just one tree even in the ambiguous grammar.

Precedence by layering

Precedence says which operator binds tighter. The standard grammar trick uses one nonterminal per precedence level, with the loosest-binding operators at the top and the tightest at the bottom:

TEXT
E -> E + T | T        (level 1: addition, loosest)
T -> T * F | F        (level 2: multiplication, tighter)
F -> ( E ) | n        (level 3: atoms and parentheses, tightest)

Why does this work? In n + n * n, the root must be E. The only way to place * is inside a T, and a T can only appear as an operand of + (or alone). So the multiplication is always deeper in the tree than the addition, and therefore happens first. The grammar cannot even express the tree (n + n) * n without parentheses: to make + the operand of *, the + must be wrapped in ( E ), which is a F.

The recipe is mechanical:

  1. List the operators from the loosest to the tightest precedence.
  2. Give each level a nonterminal.
  3. Each level's operands are the next tighter level.
  4. The tightest level is the atoms (numbers, identifiers, parenthesized expressions), and ( E ) loops back to the top.

Associativity: left or right?

Associativity decides how a chain of operators with the same precedence groups: 8 - 4 - 2 as (8 - 4) - 2 (left-associative) or 8 - (4 - 2) (right-associative). The two give 2 and 6.

In a grammar, associativity is the direction of the recursion:

TEXT
E -> E - T | T       left-associative: the recursion is on the LEFT
E -> T - E | T       right-associative: the recursion is on the RIGHT

Why? With E -> E - T, the left operand can itself be a subtraction, so the tree leans to the left: ((8 - 4) - 2). The right operand is a T, which cannot contain a bare -, so 8 - (4 - 2) is impossible without parentheses. Mirror this for right recursion.

Most binary operators (+ - * / and comparisons) are left-associative. The common right-associative ones are exponentiation (2 ^ 3 ^ 2 is 2 ^ 9, not 8 ^ 2), assignment (a = b = 0 assigns to b first) and the conditional ? :. Some operators are non-associative: in Python and in mathematics, a < b < c is special, and some languages simply forbid chaining.

Left recursion in a grammar is perfect for bottom-up parsers but a disaster for simple top-down parsers, which loop forever on it. The next lesson, Eliminating Left Recursion and Left Factoring, shows how to rewrite such rules while keeping the left-associative meaning in the tree.

A grammar built from a precedence table

Since the layering recipe is mechanical, a program can do it. The function build_grammar below takes a list of levels, each with an associativity and a list of operators, and creates the layered grammar. We then use the tree counter from before to prove that the result has exactly one tree for each test sentence. The end of the program shows what associativity changes numerically.

Python Generate a layered grammar from a precedence table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the rule for L2 with the other two levels. Because ^ is right-associative, its recursion is on the right (Atom ^ L2). The last four lines show why it matters: choosing the wrong grouping gives 2 instead of 6 for subtraction, and 64 instead of 512 for exponentiation.

The dangling else

The most famous ambiguity in language design is not about arithmetic at all:

TEXT
S -> if c then S | if c then S else S | x

Consider if c then if c then x else x. The else could belong to the inner if or to the outer one. In C, Java, Python (with blocks) and nearly every language, the rule is: an else pairs with the closest unmatched if. The grammar above does not say that, so it is ambiguous.

The classic fix splits statements into matched (every if has its else) and unmatched ones, and forbids an unmatched statement between an if and its else:

TEXT
S         -> Matched | Unmatched
Matched   -> if c then Matched else Matched | x
Unmatched -> if c then S | if c then Matched else Unmatched

Run the counter on both grammars:

Python Counting parse trees for the dangling else

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only the programs with a nested if and a possible choice for the else are ambiguous in the original grammar. The fixed grammar always has one tree, the one where the else joins the nearest if.

Many languages avoid the problem entirely by requiring braces or an end keyword (if ... end in Ruby, fi in shell, mandatory { } in Go and Rust). Then every if is closed explicitly and there is nothing dangling. Parser generators typically keep the simple ambiguous grammar and resolve the conflict by choosing "shift" (attach the else to the nearest if), which is also the default behavior of hand-written recursive descent.

Is ambiguity detectable in general?

Checking an ambiguous grammar sentence by sentence, as we did, finds ambiguity if you guess a sentence that exposes it. There is no algorithm that decides ambiguity for every grammar: it is undecidable. In practice grammar tools sidestep the question. They check a stricter property, such as "this grammar is LL(1)" or "this grammar has no LR conflicts", which implies unambiguity, and reject the grammar if the check fails.

Some ambiguity cannot be removed by rewriting: a few context-free languages are inherently ambiguous, meaning every grammar for them is ambiguous. Programming languages are designed to avoid such cases.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A grammar is ambiguous when...

    Ambiguity means one sentence can be parsed into two different trees, so its meaning is not determined by the grammar.
  2. 2. How does the layered grammar E -> E + T | T, T -> T * F | F give * higher precedence than +?

    A product can only be an operand of a sum, never the other way round (without parentheses), so multiplications sit deeper in the tree.
  3. 3. Which production makes subtraction left-associative?

    Recursion on the left side, E -> E - T, lets the left operand be another subtraction, so chains group from the left.
  4. 4. In most languages, which pair does an else belong to when the grammar is the dangling-else problem?

    The standard rule attaches an else to the nearest preceding if that has no else yet.
  5. 5. Which of these is a right-associative operator in most languages?

    2 ^ 3 ^ 2 is read as 2 ^ (3 ^ 2) in mathematics and in most languages. Assignment is another right-associative operator.

Summary

  • A grammar is ambiguous when a sentence has two or more parse trees; for a compiler that means the meaning is not defined.
  • Precedence is encoded by layering: one nonterminal per level, each level's operands come from the next tighter level, atoms and parentheses at the bottom.
  • Associativity is the direction of recursion: E -> E - T is left-associative, T -> F ^ T is right-associative.
  • The dangling else is fixed with matched and unmatched statements, or avoided with braces or an explicit end keyword.
  • Counting parse trees with dynamic programming makes ambiguity concrete: a layered grammar gives exactly one.
  • Ambiguity detection is undecidable in general, so tools check stricter properties such as LL(1) or the absence of LR conflicts.

Next: Eliminating Left Recursion and Left Factoring