Earley Parser

An Earley parser is a type of [chart parser]? used for parsing in computational linguistics, named for their discoveror.

Earley parsers, unlike other parsers, execute in cubic time in the worst case, unlike top-down or bottom-up parsers which can 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 phase 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))

Parsing any grammar without getting into an infinite loop is provably an NP-complete problem.