In 1965 [[Donald Knuth]] invented the [[LR parser|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 [[precendence parser]]s. This parser has the potential of recognizing all deterministic context-free languages and can produce both left and right derivations of grammar rules. 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 a LR(1) grammar. <ref name="Knuth 1965"/>
Unfortunately, the LR(1) parser has the practical disadvantage of having enormous memory requirements for its interalinternal [[formal grammar|grammar]] representation. The first attempt to solve this problem were the memory optimizations introduced in 1977 by D. 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> but still the LR parser required significantly more memory than other parsing methods. Earlier, in 1969, Frank DeRemer had suggested two simplified version of the LR Parser called [[LALR]] and [[Simple LR parser|SLR]] which greatly reduced memory requirements at the cost of 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}}</ref> These two parsers (especially LALR) have since been and still are by far the most common implementations of the LR Parser.
