Lesson 4.3 — Earley parsing: every context-free grammar, charts, Leo's optimization, parse forests¶
Techniques: Earley's algorithm (Earley 1970) with the Aycock–Horspool treatment of ε (2002), Leo's right-recursion optimization (Leo 1991), shared packed parse forests from Earley charts (Scott 2008) · Pebble implements: the Earley parser of the comparison lab (SPEC L4) · Prerequisites: Lesson 2.1 (derivations, ambiguity, SPPF preview), Lesson 3.1 (LR(0) items) · Time: 3 hours
LL and LR parsers accept only grammars without conflicts; PEGs accept every grammar but silently change its meaning with ordered choice (Lesson 4.2). Earley's algorithm accepts every context-free grammar — left-recursive, ambiguous, with ε-productions — and decides membership exactly, in cubic time in general and linear time on most grammars people write. It does so by running all LR(0) items at once, one set of items per input position. Earley parsers are the workhorse of grammar tooling where the grammar cannot be massaged (natural language, Lark, Marpa, grammar-engineering tools) and the reference point for "general parsing".
1. Problem and motivation¶
The problem. Given any CFG \(G = (N, T, P, S)\) and tokens \(w = t_1 \cdots t_n\), decide whether \(w \in L(G)\) and, if so, produce its parse tree — or, if \(G\) is ambiguous, all of them in a compact form.
Earley recognition¶
Jay Earley's 1970 thesis algorithm [Ear70] builds, for each position \(k\), the set \(S_k\) of LR(0)-style items \([A \to \alpha \bullet \beta, j]\) that are consistent with the input read so far: \(\alpha\) has matched \(t_{j+1} \cdots t_k\), and an \(A\) starting at \(j\) fits into some derivation of \(w\)'s prefix. Three operations fill the sets: predict (expand the nonterminal after the dot), scan (move over the next token) and complete (a finished \(A\) advances every item that was waiting for it). Earley's original completer mishandles ε-productions when items are processed once in worklist order; Aycock and Horspool [AH02] fixed it with one extra step in the predictor. The lab's Earley parser (L4) handles the left-recursive Pebble expression grammar directly.
Leo's right-recursion optimization¶
Earley's algorithm is linear on LR(k) grammars except for right recursion: on \(S \to a\, S \mid a\) every set \(S_k\) holds a completed item for every earlier origin, \(\Theta(n^2)\) items in total. Joop Leo [Leo91] observed that such completion chains are deterministic and memoized only their top, which makes Earley's algorithm linear on every LR-regular grammar, hence on every LR(k) grammar. Marpa (Kegler's Earley parser) is built on it; Lark ships the scaffolding but has the transitive-item creation removed (§7).
Parse forests (SPPF)¶
For an ambiguous grammar the number of parse trees can grow exponentially (\(E \to E + E \mid n\) has a Catalan number of trees). Tomita's shared packed parse forest (Lesson 3.6) shares common subtrees and packs alternatives; Elizabeth Scott showed how to build a binarized SPPF of cubic size directly from Earley's items [Sco08]. Lark returns it as _ambig nodes when asked.
2. Definitions and algorithms¶
Definition 4.3.1 (Earley items and sets)
Augment \(G\) with \(S' \to S\) (\(S'\) fresh). An Earley item is \([A \to \alpha \bullet \beta, j]\) with \(A \to \alpha\beta \in P\) and an origin \(0 \le j \le n\). The Earley sets \(S_0, \dots, S_n\) are the least sets closed under:
- init: \([S' \to \bullet S, 0] \in S_0\);
- predict: \([A \to \alpha \bullet B \beta, j] \in S_k\), \(B \to \gamma \in P\) \(\Rightarrow\) \([B \to \bullet \gamma, k] \in S_k\);
- scan: \([A \to \alpha \bullet a \beta, j] \in S_k\), \(a = t_{k+1}\) \(\Rightarrow\) \([A \to \alpha a \bullet \beta, j] \in S_{k+1}\);
- complete: \([B \to \gamma \bullet, i] \in S_k\), \([A \to \alpha \bullet B \beta, j] \in S_i\) \(\Rightarrow\) \([A \to \alpha B \bullet \beta, j] \in S_k\).
\(w\) is accepted if \([S' \to S \bullet, 0] \in S_n\).
Definition 4.3.2 (Validity of an item)
An item \([A \to \alpha \bullet \beta, j]\) is valid at \(k\) if \(\alpha \Rightarrow^{*} t_{j+1} \cdots t_k\) and \(S' \Rightarrow^{*} t_1 \cdots t_j\, A\, \delta\) for some \(\delta\).
Validity on the running grammar
With \(E \to E + T \mid T\), \(T \to T * F \mid F\), \(F \to (\,E\,) \mid n\) and \(w = n + n * n\): \([E \to E + \bullet T, 0]\) is valid at 2 (\(E + \Rightarrow^{*} n\,+\), and \(E\) starts at 0), and \([T \to T * \bullet F, 2]\) is valid at 4 (\(T * \Rightarrow^{*} n\,*\) from position 2; a \(T\) can start at 2 because \(S' \Rightarrow E \Rightarrow E + T\)).
Earley recognition¶
Algorithm 4.3.3 (Earley recognizer with the Aycock–Horspool predictor)
- Input: a CFG \(G\) (any), tokens \(t_1 \cdots t_n\).
- Output: the sets \(S_0, \dots, S_n\); accept iff \([S' \to S \bullet, 0] \in S_n\).
- Precondition: \(\mathrm{Nullable}\) (Lesson 2.2) computed.
- Postcondition: each \(S_k\) is the set of Definition 4.3.1, i.e. exactly the items valid at \(k\) (Theorem 4.3.8).
- Invariant: when item number \(i\) of \(S_k\) is processed, all items of \(S_0, \dots, S_{k-1}\) are final, and every item of \(S_k\) already added is valid at \(k\).
function Earley(G, t1 … tn):
S[0] ← [ [S' → • S, 0] ]; S[1..n] ← empty lists (each with a membership set)
for k in 0 … n:
i ← 0
while i < |S[k]|: # S[k] grows while we walk it
item ← S[k][i]; i ← i + 1
if item = [A → α • B β, j] with B ∈ N: # PREDICT
for each B → γ in P: Add(k, [B → • γ, k])
if B ∈ Nullable: Add(k, [A → α B • β, j]) # Aycock–Horspool
else if item = [A → α • a β, j] and k < n and a = t(k+1): # SCAN
Add(k + 1, [A → α a • β, j])
else if item = [B → γ •, i0]: # COMPLETE
for each [A → α • B β, j] in S[i0]: Add(k, [A → α B • β, j])
if S[k] is empty and k > 0: reject (error at token k)
accept iff [S' → S •, 0] ∈ S[n]
function Add(k, item): if item ∉ S[k]: append item to S[k]
Without the Aycock–Horspool line, a completed ε-item \([B \to \bullet, k]\) processed before some item \([A \to \alpha \bullet B \beta, j]\) joins \(S_k\) never advances that item: §3 shows the failure on \(S \to A\,A\,x\), \(A \to \varepsilon\).
Lark's Earley parser on a left-recursive grammar
Reproduce (Lark 1.3.1 from PyPI, Python 3.11.15):
python3.11 -m venv venv && . venv/bin/activate && pip install -q lark==1.3.1
cat > lark_earley.py <<'EOF'
from lark import Lark
g = r"""
e: e "+" t | t
t: t "*" f | f
f: "(" e ")" | NUMBER
%import common.NUMBER
%ignore " "
"""
print(Lark(g, start="e", parser="earley").parse("1 + 2 * 3").pretty())
EOF
python lark_earley.py
Output (complete):
What to notice: the grammar is this lesson's running grammar, left-recursive, fed to the parser unchanged: no LL transformation, no LALR conflict analysis. lark/parsers/earley.py [LARK-Earley] implements the predictor/scanner/completer of Algorithm 4.3.3 (its comments are numbered after the steps of Scott's SPPF paper) and then reads the tree back from the chart.
Leo's right-recursion optimization¶
Definition 4.3.5 (Deterministic reduction path, topmost item)
Let \([B \to \gamma \bullet, i] \in S_k\). An item \([A \to \alpha \bullet B, j] \in S_i\) is the unique penultimate item for \(B\) at \(i\) if it is the only item of \(S_i\) with the dot before \(B\), and \(B\) is the last symbol of its right-hand side (so completing \(B\) completes \(A\) too). The deterministic reduction path from \((B, i)\) follows unique penultimate items: \((B, i) \to (A, j) \to \cdots\) until an origin has no unique penultimate item; the completed item at its end is the topmost item \(\tau(B, i)\). (Leo [Leo91] calls the memoized pairs transitive items.)
Algorithm 4.3.6 (Leo's completer)
- Input: as Algorithm 4.3.3.
- Output: Earley sets without the intermediate completed items of deterministic reduction paths.
- Precondition: as Algorithm 4.3.3.
- Postcondition: \([S' \to S \bullet, 0] \in S_n\) iff \(w \in L(G)\); each \(S_k\) contains every item of Algorithm 4.3.3's \(S_k\) except completed items strictly inside deterministic reduction paths (Theorem 4.3.9).
- Invariant:
Top[i][B], once set, equals \(\tau(B, i)\) and never changes (the sets \(S_0, \dots, S_{i}\) are final when it is first computed, because \(i < k\)).
# replaces COMPLETE in Algorithm 4.3.3 for a completed item [B → γ •, i] in S[k]:
if i < k and (t ← Topmost(B, i)) ≠ none:
Add(k, t) # one item instead of the whole path
else:
for each [A → α • B β, j] in S[i]: Add(k, [A → α B • β, j])
function Topmost(B, i): # memoized in Top[i][B]
if Top[i][B] is set: return Top[i][B]
if S[i] has exactly one item with the dot before B, and it is [A → α • B, j]:
t ← Topmost(A, j)
if t = none: t ← [A → α B •, j]
Top[i][B] ← t
return t
return none
Trees need the skipped items back: Leo parsers record, for each topmost item, the path they skipped, and expand it when a parse is extracted.
Lark without Leo: right recursion is superlinear
Reproduce (Lark 1.3.1, Python 3.11.15, the venv of the previous box; times from one run on the course container, yours will differ, the ratios will not):
cat > leo.py <<'EOF'
import time
from lark import Lark
right = Lark('s: "a" s | "a"', start="s", parser="earley", lexer="basic")
left = Lark('s: s "a" | "a"', start="s", parser="earley", lexer="basic")
for n in (250, 500, 1000):
for name, p in (("left ", left), ("right", right)):
t0 = time.perf_counter(); p.parse("a" * n); dt = time.perf_counter() - t0
print(f"{name} n={n:5d} {dt:6.2f} s")
EOF
python leo.py
Output (complete):
left n= 250 0.02 s
right n= 250 0.61 s
left n= 500 0.06 s
right n= 500 2.67 s
left n= 1000 0.07 s
right n= 1000 16.63 s
What to notice: the left-recursive grammar is linear; the right-recursive one grows by 4.4× and 6.2× per doubling, at least quadratically, because each \(S_k\) collects \(k\) completed items \([s \to a\, s \bullet, j]\) (Proposition 4.3.10). lark/parsers/earley.py still has the "Joop Leo right recursion Completer" block, but its create_leo_transitives step is commented out ("removed at commit 4c1cfb2") [LARK-Earley], so no transitive items are ever created and the chains are completed item by item.
Parse forests (SPPF)¶
Definition 4.3.7 (Shared packed parse forest, binarized)
A binarized SPPF for \(w\) is a DAG with symbol nodes \((X, i, j)\) (the symbol \(X \in N \cup T\) derives \(t_{i+1} \cdots t_j\)), intermediate nodes \((A \to \alpha \bullet \beta, i, j)\) (the prefix \(\alpha\) of a rule, \(\lvert \alpha \rvert \ge 2\), derives \(t_{i+1} \cdots t_j\)), and packed nodes below them, one per way of splitting: a packed node \((A \to \alpha \bullet \beta, m)\) has a left child for \(\alpha\) minus its last symbol (spanning \(i..m\)) and a right child for the last symbol of \(\alpha\) (spanning \(m..j\)). Every parse tree of \(w\) is obtained by choosing one packed child at every node reached from the root \((S, 0, n)\). Scott's construction [Sco08] creates the node \((X, i, j)\) when item \([X \to \gamma \bullet, i]\) enters \(S_j\), and a packed node each time complete or scan produces an item from a (predecessor item, child) pair.
Lark returns an ambiguous parse as _ambig nodes
Reproduce (Lark 1.3.1, Python 3.11.15, same venv):
cat > lark_amb.py <<'EOF'
from lark import Lark
g = r"""
e: e "+" e | e "*" e | NUMBER
%import common.NUMBER
%ignore " "
"""
p = Lark(g, start="e", parser="earley", ambiguity="explicit")
print(p.parse("1 + 2 * 3").pretty())
EOF
python lark_amb.py
Output (complete):
What to notice: the root symbol node \((e, 0, 5)\) has two packed alternatives: \(1 + (2 * 3)\) and \((1 + 2) * 3\). Lark builds a binarized SPPF in earley_forest.py and, with ambiguity="explicit", converts each symbol node with several packed children into an _ambig node; the leaves 1, 2, 3 are shared between the two trees in the forest, though the pretty-printer shows them twice.
3. Worked example¶
The running grammar is \(E \to E + T \mid T\), \(T \to T * F \mid F\), \(F \to (\,E\,) \mid n\) and the input is \(n + n * n\) (5 tokens). The full chart, in the order the items are added (generated by the oracle, tools/course/lib/exprparse.py; ./course drill earley-chart --solution prints the same format):
| step | set | operation | item added | because of |
|---|---|---|---|---|
| 1 | \(S_0\) | init | [E′ → • E, 0] | |
| 2 | \(S_0\) | predict | [E → • E + T, 0] | [E′ → • E, 0] |
| 3 | \(S_0\) | predict | [E → • T, 0] | [E′ → • E, 0] |
| 4 | \(S_0\) | predict | [T → • T * F, 0] | [E → • T, 0] |
| 5 | \(S_0\) | predict | [T → • F, 0] | [E → • T, 0] |
| 6 | \(S_0\) | predict | [F → • ( E ), 0] | [T → • F, 0] |
| 7 | \(S_0\) | predict | [F → • n, 0] | [T → • F, 0] |
| 8 | \(S_1\) | scan n |
[F → n •, 0] | [F → • n, 0] |
| 9 | \(S_1\) | complete | [T → F •, 0] | [F → n •, 0] |
| 10 | \(S_1\) | complete | [E → T •, 0] | [T → F •, 0] |
| 11 | \(S_1\) | complete | [T → T • * F, 0] | [T → F •, 0] |
| 12 | \(S_1\) | complete | [E′ → E •, 0] | [E → T •, 0] |
| 13 | \(S_1\) | complete | [E → E • + T, 0] | [E → T •, 0] |
| 14 | \(S_2\) | scan + |
[E → E + • T, 0] | [E → E • + T, 0] |
| 15 | \(S_2\) | predict | [T → • T * F, 2] | [E → E + • T, 0] |
| 16 | \(S_2\) | predict | [T → • F, 2] | [E → E + • T, 0] |
| 17 | \(S_2\) | predict | [F → • ( E ), 2] | [T → • F, 2] |
| 18 | \(S_2\) | predict | [F → • n, 2] | [T → • F, 2] |
| 19 | \(S_3\) | scan n |
[F → n •, 2] | [F → • n, 2] |
| 20 | \(S_3\) | complete | [T → F •, 2] | [F → n •, 2] |
| 21 | \(S_3\) | complete | [E → E + T •, 0] | [T → F •, 2] |
| 22 | \(S_3\) | complete | [T → T • * F, 2] | [T → F •, 2] |
| 23 | \(S_3\) | complete | [E′ → E •, 0] | [E → E + T •, 0] |
| 24 | \(S_3\) | complete | [E → E • + T, 0] | [E → E + T •, 0] |
| 25 | \(S_4\) | scan * |
[T → T * • F, 2] | [T → T • * F, 2] |
| 26 | \(S_4\) | predict | [F → • ( E ), 4] | [T → T * • F, 2] |
| 27 | \(S_4\) | predict | [F → • n, 4] | [T → T * • F, 2] |
| 28 | \(S_5\) | scan n |
[F → n •, 4] | [F → • n, 4] |
| 29 | \(S_5\) | complete | [T → T * F •, 2] | [F → n •, 4] |
| 30 | \(S_5\) | complete | [E → E + T •, 0] | [T → T * F •, 2] |
| 31 | \(S_5\) | complete | [T → T • * F, 2] | [T → T * F •, 2] |
| 32 | \(S_5\) | complete | [E′ → E •, 0] | [E → E + T •, 0] |
| 33 | \(S_5\) | complete | [E → E • + T, 0] | [E → E + T •, 0] |
- Set sizes \(7, 6, 5, 6, 3, 6\): 33 items. Every set is nonempty and \([E' \to E \bullet, 0] \in S_5\): accepted.
- Left recursion costs nothing: in \(S_0\) the prediction of \(E\) from \([E \to \bullet E + T, 0]\) adds items already present (the membership test), so the predictor terminates.
- The tree. Walk back from \([E' \to E \bullet, 0] \in S_5\) along "because of": step 32 came from \([E \to E + T \bullet, 0]\) (step 30), which came from \([T \to T * F \bullet, 2]\) (29), and so on: \((+\ n\ (*\ n\ n))\).
The ε bug, and the fix. Take \(S \to A\, A\, x\), \(A \to \varepsilon\) and input x. Earley's completer without the Aycock–Horspool line, processing each item once:
| step | set | operation | item added | because of |
|---|---|---|---|---|
| 1 | \(S_0\) | init | [S′ → • S, 0] | |
| 2 | \(S_0\) | predict | [S → • A A x, 0] | [S′ → • S, 0] |
| 3 | \(S_0\) | predict | [A → •, 0] | [S → • A A x, 0] |
| 4 | \(S_0\) | complete | [S → A • A x, 0] | [A → •, 0] |
| 5 | \(S_0\) | (predict from step 4: [A → •, 0] is already there, nothing added) |
\([A \to \bullet, 0]\) was completed at step 4, before \([S \to A \bullet A\, x, 0]\) existed, so the second \(A\) is never completed: \(S_1\) stays empty and x is rejected. With the Aycock–Horspool predictor, predicting the nullable \(A\) from \([S \to A \bullet A\, x, 0]\) also adds \([S \to A\, A \bullet x, 0]\); x is then scanned into \([S \to A\, A\, x \bullet, 0] \in S_1\) and \([S' \to S \bullet, 0]\) follows: accepted.
Leo on right recursion. For \(S \to a\, S \mid a\) and \(a^n\), Algorithm 4.3.3 gives \(\lvert S_0 \rvert = 3\), \(\lvert S_1 \rvert = 5\) and \(\lvert S_k \rvert = k + 4\) for \(k \ge 2\) (for \(n = 3\): \(S_3 = \{[S \to a \bullet S, 2], [S \to a \bullet, 2], [S \to \bullet a S, 3], [S \to \bullet a, 3], [S \to a S \bullet, 1], [S \to a S \bullet, 0], [S' \to S \bullet, 0]\}\)). With Algorithm 4.3.6, completing \([S \to a \bullet, 2]\) in \(S_3\) looks in \(S_2\): the only item with the dot before \(S\) is \([S \to a \bullet S, 1]\), penultimate, so \(\mathrm{Topmost}(S, 2) = \mathrm{Topmost}(S, 1) = \mathrm{Topmost}(S, 0) = [S' \to S \bullet, 0]\) (memoized in Top[1][S] and Top[2][S] on the way), and \(S_3\) gets that one item instead of \([S \to a S \bullet, 1]\) and \([S \to a S \bullet, 0]\): \(\lvert S_k \rvert = 5\) for every \(k \ge 1\).
Try it
./course drill earley-chart --seed 4 --difficulty medium --solution (ambiguous and left-recursive grammars) and --difficulty hard (ε-productions, rejected inputs).
4. Invariants and correctness¶
Theorem 4.3.8 (Earley's sets are exactly the valid items)
For every \(k\), \(S_k\) as computed by Algorithm 4.3.3 is the set of items valid at \(k\) (Definition 4.3.2). Consequently the algorithm accepts iff \(w \in L(G)\), for every CFG \(G\).
Proof
Termination. Each \(S_k\) is a subset of the finite set of items with origin \(\le k\), and Add never duplicates, so every loop is bounded.
Soundness (every item added is valid). Induction on the order of addition. Init: \([S' \to \bullet S, 0]\) is valid at 0. Predict from a valid \([A \to \alpha \bullet B \beta, j]\) at \(k\): \(S' \Rightarrow^{*} t_1 \cdots t_j A \delta \Rightarrow t_1 \cdots t_j \alpha B \beta \delta \Rightarrow^{*} t_1 \cdots t_k B \beta \delta\), so \([B \to \bullet \gamma, k]\) is valid; the Aycock–Horspool item \([A \to \alpha B \bullet \beta, j]\) is valid because \(B \Rightarrow^{*} \varepsilon\). Scan: \(\alpha a \Rightarrow^{*} t_{j+1} \cdots t_{k+1}\). Complete: from valid \([B \to \gamma \bullet, i]\) at \(k\) and \([A \to \alpha \bullet B \beta, j]\) at \(i\): \(\alpha B \Rightarrow^{*} t_{j+1} \cdots t_i\, t_{i+1} \cdots t_k\).
Completeness (every valid item is added). Let \([A \to \alpha \bullet \beta, j]\) be valid at \(k\); induct on \(k\), then on the length of the derivation witnessing validity, then on \(\lvert \alpha \rvert\). If \(\alpha = \varepsilon\) (\(j = k\)): \(A\) occurs after \(t_1 \cdots t_k\) in some sentential form; take the parent item \([C \to \mu \bullet A \nu, h]\) valid at \(k\) (it exists by a shorter witness, or is the init item); it is in \(S_k\) by induction and predicts our item. If \(\alpha = \alpha' X\): split \(t_{j+1} \cdots t_k = u\, v\) with \(\alpha' \Rightarrow^{*} u\), \(X \Rightarrow^{*} v\). Then \([A \to \alpha' \bullet X \beta, j]\) is valid at \(m = j + \lvert u \rvert\) and in \(S_m\) by induction. If \(X\) is a terminal, scan adds our item to \(S_{m+1} = S_k\). If \(X \in N\) and \(v \ne \varepsilon\): \([X \to \rho \bullet, m]\) is valid at \(k\) for the rule \(X \to \rho\) used, hence in \(S_k\) (shorter witness), and complete adds our item — the completer runs on \([X \to \rho \bullet, m]\) after \([A \to \alpha' \bullet X \beta, j] \in S_m\) is final since \(m < k\). If \(v = \varepsilon\) (\(m = k\), \(X\) nullable): the item \([A \to \alpha' \bullet X \beta, j] \in S_k\) is processed at some point and the Aycock–Horspool line adds our item then. This last case is the one Earley's original completer misses when \([X \to \rho \bullet, k]\) was processed earlier (§3); with the extra line, the order of processing no longer matters [AH02, §3].
Acceptance. \([S' \to S \bullet, 0]\) is valid at \(n\) iff \(S \Rightarrow^{*} t_1 \cdots t_n\).
Theorem 4.3.9 (Leo's completer is correct)
Algorithm 4.3.6 accepts exactly \(L(G)\), and its sets are Algorithm 4.3.3's sets minus completed items that lie strictly inside deterministic reduction paths.
Proof sketch (full proof: [Leo91, §3–4])
When \([B \to \gamma \bullet, i]\) joins \(S_k\) and \((B, i)\) has a unique penultimate item \([A \to \alpha \bullet B, j]\), Algorithm 4.3.3 would add \([A \to \alpha B \bullet, j]\), which is again completed, and so on along the deterministic reduction path, adding every completed item on it; the only item of the path that can have consequences other than further completions along the path is the topmost one, because every inner item \([A \to \alpha B \bullet, j]\) completes \(A\) at \(j\), and by uniqueness \(S_j\) contains exactly one item waiting for \(A\), which is the next item of the path. So skipping the inner items loses nothing that matters for acceptance or for the other items; the memo Top[i][B] is sound because \(S_i\) is final when it is computed. Acceptance is preserved because \([S' \to S \bullet, 0]\) is either added normally or is a topmost item.
Proposition 4.3.10 (Right recursion without Leo is quadratic)
For \(S \to a\, S \mid a\) and input \(a^n\), Algorithm 4.3.3 adds exactly \(n^2/2 + 9n/2 + 3\) items for \(n \ge 2\); Algorithm 4.3.6 adds \(5n + 3\).
Proof
By induction on \(k\), \(S_k\) for \(k \ge 2\) consists of \([S \to a \bullet S, k-1]\), \([S \to a \bullet, k-1]\) (scanned), \([S \to \bullet a S, k]\), \([S \to \bullet a, k]\) (predicted), \([S \to a S \bullet, j]\) for \(j = 0, \dots, k - 2\) (completing \([S \to a \bullet, k-1]\) advances \([S \to a \bullet S, k-2] \in S_{k-1}\), whose completion advances \([S \to a \bullet S, k - 3] \in S_{k-2}\), and so on down to origin 0), and \([S' \to S \bullet, 0]\): \(k + 4\) items; \(\lvert S_0 \rvert = 3\) and \(\lvert S_1 \rvert = 5\). Summing, \(8 + \sum_{k=2}^{n} (k + 4) = n^2/2 + 9n/2 + 3\) (for \(n = 16\): 203, as the oracle reports). With Leo, the \(k - 1\) items \([S \to a S \bullet, j]\) are replaced by the single topmost item \([S' \to S \bullet, 0]\), so \(\lvert S_k \rvert = 5\) for \(k \ge 1\) (the example in §3): \(3 + 5n\).
5. Complexity¶
Let \(n\) be the input length and \(\lvert G \rvert\) the grammar size (sum of the right-hand side lengths plus the number of productions).
Theorem 4.3.11 (Earley's bounds)
Algorithm 4.3.3 runs in \(O(\lvert G \rvert^2 n^3)\) time and \(O(\lvert G \rvert\, n^2)\) space for every CFG; in \(O(\lvert G \rvert^2 n^2)\) time for unambiguous grammars; and with Leo's completer (Algorithm 4.3.6) in \(O(\lvert G \rvert^2 n)\) time on every LR-regular grammar, a class containing all LR(k) grammars.
Proof sketch (full proofs: cubic and quadratic bounds [Ear70, §4]; linearity with Leo [Leo91, §5])
Cubic. \(S_k\) holds at most \(\lvert G \rvert (k + 1)\) items (a dotted rule and an origin \(\le k\)). Predict and scan do \(O(\lvert G \rvert)\) work per item. Complete on an item with origin \(i\) walks \(S_i\), \(O(\lvert G \rvert\, n)\). So each set costs \(O(\lvert G \rvert^2 n^2)\) and all \(n + 1\) sets \(O(\lvert G \rvert^2 n^3)\). Quadratic when unambiguous: in an unambiguous grammar each item of \(S_k\) is added by at most one (item, child) pair up to the choice of the predecessor's origin, and Earley shows that the total number of completer steps per set is then \(O(\lvert G \rvert^2 n)\). Linear with Leo: on an LR-regular grammar only a bounded number of items per set are not inside deterministic reduction paths, which Leo proves by relating items to the states of an LR-regular parser.
Proposition 4.3.12 (The lab's expression grammar has bounded Earley sets)
For the CFG of the lab (SPEC §2.3) and any input whose bracket nesting depth (parentheses, index brackets, call parentheses) is at most \(d\), every Earley set has at most \(c\,(d + 1)\) items, where \(c\) is the number of dotted rules of the grammar. Hence Algorithm 4.3.3 is linear on inputs of bounded nesting depth.
Proof
Consider items in \(S_k\) with a nonempty \(\alpha\) and a fixed dotted rule with left side \(E_p\) (or \(C\), \(U\), \(P\), \(A\), \(L\)). The origin \(j\) of such an item is where an \(E_p\) constituent starts that derives \(t_{j+1} \cdots t_k\), and by Lemma 4.1.4 applied to the layered part of the grammar, an \(E_p\) constituent spanning to \(k\) must start either at the beginning of the innermost open bracket group (or of the input), or right after the last depth-0 operator of level \(< p\) in that group before \(k\): a constituent starting elsewhere would contain a depth-0 operator of level \(< p\), which \(E_p\) cannot derive. For each bracket level open at \(k\) there is therefore at most one origin per dotted rule, and there are at most \(d + 1\) open levels. Predicted items (\(\alpha\) empty) all have origin \(k\): at most \(c\) of them. Unary and postfix rules (\(U \to -\, U\), \(P \to P\,[\,E_1\,]\), …) behave the same way with the start of the current chunk as the only origin per level. Summing, \(\lvert S_k \rvert \le c(d+1) + c\), which is \(O(c(d+1))\); the completer walks sets of the same size, so each set costs \(O(c^2 (d+1)^2)\) and the whole run \(O(n)\) for fixed \(d\).
Pathological families. Proposition 4.3.10 (\(\Theta(n^2)\) items, right recursion without Leo) and the ambiguous \(E \to E + E \mid n\) on \(n (+ n)^{m}\), where \(S_k\) holds completed items \([E \to E + E \bullet, j]\) for every origin \(j\) of an operand start (\(\Theta(k)\) of them) and completing the one with origin \(j\) walks \(S_j\), which holds \(\Theta(j)\) items waiting for \(E\): \(\sum_k \sum_{j \le k} \Theta(j) = \Theta(n^3)\) completer steps, while the number of parse trees is the Catalan number \(C_m\) (1, 2, 5, 14, 42 for \(m = 1, \dots, 5\); tools/course/tests/test_ch04.py checks the counts against CYK).
At scale. The lab's Earley parser adds 25.3 items per token on random Pebble expressions and takes 157 ms for 28 500 tokens, about 20 times Pratt's time (ch04-parsebench, SPEC §6): linear, as Proposition 4.3.12 says, but with a large constant. Lark offers an LALR(1) mode for grammars that allow it because it is much faster than its Earley mode [LARK-Docs].
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Earley (with Aycock–Horspool) | \(O(\lvert G \rvert^2 n^3)\); \(O(\lvert G \rvert^2 n^2)\) unambiguous | linear on bounded-state grammars (25.3 items/token in the lab) | \(O(\lvert G \rvert n^2)\) | \(n\) tokens, \(\lvert G \rvert\) grammar size |
| Leo's completer | \(O(\lvert G \rvert^2 n)\) on LR-regular grammars | removes the right-recursion penalty (\(5n+3\) vs \(n^2/2\) items) | \(O(\lvert G \rvert n)\) items + one memo entry per (set, nonterminal) | |
| SPPF construction | \(O(n^3)\) nodes and packed nodes (binarized) | proportional to the chart | \(O(n^3)\) |
6. Variants and refinements¶
Earley recognition¶
- Precomputed Earley parsers (Aycock & Horspool [AH02]): group items into states of an LR(0)-like automaton ("split ε-DFA") so each set holds (state, origin) pairs — trade-off: several times faster, more complex construction.
- Lookahead (Earley's original \(k\)-token lookahead in the completer [Ear70]) — trade-off: fewer useless items on some grammars; later work found it rarely pays for its bookkeeping.
- The Marpa algorithm (Kegler, libmarpa): Aycock–Horspool + Leo + ranking and events — trade-off: production-quality general parsing, a large implementation.
Leo's right-recursion optimization¶
- Memoizing only on demand (Algorithm 4.3.6's
Top) vs precomputing transitive items eagerly in every set as in Leo's paper [Leo91] — trade-off: laziness avoids work for paths never completed. - Tree recovery for Leo items (Marpa, Scott's SPPF extension) — trade-off: extra bookkeeping to reconstruct the skipped completions when a forest is needed.
Parse forests (SPPF)¶
- Binarized vs unbinarized SPPFs [Sco08]: binarization (intermediate nodes) bounds the forest by \(O(n^3)\), while Tomita-style forests can reach \(O(n^{r+1})\) for rules of length \(r\) — trade-off: more node kinds.
- Ambiguity resolution on the forest (Lark's
ambiguity="resolve", priorities, rule order) — trade-off: the parser stays general, and disambiguation becomes a separate, explicit policy.
7. In real compilers¶
No production compiler for a mainstream programming language parses with Earley: their grammars are deterministic enough for recursive descent or LR, and Earley's constant factor (about 20× Pratt's in the lab) is paid on every compile. Earley lives in grammar tooling, natural-language processing and DSL front ends.
Earley recognition¶
Lark's parser="earley" (lark/parsers/earley.py, xearley.py for scannerless Earley [LARK-Earley]), Marpa (libmarpa, C), NLTK's EarleyChartParser. The box after Algorithm 4.3.3 shows Lark.
Leo's right-recursion optimization¶
Marpa implements Leo items; Lark keeps a "Joop Leo right recursion Completer" block in earley.py whose transitive-item creation is removed [LARK-Earley], which the box after Algorithm 4.3.6 measures.
Parse forests (SPPF)¶
Lark's earley_forest.py (SymbolNode, PackedNode, ForestToParseTree); GLR parsers build Tomita-style forests (Lesson 3.6), GLL parsers binarized SPPFs (Lesson 4.4). The box under the SPPF definition shows Lark's _ambig output.
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Earley (with Aycock–Horspool) | Every CFG, exact (Theorem 4.3.8); left recursion and ε included | \(O(n^3)\), \(O(n^2)\) unambiguous, linear on bounded-state grammars · 25.3 items/token, 157 ms at 28 500 tokens in the lab (≈20× Pratt) | Correct-prefix error position (first empty set); the chart lists what was expected | Medium: three operations plus tree extraction | Lark, Marpa, NLTK, grammar prototyping, the lab |
| Leo's completer | Same language; removes right-recursion blow-up | Linear on LR-regular grammars (all LR(k)) | Same; trees need path expansion | Medium–high (tree recovery) | Marpa; general parsers for grammars written with right recursion |
| SPPF construction | All parses of an ambiguous sentence in \(O(n^3)\) space | Proportional to the chart | Every tree, shared and packed | Medium (binarization) | Lark ambiguity="explicit", GLL/GLR back ends, grammar debugging |
Choose Earley when the grammar is fixed and not LL/LR (natural-language-like, user-supplied, ambiguous by design) or you are prototyping a grammar and want no conflicts at all. Choose Leo's completer when the grammar is right-recursive and inputs are long. Choose an SPPF when ambiguity is real and must be resolved later (by types, by rules, by the user).
9. Assessment¶
| Technique | Quiz ids | Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Earley recognition | earley-set-size, earley-items-s2, earley-accept |
earley-chart |
earley |
lab L4 |
| Leo's right-recursion optimization | leo-count, leo-lark |
earley-chart (count the completed items of right-recursive grammars) |
leo |
lab stretch goal |
| Parse forests (SPPF) | sppf-catalan, sppf-size |
cyk-table --difficulty hard (tree counts) |
sppf |
— |
References¶
See the chapter references.