in

Compiler Design : Shift Reducing Parsing in C

We know that Shift Reduce Parsing is a important concept in Language Processors i.e Compiler Design . When we give input string id*id+id or any of these type of strings , it gets parsed ( Shift or Reduce action )in accordance to the production rules.

In the given program below , the grammar used is

E->E+E
E->E*E
E->(E)
E->id

and you may encounter a warning like

warning: the `gets’ function is dangerous and should not be used.

which can be ignored.

Program for Shift Reducing Parsing in C

#include<stdio.h>
#include<string.h>
int k=0,z=0,i=0,j=0,c=0;
char a[16],ac[20],stk[15],act[10];
void check();
int main()
   {
      puts(“GRAMMAR is E->E+E \n E->E*E \n E->(E) \n E->id”);
      puts(“enter input string “);
      gets(a);
      c=strlen(a);
      strcpy(act,”SHIFT->”);
      puts(“stack \t input \t action”);
      for(k=0,i=0; j<c; k++,i++,j++)
       {
         if(a[j]==’i’ && a[j+1]==’d’)
           {
              stk[i]=a[j];
              stk[i+1]=a[j+1];
              stk[i+2]=’\0′;
              a[j]=’ ‘;
              a[j+1]=’ ‘;
              printf(“\n$%s\t%s$\t%sid”,stk,a,act);
              check();
           }
         else
           {
              stk[i]=a[j];
              stk[i+1]=’\0′;
              a[j]=’ ‘;
              printf(“\n$%s\t%s$\t%ssymbols”,stk,a,act);
              check();
           }
       }
   }
void check()
   {
     strcpy(ac,”REDUCE TO E”);
     for(z=0; z<c; z++)
       if(stk[z]==’i’ && stk[z+1]==’d’)
         {
           stk[z]=’E’;
           stk[z+1]=’\0′;
           printf(“\n$%s\t%s$\t%s”,stk,a,ac);
           j++;
         }
     for(z=0; z<c; z++)
       if(stk[z]==’E’ && stk[z+1]==’+’ && stk[z+2]==’E’)
         {
           stk[z]=’E’;
           stk[z+1]=’\0′;
           stk[z+2]=’\0′;
           printf(“\n$%s\t%s$\t%s”,stk,a,ac);
           i=i-2;
         }
     for(z=0; z<c; z++)
       if(stk[z]==’E’ && stk[z+1]==’*’ && stk[z+2]==’E’)
         {
           stk[z]=’E’;
           stk[z+1]=’\0′;
           stk[z+1]=’\0′;
           printf(“\n$%s\t%s$\t%s”,stk,a,ac);
           i=i-2;
         }
     for(z=0; z<c; z++)
       if(stk[z]=='(‘ && stk[z+1]==’E’ && stk[z+2]==’)’)
         {
           stk[z]=’E’;
           stk[z+1]=’\0′;
           stk[z+1]=’\0′;
           printf(“\n$%s\t%s$\t%s”,stk,a,ac);
           i=i-2;
         }
   }
Output : 
GRAMMAR is E->E+E
E->E*E
E->(E)
E->id
enter input string
id+id*id+id
stack              input                  action
$              id +id*id+id$         SHIFT->id
$E               +id*id+id$         REDUCE TO E
$E+               id*id+id$         SHIFT->symbols
$E+id           *    id+id$         SHIFT->id
$E+E                *id+id$         REDUCE TO E
$E                     *id+id$         REDUCE TO E
$E*                     id+id$         SHIFT->symbols
$E*id                     +id$         SHIFT->id
$E*E                      +id$         REDUCE TO E
$E                           +id$          REDUCE TO E
$E+                           id$          SHIFT->symbols
$E+id                           $          SHIFT->id
$E+E                            $          REDUCE TO E
$E                                 $          REDUCE TO E
Screenshot :
Program-Shift-Reduce-Parsing-Compiler-Design-C-Language-1
PS: The above screenshot is from Putty C- Compiler.

Written by Suryanarayana Murthy

Computer Grad. Web Nerd. Tech Enthusiast. I run this blog 😎

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Loading…