Wait, What?
A general context-free parser can handle left recursion and ambiguity without guessing one derivation path and getting trapped.
Earley parsing is one of the clearest examples of dynamic programming applied to language recognition. Instead of recursively exploring one grammar expansion at a time, the algorithm records partial parsing facts in a sequence of chart sets. Three operations—predict, scan and complete—systematically advance those facts until the input is accepted or no further progress is possible.
Quick Answer
Learn Earley through context-free grammar → dotted item → origin index → chart position → predictor → scanner → completer → duplicate suppression → acceptance condition → complexity → parse reconstruction. The central idea is that a chart item is not a guess. It is a compact statement about how much of one grammar rule has already been matched and where that match began.
1. Start With the Grammar, Not the Parser
A context-free grammar contains nonterminals, terminals, production rules and a start symbol. A rule such as E → E + N says that an expression can consist of another expression, a plus sign and a number. A parser must decide whether an input sequence can be generated by the grammar and, if required, reconstruct one or more derivations.
Earley is valuable because it is a general context-free parsing method. It does not require the grammar to be LL or LR before parsing begins, and it naturally tolerates left-recursive rules that cause naive top-down recursive descent to loop.
2. The Dotted Item Is the Core Data Structure
An Earley item is often written like this:
[A → α • β, i]It means: “we are trying to match production A→αβ; the symbols in α have already been recognized; the symbols in β remain; and this recognition began at input position i.”
The dot is a progress marker. If the dot is before a nonterminal, the parser can predict expansions. If it is before a terminal, the scanner may advance it by consuming input. If it is at the end, the production is complete and can advance items that were waiting for A.
3. The Chart Is a Timeline of Knowledge
For an input of length n, Earley builds chart sets S(0), S(1), …, S(n). S(k) contains items known to be valid after consuming exactly k input tokens. Items also carry their origin position, so a completed constituent can reconnect to the earlier chart set where someone first began waiting for it.
This two-coordinate idea—where we are now and where this constituent began—is what makes completion work without re-parsing the substring from scratch.
4. Seed With an Augmented Start Rule
A common implementation adds a fresh start symbol γ and rule γ → S, where S is the grammar’s original start symbol. Put the item [γ → • S, 0] into S(0). Parsing succeeds when S(n) eventually contains [γ → S •, 0].
The augmented rule gives the recognizer one unambiguous acceptance target.
5. Predictor: Expand What Could Come Next
If an item in S(k) has a nonterminal B immediately after the dot, then every production B → γ is a possible next structure. Add [B → • γ, k] to the same chart set.
if item expects nonterminal B:
for each rule B → rhs:
add [B → • rhs, k] to S(k)The origin is k because the newly predicted B would begin at the current input position.
6. Scanner: Consume a Matching Terminal
If an item in S(k) expects terminal x next and the actual input token at position k is x, advance the dot and add the resulting item to S(k+1).
if item expects terminal x and input[k] == x:
add advanced(item) to S(k + 1)Scanner is the operation that moves the algorithm forward through the input. Predictor and completer can add many facts within the same chart column without consuming a token.
7. Completer: Connect a Finished Constituent Back to Its Callers
Suppose S(k) contains a completed item [B → γ •, j]. This says that a B beginning at j has been fully recognized up to k. Look back into S(j) for every item whose dot is immediately before B. Advance those dots and add the advanced items to S(k).
if [B → rhs •, j] is complete in S(k):
for each [A → α • B β, i] in S(j):
add [A → α B • β, i] to S(k)This is the operation that turns the origin index from metadata into useful algorithmic power.
8. Trace a Left-Recursive Grammar
Use the grammar S → E, E → E + N | N, N → n and input n + n. Naive recursive descent can loop immediately on E → E + N. Earley does not recurse blindly. Predictor adds both E alternatives into S(0), but chart-set deduplication prevents the same item from being inserted forever.
Scanner consumes the first n. Completer then proves an N, which proves an E, which can advance the waiting S and also enable the left-recursive E → E • + N item. Scanner consumes +, predictor introduces N, scanner consumes the final n, and completion propagates the finished structures until the augmented start item is complete in S(3).
9. Duplicate Suppression Is a Correctness and Performance Requirement
Each chart set should behave like a set of states, not an append-only list that happily stores the same item thousands of times. The same item reached through two derivational routes represents the same recognition fact. Deduplicating items allows Earley to merge repeated work.
A practical implementation often combines a set for membership with an agenda or queue for newly added items. Each unique item is processed when it first appears, and later attempts to add it are ignored.
10. A Clear Recognizer Skeleton
def earley(tokens, grammar, start):
# item = (lhs, rhs_tuple, dot, origin)
n = len(tokens)
chart = [set() for _ in range(n + 1)]
agenda = [[] for _ in range(n + 1)]
gamma = "γ"
start_item = (gamma, (start,), 0, 0)
chart[0].add(start_item)
agenda[0].append(start_item)
for k in range(n + 1):
p = 0
while p < len(agenda[k]):
lhs, rhs, dot, origin = agenda[k][p]
p += 1
if dot < len(rhs):
symbol = rhs[dot]
if symbol in grammar: # Predictor
for prod in grammar[symbol]:
item = (symbol, tuple(prod), 0, k)
if item not in chart[k]:
chart[k].add(item)
agenda[k].append(item)
elif k < n and tokens[k] == symbol: # Scanner
item = (lhs, rhs, dot + 1, origin)
if item not in chart[k + 1]:
chart[k + 1].add(item)
agenda[k + 1].append(item)
else: # Completer
for plhs, prhs, pdot, porigin in list(chart[origin]):
if pdot < len(prhs) and prhs[pdot] == lhs:
item = (plhs, prhs, pdot + 1, porigin)
if item not in chart[k]:
chart[k].add(item)
agenda[k].append(item)
accept = (gamma, (start,), 1, 0)
return accept in chart[n]This is a teaching recognizer rather than a production parser. Real implementations need careful handling of nullable productions, efficient indexing of waiting items, parse-forest construction, tokens with attributes and potentially error recovery.
11. Recognition and Parsing Are Different Output Contracts
A recognizer answers yes or no: does the input belong to the language? A parser also reconstructs derivations or syntax trees. If a grammar is ambiguous, there may be many trees—potentially exponentially many. A professional parser should usually build a compact shared representation such as a packed parse forest rather than duplicate large subtrees eagerly.
12. Ambiguity Is Not a Failure of Earley
If a grammar intentionally permits multiple parses, Earley can represent the recognition facts supporting those alternatives. Ambiguity is a property of the grammar and input, not evidence that the recognizer is broken. The engineering question becomes how to store, score or disambiguate the parse alternatives.
13. Complexity
Jay Earley’s 1970 analysis gives a general worst-case time bound of O(n³), O(n²) for unambiguous grammars, and linear behaviour for a substantial class of grammars. Space is commonly O(n²) in the general case because chart items can span many origin/current-position pairs.
Do not interpret O(n³) as “Earley always runs cubically.” Grammar structure, ambiguity, item indexing and implementation details strongly affect actual performance. Specialized deterministic parsers are often faster when their grammar restrictions are acceptable.
14. Nullable Productions Need Special Care
A nonterminal may derive the empty string. That means prediction can lead immediately to completion without scanner advancing the input. Incorrect agenda ordering or incomplete nullable handling can cause missed completions. Production-quality Earley implementations treat nullable symbols deliberately rather than assuming every constituent consumes at least one token.
15. Professional Indexing
The teaching pseudocode scans all items in an origin chart set during completion. Faster implementations index items by the nonterminal they are waiting for, so a completed B can jump directly to the states expecting B. They may also index predicted productions, intern grammar symbols and use compact integer state identifiers.
16. Common Failure States
- Leaving out the origin index.
- Adding predicted items with the wrong origin.
- Scanning a nonterminal as if it were a terminal.
- Completing against the current chart set instead of the completed item’s origin chart set.
- Failing to deduplicate chart items.
- Using an agenda that misses items added later to the same chart column.
- Confusing recognition success with construction of a unique parse tree.
- Ignoring nullable productions.
- Assuming an ambiguous grammar should produce exactly one parse.
17. Testing Strategy
Start with grammars whose accepted and rejected strings you can enumerate. Include left recursion, right recursion, nullable rules, ambiguity, one-token inputs and empty input where legal. Compare the recognizer against a trusted parser library on small grammars. For parser output, validate that every reconstructed tree actually yields the input and follows grammar productions.
18. From Beginner to Professional
Beginner: move a dot through one production by hand. Foundation: identify when predictor, scanner and completer apply. Intermediate: trace chart sets for a short left-recursive expression. Advanced: implement deduplicated agendas and prove the acceptance condition. Professional: add nullable handling, waiting-state indexes, packed parse forests, ambiguity control, instrumentation and comparative benchmarks against LL/LR or generalized parsers.
Learning Hall Boundary
This article owns the Earley chart-parsing method: dotted items, origins, predictor/scanner/completer, ambiguity, complexity and implementation practice. It does not replace the existing Learning Hall parsing overview, grammar foundations, recursive-descent instruction, automata material or compiler architecture articles.
Evidence Boundary
Jay Earley’s “An Efficient Context-Free Parsing Algorithm” appeared in Communications of the ACM in 1970 (DOI 10.1145/362007.362035). The original analysis describes O(n³) general time, O(n²) for unambiguous grammars and linear performance for a large practical grammar class. The learning sequence here uses chart tracing, explicit state meaning, worked examples, error cases and implementation testing in line with current computing-education emphasis on code comprehension, debugging and algorithmic reasoning.
Professional rule: you understand Earley when every chart item reads like a precise sentence about what has been recognized, what is still expected, where it began and where the parser currently stands.
eduKate Sengkang 