The Earley parser is an algorithm for parsing strings belonging to a given context-free language, named after Jay Earley, who introduced it in his 1968 dissertation. It is a chart parser using dynamic programming, and unlike the LR and LL parsers more typically used in compilers it can parse all context-free languages, though the original version had a bug and high memory and time costs that later corrections and optimizations addressed as computers grew more powerful; it performs particularly well on left-recursively written grammars.
Facts
Time Complexity
Time Complexity (category) Classification
Design Technique Connections
In Field
Source Earley parser (Wikipedia)
Uses Design Technique
Sources
1. Earley Parser (Wikipedia)
https://en.wikipedia.org/wiki/Earley_parserQuote, https://en.wikipedia.org/wiki/Earley_parser
It is a chart parser that uses dynamic programming.
2. Earley parser (Wikipedia)
Lead
O ( n 3 ) {\displaystyle O(n^{3})} cubic time and O ( n 2 ) {\displaystyle O(n^{2})} quadratic space for all other context-free grammars
In Field: Algorithms and Complexity Theory, Lead sentence
Earley parser is an algorithm for parsing strings that belong to a given context-free language.
In Group: Parsing Algorithms, Lead section
algorithm for parsing strings that belong to a given context-free language
View the SourceWikidata: Earley Parser
Wikidata Q1277497, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.