LR parser
≈ 12 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.…
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. 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. The definition of \operatorname{LR}(k) is now short: A context-free grammar G is called \operatorname{LR}(k) if for every pair of derivations of right-sentential forms which matches the following pattern, where \alpha , \alpha' , \beta denote any string of terminals and nonterminals, \gamma and \gamma' denote any string of terminals, B and B' denote nonterminals, k' \le k , and c_1, \dots, c_{k'} denote terminals, we may conclude that {\color{blue} \alpha} = {\color{green} \alpha'} and {\color{red} B} = {\color{green} B'} : \begin{matrix} S &{\overset{*} \underset{G} \implies} & {\color{blue} \alpha} {\color{red}B} {\color{blue} c_1 c_2\dotsb c_{k'}}{\color{purple}\gamma} & {\underset G \implies} &{\color{blue}\alpha \beta c_1 c_2\dotsb c_{k'}} \color{purple}\gamma \\ S & {\overset{*} \underset{G} \implies} & {\color{green} \alpha' B'} {\color{blue} c_1 c_2\dotsb c_{k'}} \color{magenta}\gamma' & {\underset G \implies} & {\color{blue}\alpha \beta c_1 c_2\dotsb c_{k'}} \color{magenta}\gamma' \end{matrix} The prefix {\color{blue}\alpha} is called the viable prefix, the substring {\color{blue} \beta} is called the handle, and the string {\color{blue} c_1 c_2\dotsb c_k} is called the lookahead. Observe that from the definition of "right-sentential form", we have that {\color{blue} c_1, c_2, \dotsc, c_k} , \color{purple}\gamma and \color{magenta}\gamma' 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 \operatorname{LR}(k) property is then that the only context needed to reduce {\color{blue} \beta} to {\color{red} B} is (i) the entire viable prefix {\color{blue}\alpha} (ii) the handle {\color{blue} \beta} itself (iii) and k additional symbols of lookahead. Notably, it doesn't matter whether {\color{purple}\gamma} = {\color{magenta} \gamma'} or not. Whether or not a CFG is \operatorname{LR}(k) for a fixed k is decidable. Whether there exists any k for which a CFG G is \operatorname{LR}(k) is not decidable. In practice, k=1 is chosen. Any deterministic context-free language admits an \operatorname{LR}(1) 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.
Grammar for the example A * 2 + 1
LR parsers are constructed from a grammar that formally defines the syntax of the input language as a set of patterns. The grammar doesn't cover all language rules, such as the size of numbers, or the consistent use of names and their definitions in the context of the whole program. LR parsers use a context-free grammar that deals just with local patterns of symbols. The example grammar used here is a tiny subset of the Java or C language: r0: Goal → Sums eof r1: Sums → Sums + Products r2: Sums → Products r3: Products → Products * Value r4: Products → Value r5: Value → int r6: Value → id The grammar's terminal symbols are the multi-character symbols or 'tokens' found in the input stream by a lexical scanner. Here these include + * and int for any integer constant, and id for any identifier name, and eof for end of input file. The grammar doesn't care what the int values or id spellings are, nor does it care about blanks or line breaks. The grammar uses these terminal symbols but does not define them. They are always leaf nodes (at the bottom bushy end) of the parse tree. The capitalized terms like Sums are nonterminal symbols. These are names for concepts or patterns in the language. They are defined in the grammar and never occur themselves in the input stream. They are always internal nodes (above the bottom) of the parse tree. They only happen as a result of the parser applying some grammar rule. Some nonterminals are defined with two or more rules; these are alternative patterns. Rules can refer back to themselves, which are called recursive. This grammar uses recursive rules to handle repeated math operators. Grammars for complete languages use recursive rules to handle lists, parenthesized expressions, and nested statements. Any given computer language can be described by several different grammars. An LR(1) parser can handle many but not all common grammars. It is usually possible to manually modify a grammar so that it fits the limitations of LR(1) parsing and the generator tool. The grammar for an LR parser must be unambiguous itself, or must be augmented by tie-breaking precedence rules. This means there is only one correct way to apply the grammar to a given legal example of the language, resulting in a unique parse tree with just one meaning, and a unique sequence of shift/reduce actions for that example. LR parsing is not a useful technique for human languages with ambiguous grammars that depend on the interplay of words. Human languages are better handled by parsers like generalized LR parser, the Earley parser, or the CYK algorithm that can simultaneously compute all possible parse trees in one pass. These states are called "LR(0)" states because they use a lookahead of k=0, i.e. no lookahead. The only checking of input symbols occurs when the symbol is shifted in. Checking of lookaheads for reductions is done separately by the parse table, not by the enumerated states themselves. Starting at the begin state (S0), all of the states that can be reached from this state are now determined. The possible transitions for an item set can be found by looking at the symbols (terminals and nonterminals) found following the dots; in the case of item set 0 those symbols are the terminals '0' and '1' and the nonterminals E and B. To find the item set that each symbol x \in \{0, 1, E, B\} leads to, the following procedure is followed for each of the symbols: Take the subset, S, of all items in the current item set where there is a dot in front of the symbol of interest, x. For each item in S, move the dot to the right of x. Close the resulting set of items. For the terminal '0' (i.e. where x = '0') this results in: Item set 1 B → 0 and for the terminal '1' (i.e. where x = '1') this results in: Item set 2 B → 1 and for the nonterminal E (i.e. where x = E) this results in: Item set 3 S → E eof E → E * B E → E + B and for the nonterminal B (i.e. where x = B) this results in: Item set 4 E → B The closure does not add new items in all cases - in the new sets above, for example, there are no nonterminals following the dot. Above procedure is continued until no more new item sets are found. For the item sets 1, 2, and 4 there will be no transitions since the dot is not in front of any symbol. For item set 3 though, we have dots in front of terminals '*' and '+'. For symbol x = \texttt{*} the transition goes to: Item set 5 E → E * B + B → 0 + B → 1 and for x = \texttt{+} the transition goes to: Item set 6 E → E + B + B → 0 + B → 1 Now, the third iteration begins. For item set 5, the terminals '0' and '1' and the nonterminal B must be considered, but the resulting closed item sets for the terminals are equal to already found item sets 1 and 2, respectively. For the nonterminal B, the transition goes to: Item set 7 E → E * B For item set 6, the terminal '0' and '1' and the nonterminal B must be considered, but as before, the resulting item sets for the terminals are equal to the already found item sets 1 and 2. For the nonterminal B the transition goes to: Item set 8 E → E + B These final item sets 7 and 8 have no symbols beyond their dots so no more new item sets are added, so the item generating procedure is complete. The finite automaton, with item sets as its states is shown below. The transition table for the automaton now looks as follows: Chapman, Nigel P., LR Parsing: Theory and Practice, Cambridge University Press, 1987. Pager, D., A Practical General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249 - 268 (1977) "Compiler Construction: Principles and Practice" by Kenneth C. Louden.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378825452 under CC BY-SA 4.0; modifications have been made.