Editing LALR parser (section)

== History ==

In 1965, [[Donald Knuth]] invented the [[LR parser]] ('''L'''eft to Right, [[rightmost derivation|'''R'''ightmost derivation]]). The LR parser can recognize any [[deterministic context-free language]] in linear-bounded time.<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | author-link = Donald Knuth | title = On the translation of languages from left to right | doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | doi-access = free }}</ref> Rightmost derivation has very large memory requirements and implementing an LR parser was impractical due to the limited [[computer memory|memory]] of computers at that time. To address this shortcoming, in 1969, Frank DeRemer proposed two simplified versions of the LR parser, namely the '''Look-Ahead LR''' (LALR){{sfn|DeRemer|1969}} and the '''[[SLR parser|Simple LR parser]]''' (SLR) that had much lower memory requirements at the cost of less language-recognition power, with the LALR parser being the most-powerful alternative.{{sfn|DeRemer|1969}} In 1977, memory optimizations for the LR parser were invented<ref>{{citation|title=A Practical General Method for Constructing LR(k) Parsers|volume=7|issue=3|author=Pager, D.|work=Acta Informatica 7|pages=249–268|year=1977|doi=10.1007/BF00290336}}</ref> but still the LR parser was less memory-efficient than the simplified alternatives.

In 1979, Frank DeRemer and [[Tom Pennello]] announced a series of optimizations for the LALR parser that would further improve its memory efficiency.<ref>{{citation|title=Efficient Computation of LALR(1) Look-Ahead Sets|author=Frank DeRemer, Thomas Pennello|work=Sigplan Notices - SIGPLAN, vol. 14, no. 8|pages=176–187|year=1979}}</ref> Their work was published in 1982.<ref name="DeRemer82"/>