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: id1 * id2
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: id1 * id2 * id3
The parsing table for the input string is:
Stack
|
Input
|
Action
|
$
|
id1 * id2 * id3 $
|
shift
|
$
|
+ id2 * id3 $
|
reduce by E→id
|
$ E
|
+ id2 * id3 $
|
shift
|
$ E +
|
id2 * id3 $
|
shift
|
$E +
|
* id3 $
|
reduce by E→id
|
$ E + E
|
* id3 $
|
shift
|
$ E + E *
|
id3 $
|
shift
|
$E+E*
|
$
|
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
Home
|
