- Canonical LR parser
A

**canonical LR parser**or**LR(1) parser**is anLR parser whose parsing tables are constructed in a similar way as withLR(0) parser s except that the items in the item sets also contain a "lookahead", i.e., a terminal that is expected by theparser after the right-hand side of the rule. For example, such an item for a rule A → B C might be: A → B · C, awhich would mean that the parser has read a string corresponding to B and expects next a string corresponding to C followed by the terminal 'a'. LR(1) parsers can deal with a very large class of grammars but their parsing tables are often very big. This can often be solved by merging item sets if they are identical except for the lookahead, which results in so-calledLALR parsers .**Constructing LR(1) parsing tables**An

**LR(1) item**is a production with a marker together with a terminal, e.g., [S → a A · B e, c] . Intuitively, such an item indicates how much of a certain production we have seen already (a A), what we could expect next (B e), and a lookahead that agrees with what should follow in the input if we ever reduce by the production S → a A B e. By incorporating such lookahead information into the item concept, we can make wiser reduce decisions.The lookahead of an LR(1) item is used directly only when considering reduce actions (i.e., when the · marker is at the right end).The

**core**of an LR(1) item [S → a A · B e, c] is the LR(0) item S → a A · B e. Different LR(1) items may share the same core.For example, if we have two LR(1) items of the form* [A → α ·, a] and

* [B → α ·, b] ,we take advantage of the lookahead to decide which reduction to use. (The same setting would perhaps produce a reduce/reduce conflict in the SLR approach.)

**Validity**The notion of validity changes.An item [A → β

_{1}· β_{2}, a] is**valid**for aviable prefix α β_{1}if there is a rightmost derivation that yields α A a w which in one step yields α β_{1}β_{2}a w**Initial item**To get the parsing started, we begin with the initial item of: [S’ → · S, $] .Here $ is a special character denoting the end of the string.

**Closure**Closure is more refined.If [A → α · B β, a] belongs to the set of items, and B → γ is a production of the grammar, then we add the item [B → · γ, b] for all b in FIRST(β a).

Every state is closed according to Closure.

**Goto**Goto is the same.A state containing [A → α · X β, a] will move to a state containing [A → α X · β, a] with label X.

Every state has transitions according to Goto.for all

**Shift actions**The shift actions are the same.If [A → α · b β, a] is in state I

_{k}and I_{k}moves to state I_{m}with label b, then we add the action:action [k, b] = "shift m"**Reduce actions**The reduce actions are more refined than SLR . If [A→α ·, a] is in state I

_{k}, then we add the action:"Reduce A → α" to action [I_{k}, a] .Observe that we don’t use information from FOLLOW(A) anymore.The goto part of the table is as before.**External links*** [

*http://www.cse.uconn.edu/~akiayias/cse244fa04/N244-4-LR-more.ppt LR parsing*] MS/Powerpoint presentation, Aggelos Kiayias,University of Connecticut

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Canonical S-expressions**— A Canonical S expression (or csexp) is a binary encoding form of a subset of general S expression. It was designed for use in SPKI to retain the power of S expressions, while achieving the compactness of a binary form and maximizing the speed of… … Wikipedia**LR parser**— In computer science, an LR parser is a parser for context free grammars that reads input from Left to right and produces a Rightmost derivation. The term LR( k ) parser is also used; here the k refers to the number of unconsumed look ahead input… … Wikipedia**Validierender Parser**— Vorlage:Infobox Dateiformat/Wartung/magic fehltVorlage:Infobox Dateiformat/Wartung/website fehlt Extensible Markup Language Dateiendung … Deutsch Wikipedia**List of algorithms**— The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia**Список алгоритмов**— Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия**List of computing topics**— Originally, the word computing was synonymous with counting and calculating, and the science and technology of mathematical calculations. Today, computing means using computers and other computing machines. It includes their operation and usage,… … Wikipedia**XML**— Infobox file format name = Extensible Markup Language icon = logo = extension = .xml mime = application/xml, text/xml (deprecated) type code = uniform type = public.xml magic = owner = World Wide Web Consortium genre = Markup language container… … Wikipedia**Parsing**— In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a sequence of tokens to determine their grammatical structure with respect to a given (more or less) formal grammar.Parsing is also… … Wikipedia**Context-free grammar**— In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… … Wikipedia**Syntactic predicate**— A syntactic predicate specifies the syntactic validity of applying a production in a formal grammar and is analogous to a semantic predicate that specifies the semantic validity of applying a production. It is a simple and effective means of… … Wikipedia