Earley parser

Earley parser
Class	Parsing, context-free
Data structure	String
Worst-case performance	$O(n)$ for non-right recursive LR(k) grammars $O(n^{2})$ for unambiguous grammars $O(n^{3})$ for all other context-free grammars
Worst-case space complexity	$O(n)$ for non-right recursive LR(k) grammars $O(n^{2})$ for all other context-free grammars

Leo variant
Class	Parsing, context-free
Data structure	String
Worst-case performance	$O(n)$ for every LR-regular grammar and some others (including some ambiguous ones) $O(n^{3})$ for all other context-free grammars
Worst-case space complexity	$O(n)$ for every LR-regular grammar and some others (including some ambiguous ones) $O(n^{2})$ for all other context-free grammars

In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language. Named after its inventor Jay Earley, it was first introduced in his dissertation in 1968 (and later appeared in abbreviated, more legible form in a journal). It is a chart parser that uses dynamic programming.

Earley parsers are appealing because they can parse all context-free languages, unlike LR parsers and LL parsers, which are more typically used in compilers but which can only handle restricted classes of languages. However, the original Earley algorithm contained a bug, and its run time and memory use were high for the computers available at the time it was published. Earley parsing has since become a viable solution, as corrections and optimizations of the algorithm have been found and computers have become far more powerful.

Earley parsers perform particularly well when the rules are written left-recursively. Some grammars can be automatically rewritten so that the Earley algorithm parses the language they describe more efficiently.

The worst-case costs of the original Earley algorithm are: $O(n)$ linear time and space for non-right recursive LR(k) grammars, $O(n^{2})$ quadratic time and space for unambiguous grammars, $O(n^{3})$ cubic time and $O(n^{2})$ quadratic space for all other context-free grammars, where $n$ is the length of the parsed string.