Earley parser

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

without getting into an infinite loop. On the other hand, there are still rules on which they will loop, such as:

a(X) --> a(f(X))

In other words they can handle Context-free languages but not Unrestricted languages. Parsing an Unrestricted language without getting into an infinite loop is provably an NP-complete problem.