Context-Free Grammar and Pushdown Automata — Parse Trees, Ambiguity, CYK

Regular languages can't count or nest. Programming languages are full of nesting — brackets inside brackets, blocks inside blocks, expressions inside expressions. Context-free grammars (CFGs) describe exactly this kind of structure, and every compiler's parser is built on one.

1. Context-free grammars

G = (V, Σ, R, S): variables (non-terminals), terminals (the alphabet), rules of the form A → string of variables/terminals, and a start variable S.

aⁿbⁿ:

S → a S b | ε

Derivation of aabb: S ⇒ aSb ⇒ aaSbb ⇒ aabb.

Balanced brackets:

S → ( S ) S | ε

Arithmetic expressions with precedence (the shape of every language spec):

E → E + T | T          (sum of terms)
T → T * F | F          (product of factors)
F → ( E ) | id         (atoms)

Because * lives one level deeper than +, id + id * id can only be parsed as id + (id * id).

2. Derivations and parse trees

A parse tree shows how the start symbol derives a string: internal nodes are variables, leaves (left to right) spell the string.

Leftmost derivation: always expand the leftmost variable. Each parse tree corresponds to exactly one leftmost derivation.

3. Ambiguity

A grammar is ambiguous if some string has two different parse trees. The naive expression grammar E → E + E | E * E | id is ambiguous: id + id * id can group either way — which would make 2 + 3 * 4 evaluate to 14 or 20. Let's count parse trees by brute force:

from functools import lru_cache

tokens = ["id", "+", "id", "*", "id"]

@lru_cache(None)
def trees_ambiguous(i, j):          # E -> E + E | E * E | id   over tokens[i:j]
    if j - i == 1:
        return 1 if tokens[i] == "id" else 0
    total = 0
    for k in range(i + 1, j - 1):
        if tokens[k] in "+*":
            total += trees_ambiguous(i, k) * trees_ambiguous(k + 1, j)
    return total

@lru_cache(None)
def E(i, j):                        # E -> E + T | T
    return T(i, j) + sum(E(i, k) * T(k + 1, j) for k in range(i + 1, j - 1) if tokens[k] == "+")

@lru_cache(None)
def T(i, j):                        # T -> T * F | F
    return F(i, j) + sum(T(i, k) * F(k + 1, j) for k in range(i + 1, j - 1) if tokens[k] == "*")

@lru_cache(None)
def F(i, j):                        # F -> id
    return 1 if j - i == 1 and tokens[i] == "id" else 0

print("ambiguous grammar: parse trees for id+id*id =", trees_ambiguous(0, len(tokens)))
print("precedence grammar: parse trees for id+id*id =", E(0, len(tokens)))

ambiguous grammar: parse trees for id+id*id = 2
precedence grammar: parse trees for id+id*id = 1

The precedence grammar has exactly one tree — unambiguous. (Deciding whether an arbitrary CFG is ambiguous is undecidable, and some context-free languages are inherently ambiguous, but practical grammars are designed to avoid it.) The famous dangling else — if a then if b then s1 else s2 — is the same problem; languages resolve it with a rule: else matches the nearest if.

4. Chomsky Normal Form and CYK

Chomsky Normal Form (CNF): every rule is A → BC or A → a (plus S → ε if needed). Any CFG can be converted. CNF makes parse trees binary, which gives:

a derivation of a string of length n takes exactly 2n − 1 steps;
the CYK algorithm decides membership in O(n³) using dynamic programming.

CNF for aⁿbⁿ (n ≥ 1): S → AB | AX, X → SB, A → a, B → b.

from itertools import product

cnf = {"S": [("A", "B"), ("A", "X")], "X": [("S", "B")], "A": ["a"], "B": ["b"]}

def cyk(w):
    n = len(w)
    table = [[set() for _ in range(n)] for _ in range(n)]
    for i, ch in enumerate(w):
        table[i][i] = {v for v, rules in cnf.items() if ch in rules}
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                for v, rules in cnf.items():
                    for r in rules:
                        if isinstance(r, tuple) and r[0] in table[i][k] and r[1] in table[k + 1][j]:
                            table[i][j].add(v)
    return "S" in table[0][n - 1]

for w in ["ab", "aabb", "aaabbb", "aab", "abab", "ba"]:
    print(f"{w:7} {cyk(w)}")
ok = all(cyk(w) == (w == "a" * (len(w) // 2) + "b" * (len(w) // 2))
         for n in range(2, 11, 1) for w in ("".join(t) for t in product("ab", repeat=n)))
print("CYK agrees with a^n b^n (n>=1) on all strings of length 2..10:", ok)

ab      True
aabb    True
aaabbb  True
aab     False
abab    False
ba      False
CYK agrees with a^n b^n (n>=1) on all strings of length 2..10: True

5. Pushdown automata (PDA)

A PDA = finite automaton + a stack. Each move reads an input symbol (or ε), pops the top of the stack, and pushes a string. The stack is exactly what's needed to match nested structure.

PDA idea for aⁿbⁿ: push an A for every a; on each b pop an A; accept if the input ends exactly when the stack is empty again.

def pda_anbn(w, trace=False):
    stack, state = ["$"], "push"
    for ch in w:
        if state == "push" and ch == "a":
            stack.append("A")
        elif ch == "b" and stack[-1] == "A":
            state = "pop"
            stack.pop()
        else:
            return False                     # no valid move: reject
        if trace:
            print(f"  read {ch}  state={state:4}  stack={''.join(stack)}")
    return stack == ["$"]

print("aaabbb:"); print("accepted:", pda_anbn("aaabbb", trace=True))
print([(w, pda_anbn(w)) for w in ["", "ab", "aabbb", "abab", "aaabbb"]])

aaabbb:
  read a  state=push  stack=$A
  read a  state=push  stack=$AA
  read a  state=push  stack=$AAA
  read b  state=pop   stack=$AA
  read b  state=pop   stack=$A
  read b  state=pop   stack=$
accepted: True
[('', True), ('ab', True), ('aabbb', False), ('abab', False), ('aaabbb', True)]

Balanced brackets with several bracket types — the same idea, used in every code editor and compiler:

def balanced(s):
    pairs, stack = {")": "(", "]": "[", "}": "{"}, []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for s in ["{[()()]}", "([)]", "((()", "for (i = 0; i < n; i++) { a[i] = (b[i] + c); }"]:
    print(f"{s:45} {balanced(s)}")

{[()()]}                                      True
([)]                                          False
((()                                          False
for (i = 0; i < n; i++) { a[i] = (b[i] + c); } True

6. Facts for exams

CFG ⇔ PDA (nondeterministic) — same languages.
Deterministic PDAs are weaker than nondeterministic ones (e.g. even-length palindromes need nondeterminism to "guess the middle") — unlike DFA = NFA. Most programming languages are designed to be parsed deterministically (LL/LR parsers).
CFLs are closed under union, concatenation, star but not under intersection or complement. (aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ, which is not context-free.)
Pumping lemma for CFLs (s = uvxyz, pump v and y together) shows aⁿbⁿcⁿ and {ww} are not context-free.

Common mistakes

Thinking an unambiguous grammar exists for every CFL (some are inherently ambiguous).
Assuming deterministic and nondeterministic PDAs are equally powerful.
Claiming CFLs are closed under intersection.
Forgetting the bottom-of-stack marker $ when designing PDAs.

Quick recap

CFG rules A → …; derivations and parse trees; leftmost derivation ↔ parse tree.
Ambiguous = two parse trees for one string; fix with precedence levels (E/T/F).
CNF: A → BC | a; CYK decides membership in O(n³).
PDA = FA + stack; CFG ⇔ NPDA; DPDA weaker.
CFLs closed under ∪, concatenation, *; not under ∩ or complement.

Context-Free Grammars and Pushdown Automata — Derivations, Parse Trees, Ambiguity, CNF, CYK and Stack Machines