Earley

Earley is a chart parsing algorithm for context-free grammars, developed by Jay Earley in the 1970s. It is designed to parse all context-free grammars, including left-recursive and ambiguous ones, without requiring grammar transformations. Earley parsing is widely used in natural language processing and in compiler design where robust handling of complex grammars is beneficial.

The algorithm works by constructing a set of states, or items, organized into a chart for each position in the input. A typical item has the form A → α • β, j, indicating that from position j to the current position i, a rule A → αβ is being recognized with the dot marking progress. The three fundamental operations are Prediction, Scanning, and Completion. Prediction adds new items for possible expansions of a nonterminal that appears after the dot. Scanning advances the dot over a terminal symbol when that symbol matches the input at the current position. Completion when a nonterminal is fully recognized allows the algorithm to advance any waiting items that were predicting that nonterminal, linking shorter and longer recognitions.

Complexity is data-dependent: the worst-case time is O(n^3) for input length n, but many practical grammars yield better performance, often near O(n^2). Earley parsers can incrementally parse input and are attractive when grammar flexibility and left recursion support are priorities.

Variants include Generalized Earley and Lexicalized Earley, which adapt the basic approach for efficiency or specialized linguistic or parsing scenarios.