Implementing Shift Reduce Technique

Implementing Shift Reduce Technique

In this regard, the following two important questions must be answered

 How to detect the handle? (Without using right most derivation as shown in the above examples)

 What production is to be used when more than one production with same right side?

The operator precedence and LR parsers answer these questions in their own way

Implementing shift reduce technique can be easily done by using a data structure stack

Initially,  the parser starts with an empty stack with $ placed at its bottom and input to parsed w,  ended with $,  means that the initial configuration of the parser is,

Stack $

Input w$

Example 1:

Consider the Grammar

E → E + T

E → T

T → T * F

T → F

F → id

Input string: id₁ * id₂

The parsing table for the input string is:

Stack	Input	Action
$	id1*id2$	shift
$id2	*id2$	reduce by F→id
$F	*id2$	reduce by T→F
$T	*id2$	shift
$T*	id2$	shift
$T*id2	$	reduce by F→id
$T*F	$	reduce by T→T*F
$T	$	reduce by E→T
$E	$	Accept

Example 2:

Consider the grammar

E → E + E

E → E * E

E → (E)

E → id

Input String: id₁ * id₂ * id₃

The parsing table for the input string is:

Stack	Input	Action
$	id1 * id2 * id3 $	shift
$ id1	+ id2 * id3 $	reduce by E→id
$ E	+ id2 * id3 $	shift
$ E +	id2 * id3 $	shift
$E + id2	* id3 $	reduce by E→id
$ E + E	* id3 $	shift
$ E + E *	id3 $	shift
$E+E*id3	$	reduce by E→id
$ E + E*E	$	reduce by E→E * E
$ E + E	$	reduce by E→E + E
$ E	$	Accept

Advantages of Stack

• The handle is always found on the top of the stack only
• There is no need to go inside the stack to find a handle
• Stack makes the implementation of handle pruning easy

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.