33 History of the Marpa algorithm
This chapter is a quick summary of the most important
events in Marpa’s development.
My “timeline” of the major events in parsing theory
has a much broader scope,
and also includes more detail
about Marpa’s development.
See Parsing timeline.
- 1970:
Jay Earley invents the algorithm that now bears his
name
See Earley 1970.
- 1991:
Joop Leo describes a way to modify Earley’s algorithm so that it
runs in O(n) time for all LR-regular
grammars.
See Leo 1991.
LR-regular is a vast class of grammars, including all the
LR(k) grammars, all grammars parseable with recursive descent,
and regular expressions.
LR-regular can safely be thought of as including all grammars
in practical use today, and then some.
- 2002:
Aycock and Horspool describe a way to do LR(0)
precomputation
for Earley’s algorithm.
See Aycock and Horspool 2002.
Their method makes Earley’s faster in most
practical situations, but not all.
In particular, right-recursion remains quadratic in
the Aycock and Horspool algorithm.
Worst case is no better than Earley’s.
Leo is unaware of Aycock and Horspool’s work
and Aycock and Horspool seem unaware of Leo.
- 2010:
Marpa combines the Leo and Aycock-Horspool
algorithms
in the process making significant
changes to both of them.
See Marpa theory paper.
The result preserves the
best features of both
and tackles the many remaining
implementation issues.