5. LR PARSING INTRODUCTION:
The "L" is for left-to-right scanning of the input and the "R" is for constructing a
rightmost derivation in reverse.
5.2 WHY LR PARSING:
1. LR parsers can be constructed to recognize virtually all programming-language constructs for which context-free grammars can be written.
2. The LR parsing method is the most general non-backtracking shift-reduce parsing method known, yet it can be implemented as efficiently as other shift-reduce methods.
3. The class of grammars that can be parsed using LR methods is a proper subset of the class of grammars that can be parsed with predictive parsers.
4. An LR parser can detect a syntactic error as soon as it is possible to do so on a left -toright scan of the input.
The disadvantage is that it takes too much work to constuct an LR parser by hand for a typical programming-language grammar. But there are lots of LR parser generators available to make this
5.3 LR PARSERS:
LR(k) parsers are most general non-backtracking shift-reduce parsers. Two cases of interest are k=0 and k=1. LR(1) is of practical relevance
‘L’ stands for “Left-to-right” scan of input.
‘R’ stands for “Rightmost derivation (in reverse)”.
‘K’ stands for number of input symbols of look-a-head that are used in making parsing decisions.
When (K) is omitted, ‘K’ is assumed to be 1.
LR(1) parsers are table-driven, shift-reduce parsers that use a limited right context (1 token) for handle recognition.
LR(1) parsers recognize languages that have an LR(1) grammar. A grammar is LR(1) if, given a right-most derivation
S⇒r0⇒r1⇒r2- - - rn-1⇒rn⇒sentence.
We can isolate the handle of each right-sentential form ri and determine the production by which to reduce, by scanning ri from left-to-right, going atmost 1 symbol beyond the right end of the handle of
Parser accepts input when stack contains only the start symbol and no remaining input symbol are
LR(0) item: (no lookahead)
Grammar rule combined with a dot that indicates a position in its RHS.
Ex– 1: SI → .S$ S→.x S→.(L)
Ex-2: A→XYZ generates 4LR(0) items
The ‘.’ Indicates how much of an item we have seen at a given state in the parse.
A→.XYZ indicates that the parser is looking for a string that can be derived from XYZ.
A→XY.Z indicates that the parser has seen a string derived from XY and is looking for one
derivable from Z.
→ LR(0) items play a key role in the SLR(1) table construction algorithm.
→ LR(1) items play a key role in the LR(1) and LALR(1) table construction algorithms. LR parsers have more information available than LL parsers when choosing a production:
* LR knows everything derived from RHS plus ‘K’ lookahead symbols.
* LL just knows ‘K’ lookahead symbols into what’s derived from RHS.
Deterministic context free languages:
5.4 LR PARSING ALGORITHM:
The schematic form of an LR parser is shown below:
It consists of an input, an output, a stack, a driver program, and a parsing table that has two parts: action and goto.
The LR parser program determines Sm, the current state on the top of the stack, and ai, the current input symbol. It then consults action [Sm, ai], which can have one of four values:
1. Shift S, where S is a state.
2. reduce by a grammar production A→b
3. accept and
The function goes to takes a state and grammar symbol as arguments and produces a state. The goto function of a parsing table constructed from a grammar G using the SLR, canonical LR or LALR method is the transition function of DFA that recognizes the viable prefixes of G. (Viable prefixes of G are those prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser, because they do not extend past the right-most handle)