SHIFT REDUCE PARSER
To write a c program for implementing the shift reduce parser. The grammar used in this program is
E->E+E
E->E*E
E->(E)
E->id
This program works for all possible input strings. Lets take the input string (id*id)+id
Program:
#include<stdio.h>
#include<conio.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();
void main()
{
clrscr();
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();
}
}
getch();
}
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:
#include
ReplyDelete#include
#include
char ip_sym[15],stack[15];
int ip_ptr=0,st_ptr=0,len,i;
char temp[2],temp2[2];
char act[15];
void check();
void main()
{
printf("\n\t\t SHIFT REDUCE PARSER\n");
printf("\n GRAMMER\n");
printf("\n E->E+E\n E->E/E");
printf("\n E->E*E\n E->a/b");
printf("\n enter the input symbol:\t");
gets(ip_sym);
printf("\n\t stack implementation table");
printf("\n stack\t\t input symbol\t\t action");
printf("\n______\t\t ____________\t\t ______\n");
printf("\n $\t\t%s$\t\t\t--",ip_sym);
strcpy(act,"shift ");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
len=strlen(ip_sym);
for(i=0;i<=len-1;i++)
{
stack[st_ptr]=ip_sym[ip_ptr];
stack[st_ptr+1]='\0';
ip_sym[ip_ptr]=' ';
ip_ptr++;
printf("\n $%s\t\t%s$\t\t\t%s",stack,ip_sym,act);
strcpy(act,"shift ");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
check();
st_ptr++;
}
st_ptr++;
check();
}
void check()
{
int flag=0;
temp2[0]=stack[st_ptr];
temp2[1]='\0';
if((!strcmp(temp2,"a"))||(!strcmp(temp2,"b")))
{
stack[st_ptr]='E';
if(!strcmp(temp2,"a"))
printf("\n $%s\t\t%s$\t\t\tE->a",stack, ip_sym);
else
printf("\n $%s\t\t%s$\t\t\tE->b",stack,ip_sym);
flag=1;
}
if((!strcmp(temp2,"+"))||(!strcmp(temp2,"*"))||(!strcmp(temp2,"/")))
{
flag=1;
}
if((!strcmp(stack,"E+E"))||(!strcmp(stack,"E/E"))||(!strcmp(stack,"E*E")))
{
strcpy(stack,"E");
st_ptr=0;
if(!strcmp(stack,"E+E"))
printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);
else
if(!strcmp(stack,"E/E"))
printf("\n $%s\t\t %s$\t\t\tE->E/E",stack,ip_sym);
else
printf("\n $%s\t\t%s$\t\t\tE->E*E",stack,ip_sym);
flag=1;
}
if(!strcmp(stack,"E")&&ip_ptr==len)
{
printf("\n $%s\t\t%s$\t\t\tACCEPT",stack,ip_sym);
exit(0);
}
if(flag==0)
{
printf("\n%s\t\t\t%s\t\t reject",stack,ip_sym);
}
if(strcmp(stack,"E")&&ip_ptr==len)
printf("Reject");
return;
}
More Precise----
ReplyDelete#include
#include
char input[15],stack[15];
int ip_ptr=0,st_ptr=0,len,i;
char temp[2],temp2[2];
char act[15];
void check();
void main()
{
printf("\n GRAMMER\n\n E->E+E\n E->E/E\n E->E*E\n E->a|b");
printf("\n enter the input symbol: ");
gets(input);
printf("\n\t stack implementation table\n");
printf("\n stack\t\t input symbol\t\t action\n");
printf("\n $\t\t%s$",input);
strcpy(act,"shift ");
temp[0]=input[ip_ptr];
temp[1]='\0';
strcat(act,temp);
len=strlen(input);
for(i=0;i<=len-1;i++)
{
stack[st_ptr]=input[ip_ptr];
stack[st_ptr+1]='\0';
input[ip_ptr]=' ';
ip_ptr++;
printf("\n $%s\t\t%s$\t\t\t%s",stack,input,act);
strcpy(act,"shift ");
temp[0]=input[ip_ptr];
temp[1]='\0';
strcat(act,temp);
check();
st_ptr++;
}
st_ptr++;
check();
}
void check()
{
int flag=0;
temp2[0]=stack[st_ptr];
temp2[1]='\0';
if((!strcmp(temp2,"a"))||(!strcmp(temp2,"b")))
{
stack[st_ptr]='E';
if(!strcmp(temp2,"a"))
printf("\n $%s\t\t%s$\t\t\tE->a",stack, input);
else
printf("\n $%s\t\t%s$\t\t\tE->b",stack,input);
flag=1;
}
if((!strcmp(temp2,"+"))||(!strcmp(temp2,"*"))||(!strcmp(temp2,"/")))
{
flag=1;
}
if((!strcmp(stack,"E+E"))||(!strcmp(stack,"E/E"))||(!strcmp(stack,"E*E")))
{
//strcpy(stack,"E");
st_ptr=0;
if(!strcmp(stack,"E+E"))
{
strcpy(stack,"E");
printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,input);
}
else if(!strcmp(stack,"E/E"))
{
strcpy(stack,"E");
printf("\n $%s\t\t %s$\t\t\tE->E/E",stack,input);
}
else if(!strcmp(stack,"E*E"))
{
strcpy(stack,"E");
printf("\n $%s\t\t%s$\t\t\tE->E*E",stack,input);
}
flag=1;
}
if(!strcmp(stack,"E")&&ip_ptr==len)
{
printf("\n $%s\t\t%s$\t\t\tACCEPT",stack,input);
exit(0);
}
if(flag==0)
{
printf("\n%s\t\t\t%s\t\t Reject",stack,input);
exit(0);
}
if(strcmp(stack,"E")&&ip_ptr==len)
{
printf("Reject");
exit(0);
}
return;
}
C code for Shift reduce parsing for the grammar
ReplyDeleteE->E+T|T T->T*F|F F->(E)|id
The following code can be used for any grammar. Just feed in the grammar and check for parsing. You only need to change the number of production rules (nop) and provide the grammar, one production at a time.
ReplyDelete/*
Grammar:
E->E*E
E->E+E
E->(E)
E->x
*/
#include
#include
#include
char Stk[10],ip[10];
int top=-1;
char G[5][10];
int main(){
int nop=4;//no of rules
int i,j,len,k,l;
//char akn;
char Stk_str[10];
char *rhs;
int flag=0; //1 when reduced
//int parse=1,shift=1,reduce=1;
clrscr();
//Store the Grammar--Hardcoding
strcpy(G[0],"E->E*E\0");
strcpy(G[1],"E->E+E\0");
strcpy(G[2],"E->(E)\0");
strcpy(G[3],"E->x\0");
//print the grammar
printf("\n The Grammar is: \n");
for(i=0;i0){
Stk[top]='\0';
top--;
l--;
}
printf("\nStack after popping:%s\n ",Stk);
Stk[++top]=G[j][0];
printf("\nStack after reduce: %s\n",Stk);
flag=1;
// reduce=1;
break;
}
}
}
if(flag==0){ //cannot be reduced, thus shift
if(ip[i]!='$'){
Stk[++top]=ip[i];
printf("After Shift: \nStk: %s",Stk);
i++;
}
else break;//can neither be shifted nor reduced
}
flag=0; getch();
}
if(strcmpi(Stk,"$E")==0 && ip[i]=='$')
printf("\nParsing Successful\n");
else printf("\nInvalid String\n");
getch();
return 0;
}//end of main
sands casino | Seattle's Premier Casino
ReplyDeleteLocated on the banks of the Colorado 제왕카지노 River, the Sands Casino is Seattle's premier destination septcasino casino resort boasting 1700 slots, 50 table games, Hours of operation: 24-hour หาเงินออนไลน์ Casino: Yes; Live GamingPhone: 1-800-522-4700 Rating: 4 · 2,762 votes