Source code:
#include<conio.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
void main()
{
char
a[30][30],nt[20],t[20],b[30],temp1,temp[2],ch,ch1,symbol[30],mid[10][10],spm[10][10],string[20],string1,symb,handle[10],sp[20][20];
int n,i,j,m,count,cnt=0,ct=0,
k,l,p,q,px,py,x,s,y,z,first[20][20],firstp[20][20],firsts[20][20];
int
equal[20][20],less[20][20],last[20][20],lastp[20][20],lastt[20][20],greater[20][20];
clrscr();
printf("Enter the no. of
productions\n");
scanf("%d",&n);
t[0]='\0';
nt[0]='\0';
symbol[0]='\0';
first[i][j]='\0';
printf("Enter the productions");
for(i=0;i<n;i++)
{
scanf("%s",a[i]);
}
/*Separatinn of terminals &
nonterminals*/
for(i=0;i<n;i++)
{
for(j=0;a[i][j]!='\0';j++)
{
if(a[i][j]>=65 && a[i][j]<=90)
{
temp[0]=a[i][j];
temp[1]='\0';
strcat(nt,temp);
cnt++;
}
else if(a[i][j]!='=')
{
temp[0]=a[i][j] ;
temp[1]='\0';
strcat(t,temp);
ct++;
}
}
}
/*Sorting the array for terminals &
nonterminals*/
for(i=0;i<cnt;i++)
{
for(j=i+1;nt[j]!='\0';j++)
{
if(nt[i]>nt[j])
{
temp1=nt[i];
nt[i]=nt[j];
nt[j]=temp1;
}
}
}
for(i=0;i<ct;i++)
{
for(j=i+1;t[j]!='\0';j++)
{
if(t[i]>t[j])
{
temp1=t[i];
t[i]=t[j];
t[j]=temp1;
}
}
}
/*Removing duplicats for nonterminals*/
i=1;
while (nt[i-1]!=nt[i] && i<cnt)
{
i=i+1;
}
if (nt[i-1]!=nt[i])
{
i=i+1;
}
j=i-1;
while (i<cnt)
{
i=i+1;
if (nt[i-1]!=nt[i])
{
j=j+1;
nt[j]=nt[i];
}
}
cnt=j;
/*Removing duplicates from terminals*/
k=1;
while(t[k-1]!=t[k] && k<ct)
{
k=k+1;
}
if (t[k-1]!=t[k])
{
k=k+1;
}
l=k-1;
while (k<ct)
{
k=k+1;
if (t[k-1]!=t[k])
{
l=l+1;
t[l]=t[k];
}
}
ct=l;
count=ct+cnt;
strcat(symbol,nt);
strcat(symbol,t);
printf("\n");
printf("\n Nonterminals =
%s",nt);
printf("\n Terminals =
%s",t);
printf("\nsymbols are =
%s",symbol);
//Matrix Initializing
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
first[i][j]=0;
firstp[i][j]=0; firsts[i][j]=0;
last[i][j]=0;lastp[i][j]=0;lastt[j][i]=0;
equal[i][j]=0; less[i][j]=0; mid[i][j]=0;
greater[i][j]=0; spm[i][j]='0';
}
}
//First Matrix
for(i=0;i<n;i++)
{
ch=a[i][0];
for(p=0;p<count;p++)
{
if(ch==symbol[p])
{
px=p;
}
}
ch=a[i][2];
for(q=0;q<count;q++)
{
if(ch==symbol[q])
{
py=q;
}
}
first[px][py]=1;
}
/* printf("
\n firstmatrix is");
printf(" \n \t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c ",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d ",first[i][j]);
}
printf("\n");
}
//
Firstplus matrix*/
i=0;
while(i<count)
{
for(j=0;j<count;j++)
{
if(first[j][i]==1)
{
for(k=0;k<count;k++)
{
first[j][k] = first[j][k] || first[i][k];
}
}
}
i++;
}
/*
printf(" \n firstp matrix
is");
printf(" \n \t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c ",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d ",first[i][j]);
}
printf("\n");
}
//find firsts matrix ------*/
i=0;
while(i<count)
{
for(j=0;j<count;j++)
{
if(first[j][i]==1)
{
for(k=0;k<count;k++)
{
first[j][k] = first[j][k] || first[i][k];
}
}
}
i++;
}
for(j=0;j<count;j++)
{
for(k=0;k<count;k++)
{
if(j==k)
{ first[j][k]=1;
}
}
}
//print first
star matrix
/* printf(" \n firsts matrix
is");
printf(" \n \t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c ",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d ",first[i][j]);
}
printf("\n");
}
*/
//find last matrix
for(i=0;i<n;i++)
{
ch=a[i][0];
for(p=0;p<count;p++)
{
if(ch==symbol[p])
{
px=p;
}
}
m=strlen(a[i]);
ch=a[i][m-1];
for(q=0;q<count;q++)
{
if(ch==symbol[q])
{
py=q;
}
}
last[px][py]=1;
}
// print last matrix
/* printf("\n
lastmatrix is");
printf("\n \t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c ",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d ",last[i][j]);
}
printf("\n");
}*/
//last plus
matrix
i=0;
while(i<count)
{
for(j=0;j<count;j++)
{
if(last[j][i]==1)
{
for(k=0;k<count;k++)
{
last[j][k] = last[j][k] || last[i][k];
}
}
}
i++;
}
//print last plus
/*printf(" \n lastp matrix
is");
printf(" \n \t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c ",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d ",last[i][j]);
}
printf("\n");
}*/
//find lastpt matrix
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
lastt[i][j]=last[j][i] ;
}
}
/* printf("\n lastt
matrix is");
printf("\n
\t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c
",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d
",lastt[i][j]);
}
printf("\n");
} */
//find equal mat
for(i=0;i<n;i++)
{
ch=a[i][2];
for(p=0;p<count;p++)
{
if(ch==symbol[p])
px=p;
}
for(k=3;k<strlen(a[i]);k++)
{
ch=a[i][k];
for(q=0;q<count;q++)
{
if(ch==symbol[q])
py=q;
}
equal[px][py]=1;
px=py;
}
}
//print equal matrix
/* printf("\equal matrix
is");
printf("\n
\t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c
",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d
",equal[i][j]);
}
printf("\n");
} */
//less than matrix
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
if(equal[i][j]==1)
{
for(k=0;k<count;k++)
{
if(first[j][k]==1)
{
less[i][k]=1;
}
}
}
}
}
//print Less than Mat
/* printf("\n
less than matrix is");
printf("\n
\t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c
",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d
",less[i][j]);
}
printf("\n");
}*/
//greater than mat
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
if(equal[i][j]==1)
{
for(k=0;k<count;k++)
{
if(first[j][k]==1)
{
mid[i][k]=1; /*product of equal & firststar */
}
}
}
}
}
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
if(lastt[i][j]==1)
{
for(k=0;k<count;k++)
{
if(mid[j][k]==1)
{
greater[i][k]=1;
}
}
}
}
}
//print mid mat
/*printf("\n mid matrix
is");
printf("\n \t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c
",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d
",mid[i][j]);
}
printf("\n");
}
//print greater mat
/* printf("\ngreater
than matrix is");
printf("\n
\t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("
%c",symbol[j]);
}
printf( " \n
");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c
",symbol[i]);
for(j=0;j<count;j++)
{
printf("%2d
",greater[i][j]);
}
printf("\n");
}*/
//finding spm
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
if(equal[i][j]==1)
{
spm[i][j]='=';
}
else
if(less[i][j]==1)
{
spm[i][j]='<';
}
else
if(greater[i][j]==1)
{
spm[i][j]='>';
}
}
}
//print SPM
printf("\n");
printf("Simple Precedence Matrix is:");
printf("\n \t\t\t\t ");
for(j=0;j<strlen(symbol);j++)
{
printf("%2c",symbol[j]);
}
printf(" \n ");
for(i=0;i<count;i++)
{
printf(" \n \t\t\t\t %c" ,symbol[i]);
for(j=0;j<count;j++)
{
printf("%2c",spm[i][j]);
}
printf("\n");
}
//PARSING
printf("Enter the string for
parsing");
scanf("%s",string);
printf("\n");
for(i=0;i<count;i++)
{
for(j=2;j<strlen(string);j++)
{
sp[i][j-2]=a[i][j];
}
sp[i][j-2] ='\0';
}
for(j=0;j<strlen(string);j++)
{
i=0;
while(i<strlen(string))
{
if(string[i]=='#' &&
strlen(string)>3)
{
symb='<';
}
else if(string[i+1]=='#' &&
strlen(string)>3)
{
symb='>';
}
else
{
ch=string[i];
for(p=0;p<count;p++)
{
if(ch==symbol[p])
px=p;
}
ch1=string[i+1];
for(q=0;q<count;q++)
{
if(ch1==symbol[q])
py=q;
}
symb=spm[px][py];
}
if(symb=='=')
{
i=i;
}
else if(symb=='<')
{
m=i;
}
else if(symb=='>')
{
s=0;
for(k=m+1;k<=i;k++)
{
handle[s]=string[k];
s++;
}
handle[s]='\0';
for(x=0;x<n;x++)
{
if(strcmp(handle,sp[x])==0)
{
printf("\n Handle is %s and
%c",sp[x],a[x][0]);
string[m+1]=a[x][0];
if(s>1)
{
z=m+s+1;
y=m+2;
while(string[z]!='\0')
{
string[y]=string[z];
z++;
y++;
}
string[y]='\0';
}
i=0;
s=0;
printf("string is %s",string);
}
}
}
i++;
}
}
getch();
}
Output:
Enter the no. of productions
4
Enter the productionsZ=bMb M=a M=(L L=Ma)
Nonterminals =
LMZ
Terminals =
()ab
symbols are = LMZ()ab
Simple Precedence Matrix is:
L M Z ( ) a b
L 0 0 0 0 0
> >
M 0 0 0 0 0 =
=
Z 0 0 0 0 0 0
0
( = < 0
< 0 < 0
) 0 0 0 0 0
> >
a 0 0 0 0 =
> >
b 0 = 0 < 0
< 0
Enter the string for parsing#b(aa)b#
Handle is a and
Mstring is #b(Ma)b#
Handle is Ma)
and Lstring is #b(Lb#
Handle is (L
and Mstring is #bMb#
Handle is bMb
and Zstring is #Z#
No comments:
Post a Comment
If you have any doubts please let me know