Encyclopedia > Earley parser

  Article Content

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 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))

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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... inherently negative implications, it merely designated anyone who assumed power for any period of time without a legitimate basis of authority. The first to have the ...

This page was created in 24.6 ms