The Earley Parser

Why the Earley parser matters

Most parsers you meet in a compilers course are picky about their grammar. Recursive-descent (LL) parsers loop forever on left recursion and need the grammar factored to be predictive. LR, LALR, and their yacc/bison descendants reject grammars with shift-reduce or reduce-reduce conflicts, and they refuse ambiguity outright. Real grammars — English syntax, legacy languages, expression grammars written the natural left-recursive way — routinely violate these constraints.

The Earley parser takes any context-free grammar exactly as written and parses it. No conversion to Chomsky Normal Form (unlike CYK), no left-recursion elimination, no left-factoring, no conflict resolution. If a string is in the language, Earley recognizes it; if the grammar is ambiguous, Earley can produce a shared-packed parse forest representing all derivations. That generality is why it underpins tools like the nltk chart parsers, the Marpa and lark (earley mode) libraries, and much of computational-linguistics parsing.

The chart and dotted rules

Earley is a chart parser: it builds an array of n + 1 state sets, S(0), S(1), …, S(n), one for each gap between the input tokens (including before the first and after the last). Each set collects Earley items, also called dotted rules.

A dotted rule is a grammar production with a dot showing how far the parser has matched:

• A → α • B β means the parser has matched α and is now expecting a B.
• Each item also carries an origin index j — the input position where this rule's match started. We write the full item as (A → α • B β, j).

The whole point of the chart is work sharing. If two different derivations both need to parse the noun phrase spanning tokens 2–5, that phrase is parsed once and reused. This dynamic-programming reuse is what keeps Earley polynomial even when the number of full parse trees is exponential.

How it works: predict, scan, complete

Seed the chart by adding (S' → • S, 0) to S(0), where S is the start symbol and S' a fresh augmented start. Then process each state set S(i) in order, applying three rules until no new items appear:

• Predict. For an item (A → α • B β, j) in S(i) where B is a nonterminal, add (B → • γ, i) to S(i) for every rule B → γ. We are guessing that a B starts here at position i.
• Scan. For an item (A → α • a β, j) in S(i) where a is a terminal, if the next input token input[i] equals a, add (A → α a • β, j) to the next set S(i+1). The dot moves past the consumed token.
• Complete. For a finished item (B → γ •, j) in S(i) — the dot at the end means a whole B was recognized spanning positions j…i — look back at set S(j) and, for every item (A → α • B β, k) waiting on that B, add the advanced item (A → α B • β, k) to S(i).

Within each state set, items are deduplicated, so an item is added at most once. The input is accepted if and only if the final set S(n) contains (S' → S •, 0) — a completed start symbol that began at position 0 and consumed the entire input.

Why left recursion just works

Consider the left-recursive rule A → A a | b. A recursive-descent parser calling parseA() would immediately call parseA() again with the same input, recursing forever. Earley never touches a call stack. When it predicts A at position i, it adds (A → • A a, i) and (A → • b, i) to S(i). Prediction on the first item would try to add (A → • A a, i) again — but that item is already in S(i), so deduplication drops it and the process terminates. The left recursion resolves naturally through completion: once an A finishes, the completer advances the dot in the waiting A → • A a item. No grammar rewriting, no infinite loop.

Complexity, case by case

Earley's running time is grammar-dependent, which is unusual and worth stating precisely. Let n be the input length.

	Earley	CYK	Recursive-descent (LL)	LR / LALR
Grammar accepted	Any CFG	Any CFG (needs CNF)	LL(k), no left recursion	LR(k) / LALR(1)
Worst-case time	O(n³)	Θ(n³)	O(n) or exponential w/ backtracking	O(n)
Unambiguous grammar	O(n²)	Θ(n³)	O(n)	O(n)
LR(k) grammar	O(n)	Θ(n³)	—	O(n)
Handles left recursion	Yes	Yes	No	Yes
Handles ambiguity	Yes (parse forest)	Yes	No	No (conflicts)
Space	O(n²)	Θ(n²)	O(depth)	O(n) stack

The bounds come from counting states. Each set S(i) holds at most O(n) distinct items (bounded by grammar size times the O(n) possible origins). There are n + 1 sets, so the chart has O(n²) items — that is the space bound. The complete operation is the expensive one: a single completion at position i may scan the O(n) waiting items in S(j), and there are O(n²) completions, giving O(n³) total. When the grammar is unambiguous, each item has one way to be produced, capping completions at O(n) per position for O(n²) total. For LR(k) grammars the lookahead pins down a unique next item, so each set has O(1) relevant items and the whole parse is O(n).

Implementation in Python

A compact recognizer. It builds the chart and reports acceptance; the same items, with backpointers, let you reconstruct a parse tree or forest.

from collections import namedtuple

# grammar: dict mapping nonterminal -> list of productions (each a tuple of symbols)
# nonterminals are the dict keys; everything else is a terminal.
Item = namedtuple("Item", ["lhs", "rhs", "dot", "origin"])

def next_sym(item):
    return item.rhs[item.dot] if item.dot < len(item.rhs) else None

def earley(grammar, start, tokens):
    n = len(tokens)
    chart = [[] for _ in range(n + 1)]          # S(0) .. S(n)
    seen  = [set() for _ in range(n + 1)]       # dedup per set

    def add(i, item):
        if item not in seen[i]:
            seen[i].add(item)
            chart[i].append(item)

    for prod in grammar[start]:
        add(0, Item(start, prod, 0, 0))

    for i in range(n + 1):
        k = 0
        while k < len(chart[i]):                 # chart[i] grows during the loop
            item = chart[i][k]; k += 1
            sym = next_sym(item)
            if sym is None:                       # COMPLETE
                for prev in chart[item.origin]:
                    if next_sym(prev) == item.lhs:
                        add(i, Item(prev.lhs, prev.rhs, prev.dot + 1, prev.origin))
            elif sym in grammar:                  # PREDICT
                for prod in grammar[sym]:
                    add(i, Item(sym, prod, 0, i))
            elif i < n and tokens[i] == sym:      # SCAN
                add(i + 1, Item(item.lhs, item.rhs, item.dot + 1, item.origin))

    # accept iff a completed start rule spanning the whole input is in S(n)
    return any(it.lhs == start and it.dot == len(it.rhs) and it.origin == 0
               for it in chart[n])

# Left-recursive, ambiguous arithmetic grammar — no rewriting needed.
G = {
    "E": [("E", "+", "E"), ("E", "*", "E"), ("(", "E", ")"), ("n",)],
}
print(earley(G, "E", ["n", "+", "n", "*", "n"]))   # -> True

Note the while k < len(chart[i]) loop: predictions and completions append to the same set being iterated, and the dedup seen guard is what makes that terminate even on left-recursive rules.

Worked example: parsing "n + n"

Take the unambiguous grammar S → S + n | n on input n + n. The chart fills like this:

• S(0): seed (S → • S + n, 0) and (S → • n, 0) by prediction. The first is left-recursive — predicting S again finds both items already present, so it stops.
• Scan n: (S → n •, 0) lands in S(1). Completing it advances (S → S • + n, 0) into S(1).
• Scan +: (S → S + • n, 0) enters S(2).
• Scan n: (S → S + n •, 0) enters S(3). It began at 0 and spans the whole input, so it completes the augmented start — accepted.

The dot marched left to right; left recursion resolved by completion, not by stack recursion. That is the entire trick.

Common misconceptions and pitfalls

• "Earley is always O(n³)." Only for ambiguous grammars in the worst case. It is O(n²) unambiguous and genuinely linear on LR grammars — often competitive with LR parsers on real programming-language input.
• The epsilon (nullable) bug. Earley's original 1970 completer mishandled rules that derive the empty string: a nullable completion can enable a prediction that itself completes at the same position, and the naive completer misses it. Fix by precomputing nullable nonterminals (so prediction advances the dot over them immediately) or by iterating completion to a fixpoint per set — the Aycock–Horspool (2002) approach.
• Confusing recognition with parsing. The bare algorithm answers yes/no. To get a tree you must store backpointers on each completed item and reconstruct; for ambiguous grammars, do it as Scott's (2008) shared-packed parse forest to stay within O(n³).
• Expecting it to handle non-context-free languages. Earley parses exactly the context-free languages. Indentation-sensitive or context-dependent syntax still needs a lexer trick or a more powerful formalism.
• Poor constant factors on unambiguous LALR-friendly grammars. Even at O(n), Earley's per-token bookkeeping (building and scanning state sets) has a heavier constant than a table-driven LR parser. For a fixed programming-language grammar, generated LR/LALR is usually faster in practice.

A little history

Jay Earley introduced the algorithm in his 1968 Carnegie Mellon doctoral thesis and published it in 1970 as "An Efficient Context-Free Parsing Algorithm" in Communications of the ACM. It was one of the first general CFG parsers to beat the naive exponential blow-up while accepting arbitrary grammars. Over the following decades it became the backbone of chart parsing in computational linguistics. John Aycock and Nigel Horspool repaired the nullable-rule handling in 2002; Elizabeth Scott showed in 2008 how to build a cubic shared-packed parse forest; and Jeffrey Kegler's Marpa engine (2010s) turned it into a fast, practical, general-purpose parser with Joop Leo's 1991 optimization that makes right-recursive grammars linear too.