the Earley parser
/ ER-lee /
Like CYK, the Earley parser handles any context-free grammar, but instead of demanding a special normal form it works on the grammar as written, including ambiguous ones, and it cleverly adapts its speed to how complex the grammar actually is. Think of it as a parser that keeps, at every position in the input, a running list of 'all the rules I might be partway through right now', and advances those guesses token by token.
Earley scans the input left to right and, for each position, maintains a set of states, each a grammar rule with a dot marking how far through its right-hand side we have matched, plus where the match began. Three operations drive it. Predict: when the dot sits before a nonterminal, add states for all of that nonterminal's rules, guessing we might start one here. Scan: when the dot sits before a terminal that matches the next input token, advance the dot past it. Complete: when a rule's dot reaches the end, the rule is finished, so go back to wherever it started and advance the dots that were waiting on it. The string is accepted if, after the last token, a completed start-symbol rule spans the whole input. Because it only ever pursues guesses consistent with the input seen so far, it never wastes effort on impossible parses.
Earley's appeal is that it is general yet often fast: O(n^3) in the worst case for arbitrary grammars, but O(n^2) for unambiguous grammars and linear O(n) for the nice (LL- or LR-like) ones, so you pay for complexity only when the grammar demands it. It also handles left recursion gracefully and recovers all parses of an ambiguous input. That is why Earley is a favourite for natural-language parsing and for tools that must accept truly arbitrary grammars; the cost is more bookkeeping and slower constants than a specialized LR parser on a tame grammar.
For S -> S + S | num and input num + num, Earley predicts S-rules at position 0, scans num, completes S, predicts after +, scans the second num, completes the inner S, and finally completes S -> S + S spanning the whole input. The dot notation S -> num . records progress through each rule.
Earley: dotted rules advanced by predict / scan / complete; O(n^3) worst case, linear on nice grammars.
Earley works on any CFG with no normal-form conversion, unlike CYK, and adapts its cost to the grammar. But for the well-behaved grammars real languages use, a dedicated LR parser is still faster in practice, so Earley shines mainly where arbitrary or ambiguous grammars are unavoidable.