The document LR Parsing Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Compiler Design.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**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

task easy.

**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

ri.

Parser accepts input when stack contains only the start symbol and no remaining input symbol are

left.

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

A→.XYZ

A→X.YZ

A→XY.Z

A→XYZ.

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 4. error **

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)

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

16 videos|44 docs|29 tests