Editing Earley parser (section)

{{Short description|Algorithm for parsing context-free languages}}
{{Infobox algorithm
|name={{PAGENAMEBASE}}
|class=[[Parsing]] grammars that are [[Context-free grammar|context-free]]
|data=[[String (computer science)|String]]
|time=<math>O(n^3)</math>
|best-time={{plainlist|
* <math>\Omega(n)</math> for all [[deterministic context-free grammar]]s
* <math>\Omega(n^2)</math> for [[Ambiguous grammar|unambiguous grammars]]
}}
|average-time=<math>\Theta(n^3)</math>
|space=
}}

In [[computer science]], the '''Earley parser''' is an [[algorithm]] for [[parsing]] [[String (computer science)|strings]] that belong to a given [[context-free language]], though (depending on the variant) it may suffer problems with certain nullable grammars.<ref>{{cite web|last=Kegler|first=Jeffrey|title=What is the Marpa algorithm?|url=http://blogs.perl.org/users/jeffrey_kegler/2011/11/what-is-the-marpa-algorithm.html|access-date=20 August 2013}}</ref> The algorithm, named after its inventor [[Jay Earley]], is a [[chart parser]] that uses [[dynamic programming]]; it is mainly used for parsing in [[computational linguistics]]. It was first introduced in his dissertation<ref name=Earley1>{{cite book
 | last=Earley
 | first=Jay
 | title=An Efficient Context-Free Parsing Algorithm
 | year=1968
 | publisher=Carnegie-Mellon Dissertation
 | url=http://reports-archive.adm.cs.cmu.edu/anon/anon/usr/ftp/scan/CMU-CS-68-earley.pdf
 | access-date=2012-09-12
 | archive-date=2017-09-22
 | archive-url=https://web.archive.org/web/20170922004954/http://reports-archive.adm.cs.cmu.edu/anon/anon/usr/ftp/scan/CMU-CS-68-earley.pdf
 | url-status=dead
 }}</ref> in 1968 (and later appeared in abbreviated, more legible form in a journal).<ref name="Earley2">{{citation
 | last = Earley | first = Jay | author-link = Jay Earley
 | doi = 10.1145/362007.362035 | url = http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/p94-earley.pdf | archive-url = https://web.archive.org/web/20040708052627/http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/p94-earley.pdf | url-status = dead | archive-date = 2004-07-08 | issue = 2
 | journal = [[Communications of the ACM]]
 | pages = 94–102
 | title = An efficient context-free parsing algorithm
 | volume = 13
 | year = 1970| s2cid = 47032707 }}</ref>

Earley parsers are appealing because they can parse all context-free languages, unlike [[LR parser]]s and [[LL parser]]s, which are more typically used in [[compiler]]s but which can only handle restricted classes of languages.  The Earley parser executes in cubic time in the general case <math>{O}(n^3)</math>, where ''n'' is the length of the parsed string, quadratic time for [[unambiguous grammar]]s <math>{O}(n^2)</math>,<ref>{{cite book | isbn=978-0-201-02988-8 | author=John E. Hopcroft and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Reading/MA | publisher=Addison-Wesley | year=1979 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }} p.145</ref> and linear time for all [[deterministic context-free grammar]]s. It performs particularly well when the rules are written [[left recursion|left-recursively]].