General Parsing: CYK and Earley

Why we need a general parser at all

The previous guides handed you two fast families of parsers. LL(1) reads top-down, deciding each rule from one lookahead token; LR reads bottom-up, recognising a handle and reducing it. Both are linear time, which is wonderful — but both demand a well-behaved grammar. LL(1) chokes on left recursion and on overlapping FIRST sets; LR rejects any grammar with an unresolved shift-reduce or reduce-reduce conflict. To use them you must first reshape your grammar to fit the parser, and some grammars simply cannot be reshaped at all.

Now flip the requirement. Suppose you are handed an arbitrary context-free grammar — maybe a messy English-syntax grammar bristling with ambiguity, maybe one with deep left recursion you have no licence to rewrite — and you must answer: does this string belong to the language, and if so, what is its structure? You want a parser that works for every context-free grammar, no preconditions. That is a general parser, and the theory already promises one can exist: membership in a context-free language is decidable. CYK and Earley are the two classic ways to actually do it.

CYK: fill a triangle of cells

The CYK algorithm (Cocke–Younger–Kasami) has one prerequisite: the grammar must be in Chomsky normal form (CNF), which you met in the normal-forms rung. In CNF every rule is either A → B C (one variable rewrites to exactly two variables) or A → a (one variable rewrites to a single terminal), with epsilon allowed only for the start symbol. The two-variables-on-the-right shape is the whole reason CYK works: every time you build a piece of the string, it splits cleanly into a left half and a right half, and CYK just tries every place to make the split.

Think of it as dynamic programming over substrings. For a string of length n, CYK fills a triangular table whose cell (i, length) holds every variable that can derive the substring starting at position i and running for that length. It is bottom-up by span, not by tree shape: first solve all length-1 spans (a single terminal — easy, just look up which variables have rule A → a), then length-2, then length-3, and so on up to the whole string. A variable A goes into a longer cell if some rule A → B C lets you split that span into a left part B can cover and a right part C can cover.

1. Length-1 row: for each single character at position i, put in cell (i,1) every variable A with a rule A → a matching that character. This is the base case, read straight off the terminal rules.
2. For each longer span (length 2, then 3, ... up to n), try every way to split it into a non-empty left piece and a non-empty right piece. There are at most n−1 split points.
3. For a given split, look at the variables already proven for the left piece and for the right piece. If some rule A → B C has B in the left set and C in the right set, then A derives the whole span — add A to this cell.
4. After filling the top cell (the whole string, position 1, length n), accept if and only if the start symbol S appears in it. That cell answers membership; the back-pointers you saved at each split reconstruct the parse tree.

Grammar (Chomsky normal form):     Parse the string:  b a a b
  S -> A B | B C                   positions:         1 2 3 4
  A -> B A | a
  B -> C C | b                     CYK table  (cell shows variables; rows = span length)
  C -> A B | a
                                   len4: [ S, A, C ]            <- S here => ACCEPT
  Terminals:                       len3: [ -    ] [ B    ]
    a  is derived by  A and C      len2: [ S,A ] [ B   ] [ B  ]
    b  is derived by  B            len1: [ B ] [ A,C ] [ A,C ] [ B ]
                                          b      a      a     b
  How len2 cell over 'b a' got S,A:
    split b | a -> left has B, right has A,C
    rule S -> B C? need B then C : B(left)+C(right) = yes -> S
    rule A -> B A? B(left)+A(right) = yes -> A

Why CYK is honestly cubic, and what it really decides

Count the work and the cubic cost is no mystery. There are about n^2/2 cells (one per (start, length) pair). Filling one cell means trying up to n split points, and at each split doing a bounded amount of rule-matching (bounded because the grammar is fixed, not part of the input). So the total is roughly (number of cells) times (splits per cell) = O(n^2) · O(n) = O(n^3). This is a genuine worst case, not a loose estimate: there are grammars and strings that really do force you to consider that many splits.

Be precise about what one filled table buys you. The top cell answers the membership question — is the string in the language? — with a clean yes or no. But CYK does more: because each variable in a cell remembers which rule and which split put it there, you can walk the back-pointers down from S to recover an actual parse. If the grammar is ambiguous, a single cell may hold a variable via several different splits, and those alternatives are precisely the multiple parse trees of an ambiguous string. CYK does not panic at ambiguity; it represents all the parses at once, compactly.

Earley: parse the grammar as written

CYK is elegant but it forces you into Chomsky normal form first, which inflates the grammar and obscures its natural shape. The Earley parser removes that chore: it runs on any context-free grammar exactly as written — left recursion, epsilon-rules, arbitrary right-hand sides, ambiguity, all fine, no conversion. The idea is to track, left to right, every rule the parser could be in the middle of, using a dotted marker to record how far it has gotten.

The bookkeeping unit is an Earley item: a rule with a dot showing the boundary between what has already matched and what remains, plus the input position where this rule's match began. Write A → α · β @ k to mean 'we are partway through producing an A; we have matched α, we still need β, and this attempt started at position k.' The parser keeps one set of such items per input position. It fills these sets left to right by repeatedly applying three operations until nothing new appears.

1. PREDICT: if the dot sits just before a variable B (A → α · B β), then B might start right here, so add fresh items B → · γ @ (here) for every rule of B. This is the top-down guess — like recursive descent expanding a nonterminal, but it expands ALL of B's rules in parallel.
2. SCAN: if the dot sits just before a terminal a (A → α · a β) and the next input symbol really is a, advance the dot past it and carry the item into the next position's set. This is the only operation that consumes input.
3. COMPLETE: if an item is finished (B → γ · @ k, dot at the end), then B has been fully matched over the span from k to here. Go back to position k and advance the dot in every item that was waiting for a B at that point. This is the bottom-up reduction — like LR recognising a handle.
4. Accept exactly when, in the set at the final position, you find S → γ · @ 0 — a completed start-symbol item that began at position 0 and spans the whole input. Saved completion links rebuild the parse tree, with several links per cell whenever the string is ambiguous.

Notice the beautiful fusion: PREDICT is top-down guessing (the spirit of recursive descent) while COMPLETE is bottom-up reducing (the spirit of LR). Earley runs both at once, and the @k origin pointers stitch them together so that only consistent partial parses survive. This is also why left recursion is harmless: a left-recursive PREDICT just adds an item that, once completed, immediately feeds COMPLETE — no infinite loop, because items are stored in sets and duplicates are never re-added.

Choosing a parser, and parsing beyond code

So which do you reach for? For a programming language you control, keep an LR (or LL) parser: it is linear, and you are free to design a conflict-free grammar to feed it. Reach for a general parser when you cannot bend the grammar to the tool — when the grammar is given, ambiguous, deeply left-recursive, or evolving experimentally. Between the two general parsers, Earley is usually the friendlier choice: it parses the grammar as written, often runs better than cubic on the grammars people actually use (linear on many unambiguous ones), and degrades gracefully. CYK shines as the clean, easy-to-prove-correct algorithm for teaching, for theory, and when a CNF grammar is already in hand.

Here is where generality earns its keep. Natural-language parsing is the killer application: human grammars (English, Chinese) are inescapably ambiguous — 'I saw the man with the telescope' has two real readings — and they bristle with the kind of structure LR cannot stomach. Earley grew up precisely in computational linguistics, where you want every legal parse returned so a later stage can rank them by probability. General parsers also serve dynamic or user-supplied grammars: data formats, query languages, and live grammar-prototyping tools, where you cannot demand a conflict-free grammar from the user in advance.

Step back and see the through-line of this whole rung. A scanner turned characters into tokens using regular-language machinery; a grammar gave those tokens nested structure; top-down and bottom-up parsers read that structure fast for restricted grammars; and now CYK and Earley read it for all grammars, at a cubic price. Whichever parser you use, the output is the same prize: a structured tree (usually distilled into an abstract syntax tree) that the rest of the compiler — or the linguist, or the data tool — can finally reason about. The final guide turns to the practical machinery: parser generators like yacc and bison, real-world grammar conflicts, and how precedence declarations resolve them.