source code

#include
#include
#include
#include
#include
class prod
{
public:
char a[10];
prod *rt;
}
pc[20],*temp=NULL;
void main()
{
clrscr();
int np,end=-1,chpt,j;
char str[25],tmp1[25],tmp2[25];
cout<<"Enter the no.of.productions:";
cin>>np;
for(int i=0;i{
cout<<"\n Enter production"<cout<<"Enter L.H.S:";
cin>>pc[i].a;
cout<<"Enter R.H.S:";
cin>>str;
pc[i].rt=new(prod);
temp=pc[i].rt;
strcpy(temp->a,"");
temp->rt=NULL;
for(j=0;str[j]!='\0';j++)
{
if(str[j]=='|')
{
temp->rt=new(prod);
temp=temp->rt;
strcpy(temp->a,"");
temp->rt=NULL;
continue;
}
tmp1[0]=str[j];
tmp1[1]='\0';
strcat(temp->a,tmp1);
}
}
strstart:
cout<<"\n\n";
for(i=0;i{
cout<";
temp=pc[i].rt;
while(temp!=NULL)
{
if(temp!=pc[i].rt)
cout<<"|";
cout<a;
temp=temp->rt;
}
cout<<"\n\n";
}
end=-1;
cout<<"Enter the input string:";
cin>>str;
cout<<"\n\n\t ACTION STACK \t\t INPUT \n\n";
strcpy(tmp1,"");
for(i=0;str[i]!='\0';i++)
{
end++;
tmp1[end]=str[i];
tmp1[end+1]='\0';
cout<<"\t Shift "<for(j=j+1;str[j]!='\0';j++)
cout<cout<<"\n\n";
getch();
doagain:
chpt=0;
for(j=0;j{
strcpy(tmp2,"");
for(int k=j,l=0;k<=strlen(tmp1);k++,l++)
tmp2[l]=tmp1[k];
tmp2[l]='\0';
for(l=0;l{
temp=pc[l].rt;
while(temp!=NULL)
{
if(strcmp(temp->a,tmp2)==0 && strlen(tmp2)==1 &&(((int)tmp2[0]<=122 && (int)tmp2[0]>=97) || ((int)tmp2[0]<=57 && (int)tmp2[0]>=48)))
{
if(strcmp(tmp2,pc[l].a)!=0)
chpt=1;
strcpy(tmp2,pc[l].a);
for(k=j,l=0;k{
if(tmp2[l]!='\0')
tmp1[k]=tmp2[l];
else
{
l--;
tmp1[k]='^';
}
}
strcpy(tmp2,"");
for(k=0,l=0;k{
if(tmp1[k]!='^')
tmp2[l]=tmp1[k];
else
l--;
}
tmp2[l]='\0';
strcpy(tmp1,tmp2);
cout<<"\tReduce "<for(k=i+1;str[k]!='\0';k++)
cout<cout<<"\n\n";
getch();
break;
}
temp=temp->rt;
}
}
}
if(chpt==1)
goto doagain;
}
doagain1:
chpt=0;
for(j=0;j{
strcpy(tmp2,"");
for(int k=j,l=0;ktmp2[l]=tmp1[k];
tmp2[l]='\0';
for(l=0;l{
temp=pc[l].rt;
while(temp!=NULL)
{
if(strcmp(temp->a,tmp2)==0)
{
if(strcmp(tmp2,pc[l].a)!=0)
chpt=1;
strcpy(tmp2,pc[l].a);
for(k=j,l=0;k{
if(tmp2[l]!='\0')
tmp1[k]=tmp2[l];
else
{
l--;
tmp1[k]='^';
}
}
strcpy(tmp2,"");
for(k=0,l=0;k{
if(tmp1[k]!='^')
tmp2[l]=tmp1[k];
else
l--;
}
tmp2[l]='\0';
strcpy(tmp1,tmp2);
cout<<"\t Reduce "<getch();
break;
}
temp=temp->rt;
}
}
}
if(chpt==1)
goto doagain1;
if(strcmp(tmp1,pc[0].a)==0)
cout<<"\n Accepted \n\n";
else
cout<<"\n Rejected \n\n";
getch();
cout<<"Another string:";
cin>>tmp1[0];
if(tmp1[0]=='Y')
{
strcpy(tmp1,"");
strcpy(tmp2,"");
clrscr();
goto strstart;
}
exit(0);
}

Output:

Enter the no of productions:1
Enter the production 1…
Enter LHS:E
Enter RHS:E*E|E+E|a
E->E*E|E+E|a
Enter input string:a*a+a

Action Stack Input
SHIFT a *a+a
REDUCE E *a+a
SHIFT E* a+a
SHIFT E*a +a
REDUCE E*E +a
SHIFT E*E+ a
SHIFT E*E+a
REDUCE E*E+E
REDUCE E*E
REDUCE E
Accepted