In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, canonical LR(1) parsers, minimal LR(1) parsers, and generalized LR parsers (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 languages.
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 parse – not a 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 lookahead input symbols 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."
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., Cocke–Younger–Kasami, Earley, GLR) have worst-case performance of O(3) time. Other methods which backtrack or yield multiple parses may even take exponential time when they guess badly.
The above properties of L, R, and k are actually shared by all shift-reduce parsers, including precedence parsers. 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). LR parsers can handle a larger range of languages and grammars than precedence parsers or top-down LL parsing.Language theoretic comparison of LL and LR grammars 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.
Overview
Definition of LR(k) grammars
While grammars are mainly used for parsing, the following definition of the grammars instead uses the dual perspective: That of beginning with the start symbol and repeatedly applying a grammar's production rules so as to produce a sequence of sentential forms. By a sentence, we mean a sentential form without any nonterminal symbols.
A right-sentential form is any sentential form which may be obtained by beginning with the start symbol and repeatedly applying productions rules only to the rightmost nonterminals. The entire LR framework uses only right-sentential forms.
The definition of is now short: A context-free grammar is called if for every pair of derivations of right-sentential forms which matches the following pattern, where , , denote any string of terminals and nonterminals, and denote any string of terminals, and denote nonterminals, , and denote terminals, we may conclude that and :
Further terminology and discussion The prefix is called the viable prefix, the substring is called the handle, and the string is called the lookahead. Observe that from the definition of "right-sentential form", we have that , and are all terminal symbols. Note that parsing consists of applying production rules backwards, which is called reducing. Furthermore, a parser will visit the symbols in an input string from left to right, which is backwards to the above derivations. The intuition behind the property is then that the only context needed to reduce to is (i) the entire viable prefix (ii) the handle itself (iii) and additional symbols of lookahead. Notably, it doesn't matter whether or not.
Whether or not a CFG is for a fixed is decidable. Whether there exists any for which a CFG is is not decidable. In practice, is chosen. Any deterministic context-free language admits an grammar, but this is in general neither small nor unique, and each of those grammars will result in a different parse tree for the same string.
Bottom-up parse tree for example A * 2 + 1
An LR parser scans and parses the input text in one forward pass over the text. The parser builds up the parse tree incrementally, bottom up, and left to right, without guessing or backtracking. At every point in this pass, the parser has accumulated a list of subtrees or phrases of the input text that have been already parsed. Those subtrees are not yet joined together because the parser has not yet reached the right end of the syntax pattern that will combine them.
At step 6 in an example parse, only "A * 2" has been parsed, incompletely. Only the shaded lower-left corner of the parse tree exists. None of the parse tree nodes numbered 7 and above exist yet. Nodes 3, 4, and 6 are the roots of isolated subtrees for variable A, operator *, and number 2, respectively. These three root nodes are temporarily held in a parse stack. The remaining unparsed portion of the input stream is "+ 1".
Shift and reduce actions
As with other shift-reduce parsers, an LR parser works by doing some combination of Shift steps and Reduce steps. A Shift step advances in the input stream by one symbol. That shifted symbol becomes a new single-node parse tree. A Reduce step applies a completed grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol. If the input has no syntax errors, the parser continues with these steps until all of the input has been consumed and all of the parse trees have been reduced to a single tree representing an entire legal input.
LR parsers differ from other shift-reduce parsers in how they decide when to reduce, and how to pick between rules with similar endings. But the final decisions and the sequence of shift or reduce steps are the same.
Much of the LR parser's efficiency is from being deterministic. To avoid guessing, the LR parser often looks ahead (rightwards) at the next scanned symbol, before deciding what to do with previously scanned symbols. The lexical scanner works one or more symbols ahead of the parser. The lookahead symbols are the 'right-hand context' for the parsing decision.Engineering a Compiler (2nd edition), by Keith Cooper and Linda Torczon, Morgan Kaufmann 2011.
Bottom-up parse stack
Like other shift-reduce parsers, an LR parser lazily waits until it has scanned and parsed all parts of some construct before committing to what the combined construct is. The parser then acts immediately on the combination instead of waiting any further. In the parse tree example, the phrase A gets reduced to Value and then to Products in steps 1-3 as soon as lookahead * is seen, rather than waiting any later to organize those parts of the parse tree. The decisions for how to handle A are based only on what the parser and scanner have already seen, without considering things that appear much later to the right.
Reductions reorganize the most recently parsed things, immediately to the left of the lookahead symbol. So the list of already-parsed things acts like a stack. This parse stack grows rightwards. The base or bottom of the stack is on the left and holds the leftmost, oldest parse fragment. Every reduction step acts only on the rightmost, newest parse fragments. (This accumulative parse stack is very unlike the predictive, leftward-growing parse stack used by top-down parsers.)
Bottom-up parse steps for example A * 2 + 1 Step Parse Stack Unparsed Shift/Reduce 0 empty A * 2 + 1 shift 1 id * 2 + 1 Value → id 2 Value * 2 + 1 Products → Value 3 Products * 2 + 1 shift 4 Products * 2 + 1 shift 5 Products * int + 1 Value → int 6 Products * Value + 1 Products → Products * Value 7 Products + 1 Sums → Products 8 Sums + 1 shift 9 Sums + 1 shift 10 Sums + int eof Value → int 11 Sums + Value eof Products → Value 12 Sums + Products eof Sums → Sums + Products 13 Sums eof accept
Step 6 applies a grammar rule with multiple parts: Products → Products * Value This matches the stack top holding the parsed phrases "... Products * Value". The reduce step replaces this instance of the rule's right hand side, "Products * Value" by the rule's left hand side symbol, here a larger Products. If the parser builds complete parse trees, the three trees for inner Products, *, and Value are combined by a new tree root for Products. Otherwise, semantic details from the inner Products and Value are output to some later compiler pass, or are combined and saved in the new Products symbol.Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.
LR parse steps for example A * 2 + 1
In LR parsers, the shift and reduce decisions are potentially based on the entire stack of everything that has been previously parsed, not just on a single, topmost stack symbol. If done in an unclever way, that could lead to very slow parsers that get slower and slower for longer inputs. LR parsers do this with constant speed, by summarizing all the relevant left context information into a single number called the LR(0) parser state. For each grammar and LR analysis method, there is a fixed (finite) number of such states. Besides holding the already-parsed symbols, the parse stack also remembers the state numbers reached by everything up to those points.
At every parse step, the entire input text is divided into a stack of previously parsed phrases, a current look-ahead symbol, and the remaining unscanned text. The parser's next action is determined by its current LR(0) (rightmost on the stack) and the lookahead symbol. In the steps below, all the black details are exactly the same as in other non-LR shift-reduce parsers. LR parser stacks add the state information in purple, summarizing the black phrases to their left on the stack and what syntax possibilities to expect next. Users of an LR parser can usually ignore state information. These states are explained in a later section.
Step Parse Stack [Symbol]* LookAhead Unscanned ParserAction Grammar Rule NextState 0 id * 2 + 1 shift 1 id * 2 + 1 reduce Value → id 2 Value * 2 + 1 reduce Products → Value 3 Products * 2 + 1 shift 4 Products * int + 1 shift 5 Products * int + 1 reduce Value → int 6 Products * Value + 1 reduce Products → Products * Value 7 Products + 1 reduce Sums → Products 8 Sums + 1 shift 9 Sums + int eof shift 10 Sums + int eof reduce Value → int 11 Sums + Value eof reduce Products → Value 12 Sums + Products eof reduce Sums → Sums + Products 13 Sums eof accept
At initial step 0, the input stream "A * 2 + 1" is divided into an empty section on the parse stack, lookahead text "A" scanned as an id symbol, and the remaining unscanned text "* 2 + 1". The parse stack begins by holding only initial state 0. When state 0 sees the lookahead id, it knows to shift that id onto the stack, and scan the next input symbol *, and advance to state 9.
At step 4, the total input stream "A * 2 + 1" is currently divided into the parsed section "A *" with 2 stacked phrases Products and *, lookahead text "2" scanned as an int symbol, and the remaining unscanned text " + 1". The states corresponding to the stacked phrases are 0, 4, and 5. The current, rightmost state on the stack is state 5. When state 5 sees the lookahead int, it knows to shift that int onto the stack as its own phrase, and scan the next input symbol +, and advance to state 8.