Context-free grammars and normal forms

Regular languages cannot match nested structure. They cannot check that parentheses balance, that every begin has a matching end, or that the number of as equals the number of bs. Yet nested structure is everywhere: arithmetic expressions, programming language syntax, XML and JSON documents, and the phrase structure of natural language. Context-free grammars describe such structure. CMPUT-415 used them to specify and parse programming languages, with LL and LR parsers. Here we study the class of languages they generate, the context-free languages: how to reason about derivations and ambiguity, how to put grammars into a normal form, and how to decide membership for any context-free grammar with the CYK algorithm.

Grammars and derivations

A context-free grammar (CFG) is a 4-tuple \(G = (V, \Sigma, R, S)\): a finite set V of variables (nonterminals), a finite alphabet \(\Sigma\) of terminals disjoint from V, a finite set R of rules of the form \(A \to \alpha\) with \(A \in V\) and \(\alpha \in (V \cup \Sigma)^*\), and a start variable \(S \in V\). A rule says that the variable A may be replaced by the string \(\alpha\), anywhere it occurs, regardless of what surrounds it; this independence from surroundings is what 'context-free' means. We write \(uAv \Rightarrow u\alpha v\) for one application of a rule and \(\Rightarrow^*\) for zero or more steps. The language of G is \(L(G) = \{w \in \Sigma^* : S \Rightarrow^* w\}\), and a language is context-free if some CFG generates it.

Here is the grammar for \(\{a^n b^n : n \ge 0\}\): \(S \to aSb \mid \varepsilon\). A derivation of aaabbb is \(S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSbbb \Rightarrow aaabbb\). Each step wraps one more a and b around the middle, which is exactly the matching that no finite automaton can perform. Balanced parentheses are generated by \(S \to (S)S \mid \varepsilon\): a balanced string is either empty or an opening parenthesis, a balanced string, its matching closing parenthesis, and another balanced string. The program below generates the shortest strings of this grammar by breadth-first derivation and checks that they are exactly the balanced strings up to length 8.

# Generate the shortest strings of a context-free grammar by breadth-first leftmost derivation.
# Grammar for balanced parentheses: S -> ( S ) S | epsilon   (written "" below)
from collections import deque
G = {"S": [["(", "S", ")", "S"], []]}

def generate(G, start="S", max_len=8, limit=20):
    found, seen = [], set()
    q = deque([(start,)])
    while q and len(found) < limit:
        form = q.popleft()
        if len([s for s in form if s not in G]) > max_len: continue
        i = next((k for k, s in enumerate(form) if s in G), None)
        if i is None:
            w = "".join(form)
            if w not in seen: seen.add(w); found.append(w)
            continue
        for rhs in G[form[i]]:
            q.append(form[:i] + tuple(rhs) + form[i + 1:])
    return found

words = generate(G)
print("first strings derived:", ", ".join(w or "eps" for w in sorted(words, key=lambda w: (len(w), w))[:14]))
# check: every derived string is balanced, and every balanced string up to length 8 is derived
from itertools import product
def balanced(w):
    d = 0
    for c in w:
        d += 1 if c == "(" else -1
        if d < 0: return False
    return d == 0
allb = {"".join(t) for n in range(0, 9, 2) for t in product("()", repeat=n) if balanced("".join(t))}
print("balanced strings up to length 8:", len(allb), " derived:", len(set(generate(G, max_len=8, limit=10**6)) & allb))

first strings derived: eps, (), (()), ()(), ((())), (()()), (())(), ()(()), ()()(), (((()))), ((()())), ((())()), ((()))(), (()(()))
balanced strings up to length 8: 23  derived: 23

Proving that a grammar generates exactly a given language requires two inductions. Soundness, that every derived string is in the language, is usually an induction on the length of the derivation, showing that every sentential form satisfies some invariant. Completeness, that every string in the language can be derived, is an induction on the length of the string, showing how to decompose it according to the rules. For balanced parentheses, completeness uses the first-return decomposition: in a non-empty balanced string, find the position where the opening parenthesis at the start is closed; the part inside and the part after are both balanced and shorter.

Parse trees and ambiguity

A parse tree records the structure of a derivation while forgetting the order in which rules were applied. Its root is S, each internal node is a variable whose children spell out the right side of a rule, and its leaves, read left to right, give the derived string. Many derivations correspond to the same tree; choosing always to expand the leftmost variable gives a canonical leftmost derivation for each tree. A grammar is ambiguous if some string has two different parse trees, equivalently two different leftmost derivations. Ambiguity matters because a compiler uses the tree to assign meaning: the two trees for \(a + a * a\) in the grammar \(E \to E + E \mid E * E \mid a\) correspond to \((a + a) * a\) and \(a + (a * a)\), which evaluate differently.

Ambiguity can often be removed by rewriting the grammar. The layered grammar \(E \to E + T \mid T\), \(T \to T * F \mid F\), \(F \to a \mid (E)\) builds precedence and associativity into its structure: multiplication binds tighter because products are formed at a lower level, and both operators associate to the left because the recursion is on the left. The program below counts parse trees by dynamic programming. In the ambiguous grammar the number of trees for an expression with n operators is the n-th Catalan number, growing roughly like \(4^n\); in the layered grammar every expression has exactly one tree.

# Counting parse trees: E -> E + E | E * E | a is ambiguous; an unambiguous grammar
# with precedence levels gives exactly one tree per string.
from functools import lru_cache

def count_ambiguous(tokens):
    @lru_cache(None)
    def E(i, j):                       # number of trees deriving tokens[i:j] from E
        if j - i == 1: return 1 if tokens[i] == "a" else 0
        total = 0
        for k in range(i + 1, j - 1):
            if tokens[k] in "+*":
                total += E(i, k) * E(k + 1, j)
        return total
    return E(0, len(tokens))

def count_layered(tokens):
    # E -> E + T | T ;  T -> T * F | F ;  F -> a
    @lru_cache(None)
    def F(i, j): return 1 if j - i == 1 and tokens[i] == "a" else 0
    @lru_cache(None)
    def T(i, j): 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 E(i, j): return T(i, j) + sum(E(i, k) * T(k + 1, j) for k in range(i + 1, j - 1) if tokens[k] == "+")
    return E(0, len(tokens))

for expr in ["a", "a+a", "a+a*a", "a+a+a+a", "a*a+a*a+a", "a+a+a+a+a+a+a+a"]:
    t = list(expr)
    print(f"{expr:17s} ambiguous grammar: {count_ambiguous(t):4d} trees   layered grammar: {count_layered(t)}")
print("trees for n operators in the ambiguous grammar are Catalan numbers: 1, 1, 2, 5, 14, 42, 132, 429")

a                 ambiguous grammar:    1 trees   layered grammar: 1
a+a               ambiguous grammar:    1 trees   layered grammar: 1
a+a*a             ambiguous grammar:    2 trees   layered grammar: 1
a+a+a+a           ambiguous grammar:    5 trees   layered grammar: 1
a*a+a*a+a         ambiguous grammar:   14 trees   layered grammar: 1
a+a+a+a+a+a+a+a   ambiguous grammar:  429 trees   layered grammar: 1
trees for n operators in the ambiguous grammar are Catalan numbers: 1, 1, 2, 5, 14, 42, 132, 429

Not every ambiguity can be removed. A context-free language is inherently ambiguous if every grammar for it is ambiguous. The standard example is \(\{a^i b^j c^k : i = j \text{ or } j = k\}\): strings with \(i = j = k\) can be generated both by the part of a grammar that matches as with bs and by the part that matches bs with cs, and a counting argument due to Parikh (1961) shows that every grammar must have two trees for some such strings. Moreover, whether a given grammar is ambiguous is undecidable, as lesson 9 shows. Parser generators sidestep the problem by accepting only grammar classes, such as LL(1) and LALR(1), that are unambiguous by construction, and by letting designers resolve conflicts with precedence declarations.

Chomsky normal form

Many algorithms and proofs are simpler if grammars have a restricted shape. A grammar is in Chomsky normal form (CNF) if every rule has one of the forms \(A \to BC\), where B and C are variables other than the start variable, or \(A \to a\), where a is a terminal; additionally \(S \to \varepsilon\) is allowed when \(\varepsilon \in L\). Theorem. Every context-free language is generated by a grammar in CNF. In a CNF grammar, every parse tree is a binary tree above its leaves, and a string of length \(n \ge 1\) has a derivation of exactly \(2n - 1\) steps: \(n - 1\) uses of binary rules and n uses of terminal rules.

The conversion has five steps, and the order matters. First, add a new start variable \(S_0 \to S\), so the start variable never appears on a right side. Second, eliminate \(\varepsilon\)-rules: find the nullable variables, those that derive \(\varepsilon\), and for each rule add versions with every combination of nullable occurrences deleted; then remove the \(\varepsilon\)-rules, except possibly \(S_0 \to \varepsilon\). Third, eliminate unit rules \(A \to B\) by replacing them with copies of B's rules. Fourth, replace terminals inside long right sides with new variables, such as \(A \to a\). Fifth, break right sides longer than two into chains of binary rules with fresh variables. Each step preserves the language, and the result can be quadratically larger than the original grammar, or worse if the steps are done in a careless order.

The CYK algorithm

Membership in a context-free language is decidable, and CNF makes the algorithm clean. The Cocke–Younger–Kasami (CYK) algorithm, developed independently in the 1960s, uses dynamic programming over substrings. For a string w of length n, let \(T[i, \ell]\) be the set of variables that derive the substring of length \(\ell\) starting at position i. For \(\ell = 1\), \(T[i, 1]\) contains every A with a rule \(A \to w_i\). For longer substrings, A belongs to \(T[i, \ell]\) if there is a rule \(A \to BC\) and a split point k with \(B \in T[i, k]\) and \(C \in T[i + k, \ell - k]\). Then \(w \in L(G)\) exactly when the start variable is in \(T[0, n]\). The table has \(O(n^2)\) entries, each examining \(O(n)\) split points, so the running time is \(O(n^3 |G|)\).

# Chomsky normal form and the CYK algorithm for { a^n b^n : n >= 1 }.
# Original grammar: S -> a S b | a b.  CNF: S -> A X | A B ; X -> S B ; A -> a ; B -> b
CNF = {
    "S": [("A", "X"), ("A", "B")],
    "X": [("S", "B")],
    "A": ["a"],
    "B": ["b"],
}

def cyk(w, G=CNF, start="S"):
    n = len(w)
    T = [[set() for _ in range(n + 1)] for _ in range(n)]    # T[i][l] = variables deriving w[i:i+l]
    for i, c in enumerate(w):
        T[i][1] = {v for v, rules in G.items() for r in rules if r == c}
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            for k in range(1, l):
                for v, rules in G.items():
                    for r in rules:
                        if isinstance(r, tuple) and r[0] in T[i][k] and r[1] in T[i + k][l - k]:
                            T[i][l].add(v)
    return start in T[0][n], T

ok, T = cyk("aaabbb")
print("table for aaabbb (row = substring length, column = start position):")
for l in range(6, 0, -1):
    print(f"  len {l}: " + "  ".join(f"{''.join(sorted(T[i][l])) or '-':3s}" for i in range(6 - l + 1)))
print("accepted:", ok)
for w in ["ab", "aabb", "aab", "abab", "aaaabbbb", "ba"]:
    print(f"  {w:9s} {cyk(w)[0]}")

table for aaabbb (row = substring length, column = start position):
  len 6: S  
  len 5: -    X  
  len 4: -    S    -  
  len 3: -    -    X    -  
  len 2: -    -    S    -    -  
  len 1: A    A    A    B    B    B  
accepted: True
  ab        True
  aabb      True
  aab       False
  abab      False
  aaaabbbb  True
  ba        False

Cubic time is too slow for compiling large programs, which is why compilers restrict themselves to grammar classes that admit linear-time parsing, as in CMPUT-415. But CYK and its relatives, such as Earley's algorithm, handle any context-free grammar, including ambiguous ones, and they matter wherever grammars are not designed for easy parsing: in natural language processing, in parsing RNA secondary structure in bioinformatics, and in grammar-based testing tools. Valiant showed in 1975 that general CFG parsing can be done as fast as Boolean matrix multiplication, about \(O(n^{2.37})\) with current algorithms, and later work showed that substantially faster general parsing would imply faster matrix multiplication, so cubic-like time is close to the truth for arbitrary grammars.

Worked examples