Earley parser
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. DECLARE ARRAY S; function INIT(words) S ← CREATE_ARRAY(LENGTH(words) + 1) for k ← from 0 to LENGTH(words) do S[k] ← EMPTY_ORDERED_SET function EARLEY_PARSE(words, grammar) INIT(words) ADD_TO_SET((γ → •S, 0), S[0]) for k ← from 0 to LENGTH(words) do for each state in S[k] do // S[k] can expand during this loop if not FINISHED(state) then if NEXT_ELEMENT_OF(state) is a nonterminal then PREDICTOR(state, k, grammar) // non_terminal else do SCANNER(state, k, words) // terminal else do COMPLETER(state, k) end end return chart procedure PREDICTOR((A → α•Bβ, j), k, grammar) for each (B → γ) in GRAMMAR_RULES_FOR(B, grammar) do ADD_TO_SET((B → •γ, k), S[k]) end procedure SCANNER((A → α•aβ, j), k, words) if k ::= # the start rule ::= "+" | ::= "*" | ::= "1" | "2" | "3" | "4" With the input: 2 + 3 * 4 This is the sequence of state sets: The state (P → S •, 0) represents a completed parse. This state also appears in S(3) and S(1), which are complete sentences.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371759853 under CC BY-SA 4.0; modifications have been made.