Editing Canonical LR parser (section)

== History ==
In 1965 [[Donald Knuth]] invented the LR(k) parser ('''L'''eft to right, [[Rightmost derivation#Derivations and syntax trees|'''R'''ightmost derivation]] parser) a type of [[shift-reduce parser]], as a generalization of existing [[precedence parser (disambiguation)|precedence parser]]s. This parser has the potential of recognizing all deterministic context-free languages and can produce both left and right derivations of statements encountered in the input file. Knuth proved that it reaches its maximum language recognition power for k=1 and provided a method for transforming LR(k), k > 1 grammars into LR(1) grammars.<ref name="Knuth 1965"/>

Canonical LR(1) parsers have the practical disadvantage of having enormous memory requirements for their internal parser-table representation. In 1969, Frank DeRemer suggested two simplified versions of the LR parser called [[LALR parser|LALR]] and [[Simple LR parser|SLR]]. These parsers require much less memory than Canonical LR(1) parsers, but have slightly less language-recognition power.<ref name="DeRemer 1969">{{cite web|title=Practical Translators for LR(k) languages |url=http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf |author=Franklin L. DeRemer |publisher=MIT, PhD Dissertation |year=1969 |url-status=dead |archive-url=https://web.archive.org/web/20120405124425/http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf |archive-date=April 5, 2012 }}</ref> LALR(1) parsers have been the most common implementations of the LR Parser.

However, a new type of LR(1) parser, some people call a "Minimal LR(1) parser" was introduced in 1977 by David Pager<ref name="Pager 1977">{{citation|title=A Practical General Method for Constructing LR(k) Parsers|author=Pager, D.|work=Acta Informatica 7|pages=249–268|year=1977}}</ref> who showed that LR(1) parsers can be created whose memory requirements rival those of LALR(1) parsers. Recently{{when|date=November 2019}}, some parser generators are offering Minimal LR(1) parsers, which not only solve the memory requirement problem, but also the mysterious-conflict-problem inherent in LALR(1) parser generators.{{citation needed|date=November 2019}} In addition, Minimal LR(1) parsers can use shift-reduce actions, which makes them faster than Canonical LR(1) parsers.