Skip to main content

LR parsing

LR parsing A bottom-up parsing technique, LR standing for Left-to-right Rightmost derivation sequence. Originally developed by D. E. Knuth, it is the most powerful left-to-right, no backtracking parsing method for context-free grammars.

An LR parser consists of a pushdown stack, a parsing table, and a driving routine. The driving routine is the same for all grammars. The stack is manipulated by the driving routine using the information contained in the top stack element and the next k symbols in the input stream (called the k lookahead); k is an integer ≥0, but for most practical purposes k = 1. The stack consists of a string s0X0s1X1snXnsn+1

where each Xi is a symbol of the input grammar and each si is called a state.

The parsing table is indexed by pairs (s,a) where s is a state and a is the lookahead. Each entry in the table has two parts: (a) an action, which may be shift, reduce p (for some production p), accept, or error, and (b) a state, called the goto state. When the action is shift, the next input symbol and goto state are pushed onto the stack (in that order). When the action is reduce p the top 2l elements of the stack will spell the right-hand side of p but with goto states interspersed, where l is the length of this right-hand side. These 2l elements are popped from the stack and replaced by the left-hand side of p and the new goto state. This operation corresponds to adding a new node to the parse tree for the input string. The accept action is only encountered when the start symbol S is the only symbol on the stack (i.e. the stack contains s0Ss1 for some states s0 and s1) and the lookahead is the end-of-input symbol. It signifies that parsing has been successfully completed. On the other hand an error entry in the parse table indicates an error in the input string.

A grammar that can be parsed by an LR parser using k-symbol lookahead is called an LR(k) grammar. The power of the LR parsing method comes from the fact that the LR(1) grammars properly include other grammar types like precedence grammars and LL(1) grammars (see LL parsing). This and its efficiency make it a popular choice of parsing method in compiler-compilers. If a grammar is not LR(1) this will be evidenced as multiply defined entries in the parsing tables called shift-reduce conflicts or reduce-reduce conflicts.

Many different parsing tables may be constructed for one grammar, each differing in the number of states it defines. The so-called canonical LR table tends to be too long for practical purposes and it is commonly replaced by an SLR (simple LR) or LALR (lookahead LR) table. A grammar that is LR(1) may not however be SLR(1) or LALR(1).

Cite this article
Pick a style below, and copy the text for your bibliography.

  • MLA
  • Chicago
  • APA

"LR parsing." A Dictionary of Computing. . Encyclopedia.com. 16 Aug. 2018 <http://www.encyclopedia.com>.

"LR parsing." A Dictionary of Computing. . Encyclopedia.com. (August 16, 2018). http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/lr-parsing

"LR parsing." A Dictionary of Computing. . Retrieved August 16, 2018 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/lr-parsing

Learn more about citation styles

Citation styles

Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).

Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.

Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the most-recent information available at these sites:

Modern Language Association

http://www.mla.org/style

The Chicago Manual of Style

http://www.chicagomanualofstyle.org/tools_citationguide.html

American Psychological Association

http://apastyle.apa.org/

Notes:
  • Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
  • In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.