Lesson plan

Earley parser

In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language. Named after its inventor Jay Earley, it was first introduced in his dissertation in 1968 (and later appeared in abbreviated, more legible form in a journal). It is a chart parser that uses dynamic programming. Earley parsers are appealing because they can parse all context-free languages, unlike LR parsers and LL parsers, which are more typically used in compilers but which can only handle restricted classes of languages. However, the original Earley algorithm contained a bug, and its run time and memory use were high for the computers available at the time it was published. Earley parsing has since become a viable solution, as corrections and optimizations of the algorithm have been found and computers have become far more powerful. Earley parsers perform particularly well when the rules are written left-recursively. Some grammars can be automatically rewritten so that the Earley algorithm parses the language they describe more efficiently. The worst-case costs of the original Earley algorithm are: O(n) linear time and space for non-right recursive LR(k) grammars, O(n^2) quadratic time and space for unambiguous grammars, O(n^3) cubic time and O(n^2) quadratic space for all other context-free grammars, where n is the length of the parsed string.

Back to article

Article summary

In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language. Named after its inventor Jay Earley, it was first introduced in his dissertation in 1968 (and later appeared in abbreviated, more legible form in a journal). It is a chart parser that uses dynamic programming. Earley parsers are appealing because they can parse all context-free languages, unlike LR parsers and LL parsers, which are more typically used in compilers but which can only handle restricted classes of languages. However, the original Earley algorithm contained a bug, and its run time and memory use were high for the computers available at the time it was published. Earley parsing has since become a viable solution, as corrections and optimizations of the algorithm have been found and computers have become far more powerful. Earley parsers perform particularly well when the rules are written left-recursively. Some grammars can be automatically rewritten so that the Earley algorithm parses the language they describe more efficiently. The worst-case costs of the original Earley algorithm are: O(n) linear time and space for non-right recursive LR(k) grammars, O(n^2) quadratic time and space for unambiguous grammars, O(n^3) cubic time and O(n^2) quadratic space for all other context-free grammars, where n is the length of the parsed string.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.