Editing Canonical LR parser (section)

{{Short description|Algorithm used to analyze and process programming languages}}
A '''canonical LR parser''' (also called a '''LR(1) parser''') is a type of [[bottom-up parsing]] algorithm used in [[computer science]] to analyze and process [[programming language]]s. It is based on the [[LR parsing]] technique, which stands for "left-to-right, rightmost derivation in reverse."

Formally, a canonical LR parser is an [[LR(k)]] parser for ''k=1'', i.e. with a single [[Parsing#Lookahead|lookahead]] [[terminal symbol|terminal]]. The special attribute of this parser is that any LR(k) grammar with ''k>1'' can be transformed into an LR(1) grammar.<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 =  }}</ref> However, back-substitutions are required to reduce k and as back-substitutions increase, the grammar can quickly become large, repetitive and hard to understand.  LR(k) can handle all [[deterministic context-free language]]s.<ref name="Knuth 1965"/>  In the past this LR(k) parser has been avoided because of its huge memory requirements in favor of less powerful alternatives such as the [[LALR]] and the [[LL(1)]] parser.  Recently, however, a "minimal LR(1) parser" whose space requirements are close to LALR parsers{{citation needed|date=October 2020}}, is being offered by several parser generators.

Like most parsers, the LR(1) parser is automatically generated by [[compiler-compiler]]s like [[GNU Bison]], MSTA, Menhir,<ref>{{cite web|title=What is Menhir?|url=http://cristal.inria.fr/~fpottier/menhir/|publisher=INRIA, CRISTAL project|access-date=29 June 2012}}</ref> HYACC,<ref>{{cite web|title=HYACC, minimal LR(1) parser generator|url=http://hyacc.sourceforge.net/}}</ref> and LRSTAR.<ref>{{cite web|title=LRSTAR parser generator | url=http://lrstar.cc/}}</ref>