Lesson 4.4 — CYK and GLL: general parsing bottom-up by spans and top-down with a graph stack¶

Techniques: Chomsky normal form and the Cocke–Younger–Kasami algorithm (Kasami 1965; Younger 1967), with Valiant's sub-cubic reduction (1975) as a variant; generalized LL parsing (Scott & Johnstone 2010) · Pebble implements: nothing in pebblec; CYK and GLL are theory + drills + oracle (tools/course/lib/exprparse.py) · Prerequisites: Lesson 4.3, Lesson 3.6 (GSS, GLR) · Time: 2.5 hours

Earley's algorithm reads the input left to right and predicts what may come. Two other general algorithms answer the same question differently. CYK forgets about direction: it computes, for every span of the input, which nonterminals derive it, filling a triangular table bottom-up — the simplest correct general parser, and the one with the cleanest complexity theory. GLL keeps the recursive-descent shape (one "procedure" per nonterminal) and makes it general by replacing the call stack with a graph-structured stack, as GLR did for LR in Lesson 3.6.

1. Problem and motivation¶

The problem. As in Lesson 4.3: decide \(w \in L(G)\) for an arbitrary CFG (and produce the parse trees), here with (a) an algorithm whose correctness and cost are easy to establish and that reduces to matrix multiplication, and (b) a general algorithm that keeps the structure, debuggability and hand-writability of recursive descent.

CYK¶

Tadao Kasami (1965, an Air Force report [Kas65]) and Daniel Younger (1967 [You67]) independently showed that every CFG in Chomsky normal form can be recognized in \(O(n^3)\) time by dynamic programming over spans (John Cocke's name is attached through an unpublished program). It is the textbook proof that CFL membership is polynomial [HMU07 §7.4], the basis of probabilistic parsing in natural-language processing (the CKY/inside algorithm), and — via Valiant [Val75] — the link between parsing and Boolean matrix multiplication.

GLL¶

A recursive-descent parser fails on left recursion and commits on the first alternative; backtracking fixes the second and not the first, at exponential cost (Lesson 2.5). Elizabeth Scott and Adrian Johnstone's generalized LL [SJ10] runs all alternatives "in parallel" as descriptors, shares call stacks in a graph-structured stack (GSS) so that each (return point, input position) exists once, and handles left recursion because a recursive call to the same nonterminal at the same position just adds an edge to an existing GSS node. The result is cubic and general, and the generated code still looks like recursive descent.

2. Definitions and algorithms¶

CYK¶

Definition 4.4.1 (Chomsky normal form)

A CFG is in Chomsky normal form (CNF) if every production is \(A \to B\,C\) (\(B, C \in N\)), \(A \to a\) (\(a \in T\)), or \(S \to \varepsilon\) where the start symbol \(S\) occurs on no right-hand side. For \(w = t_1 \cdots t_n\), the CYK table is \(V[i, \ell] \triangleq \{\, A \in N \mid A \Rightarrow^{*} t_i \cdots t_{i+\ell-1} \,\}\) for \(1 \le i\) and \(i + \ell - 1 \le n\) (1-based start \(i\), length \(\ell\)).

Algorithm 4.4.2 (Conversion to CNF)

Input: a CFG \(G\).
Output: a CNF grammar \(G'\) with \(L(G') = L(G)\).
Precondition: none (every CFG).
Postcondition: Theorem 4.4.6; \(\lvert G' \rvert = O(\lvert G \rvert^2)\).
Invariant: each step preserves the language; after step \(k\), the property established by steps \(1..k\) holds (a fresh start symbol; no terminals in long right sides; right sides of length \(\le 2\); no ε except at the start; no unit productions).

function ToCNF(G):
    START: if S occurs on a right-hand side: add S0 → S and make S0 the start
    TERM:  for each terminal a inside a right-hand side of length ≥ 2:
               use a fresh U_a with U_a → a in its place
    BIN:   replace A → X1 X2 … Xm (m ≥ 3) by A → X1 Y1, Y1 → X2 Y2, …, Y(m-2) → X(m-1) Xm
    DEL:   N0 ← Nullable(G)
           for each A → α: add every variant of α with some N0 symbols omitted (not all of α,
               unless A is the start); then delete every A → ε except S0 → ε
    UNIT:  for each A, the unit closure U(A) ← { B | A ⇒* B by unit productions }
           replace unit productions: A → β for every B ∈ U(A) and non-unit B → β
    remove non-generating and unreachable nonterminals
    return the result

Algorithm 4.4.3 (CYK recognition)

Input: a CNF grammar \(G\), tokens \(t_1 \cdots t_n\) (\(n \ge 1\); the empty string is in \(L(G)\) iff \(S \to \varepsilon \in P\)).
Output: the table \(V\); accept iff \(S \in V[1, n]\).
Precondition: \(G\) in CNF.
Postcondition: \(V[i, \ell]\) is exactly the set of Definition 4.4.1 (Theorem 4.4.7).
Invariant: before length \(\ell\) is processed, every \(V[i, \ell']\) with \(\ell' < \ell\) is final.

function CYK(G, t1 … tn):
    for i in 1 … n:   V[i, 1] ← { A | A → t_i ∈ P }
    for ℓ in 2 … n:                         # span length
        for i in 1 … n − ℓ + 1:             # span start
            V[i, ℓ] ← ∅
            for s in 1 … ℓ − 1:             # split: left part has length s
                for each A → B C in P:
                    if B ∈ V[i, s] and C ∈ V[i + s, ℓ − s]:  V[i, ℓ] ← V[i, ℓ] ∪ {A}
    return S ∈ V[1, n]

Replacing sets by counts (\(\#[i, \ell, A] = \sum_{s} \sum_{A \to B C} \#[i, s, B] \cdot \#[i+s, \ell-s, C]\)) counts parse trees; replacing them by probabilities gives the inside algorithm of probabilistic CFGs.

Lark's CYK parser agrees with its Earley and LALR parsers

Reproduce (Lark 1.3.1, Python 3.11.15):

python3.11 -m venv venv && . venv/bin/activate && pip install -q lark==1.3.1
cat > lark_cyk.py <<'EOF'
from lark import Lark
g = r"""
    e: e "+" t | t
    t: t "*" f | f
    f: "(" e ")" | NUMBER
    %import common.NUMBER
    %ignore " "
"""
for algo in ("earley", "cyk", "lalr"):
    print(algo, Lark(g, start="e", parser=algo).parse("1 + 2 * 3"))
EOF
python lark_cyk.py

Output (complete):

earley Tree(Token('RULE', 'e'), [Tree(Token('RULE', 'e'), [Tree(Token('RULE', 't'), [Tree(Token('RULE', 'f'), [Token('NUMBER', '1')])])]), Tree(Token('RULE', 't'), [Tree(Token('RULE', 't'), [Tree(Token('RULE', 'f'), [Token('NUMBER', '2')])]), Tree(Token('RULE', 'f'), [Token('NUMBER', '3')])])])
cyk Tree(Token('RULE', 'e'), [Tree(Token('RULE', 'e'), [Tree(Token('RULE', 't'), [Tree(Token('RULE', 'f'), [Token('NUMBER', '1')])])]), Tree(Token('RULE', 't'), [Tree(Token('RULE', 't'), [Tree(Token('RULE', 'f'), [Token('NUMBER', '2')])]), Tree(Token('RULE', 'f'), [Token('NUMBER', '3')])])])
lalr Tree(Token('RULE', 'e'), [Tree(Token('RULE', 'e'), [Tree(Token('RULE', 't'), [Tree(Token('RULE', 'f'), [Token('NUMBER', '1')])])]), Tree(Token('RULE', 't'), [Tree(Token('RULE', 't'), [Tree(Token('RULE', 'f'), [Token('NUMBER', '2')])]), Tree(Token('RULE', 'f'), [Token('NUMBER', '3')])])])

What to notice: three paradigms, one tree. lark/parsers/cyk.py [LARK-CYK] converts the grammar to CNF (to_cnf is _unit(_bin(_term(g))): the TERM, BIN and UNIT steps of Algorithm 4.4.2), fills the span table of Algorithm 4.4.3 in _parse, and then revert_cnf removes the __T_ and __SP_ helper nonterminals, so the tree it returns is over the original rules e, t, f. Lark documents CYK as \(O(n^3 \lvert G \rvert)\) [LARK-Docs].

GLL¶

Definition 4.4.4 (Grammar slots, GSS, descriptors)

A grammar slot is a production with a dot, written \(X ::= \alpha \cdot \beta\). The graph-structured stack (GSS) has a root \(u_0\) and nodes \(\langle L, j \rangle\), where \(L = X ::= \alpha B \cdot \beta\) is the return slot after a call of \(B\) and \(j\) the input position where that call started; an edge \(\langle L, j \rangle \to u\) means "when \(B\) returns, continue at \(L\) with stack \(u\)". A descriptor \((L, u, i)\) is a unit of work: continue at slot \(L\) with stack top \(u\) at input position \(i\). \(\mathcal{U}_i\) is the set of descriptors ever created for position \(i\) (each is processed once), and \(\mathcal{P}\) the set of pairs \((u, i)\) such that the node \(u\) has been popped at \(i\) (a call it represents returned at \(i\)).

Algorithm 4.4.5 (GLL recognition, grammar-interpreting form)

Input: a CFG \(G\) (any: left-recursive, ambiguous, with ε), tokens \(t_1 \cdots t_n\).
Output: accept iff \(w \in L(G)\).
Precondition: none.
Postcondition: accepts iff \(S \Rightarrow^{*} w\) (Theorem 4.4.8).
Invariant: for every processed descriptor \((X ::= \alpha \cdot \beta, u, i)\) there is a derivation of the input up to position \(i\) consistent with the GSS path from \(u\); every pair (GSS node, position) at which a call returns is in \(\mathcal{P}\), and every edge into a popped node has been served for every recorded return position (the create loop).

function GLL(G, t1 … tn):
    for each S ::= γ:  Add(S ::= · γ, u0, 0)
    while R is not empty:
        (X ::= α · β, u, i) ← remove the first descriptor of R
        loop:                                        # run the "procedure body" from this slot
            if β = ε:  Pop(u, i);  break                           # X returns at i
            s ← first symbol of β
            if s is a terminal:
                if i < n and t(i+1) = s:  advance the slot over s;  i ← i + 1;  continue
                break                                               # this thread dies
            v ← Create(X ::= α s · β', u, i)                        # call s: push a return slot
            for each s ::= γ:  Add(s ::= · γ, v, i)
            break
    accept iff Pop(u0, n) happened

function Add(L, u, i):   if (L, u) ∉ U_i: insert into U_i;  append (L, u, i) to R
function Create(L, u, i):
    v ← GSS node ⟨L, i⟩ (create it if new)
    if the edge v → u is new:
        add it;  for each (v, k) ∈ P:  Add(L, u, k)           # v already returned at k: serve u too
    return v
function Pop(u, k):
    if u = u0:  record "accept" if k = n;  return
    insert (u, k) into P
    for each edge u → w:  Add(label(u), w, k)                # return to every caller

Scott and Johnstone's generated parsers [SJ10] compile each slot to a labelled code block and filter alternatives with FIRST/FOLLOW tests before Add; the interpreter above omits the tests (they change performance, not the result).

GLL returns every parse of an ambiguous, left-recursive grammar

Reproduce (gll-pg 0.5.0 and logos 0.11.4 from crates.io, rustc/cargo 1.94.1; gll-pg's proc macro uses an unstable feature, hence RUSTC_BOOTSTRAP=1):

cargo new -q gllt && cd gllt
printf 'gll-pg-core = "0.5"\ngll-pg-macros = "0.5"\nlogos = "0.11.4"\n' >> Cargo.toml
cat > src/main.rs <<'EOF'
use gll_pg_core::*;
use gll_pg_macros::gll;
use logos::Logos;

#[derive(Logos, Debug, Eq, PartialEq, Clone)]
pub enum Token {
    End, // required by gll-pg
    #[error]
    Error,
    #[token(" ")]
    _Eps, // required by gll-pg: skipped
    #[token("+")]
    Add,
    #[token("*")]
    Mul,
    #[regex("[0-9]+")]
    Int,
}

struct Parser {}

#[gll(E, Token)]
impl Parser {
    #[rule(E -> E Add E)]
    fn add(l: &String, _o: &LogosToken<Token>, r: &String) -> String { format!("(+ {l} {r})") }
    #[rule(E -> E Mul E)]
    fn mul(l: &String, _o: &LogosToken<Token>, r: &String) -> String { format!("(* {l} {r})") }
    #[rule(E -> Int)]
    fn int(i: &LogosToken<Token>) -> String { i.slice.to_string() }
}

fn main() {
    for input in ["1 + 2 * 3", "1 + 2 + 3 + 4"] {
        let mut lexer = Token::lexer(input);
        let mut parser = Parser {};
        let trees: Vec<String> = parser.parse(&mut lexer).unwrap().cloned().collect();
        println!("{input:?}: {} parse(s)", trees.len());
        for t in trees { println!("  {t}"); }
    }
}
EOF
RUSTC_BOOTSTRAP=1 cargo run -q 2>/dev/null

Output (complete):

"1 + 2 * 3": 2 parse(s)
  (* (+ 1 2) 3)
  (+ 1 (* 2 3))
"1 + 2 + 3 + 4": 5 parse(s)
  (+ 1 (+ 2 (+ 3 4)))
  (+ 1 (+ (+ 2 3) 4))
  (+ (+ 1 (+ 2 3)) 4)
  (+ (+ (+ 1 2) 3) 4)
  (+ (+ 1 2) (+ 3 4))

What to notice: the grammar is both left- and right-recursive and ambiguous; a recursive-descent parser would loop on it. gll-pg generates a GLL parser with a GSS and an SPPF and enumerates the trees from the forest: the Catalan numbers \(C_2 = 2\) and \(C_3 = 5\) of Lesson 4.3 §5. gll-pg is a small research-grade crate (2020), not a production front end; production GLL use is mostly in grammar engineering (Iguana, the Rascal meta-programming language).

3. Worked examples¶

CYK¶

The grammar is Hopcroft and Ullman's CNF example [HMU07 §7.4]:

\[ \begin{aligned} S &\to A\,B \mid B\,C \qquad & A &\to B\,A \mid a \\ B &\to C\,C \mid b & C &\to A\,B \mid a \end{aligned} \]

and the input is \(w = b\,a\,a\,b\,a\). Every rule that fires, in the order Algorithm 4.4.3 finds it (26 firings, generated by the oracle):

cell	splits that fire (s: rule)	\(V[i, \ell]\)
V[1,1] … V[5,1]	`b`: B → b; `a`: A → a, C → a	{B}, {A, C}, {A, C}, {B}, {A, C}
V[1,2] = `b a`	s=1: S → B C, A → B A	{A, S}
V[2,2] = `a a`	s=1: B → C C	{B}
V[3,2] = `a b`	s=1: S → A B, C → A B	{C, S}
V[4,2] = `b a`	s=1: S → B C, A → B A	{A, S}
V[1,3] = `b a a`	s=1: V[1,1]·V[2,2] = {B}·{B}: no rule; s=2: {A,S}·{A,C}: no rule	{}
V[2,3] = `a a b`	s=1: {A,C}·{C,S}: B → C C; s=2: {B}·{B}: none	{B}
V[3,3] = `a b a`	s=1: {A,C}·{A,S}: none; s=2: {C,S}·{A,C}: B → C C	{B}
V[1,4] = `b a a b`	s=1: {B}·{B}; s=2: {A,S}·{C,S}; s=3: {}·{B}: none	{}
V[2,4] = `a a b a`	s=1: {A,C}·{B}: S → A B, C → A B; s=2: {B}·{A,S}: A → B A; s=3: {B}·{A,C}: S → B C, A → B A	{A, C, S}
V[1,5] = `b a a b a`	s=1: {B}·{A,C,S}: S → B C, A → B A; s=2: {A,S}·{B}: S → A B, C → A B; s=3, s=4: none	{A, C, S}

The table, row \(\ell\) (length) from the top, column \(i\) (start):

\(\ell\) \(i\)	1	2	3	4	5
5	{A, C, S}
4	{}	{A, C, S}
3	{}	{B}	{B}
2	{A, S}	{B}	{C, S}	{A, S}
1	{B}	{A, C}	{A, C}	{B}	{A, C}
token	b	a	a	b	a

\(S \in V[1, 5]\): accepted. Converting a non-CNF grammar first: the running expression grammar \(E \to E + T \mid T\), \(T \to T * F \mid F\), \(F \to (\,E\,) \mid n\) becomes (START, TERM, BIN, DEL, UNIT; fresh names \(E0\), \(U_1 \dots U_4\), \(X_1 \dots X_3\)):

E0 → E X1 | T X2 | U3 X3 | n        E → E X1 | T X2 | U3 X3 | n
T  → T X2 | U3 X3 | n               F → U3 X3 | n
U1 → +    U2 → *    U3 → (    U4 → )
X1 → U1 T     X2 → U2 F     X3 → E U4

(UNIT copied the non-unit productions of \(T\) and \(F\) into \(E0\) and \(E\); ./course drill cyk-table --difficulty hard prints such conversions.)

Try it

./course drill cyk-table --seed 1 --difficulty medium --solution; --difficulty hard converts an ambiguous grammar and asks for the number of parse trees.

GLL¶

Grammar \(S \to S\,a \mid a\) (left-recursive), input \(a\,a\). Descriptors are processed first-in first-out (generated by the oracle):

step	descriptor \((L, u, i)\)	action
1	(S ::= · S a, u0, 0)	call S: edge ⟨S ::= S · a, 0⟩ → u0; add 2 descriptors
2	(S ::= · a, u0, 0)	match `a`; slot complete at 1: pop u0 at 1 (not the end: no accept)
3	(S ::= · S a, ⟨S ::= S · a, 0⟩, 0)	call S at 0 again: the node ⟨S ::= S · a, 0⟩ already exists; new edge to itself; add 2 descriptors
4	(S ::= · a, ⟨S ::= S · a, 0⟩, 0)	match `a`; pop ⟨S ::= S · a, 0⟩ at 1: \(\mathcal{P}\) ∋ (node, 1); return along both edges: add (S ::= S · a, u0, 1) and (S ::= S · a, ⟨…⟩, 1)
5	(S ::= S · a, ⟨S ::= S · a, 0⟩, 1)	match `a`; pop ⟨S ::= S · a, 0⟩ at 2: add (S ::= S · a, u0, 2) and (S ::= S · a, ⟨…⟩, 2)
6	(S ::= S · a, u0, 1)	match `a`; pop u0 at 2 = n: accept
7	(S ::= S · a, ⟨S ::= S · a, 0⟩, 2)	`a` does not match at 2: drop
8	(S ::= S · a, u0, 2)	`a` does not match at 2: drop

The left-recursive call at step 3 creates no new node: the self-loop edge is the whole cost of left recursion, and the pop at step 4 returns both to the outer caller (u0) and to the recursive caller (the self-loop), which is how the loop "grows" \(S\,a\), \(S\,a\,a\), …
8 descriptors, 2 GSS nodes (u0 and ⟨S ::= S · a, 0⟩), 2 edges.

4. Invariants and correctness¶

Theorem 4.4.6 (CNF conversion preserves the language)

Algorithm 4.4.2 returns a CNF grammar \(G'\) with \(L(G') = L(G)\).

Proof sketch (full proof: [HMU07 §7.1.5, Theorem 7.16])

Each step preserves the language. START: \(S_0 \to S\) adds nothing. TERM and BIN: the new nonterminals have single productions, so any derivation in the new grammar can be contracted to one in the old and vice versa. DEL: a derivation in \(G\) that derives ε from some nullable occurrences corresponds to the variant of the production with those occurrences omitted, and conversely every variant is simulated by deriving ε from the omitted symbols; only \(S_0 \to \varepsilon\) is kept, so \(\varepsilon \in L\) is preserved. UNIT: a derivation using a chain of unit productions \(A \Rightarrow B_1 \Rightarrow \cdots \Rightarrow B_m \Rightarrow \beta\) is replaced by \(A \to \beta\), which is added exactly because \(B_m \in U(A)\). Removing useless symbols does not change the language. After all steps every production is \(A \to BC\), \(A \to a\) or \(S_0 \to \varepsilon\). The order matters: DEL before UNIT (deletion creates unit productions), and TERM and BIN before DEL keep the right-hand sides short so DEL adds at most 3 variants per production.

Theorem 4.4.7 (CYK is correct)

For a CNF grammar, Algorithm 4.4.3 computes \(V[i, \ell] = \{\, A \mid A \Rightarrow^{*} t_i \cdots t_{i+\ell-1} \,\}\) for all \(i, \ell\); hence it accepts iff \(w \in L(G)\) (for \(n \ge 1\)).

Proof

By induction on \(\ell\). \(\ell = 1\): in CNF a nonterminal derives a single token \(a\) only by a production \(A \to a\) (a derivation starting with \(A \to BC\) yields at least two tokens, because in CNF no nonterminal other than the start derives ε and the start occurs on no right side). \(\ell \ge 2\): (\(\supseteq\)) if \(A \to BC\) with \(B \in V[i, s]\), \(C \in V[i+s, \ell-s]\), then by the induction hypothesis \(B \Rightarrow^{*} t_i \cdots t_{i+s-1}\) and \(C \Rightarrow^{*} t_{i+s} \cdots t_{i+\ell-1}\), so \(A\) derives the span. (\(\subseteq\)) if \(A \Rightarrow^{*}\) the span with \(\ell \ge 2\), the first step must be some \(A \to BC\) (not \(A \to a\), which yields one token); \(B\) and \(C\) derive nonempty consecutive pieces of lengths \(s\) and \(\ell - s\) with \(1 \le s \le \ell - 1\), which are in \(V\) by the induction hypothesis (both lengths \(< \ell\) and final by the invariant); the loop tries that split and that production.

Theorem 4.4.8 (GLL recognizes exactly L(G))

For every CFG \(G\) and input \(w\), Algorithm 4.4.5 terminates and accepts iff \(S \Rightarrow^{*} w\).

Proof sketch (full proof: [SJ10, §3–4]; the GSS is the same as GLR's, Lesson 3.6)

Termination: descriptors are triples of a slot, a GSS node and a position, GSS nodes are pairs of a slot and a position, and \(\mathcal{U}_i\) forbids repeats, so finitely many descriptors are processed, each doing bounded work plus a loop over edges or \(\mathcal{P}\). Soundness: by induction on the order of processing, a descriptor \((X ::= \alpha \cdot \beta, u, i)\) means \(\alpha\) derives the tokens between the position where \(u\)'s top call started and \(i\), and following any GSS path from \(u\) to \(u_0\) spells a valid stack of pending return slots, each consistent with the input before it; a pop of \(u_0\) at \(n\) therefore witnesses \(S \Rightarrow^{*} w\). Completeness: consider a leftmost derivation of \(w\) and the sequence of (call, return) events a naive recursive-descent parser would perform along it; induction on that sequence shows each event is matched by a descriptor. The only subtle case is a call to a nonterminal whose GSS node already exists and has already returned at some positions: Create then adds the missing descriptors from \(\mathcal{P}\) (the "contingent returns" of step 3 in §3), so no return is lost, and left recursion is a self-loop edge rather than an infinite descent.

5. Complexity¶

Let \(n\) be the input length, \(\lvert G \rvert\) the grammar size, \(\lvert P \rvert\) the number of productions and \(\omega < 2.372\) the exponent of Boolean matrix multiplication.

Proposition 4.4.9 (CYK's cost)

Algorithm 4.4.3 runs in \(\Theta(n^3 \lvert P \rvert)\) time and \(\Theta(n^2 \lvert N \rvert)\) space, on every input (best case = worst case). Algorithm 4.4.2 produces a grammar of size \(O(\lvert G \rvert^2)\) in the worst case (UNIT can copy every production to every nonterminal), \(O(\lvert G \rvert)\) without unit chains.

Proof

The three nested loops over \(\ell\), \(i\), \(s\) run \(\sum_{\ell=2}^{n} (n - \ell + 1)(\ell - 1) = \binom{n+1}{3} = \Theta(n^3)\) times, each scanning the binary productions: \(\Theta(n^3 \lvert P \rvert)\) with sets as bit vectors (constant-time membership). No early exit exists, so the best case is the same. The table has \(n(n+1)/2\) cells of at most \(\lvert N \rvert\) bits. For the grammar size: DEL multiplies each production (length \(\le 2\) after BIN) by at most 3; UNIT adds, for each of the \(\lvert N \rvert\) nonterminals, copies of the non-unit productions of the nonterminals in its unit closure: at most \(\lvert N \rvert \cdot \lvert P \rvert\).

Theorem 4.4.10 (Valiant: CFL recognition in matrix-multiplication time)

Every CNF grammar can be recognized in \(O(\lvert G \rvert\, M(n))\) time, where \(M(n) = O(n^{\omega})\) is the time to multiply two \(n \times n\) Boolean matrices; conversely (Lee 2002), a parser that runs in \(O(\lvert G \rvert\, n^{3-\epsilon})\) time for every grammar yields Boolean matrix multiplication in \(O(m^{3 - \epsilon/3})\) time.

Proof sketch (full proofs: [Val75]; converse [Lee02])

CYK's table satisfies the "transitive closure" equation \(V = V \cdot V\) over the semiring whose product of two cells is \(\{ A \mid A \to BC, B \in x, C \in y \}\) and whose sum is union. Valiant shows that this non-associative closure can still be computed by divide and conquer on the table with a constant number of matrix products per level of recursion (splitting the span range in halves), each product being reduced to \(\lvert N \rvert^2\) Boolean matrix multiplications, which gives \(O(M(n))\) per level and a geometric sum overall. Lee reduces Boolean matrix multiplication to parsing a grammar that encodes the matrix entries, so no parser can beat BMM by a polynomial factor.

Theorem 4.4.11 (GLL is cubic)

Algorithm 4.4.5 runs in \(O(n^3)\) time and \(O(n^2)\) space for a fixed grammar (with the binarized SPPF of Definition 4.3.7 for parsing, \(O(n^3)\) space).

Proof sketch (full proof: [SJ10, §5])

There are \(O(n)\) GSS nodes (a return slot and a position), hence \(O(n^2)\) edges; descriptors are (slot, node, position): \(O(n^2)\), each processed once with \(O(1)\) work besides pops and creates. A pop of a node at position \(k\) walks its \(O(n)\) out-edges, and a node is popped at most once per position: \(O(n)\) nodes \(\times\) \(O(n)\) positions \(\times\) \(O(n)\) edges \(= O(n^3)\). Create's loop over \(\mathcal{P}\) is charged the same way.

Pathological inputs. CYK is \(\Theta(n^3)\) on every input, including trivial ones: it never uses the left context, so on the deterministic expression grammar where Earley and Pratt are linear it still fills \(n^2/2\) cells (\(n = 1000\): 166 million (span, split) pairs). GLL is cubic on highly ambiguous grammars: for \(E \to E + E \mid n\), the oracle's descriptor counts grow quadratically for the recognizer (16, 30, 48, 70 descriptors for 1–4 +), and the SPPF needed for parsing has \(\Theta(n^3)\) packed nodes.

At scale. For NLP-sized inputs (sentences of 20–60 words) cubic is fine; for source files of \(10^5\) tokens it is not (\(10^{15}\) steps), which is why no compiler for a mainstream language parses with CYK. Valiant's algorithm is of theoretical interest: its constants make it slower than CYK for any realistic input.

Technique	Time (worst)	Time (typical)	Space	Variables
CNF conversion	\(O(\lvert G \rvert^2)\)	\(O(\lvert G \rvert)\)	\(O(\lvert G \rvert^2)\)	grammar size
CYK	\(\Theta(n^3 \lvert P \rvert)\)	the same (no fast path)	\(\Theta(n^2 \lvert N \rvert)\)	\(n\) tokens
Valiant	\(O(\lvert G \rvert\, n^{\omega})\)	impractical constants	\(O(n^2 \lvert N \rvert)\)	\(\omega < 2.372\)
GLL	\(O(n^3)\)	near-linear on near-deterministic grammars (with FIRST/FOLLOW tests)	\(O(n^2)\) recognizer, \(O(n^3)\) SPPF	fixed grammar

CYK¶

Valiant's reduction (Theorem 4.4.10) — trade-off: sub-cubic asymptotically, never faster in practice.
Binarizing without full CNF (Lange & Leiß, "To CNF or not to CNF?" [LL09]): keep unit and ε-productions and binarize only long right sides, using a unit-closure step inside CYK — trade-off: a grammar of linear size and trees over the original rules, with a slightly more complex inner loop.
Probabilistic CKY / inside–outside (NLP): replace sets by probabilities or by Viterbi scores — trade-off: best-parse selection for ambiguous natural language at the same \(O(n^3)\) cost.

GLL¶

FIRST/FOLLOW tests before Add [SJ10]: only add alternatives whose FIRST set contains the next token — trade-off: near-linear behavior on LL(1)-like grammars, requires the set computations of Lesson 2.2.
GLL combinators (Spiewak's gll-combinators; Izmaylova, Afroozeh & van der Storm, "Practical, general parser combinators", PEPM 2016 [IAS16]): GLL behind a combinator API — trade-off: general parsing in a library, at a constant factor over hand-written parsers.
Binarized SPPF construction in GLL (Scott & Johnstone, "GLL parse-tree generation" 2013 [SJ13]) — trade-off: all parses in cubic space, as for Earley.

7. In real compilers¶

No mainstream compiler uses CYK or GLL for its main language. CYK lives in NLP toolkits and in Lark; GLL in grammar-engineering tools (Iguana, Rascal) and in research on language composition, where grammars are combined and cannot be kept deterministic.

CYK¶

Lark's parser="cyk" (lark/parsers/cyk.py, to_cnf and _parse [LARK-CYK]); NLTK's ViterbiParser (probabilistic CKY). The box after Algorithm 4.4.3 shows Lark.

GLL¶

gll-pg (Rust, box after Algorithm 4.4.5); Iguana (Java, Afroozeh & Izmaylova) and the Rascal metaprogramming language's parser generator use GLL with data-dependent disambiguation. In LLVM's world, nothing: Clang's grammar is handled by hand-written recursive descent with tentative parsing (Lesson 2.6).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
CYK	Every CFG (after CNF, Theorem 4.4.6), exact membership, all parses countable	\(\Theta(n^3 \lvert P \rvert)\) on every input (166 million span/split pairs at \(n = 1000\))	No error position (only "not in \(V[1,n]\)"); trees over CNF helpers unless reverted	Low: three loops + CNF conversion	NLP (probabilistic CKY), teaching, Lark, complexity theory
GLL	Every CFG, left recursion and ambiguity included; SPPF of all parses	\(O(n^3)\); near-linear on near-deterministic grammars with FIRST/FOLLOW tests	Recursive-descent-shaped; errors at the furthest descriptor position	Medium–high: GSS, descriptors, SPPF	Grammar engineering (Iguana, Rascal), language composition, gll-pg

Choose CYK when you need the simplest provably-correct general recognizer, a probabilistic parser, or a matrix-algebra view; never for long programs. Choose GLL when you want general parsing but also the structure of recursive descent (debuggable procedures, semantic actions per rule), or grammars are composed from modules.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
CYK	`cyk-cell`, `cyk-top`, `cyk-cnf-count`	`cyk-table`	`cyk`	— (theory + drills)
GLL	`gll-descriptors`, `gll-leftrec`	`paradigm-accepts` (GLL, like Earley, accepts every CFG)	`gll`	— (theory + drills)

GLL has no dedicated drill: its traces grow with the GSS and are dominated by the same bookkeeping as the Earley chart, which earley-chart already drills; the quiz asks for a GLL descriptor count on the example of §3 and for the left-recursion mechanism.

References¶

See the chapter references.

Lesson 4.4 — CYK and GLL: general parsing bottom-up by spans and top-down with a graph stack¶

1. Problem and motivation¶

CYK¶

GLL¶

2. Definitions and algorithms¶

CYK¶

GLL¶

3. Worked examples¶

CYK¶

GLL¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

CYK¶

GLL¶

7. In real compilers¶

CYK¶

GLL¶

8. Comparison¶

9. Assessment¶

References¶