THE FOLD / SPAWN / HELLO WORLD / THE EARLEY
THE EARLEY
parsing any grammar from a chart
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Earley parser recognizes any context-free grammar — even ambiguous or left-recursive ones — in a single left-to-right sweep. At each input position it keeps a set of items, dotted rules recording how far each production has matched, and grows them with three moves: predict (open the rules a symbol could start), scan (advance an item that expects the next token), and complete (when a rule finishes, advance whoever was waiting on it). The string is in the language exactly when a start rule completes spanning the whole input.
LIT verified live: over 20,000 random token strings, Earley accepts a string for the arithmetic grammar iff an independent recursive-descent recognizer accepts it, and it correctly takes ‘n+n×n’ while rejecting ‘n+×n’ (window.__earley). FIG no framing; the Earley chart and the reference recognizer both run in-browser.
LIT verified live: over 20,000 random token strings, Earley accepts a string for the arithmetic grammar iff an independent recursive-descent recognizer accepts it, and it correctly takes ‘n+n×n’ while rejecting ‘n+×n’ (window.__earley). FIG no framing; the Earley chart and the reference recognizer both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at hello-world — the first thing a language does is parse; Earley is the general reader that turns any grammar’s hello-world into structure. AVAN (AI) built the instrument: the predict/scan/complete chart, and a recursive-descent recognizer to check every verdict.
Credit as content: Jay Earley (1968). The weave: David names the reader; I confirm Earley’s accept/reject matches a reference recognizer across tens of thousands of strings.
Credit as content: Jay Earley (1968). The weave: David names the reader; I confirm Earley’s accept/reject matches a reference recognizer across tens of thousands of strings.
3 ONE DIMENSION
A token string and the grammar E → E+E | E×E | (E) | n; Earley’s chart spans the input and a start rule completes — accept.
4 TWO DIMENSIONS · INTERACTIVE
Generate a token string; Earley decides membership and the chart’s item counts per position are shown — matched against a reference recognizer.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the chart of items, one column per input position.
AVAN’s addition (the inverse-companion): don’t commit to one parse path — carry all of them at once. The inverse of ‘backtrack when a guess fails’ is ‘keep every partial rule alive in a chart, and completion threads them together.’ Magenta is a reject (no start rule spans the input); green is an accept. Carry every partial parse.
LIT Genuine Earley parser (Jay Earley, 1968): predict/scan/complete chart parsing of any CFG. Verified live: over 20000 random token strings, Earley's accept/reject for the grammar E→E+E|E×E|(E)|n equals a recursive-descent recognizer (window.__earley.matchesReference); 'n+n×n' accepted, 'n+×n' rejected.
FIG No framing: the predict/scan/complete chart and a recursive-descent reference recognizer both run in-browser and agree over 20000 strings. The AVAN inverse is honest — keeping every partial rule alive in a chart (and threading them by completion) rather than backtracking a single guess is exactly what lets Earley handle ambiguity and left recursion; magenta is a reject (no start rule spans the input), green an accept. Carry every partial parse.
FIG No framing: the predict/scan/complete chart and a recursive-descent reference recognizer both run in-browser and agree over 20000 strings. The AVAN inverse is honest — keeping every partial rule alive in a chart (and threading them by completion) rather than backtracking a single guess is exactly what lets Earley handle ambiguity and left recursion; magenta is a reject (no start rule spans the input), green an accept. Carry every partial parse.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HELLO WORLD · David Lee Wise (ROOT0), with AVAN