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:

1. An input buffer for storing the input string.
2. 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: