Introduction

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(n3)O(n^{3}) time in the worst case, O(n2)O(n^{2}) for unambiguous grammars, and O(n)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.

Try It: Watch the Chart Fill

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:</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="e.g. the dog sees a cat" spellcheck="false" />
  <button id="parseBtn" type="button">Parse</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// โ”€โ”€ Grammar โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Rules stored as { lhs: string, rhs: string[] }
const RULES = [
  { lhs:'S',  rhs:['NP','VP'] },
  { lhs:'NP', rhs:['det','noun'] },
  { lhs:'NP', rhs:['noun'] },
  { lhs:'VP', rhs:['verb','NP'] },
  { lhs:'VP', rhs:['verb'] },
];
const TERMINALS = {
  det:  ['the','a'],
  noun: ['dog','cat','fish'],
  verb: ['sees','chases','ate'],
};

function termMatches(sym, word) {
  return TERMINALS[sym] && TERMINALS[sym].includes(word.toLowerCase());
}

// โ”€โ”€ Earley item: { rule, dot, origin, op }
function itemKey(item) {
  return item.rule.lhs + 'โ†’' + item.rule.rhs.slice(0,item.dot).join(' ') + 'โ€ข' + item.rule.rhs.slice(item.dot).join(' ') + '[' + item.origin + ']';
}

function earley(words) {
  const n = words.length;
  // chart[i] = array of items at column i
  const chart = Array.from({length: n+1}, () => []);
  const seen  = Array.from({length: n+1}, () => new Set());

  function addItem(col, item) {
    const k = itemKey(item);
    if (seen[col].has(k)) return;
    seen[col].add(k);
    chart[col].push(item);
  }

  // Seed: all rules for S at position 0
  RULES.filter(r => r.lhs === 'S').forEach(r =>
    addItem(0, { rule:r, dot:0, origin:0, op:'predict' }));

  for (let i = 0; i <= n; i++) {
    let j = 0;
    while (j < chart[i].length) {
      const item = chart[i][j++];
      const nextSym = item.rule.rhs[item.dot]; // symbol after dot

      if (nextSym === undefined) {
        // COMPLETE: this item is done; advance items waiting for item.rule.lhs
        for (const waiting of chart[item.origin]) {
          if (waiting.rule.rhs[waiting.dot] === item.rule.lhs) {
            addItem(i, { rule:waiting.rule, dot:waiting.dot+1, origin:waiting.origin, op:'complete' });
          }
        }
      } else if (TERMINALS[nextSym]) {
        // SCAN: terminal โ€” advance into next column if the word matches
        if (i < n && termMatches(nextSym, words[i])) {
          addItem(i+1, { rule:item.rule, dot:item.dot+1, origin:item.origin, op:'scan' });
        }
      } else {
        // PREDICT: non-terminal โ€” add its rules at column i
        RULES.filter(r => r.lhs === nextSym).forEach(r => {
          addItem(i, { rule:r, dot:0, origin:i, op:'predict' });
        });
      }
    }
  }

  const accepted = chart[n].some(it =>
    it.rule.lhs === 'S' && it.dot === it.rule.rhs.length && it.origin === 0);
  return { chart, accepted };
}

// โ”€โ”€ Render โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function formatItem(it) {
  const { lhs, rhs } = it.rule;
  const left  = rhs.slice(0, it.dot).join(' ');
  const right = rhs.slice(it.dot).join(' ');
  const dot   = right ? left + ' โ€ข ' + right : left + ' โ€ข';
  return lhs + ' โ†’ ' + dot + ' [' + it.origin + ']';
}

function render(words, chart, accepted) {
  const wrap = document.getElementById('chart-wrap');
  const res  = document.getElementById('result');

  if (accepted) { res.textContent = 'โœ“ Parse succeeded โ€” S spans the whole input!'; res.className = 'result ok'; }
  else          { res.textContent = 'โœ— Parse failed โ€” sentence not in language.';   res.className = 'result fail'; }

  // Legend
  let html = '<div class="legend"><span><span class="dot" style="background:#0066cc"></span> Predict</span><span><span class="dot" style="background:#0a7d33"></span> Scan</span><span><span class="dot" style="background:#8b5e00"></span> Complete</span></div>';

  html += '<table><tr><th>Column</th>';
  for (let i = 0; i <= words.length; i++)
    html += '<th>' + i + (i < words.length ? '<br><small>"' + words[i] + '"</small>' : '<br><small>(end)</small>') + '</th>';
  html += '</tr>';

  // One row per "step" (predict / scan / complete labelling)
  const maxItems = Math.max(...chart.map(c => c.length));
  for (let row = 0; row < maxItems; row++) {
    html += '<tr><td>' + (row + 1) + '</td>';
    for (let col = 0; col <= words.length; col++) {
      const it = chart[col][row];
      if (it) {
        html += '<td><span class="item ' + it.op + '" title="' + it.op + '">' + formatItem(it) + '</span></td>';
      } else {
        html += '<td></td>';
      }
    }
    html += '</tr>';
  }
  html += '</table>';
  wrap.innerHTML = html;
}

function doParse() {
  const raw   = document.getElementById('sentence').value.trim();
  const words = raw.split(/\s+/).filter(Boolean);
  if (!words.length) { document.getElementById('result').textContent = 'Enter a sentence first.'; document.getElementById('result').className='result'; document.getElementById('chart-wrap').innerHTML=''; return; }
  const { chart, accepted } = earley(words);
  render(words, chart, accepted);
  // console log for node verification
  console.log(fmt('parse("%raw%") =', { raw: raw }), accepted, '| items per col:', chart.map(c=>c.length).join(','));
}

document.getElementById('parseBtn').addEventListener('click', doParse);
document.getElementById('sentence').addEventListener('keydown', e => { if (e.key==='Enter') doParse(); });
doParse();
Result
Console

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 Real Complexity

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(n3)O(n^{3}) worst case. For any context-free grammar and any input of length n, the chart has at most O(n2)O(n^{2}) items, and filling each item takes O(n)O(n) work. Total: O(n3)O(n^{3}). This matches the earlier CYK algorithm and is a known lower-bound target for general CFG parsing.
  • O(n2)O(n^{2}) for unambiguous grammars. When the grammar has at most one parse tree for any string, the chart stays smaller โ€” O(n)O(n) items per column โ€” giving O(n2)O(n^{2}) overall.
  • O(n)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(n2.37โ€ฆ)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.

Where It Matters

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.

Conclusion

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)O(n) in practice to O(n3)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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/earley-parser/Content licensed under CC BY-NC 4.0.