The idea: after each word, list the rules that could still be true
The Earley parser (Jay Earley, 1970) reads a sentence from left to right and works with any context-free grammar: no Chomsky normal form as in CYK, and no ban on left recursion as in LL(1). A sentence of n words has n + 1 positions between its words, 0 before the first word and n after the last. The chart has one set S0 … Sn per position. Each set lists the rules that are half finished at that point: how far they got, and where they started.
Items: a rule with a dot
An item is a rule with a dot and an origin, written
A → α • β [j]. In set Si it means: the part α before the dot matches the words from
position j to position i, and β is still to come. VP → V • NP [1] in S2 says
"a VP started at position 1, its V is "saw", and an NP should come next". An item whose dot is at the end,
such as NP → Det N • [2], is finished: the phrase NP covers positions 2 to
i. The page draws finished items grey. S0 starts with one item, S' → • S [0]: a whole
sentence S should start at position 0.
The grammar has seven rules, two of them left recursive (NP → NP PP, VP → VP PP).
The word classes Pro, Det, N, V and P come from a small lexicon. They are read by the scanner and never
predicted, as in Jurafsky and Martin's version of the algorithm.
Predict, scan, complete
Each set is a queue. The parser takes its items in order, and each item gets exactly one of three operations, depending on what stands after its dot. On the canvas each Step is one item: orange is the item being processed, green the items it adds.
| after the dot | operation | what it adds |
|---|---|---|
| a phrase X (S, NP, VP, PP) | predict | X → • γ [i] in Si, for every rule of X: an X could start here |
| a word class C (Pro, Det, N, V, P) | scan | if word i + 1 is a C: C → word • [i] in the next set Si+1 |
nothing: the item is finished, B → γ • [j] | complete | for every item of Sj waiting for B, the same item with the dot moved over B, in Si |
Complete is the step that builds phrases. It looks back to the set where the finished phrase started, finds
the items there that were waiting for that phrase (blue on the canvas), and moves their dots. One finished
phrase can set off a chain: in S4 of "I saw a man", N → man • finishes the NP "a man", that NP
finishes the VP "saw a man", that VP finishes the S "I saw a man", and that S finishes S' → S • [0].
(Demo: S4 already holds a whole sentence)
Left recursion does not loop
A top-down LL parser cannot use NP → NP PP: to expand NP it must first expand NP, forever.
Earley predicts too, but it adds an item to a set only once. In S0, predicting from S → • NP VP
adds the three NP rules. Then NP → • NP PP [0] asks for NP again, and all three NP items are
already in S0, so nothing is added and the queue moves on. S0 ends with 5 items, and the scanner puts
Pro → I • [0] into S1. (Demo: left recursion — S0 predicts NP once)
Accept, or fail at the first bad word
The sentence is in the language exactly when S' → S • [0] is in the last set Sn: an S
covers everything from position 0 to n. The same item can also appear earlier. "I saw a man" is a
whole sentence, so S4 of "I saw a man with a telescope" holds S' → S • [0] too, but there are more
words, so the parser goes on.
If a set ends up empty, no sentence of the grammar starts with the words read so far, and the parser can stop. In "I saw with a man", S2 expects an NP after "saw", and an NP starts with Det or Pro, never with P. So the scanner finds nothing for "with", S3 is empty, and the parse fails at word 3 after 17 items, without reading "a man". This is the valid prefix property, which LL and LR parsers have too. (Demo: rejected — I saw with a man)
Two trees from one chart
"I saw a man with a telescope" has two meanings: I used the telescope, or the man had it. This is
PP attachment ambiguity. Earley does not run twice. In S7 the PP "with a telescope" finishes,
and complete builds both VP → VP PP • [1] (the PP goes with "saw a man") and, through
NP → NP PP • [2], VP → V NP • [1] (the PP goes with "a man"). Both VPs then complete
S → NP • VP [0], so S → NP VP • [0] is reached twice. It stays one item with two
back pointers (shown as ×2, yellow). Each back pointer records the item whose dot moved and
the finished item that moved it. Following them down from S gives the two parse trees.
(Demo: ambiguous PP — two trees for one sentence)
How much work
A set Si holds at most (number of dotted rules) × (i + 1) items, because the origin is one of 0 … i. Completing one item can look through a whole earlier set. That gives O(n³) time in the worst case, the same as CYK, and O(n²) space. For an unambiguous grammar the bound drops to O(n²), and for most grammars that LR parsers accept it is linear (with Leo's 1991 fix for right recursion). The counters under the chart count the processed items by operation:
| sentence | n | items | set sizes | predict / scan / complete | result |
|---|---|---|---|---|---|
| I saw a man | 4 | 27 | 5 7 5 2 8 | 10 / 8 / 9 | accepted, 1 tree |
| I saw a man with a telescope | 7 | 46 | 5 7 5 2 8 5 2 12 | 15 / 12 / 19 | accepted, 2 trees |
| I saw with a man | 5 | 17 | 5 7 5 0 | 8 / 6 / 3 | rejected at "with" |
Compared with the other parsers on this site: CYK fills a table over every span bottom up and needs Chomsky normal form; LR parsing shifts and reduces in linear time but only for grammars without conflicts, and so cannot take an ambiguous English grammar; LL(1) predicts with one word of lookahead and needs left recursion removed first. Earley mixes the two directions: it predicts top down and completes bottom up, and the chart keeps every alternative instead of choosing one. All of them recognize languages that a pushdown automaton accepts.
What the page leaves out
The grammar and the three sentences are fixed presets, and word classes come from a tiny lexicon with one class per word. The page leaves out rules that derive the empty string (they need an extra fix in predict and complete), lookahead in the original 1970 algorithm, Leo's optimization for right recursion, packed parse forests (SPPF) that store an exponential number of trees in polynomial space, and probabilistic Earley parsing that keeps only the most likely tree.