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.

The Earley chart for I saw a man: five columns S0 to S4 with the words I, saw, a, man between them. S0 has 5 items starting with S' → • S [0]; S1 has 7, S2 has 5, S3 has 2 and S4 has 8, including S' → S • [0], so the sentence is accepted. 27 items in all.
The chart for "I saw a man": 27 items in five sets, and S' → S • [0] in the last set means the sentence is accepted.

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 dotoperationwhat it adds
a phrase X (S, NP, VP, PP)predictX → • γ [i] in Si, for every rule of X: an X could start here
a word class C (Pro, Det, N, V, P)scanif word i + 1 is a C: C → word • [i] in the next set Si+1
nothing: the item is finished, B → γ • [j]completefor 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)

One complete step. In S4 the finished item NP → Det N • [2] has origin 2. In S2 the item VP → V • NP [1] is waiting for NP. Completing moves its dot over NP and adds VP → V NP • [1] to S4, with a back pointer to both items.
Complete: the finished NP over "a man" started at position 2, so the parser looks in S2, finds VP → V • NP [1] waiting for an NP, and adds VP → V NP • [1] to S4.

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)

Two parse trees for I saw a man with a telescope. Left: VP → VP PP, the PP attaches to the seeing. Right: VP → V NP with NP → NP PP, the PP attaches to the man. Both have S → NP VP at the root and the same words at the leaves.
The two back pointers of S → NP VP • [0] give two trees: the PP attaches to the verb phrase (left) or to "a man" (right).

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:

sentencenitemsset sizespredict / scan / completeresult
I saw a man4275 7 5 2 810 / 8 / 9accepted, 1 tree
I saw a man with a telescope7465 7 5 2 8 5 2 1215 / 12 / 19accepted, 2 trees
I saw with a man5175 7 5 08 / 6 / 3rejected 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.

On the mind map

This page on the Dynamic Programming mind map · 35 pages in 8 branches · open it to see the whole map and test yourself in recall mode.