THE EARLEY PARSER any grammar, whole, no normal form
The classic general parser that swallows any context-free grammar directly — left recursion, ambiguity, and empty rules included, with the rules written the natural way (no Chomsky Normal Form). (GLR and GLL are general too; Earley is the original chart form.) It keeps one state set per gap between tokens; each item is a rule with a dot showing progress plus the position where the match began. Three moves — predict, scan, complete — fill the sets left to right.
THE TECHNIQUE predict, scan, complete
For grammar S → a S b | ε (augmented γ → S), each state set Sₖ holds items [rule with dot, origin]. PREDICT adds a rule’s items when its symbol is expected; SCAN advances items across a matching input token; COMPLETE advances the parent when a rule finishes. Accept iff [γ → S ., 0] lands in the final set. Type a string of a’s and b’s. live demo
HISTORY & CREDIT the recognizer is his; the fixes are not
“Earley needs CNF like CYK” — yes no; that is the whole point. CYK (093) requires CNF; Earley parses any CFG directly. cited
1965 · Knuth’s LR(k) paper gives the dotted-item notation A → α . β Earley’s items reuse. 1968 / 1970 · Jay Earley (CMU thesis; CACM 13(2):94–102): the state-set recognizer with predict/scan/complete over origin-tagged items. O(n³) general, O(n²) unambiguous. 1972 / 2002 · the original nullable-rule bug in COMPLETE is patched by Aho-Ullman (1972), then cleanly by Aycock-Horspool (2002). 1991 / 2008 · Joop Leo makes it linear on every LR-regular grammar (killing the right-recursion O(n²) trap); Elizabeth Scott gives the correct parse-forest — Earley’s own 1970 tree sketch over-generates.
The core recognizer remains his and correct; only the tree extraction and right-recursion bound were someone else’s. Earley, 1970
RECOMMEND FOR I-13 the verdict runs; the chart is the frontier
The recognition verdict for this grammar runs today — S → a S b | ε accepts exactly the balanced language anbn, a matched-pair recursion over an f64 code array:
$ i13 run earley.i13 # S -> a S b | eps, inputs as code points
"aabb" [97,97,98,98] -> 1 ACCEPT "aab" -> 0 REJECT "abb" -> 0 REJECT
Recommend: the verdict is LIT — the string is an f64 code-point array (I-13 has no strings), and a matched-outer-pair recursion rec(lo,hi) recognizes this grammar exactly (verified aabb ACCEPT, aab/abb REJECT). Note: the frontier is the general engine: Earley’s chart is one item-set per gap, and a general item set is a 2-D array (PS-004) plus dotted items (which want a record / node arena, PS-015). The demo animates the real S0…S4 chart; the compiler grounds the accept/reject a fixed-grammar recognizer proves.