Earley Parser

Programming languages, arithmetic expressions, and natural language all share a property: their structure is context-free. Every valid sentence can be described by a grammar — a set of rules that say "a sentence is a noun phrase followed by a verb phrase," "a verb phrase is a verb followed by a noun phrase," and so on recursively.

Most parsers in practice demand a restricted form of grammar so they can run fast. LL parsers read left to right and allow only certain rule shapes. LR parsers are more powerful, but still reject many natural grammars and require preprocessing. Both silently refuse grammars that feel perfectly reasonable to write.

In 1970, Jay Earley published an algorithm that imposes no restrictions at all. Feed it any context-free grammar — ambiguous, left-recursive, wildly nested — and it will answer: "does this string belong to the language?" It does so in $O(n^{3})$ time in the worst case, $O(n^{2})$ for unambiguous grammars, and $O(n)$ for most grammars found in practice (like most programming languages).

The secret is a chart: an array of sets of "Earley items" that grow column by column as each input token is read. Three simple rules — Predict, Scan, and Complete — propagate items through the chart until the whole input is accounted for.

Below is a small English-like grammar. Type a sentence in the input box and press Parse — the chart will fill column by column, showing every Predict, Scan, and Complete step. An item like S → NP • VP [0] means: "we are trying to build an S, we have matched an NP so far, we still need a VP, and the match started at position 0."

<div class="grammar-box">
  <strong>{{grammar_label}}</strong>
  <code>S → NP VP</code>
  <code>NP → det noun | noun</code>
  <code>VP → verb NP | verb</code>
  <code>det → "the" | "a"</code>
  <code>noun → "dog" | "cat" | "fish"</code>
  <code>verb → "sees" | "chases" | "ate"</code>
</div>
<div class="input-row">
  <input id="sentence" type="text" value="the dog sees a cat" placeholder="{{input_placeholder}}" spellcheck="false" />
  <button id="parseBtn" type="button">{{parse_btn}}</button>
</div>
<div id="result" class="result"></div>
<div id="chart-wrap"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.grammar-box { background: #f0f4f8; border: 1px solid #cdd5de; border-radius: 8px; padding: .6rem .9rem; margin-bottom: .7rem; }
.grammar-box strong { display: block; margin-bottom: .3rem; font-size: .85rem; color: #4a5568; }
.grammar-box code { display: inline-block; background: #e2e8f0; border-radius: 4px; padding: .1rem .4rem; font-size: .8rem; margin: .15rem .2rem; }
.input-row { display: flex; gap: .5rem; margin-bottom: .6rem; }
#sentence { flex: 1; font: 600 15px ui-monospace,monospace; padding: .45rem .7rem; border: 1px solid #b0bec5; border-radius: 8px; outline: none; }
#sentence:focus { border-color: #2563eb; }
button { font: 600 14px system-ui,sans-serif; padding: .45rem 1rem; background: #1d3557; color: #fff; border: none; border-radius: 8px; cursor: pointer; }
button:hover { background: #16304f; }
.result { font-weight: 700; font-size: 1rem; min-height: 1.4em; margin-bottom: .5rem; }
.result.ok { color: #0a7d33; }
.result.fail { color: #c92f3c; }
#chart-wrap { overflow-x: auto; }
table { border-collapse: collapse; font-size: .78rem; min-width: 100%; }
th { background: #1d3557; color: #fff; padding: .3rem .7rem; text-align: center; font-weight: 700; }
td { vertical-align: top; padding: .3rem .7rem; border: 1px solid #d1d9e0; min-width: 160px; max-width: 220px; }
td:first-child { background: #f0f4f8; font-weight: 700; color: #1d3557; text-align: center; white-space: nowrap; }
.item { display: block; font-family: ui-monospace,monospace; white-space: nowrap; margin: .1rem 0; font-size: .76rem; }
.item.predict { color: #0066cc; }
.item.scan { color: #0a7d33; }
.item.complete { color: #8b5e00; }
.legend { display: flex; gap: 1rem; margin-bottom: .4rem; font-size: .78rem; }
.legend span { display: flex; align-items: center; gap: .25rem; }
.dot { width: 10px; height: 10px; border-radius: 50%; display: inline-block; }

// Code not found

Notice how the chart grows: each column corresponds to one word. A Predict step adds items for rules that could apply next. A Scan step advances items whose next expected symbol matches the current word. A Complete step wakes up all waiting items when a non-terminal is finished. When the full input is consumed and an item S → … • [0] sits in the last column, the parse succeeds.

See how it compares to the all-at-once approach of CYK or the restricted grammars required by LR parsers used in most compilers.

The Earley parser was proven correct and analyzed by Jay Earley in his 1970 Ph.D. thesis — solved as a theoretical result. Here is what the analysis shows:

• $O(n^{3})$ worst case. For any context-free grammar and any input of length n, the chart has at most $O(n^{2})$ items, and filling each item takes $O(n)$ work. Total: $O(n^{3})$. This matches the earlier CYK algorithm and is a known lower-bound target for general CFG parsing.
• $O(n^{2})$ for unambiguous grammars. When the grammar has at most one parse tree for any string, the chart stays smaller — $O(n)$ items per column — giving $O(n^{2})$ overall.
• $O(n)$ for most practical grammars. Grammars for real programming languages are almost always unambiguous and non-left-recursive after minor rewriting. On these, Earley behaves like a linear-time parser — matching the speed of LL and LR parsers without their restrictions.
• No preprocessing required. Unlike LR parsers, which need an O(|grammar|³) table-construction step, Earley parses directly from the grammar rules. This matters when grammars change at runtime (natural language, user-extensible languages).
• Handles all CFLs. Left recursion, ambiguity, ε-productions (rules that derive the empty string) — none of these derail the algorithm. It is one of the most general parsing algorithms known.

The cubic worst case has proven hard to beat: the best known improvements shave constant factors but do not reduce the exponent for general CFGs. Whether general CFG parsing can be done in $O(n^{2.37…})$ using matrix multiplication methods remains an open theoretical question — see the analysis in P vs NP for why such structural questions matter.

The ability to parse any context-free grammar — without preprocessing, without grammar restrictions — makes the Earley parser the right tool in several settings:

• Natural language processing: natural language grammars are naturally ambiguous and often left-recursive. Earley handles them directly; LL/LR parsers cannot. Modern probabilistic extensions of the Earley algorithm are used in statistical parsing.
• User-extensible languages: when a programming language lets the user define new syntax at runtime (Prolog, some Lisp dialects, Haskell's layout rules), the grammar changes dynamically. Earley needs no precompilation step.
• Error recovery and partial parses: because the chart records all partial matches, not just one path, it is straightforward to extract the best partial parse when input is malformed — useful for IDE autocompletion.
• Protocol and data-format parsing: binary protocols and structured data formats often have context-free descriptions that do not fit LL/LR restrictions. Earley parses them without grammar surgery.
• Teaching parsing theory: Earley items make the three core operations of parsing — prediction, scanning, completion — completely explicit, making the algorithm the standard vehicle for teaching formal language theory.

Learn how the Earley chart works and you understand the common substrate shared by all chart-based parsers — from CYK to GLR — and why some grammars are genuinely harder to parse than others.

Jay Earley's algorithm is a rare thing in computer science: a beautiful, simple idea that solves a problem in full generality. Three rules — Predict, Scan, Complete — are enough to handle every context-free grammar ever written, in time that degrades gracefully from $O(n)$ in practice to $O(n^{3})$ in the worst case.

Practical parsers in compilers are usually faster because they accept grammar restrictions. But every time you encounter a grammar that an LL or LR parser refuses — an ambiguous language, a left-recursive rule, a runtime-defined extension — the Earley algorithm is the principled answer, and the pattern-matching intuition underneath it connects to the deepest questions in formal language theory.