Shift Reduce Parsing in Compiler Design
Like the bottom-up parsing, the shift reduce parser also builds the parse tree from the leaves (bottom) to the root (up). The LR parser is a more versatile variation of the shift-reduce parser.
Shift Reduce Parser requires two Data Structures:
- An input buffer for storing the input string.
- Stack for storing and accessing the production rules.
Basic Operations:
- Shift: In this operation, symbols from the input buffer are transferred to the stack.
- Reduce: If the handle appears on top of the stack, then it is reduced using the proper production rule, which push the LHS of a production rule into the stack and pop out the RHS of a production rule from it.
- Accept: The parsing operation is referred to as accepting if the stack contains only the start symbol, and the input buffer is empty. When the acceptable action is achieved, successful parsing gets take place.
- Error: In this case, the parser is unable to perform shift action, decrease action, or even accept action.
Example 1:
Consider the grammar:
S –> S + S
S –> S * S
S –> id
Applying shift reduce parsing to the input string "id + id + id".
Stack | Input Buffer | Parsing Action |
$ | id+id+id$ | Shift |
$id | +id+id$ | Reduce S->id |
$S | +id+id$ | Shift |
$S+ | id+id$ | Shift |
$S+id | +id$ | Reduce S->id |
$S+S | +id$ | Reduce S->S+S |
$S | +id$ | Shift |
$S+ | id$ | Shift |
$S+id | $ | Reduce S->id |
$S+S | $ | Reduce S->S+S |
$S | $ | Accept |
Example 2:
Consider the grammar:
E –> 2E2
E –> 3E3
E –> 4
Applying shift reduce parsing to the input string "32423"
Stack | Input Buffer | Parsing Action |
$ | 32423$ | Shift |
$3 | 2423$- | Shift |
$32 | 423$ | Shift |
$324 | 23$ | Reduce by E?4 |
$32E | 23$ | Shift |
$32E2 | 3$ | Reduce by E?2E2 |
$3E | 3$ | Shift |
$3E3 | $ | Reduce by E?3E3 |
$E | $ | Accept |
Example 3:
Consider the grammar:
S –> ( L ) | a
L –> L , S | S
Applying shift reduce parsing to the input string "(a,(a,a))”
Stack | Input Buffer | Parsing Action |
$ | (a,(a,a))$ | Shift |
$( | a,(a,a))$ | Shift |
$(a | ,(a,a))$ | Reduce S?a |
$(S | ,(a,a))$ | Reduce L ?S |
$(L | ,(a,a))$ | Shift |
$(L, | (a,a))$ | Shift |
$(L,( | a,a))$ | Shift |
$(L,(a | ,a))$ | Shift |
$(L,(S | ,a))$ | Reduce S?a |
$(L,(L | ,a))$ | Shift |
$(L,(L,a | ))$ | Reduces S?a |
$(L,(L,S) | ))$ | Reduces L?L,S |
$(L,(L | ))$ | Shift |
$(L,(L) | )$ | Reduces S?(L) |
$(L,S | )$ | Reduces L?L,S |
$(L | )$ | Shift |
$(L) | $ | Reduces S?(L) |
$S | $ | Accept |
Implementation of Shift Reduce Parsing in C++:
// Including libraries that is required for the operation
#include <bits/stdc++.h>
using namespace std;
// These are Global Variables
int z = 0, i = 0, j = 0, c = 0;
// You have to modify the array so that it's size could be increased
// Parsing will be done as per the length of string
char ab[16], ace[20], stak[15], act[10];
/* This Function's purpose is to check whether
a production rule
which is to be Reduce is in the stack.
Rules can be E->2E2 , E->3E3 , E->4 */
void checking()
{
// Copied string is to be printed as an action
strcpy(ace,"REDUCE TO E -> ");
// c=length of string that is taken as input
for(z = 0; z < c; z++)
{
// checking for producing rule E->4
if(stak[z] == '4')
{
printf("%s4", ace);
stak[z] = 'E';
stak[z + 1] = '\0';
//printing the action
printf("\n$%s\t%s$\t", stak, ab);
}
}
for(z = 0; z < c - 2; z++)
{
// checking for another production
if(stak[z] == '2' && stak[z + 1] == 'E' &&
stak[z + 2] == '2')
{
printf("%s2E2", ace);
stak[z] = 'E';
stak[z + 1] = '\0';
stak[z + 2] = '\0';
printf("\n$%s\t%s$\t", stak, ab);
i = i - 2;
}
}
for(z = 0; z < c - 2; z++)
{
//checking for E->3E3
if(stak[z] == '3' && stak[z + 1] == 'E' &&
stak[z + 2] == '3')
{
printf("%s3E3", ace);
stak[z]='E';
stak[z + 1]='\0';
stak[z + 1]='\0';
printf("\n$%s\t%s$\t", stak, ab);
i = i - 2;
}
}
return ; // return to main
}
// It is ab Driver Function
int main()
{
printf("GRAMMAR is -\nE->2E2 \nE->3E3 \nE->4\n");
// ab is input string
strcpy(ab,"32423");
// strlen(ab) will return the length of ab to c
c=strlen(ab);
// "SHIFT" is copied to act to be printed
strcpy(act,"SHIFT");
// This will print Labels (column name)
printf("\nstack \t input \t action");
// This will print the initial
// values of stack and input
printf("\n$\t%s$\t", ab);
// This will Run upto length of input string
for(i = 0; j < c; i++, j++)
{
// Printing action
printf("%s", act);
// Pushing into stack
stak[i] = ab[j];
stak[i + 1] = '\0';
// Moving the pointer
ab[j]=' ';
// Printing action
printf("\n$%s\t%s$\t", stak, ab);
// Call checking function ..which will
// checking the stack whether its contain
// any production or not
checking();
}
// Rechecking last time if contain
// any valid production then it will
// replace otherwise invalid
checking();
// if top of the stack is E(starting symbol)
// then it will accept the input
if(stak[0] == 'E' && stak[1] == '\0')
printf("Accept\n");
else //else reject
printf("Reject\n");
}
Output:
GRAMMAR is -
E->2E2
E->3E3
E->4
stack input action
$ 32423$ SHIFT
$3 2423$ SHIFT
$32 423$ SHIFT
$324 23$ REDUCE TO E -> 4
$32E 23$ SHIFT
$32E2 3$ REDUCE TO E -> 2E2
$3E 3$ SHIFT
$3E3 $ REDUCE TO E -> 3E3
$E $ Accept
Picture of output terminal: