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 s0X0s1X1…snXnsn+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).
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 s0X0s1X1…snXnsn+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).
More From encyclopedia.com
Table , Table
Background
The table is a basic piece of household furniture. It generally consists of a flat top that is supported by either a set of legs, pi… Tabular Presentation , Statistical tables are the most common form of documentation used by the quantitative social scientist, and he should cultivate skill in table constr… tabular , tabular •ampulla, bulla, fuller, Müller, pula, puller •titular • Weissmuller • wirepuller •incunabula, tabular •preambular • glandular • coagula •ang… Periodic Table Of The Elements Phosphorus , Skip to main content
Periodic Table of the Elements Phosphorus Table Tennis , Table tennis, sometimes known as "ping pong" is a miniaturized version of outdoor or lawn tennis. A dynamic indoor racquets sport played world wide,… Round Table , Arthurian legends* tell of a great Round Table in King Arthur's court at Camelot at which the king held meetings with his knights. Usually a king sat…