> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/programming_language_theory/parsers/earley.md).

# Earley parser

## Basic idea

Bottom-up chart parser that handles *any* context-free grammar — including ambiguous and left-recursive ones. Maintains a set of "items" (dotted productions with a start index) per input position.

## Key formulas

* General CFG: $O(n^3)$
* Unambiguous CFG: $O(n^2)$
* Deterministic / LR-style grammar: $O(n)$
* Memory: $O(n^2)$

Can parse all CFG's but are slow