Editing LR parser (section)

=== Theory ===

LR parsers were invented by [[Donald Knuth]] in 1965 as an efficient generalization of [[simple precedence parser|precedence parser]]s.  Knuth proved that LR parsers were the most general-purpose parsers possible that would still be efficient in the worst cases.{{citation needed|date=September 2019}}  
: "LR(''k'') grammars can be efficiently parsed with an execution time essentially proportional to the length of the string."<ref>Knuth (1965), p.638</ref>
: For every {{nowrap|''k'' ≥ 1}}, "a language can be generated by an LR(''k'') grammar if and only if it is deterministic [and context-free], if and only if it can be generated by an LR(1) grammar."<ref>Knuth (1965), p.635. Knuth didn't mention the restriction {{nowrap|''k'' ≥ 1}} there, but it is required by his theorems he referred to, viz. on p. 629 and p. 630. Similarly, the restriction to [[context-free language]]s is tacitly understood from the context.</ref>

In other words, if a language was reasonable enough to allow an efficient one-pass parser, it could be described by an LR(''k'') grammar.  And that grammar could always be mechanically transformed into an equivalent (but larger) LR(1) grammar.  So an LR(1) parsing method was, in theory, powerful enough to handle any reasonable language.  In practice, the natural grammars for many programming languages are close to being LR(1).{{citation needed|date=June 2012}}

The canonical LR parsers described by Knuth had too many states and very big parse tables that were impractically large for the limited memory of computers of that era.  LR parsing became practical when [[Frank DeRemer]] invented [[Simple LR parser|SLR]] and [[LALR]] parsers with much fewer states.<ref>
Practical Translators for LR(''k'') Languages, by Frank DeRemer, MIT PhD dissertation 1969.</ref><ref>
Simple LR(''k'') Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.</ref>

For full details on LR theory and how LR parsers are derived from grammars, see ''The Theory of Parsing, Translation, and Compiling, Volume 1'' (Aho and Ullman).<ref name="Compilers 2006"/><ref name="AhoUllman 1972" />

[[Earley parser]]s apply the techniques and <big>{{color|#f7f|•}}</big> notation of LR parsers to the task of generating all possible parses for ambiguous grammars such as for human languages.

While LR(''k'') grammars have equal generative power for all ''k''≥1, the case of LR(0) grammars is slightly different.
A language ''L'' is said to have the ''prefix property'' if no word in ''L'' is a [[Prefix (formal languages)|proper prefix]] of another word in ''L''.<ref>{{cite book |last1=Hopcroft |first1=John E. |last2=Ullman |first2=Jeffrey D. |date=1979 |title=Introduction to Automata Theory, Languages, and Computation |publisher=Addison-Wesley |isbn=0-201-02988-X |url=https://archive.org/details/introductiontoau00hopc }} Here: Exercise 5.8, p.121.</ref>
A language ''L'' has an LR(0) grammar if and only if ''L'' is a [[deterministic context-free language]] with the prefix property.<ref>Hopcroft, Ullman (1979), Theorem 10.12, p.260</ref>
As a consequence, a language ''L'' is deterministic context-free if and only if [[Concatenation#Concatenation of sets of strings|''L''$]] has an LR(0) grammar, where "$" is not a symbol of ''L''{{'}}s [[Alphabet (formal languages)|alphabet]].<ref>Hopcroft, Ullman (1979), Corollary p.260</ref>