This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details.(November 2023) (Learn how and when to remove this message)
In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time.[1] 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."[1]
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(n3) time. Other methods which backtrack or yield multiple parses may even take exponential time when they guess badly.[2]
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).[1]
LR parsers can handle a larger range of languages and grammars than precedence parsers or top-down LL parsing.[3] 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.
^ abcKnuth, D. E. (July 1965). "On the translation of languages from left to right". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
^Aho, Alfred V.; Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (Repr. ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 978-0139145568.
^Language theoretic comparison of LL and LR grammars
parsers[citation needed], is being offered by several parser generators. Like most parsers, the LR(1) parser is automatically generated by compiler-compilers...
Simple LR or SLR parser is a type of LRparser with small parse tables and a relatively simple parser generator algorithm. As with other types of LR(1) parser...
grammar for a computer language. An LALR parser is a simplified version of a canonical LRparser. The LALR parser was invented by Frank DeRemer in his 1969...
A GLR parser (generalized left-to-right rightmost derivation parser) is an extension of an LRparser algorithm to handle non-deterministic and ambiguous...
some inputs, the depth of the parse tree can be proportional to the input size, so both an LRparser and a packrat parser will appear to have the same...
In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language, though (depending on the variant)...
lookahead LRparser (LALR) generator is a software tool that reads a context-free grammar (CFG) and creates an LALR parser which is capable of parsing files...
computer science, an LL parser (Left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. It parses the input from Left...
LRparser is a parser that reads input from Left to right (as it would appear if visually displayed) and produces a Rightmost derivation. The term LR(k)...
top-level domain for Liberia Little Rock, Arkansas, United States LR parser, a type of parser in computer science Lexical resource, a database consisting of...
parsed by an LL parser, which parses the input from Left to right, and constructs a Leftmost derivation of the sentence (hence LL, compared with LR parser...
ambiguity: If the parser is produced by an SLR, LR(1) or LALR LRparser generator, the programmer will often rely on the generated parser feature of preferring...
recursive ascent parsing is a technique for implementing an LRparser which uses mutually-recursive functions rather than tables. Thus, the parser is directly...
stands for Seminole Gulf Railway Scannerless Generalized LRParser describes a Generalized LRparser without a separate Scanner aka. Lexical analysis Steeple...
Simple LRparser. SLR grammars are a superset of all LR(0) grammars and a subset of all LALR(1) and LR(1) grammars. When processed by an SLR parser, an SLR...
In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent)...
algorithm Sending loudness rating for microphones Simple LRparser (Simple Left-to-right parser) Single-lens reflex camera See also: Digital single-lens...
The Packrat parser is a type of parser that shares similarities with the recursive descent parser in its construction. However, it differs because it...
Global Information