CFG Derivations, Parse Trees & Ambiguity

Grammars build strings

A context-free grammar (CFG) describes a language by telling you how to build its strings. It has:

Part	Meaning	In the expression grammar
V	variables (non-terminals)	E, T, F
Σ	terminals: the symbols of the strings	id, +, *, (, )
R	rules (productions) of the form A → body	E → E + T, …
S	the start variable	E

Start from S and keep replacing one variable with the body of one of its rules. Every in-between string is a sentential form. When only terminals are left, you have derived a string of the language: S ⇒* w.

Leftmost and rightmost derivations

With E → E + T ∣ T, T → T * F ∣ F, F → ( E ) ∣ id, the string a+b*c (each letter is an id) can be derived in two standard orders:

Step	Leftmost: replace the leftmost variable	Rightmost: replace the rightmost variable
1	E + T	E + T
2	T + T	E + T * F
3	F + T	E + T * c
4	a + T	E + F * c
5	a + T * F	E + b * c
6	a + F * F	T + b * c
7	a + b * F	F + b * c
8	a + b * c	a + b * c

The order is different, but the rules used are the same, so the parse tree is the same. A compiler’s top-down (LL) parser follows leftmost derivations, and a bottom-up (LR) parser finds a rightmost derivation in reverse.

Parse trees

A parse tree records which rule built which part of the string:

• the root is the start variable,
• every inside node is a variable, and its children are the body of the rule used,
• the leaves are terminals or ε,
• reading the leaves from left to right gives the string, called the yield of the tree.

Each parse tree has exactly one leftmost derivation and one rightmost derivation.

Ambiguity

A grammar is ambiguous if some string has two or more parse trees. The simple grammar E → E + E ∣ E * E ∣ ( E ) ∣ id gives a+b*c two trees:

Tree	Grouping	With a = 2, b = 3, c = 4
1	a + (b * c)	14
2	(a + b) * c	20

The string is the same, but the meaning differs. For a compiler that is a disaster, so programming-language grammars are written to be unambiguous.

Removing ambiguity

The usual fix gives each precedence level its own variable:

E → E + T | T        sums of terms
T → T * F | F        products of factors
F → ( E ) | id       a single value or a bracket

Products are built by T, below E, so * always binds tighter than +. The rules are left-recursive (E → E + T), which makes a+b+c group as (a+b)+c: left associativity. Now every string has exactly one tree.

Two warnings:

• Some languages are inherently ambiguous: every grammar for them is ambiguous. A classic example is {aⁱbʲcᵏ ∣ i = j or j = k}.
• No algorithm can decide whether an arbitrary CFG is ambiguous. That question is undecidable.

Code

from functools import lru_cache

GRAMMAR = {'E': [('E', '+', 'E'), ('E', '*', 'E'), ('(', 'E', ')'), ('id',)]}

@lru_cache(maxsize=None)
def trees(sym, toks):
    """How many parse trees let `sym` derive exactly the tokens in `toks`."""
    if sym not in GRAMMAR:                       # a terminal matches one token
        return 1 if toks == (sym,) else 0
    return sum(ways(body, toks) for body in GRAMMAR[sym])

@lru_cache(maxsize=None)
def ways(body, toks):
    """How many ways the symbols of `body` can derive `toks`, one part each."""
    if not body:
        return 1 if not toks else 0
    first, rest = body[0], body[1:]
    return sum(trees(first, toks[:k]) * ways(rest, toks[k:])
               for k in range(1, len(toks) - len(rest) + 1))

tokens = lambda s: tuple('id' if c.isalpha() else c for c in s)
print(trees('E', tokens('a+b*c')))       # 2  -> the grammar is ambiguous
print(trees('E', tokens('a+b+c+d')))     # 5
print(trees('E', tokens('(a+b)*c')))     # 1

This grammar has no ε-rules, so every symbol covers at least one token. That makes the recursion finish. For a fast general parser, convert the grammar to Chomsky normal form and use the CYK algorithm.

Common mistakes

• Thinking leftmost and rightmost derivations give different trees. They only change the order of the steps. Different trees mean ambiguity.
• “Proving” a grammar unambiguous with one example. One string with one tree says nothing about the others.
• Mixing up an ambiguous grammar with an ambiguous language. Most ambiguous grammars can be rewritten. Only inherently ambiguous languages can’t.
• Forgetting ε leaves. A rule A → ε still appears in the tree as a leaf labelled ε.