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");
}
getch();
}
Output:
Enter the no. of productions4
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
No comments:
Post a Comment
If you have any doubts please let me know