Earley1970:
  type: article
  title: An efficient context-free parsing algorithm
  author: Earley, Jay
  date: 1970-02
  page-range: 94-102
  url: https://doi.org/10.1145/362007.362035
  serial-number:
    doi: 10.1145/362007.362035
    issn: 0001-0782
  abstract: A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
  parent:
    type: periodical
    title: Commun. ACM
    publisher:
      name: Association for Computing Machinery
      location: New York, NY, USA
    issue: 2
    volume: 13