Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev

Compiler Design

Created by: Cstoppers Instructors

Computer Science Engineering (CSE) : Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev

The document Shift: Reduce 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)

SHIFT- REDUCE PARSING:
Shift Reduce Parsing uses a stuck to hold grammar symbols and input buffer to hold string to be parsed, because handles always appear at the top of the stack i.e., there’s no need to look deeper into 
the state.

A shift-reduce parser has just four actions: 
1. Shift-next word is shifted onto the stack (input symbols) until a handle is formed.
2. Reduce – right end of handle is at top of stack, locate left end of handle within the stack. Pop handle off stack and push appropriate LHS.
3. Accept – stop parsing on successful completion of parse and report success.
4. Error – call an error reporting/recovery routine.

3.1 Possible Conflicts: Ambiguous grammars lead to parsing conflicts.
1. Shift-reduce: Both a shift action and a reduce action are possible in the same state (should we shift or reduce)

Example: dangling-else problem

2. Reduce-reduce: Two or more distinct reduce actions are possible in the same state. (Which production should we reduce with 2). 
 

Example:

Stmt →id (param) (a(i) is procedure call)

Param→ id Expr → id

(expr) /id (a(i) is array subscript)

Stack input buffer action

$&aa (i ) &.$ Reduce by ?

Should we reduce to param or to expr? Need to know the type of a: is it an array or a function. This information must flow from declaration of a to this use, typically via a symbol table.
 

Shift – reduce parsing example: (Stack implementation)

Grammar: E→E+E/E*E/(E)/id Input: id1+id2+id3
 

One Scheme to implement a handle-pruning, bottom-up parser is called a shift-reduce parser. Shift

reduce parsers use stack and an input buffer.

The sequence of steps is as follows:
1. initialize stack with $.
2. Repeat until the top of the stack is the goal symbol and the input token is “end of life”. a. Find the handle 
If we don’t have a handle on top of stack, shift an input symbol onto the stack.

b.  Prune the handle

if we have a handle (A→b) on the stack, reduce (i) pop /b/ symbols off the stack (ii)push A onto the stack.
 

Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev
Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev
 

Example 2:
Goal à Expr
Expr à Expr + term | Expr – Term | Term
Term à Tem & Factor | Term | factor | Factor
Factor à number | id | (Expr) The expression grammar : x – z * y
 

Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev
 

Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev
1. shift until the top of the stack is the right end of a handle
2. Find the left end of the handle & reduce.
 

Procedure:
1. Shift until top of stack is the right end of a handle.
2. Find the left end of the handle and reduce.
* Dangling-else problem: 

stmt→if expr then stmt/if expr then stmt/other then example string is: if E1 then if E2 then S1 else S2 has two parse trees (ambiguity) and so this grammar is not of LR(k) type.
 

        Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev
 

       Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev

 

Share with a friend

Dynamic Test

Content Category

Related Searches

Objective type Questions

,

video lectures

,

Important questions

,

shortcuts and tricks

,

study material

,

Viva Questions

,

Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev

,

Sample Paper

,

past year papers

,

Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev

,

practice quizzes

,

mock tests for examination

,

Free

,

Exam

,

ppt

,

pdf

,

Semester Notes

,

Previous Year Questions with Solutions

,

Extra Questions

,

MCQs

,

Shift: Reduce Parsing Computer Science Engineering (CSE) Notes | EduRev

,

Summary

;