Earley parser
Algorithm for parsing contextfree languages / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Earley parser?
Summarize this article for a 10 year old
In computer science, the Earley parser is an algorithm for parsing strings that belong to a given contextfree language, though (depending on the variant) it may suffer problems with certain nullable grammars.^{[1]} 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^{[2]} in 1968 (and later appeared in an abbreviated, more legible, form in a journal^{[3]}).
Class  Parsing grammars that are contextfree 

Data structure  String 
Worstcase performance  $O(n^{3})$ 
Bestcase performance 

Average performance  $\Theta (n^{3})$ 
Earley parsers are appealing because they can parse all contextfree languages, unlike LR parsers and LL parsers, which are more typically used in compilers but which can only handle restricted classes of languages. The Earley parser executes in cubic time in the general case ${O}(n^{3})$, where n is the length of the parsed string, quadratic time for unambiguous grammars ${O}(n^{2})$,^{[4]} and linear time for all deterministic contextfree grammars. It performs particularly well when the rules are written leftrecursively.