Editing LR parser (section)

{{Short description|Type of parser in computer science}}
{{Technical|date=November 2023}}

In [[computer science]], '''LR parsers''' are a type of [[bottom-up parsing|bottom-up parser]] that analyse [[deterministic context-free language]]s in linear time.<ref name="Knuth 1965">{{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> There are several variants of LR parsers: [[SLR parser]]s, [[LALR parser]]s, [[canonical LR parser|canonical LR(1) parsers]], [[canonical LR parser|minimal LR(1) parsers]], and [[generalized LR parser]]s (GLR parsers). LR parsers can be generated by a [[parser generator]] from a [[formal grammar]] defining the syntax of the language to be parsed. They are widely used for the processing of [[computer language]]s.

An LR parser (left-to-right, rightmost derivation in reverse) reads input text from left to right without backing up (this is true for most parsers), and produces a [[rightmost derivation]] in reverse: it does a [[bottom-up parsing|bottom-up parse]] – not a [[top-down parsing|top-down LL parse]] or ad-hoc parse. The name "LR" is often followed by a numeric qualifier, as in "LR(1)" or sometimes "LR(''k'')". To avoid [[backtracking]] or guessing, the LR parser is allowed to peek ahead at ''k'' [[parsing#Lookahead|lookahead]] input [[symbol (formal)|symbol]]s before deciding how to parse earlier symbols. Typically ''k'' is 1 and is not mentioned. The name "LR" is often preceded by other qualifiers, as in "SLR" and "LALR".  The "LR(''k'')" notation for a grammar was suggested by Knuth to stand for "translatable from left to right with bound ''k''."<ref name="Knuth 1965"/>

LR parsers are deterministic; they produce a single correct parse without guesswork or backtracking, in linear time.  This is ideal for computer languages, but LR parsers are not suited for human languages which need more flexible but inevitably slower methods.  Some methods which can parse arbitrary context-free languages (e.g., [[CYK algorithm|Cocke–Younger–Kasami]], [[Earley parser|Earley]], [[GLR parser|GLR]]) have worst-case performance of O({{var|n}}<sup>3</sup>) time.  Other methods which backtrack or yield multiple parses may even take exponential time when they guess badly.<ref name="AhoUllman 1972">{{cite book |last1=Aho |first1=Alfred V. |author-link1=Alfred Aho |last2=Ullman |first2=Jeffrey D. |author-link2=Jeffrey Ullman |title=The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) |year=1972 |publisher=[[Prentice Hall]] |location=[[Englewood Cliffs, NJ]] |isbn=978-0139145568 |edition=Repr. |url=https://archive.org/details/theoryofparsingt00ahoa }}</ref>

The above properties of '''L''', '''R''', and '''''k''''' are actually shared by all [[shift-reduce parser]]s, including [[simple precedence parser|precedence parser]]s. But by convention, the LR name stands for the form of parsing invented by [[Donald Knuth]], and excludes the earlier, less powerful precedence methods (for example [[Operator-precedence parser]]).<ref name="Knuth 1965"/>
LR parsers can handle a larger range of languages and grammars than precedence parsers or top-down [[LL parsing]].<ref>[https://cs.stackexchange.com/q/43 Language theoretic comparison of LL and LR grammars]</ref> This is because the LR parser waits until it has seen an entire instance of some grammar pattern before committing to what it has found. An LL parser has to decide or guess what it is seeing much sooner, when it has only seen the leftmost input symbol of that pattern.