Earley Parser

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.