The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named for its inventor.
Earley parsers execute in cubic time in the worst case, whereas top-down or bottom-up parsers in the worst case take exponential time. However, since the input in computational linguistics is generally small (i.e. most sentences have no more than about a dozen words), Earley parsers often give worse performance than exponential time algorithms.
Unlike top-down or bottom-up parsers, Earley parsers can handle recursive phrase structure rules such as:
- a --> a b
- a(X) --> a(f(X))