LR Parsing | Compiler Design - Computer Science Engineering (CSE) PDF Download

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)