Source
code:
#include<conio.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
void main()
{
char
fun[]={'f','g'},a[30][30],nt[20],t[20],b[30],var1,var[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,v,u,count1,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],c[20],d[20],B[20][20],LE[20][20],LET[20][20],last[20][20],GE[20][20],lastp[20][20],lastt[20][20],greater[20][20];
clrscr();
printf("Enter the no.of productions and
press enter:");
scanf("%d",&n);
// printf("Now Enter %d
productions:",n);
for(i=0;i<n;i++)
{
scanf("%s",a[i]);
}
t[0]='\0';
nt[0]='\0';
symbol[0]='\0';
first[i][j]='\0';
/*Separating 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)
{
var[0]=a[i][j];
var[1]='\0';
strcat(nt,var);
cnt++;
}
else if(a[i][j]!='=')
{
var[0]=a[i][j] ;
var[1]='\0';
strcat(t,var);
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])
{
var1=nt[i];
nt[i]=nt[j];
nt[j]=var1;
}
}
}
for(i=0;i<ct;i++)
{
for(j=i+1;t[j]!='\0';j++)
{
if(t[i]>t[j])
{
var1=t[i];
t[i]=t[j];
t[j]=var1;
}
}
}
/*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;
count1=2*count;
strcat(symbol,nt);
strcat(symbol,t);
printf("Nonterminals =
%s",nt);
printf("\n Terminals =
%s",t);
//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;LE[i][j]=0;LET[i][j]=0;
greater[i][j]=0; spm[i][j]='\0';GE[i][j]=0;
}
}
for(i=0;i<count1;i++)
{
for(j=0;j<count1;j++)
{
B[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;
}
// 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++;
}
//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;
}
}
}
//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;
}
//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++;
}
//find lastplus trans matrix
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
lastt[i][j]=last[j][i] ;
}
}
//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;
}
}
//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;
}
}
}
}
}
//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;
}
}
}
}
}
//greater than and equal matrix
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{if((equal[i][j]==1)||(greater[i][j]==1))
{
GE[i][j]=1;
}
}
}
//finding LE matrix
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{if((equal[i][j]==1)||(less[i][j]==1))
{
LE[i][j]=1;
}
}
}
//finding LET matrix
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
LET[i][j]=LE[j][i] ;
}
}
//finding B matrix
for(i=0;i<count;i++)
{ for(j=0;j<count;j++)
{ if(GE[i][j]==1)
{ v=count+j;
B[i][v]=1;
}
}
}
for(i=0;i<count;i++)
{ for(j=0;j<count;j++)
{ if(LET[i][j]==1)
{ u=count+i;
B[u][j]=1;
}
}
}
//
BP matrix
i=0;
while(i<count1)
{
for(j=0;j<count1;j++)
{
if(B[j][i]==1)
{
for(k=0;k<count1;k++)
{
B[j][k] = B[j][k] || B[i][k];
}
}
}
i++;
}
//BS matrix
i=0;
while(i<count1)
{
for(j=0;j<count1;j++)
{
if(B[j][i]==1)
{
for(k=0;k<count;k++)
{
B[j][k] = B[j][k] || B[i][k];
}
}
}
i++;
}
for(j=0;j<count1;j++)
{
for(k=0;k<count1;k++)
{
if(j==k)
{
B[j][k]=1;
}
}
}
//printing of BS matrix
printf("\n BS matrix is:");
printf("\n \t\t ");
for(j=0;j<count1;j++)
{
printf(" %3d",j);
}
for(i=0;i<count1;i++)
{
printf(" \n\t\t %d ",i);
for(j=0;j<count1;j++)
{
printf("%3d
",B[i][j]);
}
}
//Finding SPF
for(i=0;i<count;i++)
{
k=0;
for(j=0;j<count1;j++)
{
if(B[i][j]==1)
{
k++;
}
}
c[i]=k;
}
printf("\n");
for(i=count;i<count1;i++)
{
k=0;
for(j=0;j<count1;j++)
{
if(B[i][j]==1)
{
k++;
}
}
d[i]=k;
}
//print SPF matrix
printf("\n");
printf("SPF matrix is:");
printf("\n\t\t\t\t ");
for(j=0;j<count;j++)
{
printf("%2c",symbol[j]);
}
printf("\n");
for(i=0;i<2;i++)
{
printf("\n\t\t\t\t%c",fun[i]);
if(fun[i]=='f')
{
for(j=0;j<count;j++)
{
printf("%2d",c[j]);
}
}
else if(fun[i]=='g')
{
for(j=count;j<count1;j++)
{
printf("%2d",d[j]);
}
}
printf("\n");
}
getch();
}
Output:
Enter the no.of productions
and press enter:4
Z=bMb M=a M=(L
L=Ma)
Nonterminals =
LMZ
Terminals = ()ab
BS matrix is:
0 1
2 3 4
5 6 7
8 9 10
11 12 13
0 1
1 0 1
0 0 1
1 1 0
0 0 1 1
1 0
1 0 1
0 0 1
1 1 0
0 0 1 1
2 0
0 1 0
0 0 0
0 0 0
0 0 0 0
3 0
0 0 1
0 0 0
1 0 0
0 0 0 0
4 0
1 0 1
1 0 1
1 1 0
0 0 1 1
5 0
1 0 1
0 1 1
1 1 0
0 1 1 1
6 0
0 0 1
0 0 1
1 1 0 0 0
0 0
7 0
0 0 1
0 0 0
1 0 0
0 0 0 0
8 0
0 0 1
0 0 1
1 1 0
0 0 0 0
9 0
0 0 0
0 0 0
0 0 1
0 0 0 0
10 0
0 0 1
0 0 1
1 1 0
1 0 0 0
11 0
1 0 1
0 1 1
1 1 0
0 1 1 1
12 0
1 0 1
0 0 1
1 1 0
0 0 1 1
13 0
1 0 1
0 0 1
1 1 0
0 0 1 1
SPF matrix is:
L M Z ( ) a b
f 8 7 1 2 8 9 4
g 2 4 1 5 9 7 7
No comments:
Post a Comment
If you have any doubts please let me know