In the 1960s, theoretical research in computer science on regular expressions and finite automata led to the discovery that context-free grammars are equivalent to nondeterministic pushdown automata.123 These grammars were thought to capture the syntax of computer programming languages. The first high-level computer programming languages were under development at the time (see History of programming languages) and writing compilers was difficult. But using context-free grammars to help automate the parsing part of the compiler simplified the task. Deterministic context-free grammars were particularly useful because they could be parsed sequentially by a deterministic pushdown automaton, which was a requirement due to computer memory constraints.4 In 1965, Donald Knuth invented the LR(k) parser and proved that there exists an LR(k) grammar for every deterministic context-free language.5 This parser still required a lot of memory. In 1969 Frank DeRemer invented the LALR and Simple LR parsers, both based on the LR parser and having greatly reduced memory requirements at the cost of less language recognition power. The LALR parser was the stronger alternative.6 These two parsers have since been widely used in compilers of many computer languages. Recent research has identified methods by which canonical LR parsers may be implemented with dramatically reduced table requirements over Knuth's table-building algorithm.7
Chomsky, Noam (1962). "Context Free Grammars and Pushdown Storage". Quarterly Progress Report, MIT Research Laboratory in Electronics. 65: 187–194. /wiki/Noam_Chomsky ↩
Evey, R.J. (1963). "Application of Pushdown-Store Machines". 1963 AFIPS Proceedings of the Fall Joint Computer Conference: 215–227. ↩
Schützenberger, Marcel Paul (1963). "On Context-Free Languages and Push-Down Automata". Information and Control. 6 (3): 246–264. doi:10.1016/s0019-9958(63)90306-1. /wiki/Marcel_Paul_Sch%C3%BCtzenberger ↩
A. Salomaa; D. Wood; S. Yu, eds. (2001). A Half-Century of Automata Theory. World Scientific Publishing. pp. 38–39. /wiki/Arto_Salomaa ↩
Knuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. /wiki/Donald_Knuth ↩
Franklin L. DeRemer (1969). "Practical Translators for LR(k) languages" (PDF). MIT, PhD Dissertation. Archived from the original (PDF) on 2012-04-05. https://web.archive.org/web/20120405124425/http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf ↩
X. Chen, Measuring and extending LR(1) parsing, University of Hawaii PhD dissertation, 2009. http://cssauh.com/xc/pub/chenx_dissertation.pdf ↩