Friday, 31 July 2020
9. PARSING OF INPUT STRING USING THE GIVEN SPF
Source code:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
void main()
{
int i,j,n,k=0,l=0,p=0,z=0,d=0,r=0,y=0;
int c[20],m,ch,mx,my,x,x1,s1,flag;
char
pr[20][20],s[20],ntt[20],nt[10],t[10],pa[20];
char string[20],string1[10][10],sym,ch1,ch2,handle[20];
clrscr();
printf("Enter the no. of
productions");
scanf("%d",&n);
printf("\nEnter the
productions");
for(i=0;i<n;i++)
{
scanf("%s",&pr[i]);
}
for(i=0;i<n;i++)
{
m=strlen(pr[i]);
for(j=0;j<m;j++)
{
s[k]=pr[i][j];
k++;
l=k;
}
}
for(i=0;i<l;i++)
{
for(j=i+1;j<l;j++)
{
if(s[i]>=s[j])
{
ch=s[i];
s[i]=s[j];
s[j]=ch;
}
}
}
for(i=0;i<l;i++)
{
ch=s[i];
if(ch!=s[i+1])
{
if(ch!='=')
{
s[p]=ch;
ntt[z]=s[p];
p++;
z++;
}
}
d=z;
}
printf("\n The symbols are:\n");
for(i=0;i<d;i++)
{
printf("%c",ntt[i]);
}
for(i=0;i<d;i++)
{
if(isupper(ntt[i]))
{
nt[r]=ntt[i];
r++;
}
else
{
t[y]=ntt[i];
y++;
}
}
printf("\n");
printf("\nnon-terminals:");
for(i=0;i<r;i++)
printf("%c ",nt[i]);
printf("\n");
printf("\nterminals:");
for(i=0;i<y;i++)
printf("%c ",t[i]);
printf("\n\nEnter the entries for
SPF");
for(i=0;i<2*d;i++)
scanf("%d",&c[i]);
printf(" SPF");
printf("\n");
printf(" ");
for(i=0;i<d;i++)
printf("%2c ",ntt[i]);
printf("\n");
printf("f ");
for(i=0;i<d;i++)
printf("%2d ",c[i]);
printf("\n");
printf("g ");
for(i=0;i<d;i++)
printf("%2d ",c[i+7]);
getch();
//-----------------------------SPF
parsing-----------------------------------
printf("\n\nEnter the input
string");
scanf("%s",&pa);
printf("\n");
for(i=0;i<n;i++)
{
for(j=2;j<strlen(pr[i]);j++)
{
string1[i][j-2]=pr[i][j];
}
string1[i][j-2] ='\0';
}
for(j=0;j<strlen(pa);j++)
{
i=0;
while(i<strlen(pa))
{
if(pa[i]=='#' &&
strlen(pa)>3)
{
sym='<';
}
else if(pa[i+1]=='#'
&& strlen(pa)>3)
{
sym='>';
}
else
{
ch1=pa[i];
for(x=0;x<d;x++)
{
if(ch1==ntt[x])
mx=x;
}
ch2=pa[i+1];
for(y=0;y<d;y++)
{
if(ch2==ntt[y])
my=y+7;
}
if(c[mx]<c[my])
sym='<';
else if(c[mx]>c[my])
sym='>';
else
sym='=';
}
if(sym=='=')
{
i=i;
}
else if(sym=='<')
{
x1=i;
}
else if(sym=='>')
{
s1=0;
for(k=x1+1;k<=i;k++)
{
handle[s1]=pa[k];
s1++;
flag=1;
}
handle[s1]='\0';
z=0,y=0;
for(x=0;x<n;x++)
{
if(strcmp(handle,string1[x])==0)
{
printf("\nHandle
is %s = %c",string1[x],pr[x][0]);
pa[x1+1]=pr[x][0];
if(s1>1)
{
z=x1+s1+1;
y=x1+2;
while(pa[z]!='\0')
{
pa[y]=pa[z];
z++;
y++;
}
pa[y]='\0';
}
i=0;
s1=0;
printf(" string is %s",pa);
flag=0;
}
}
}
i++;
}
}
if(flag==0)
{
printf("\n string is valid" );
}
else if(flag==1)
{
printf(" \n string is not
valid");
}
getch();
}
Output:
Enter the no. of
productions 4
Enter the
productions Z= bMb M=a M=(L
L=Ma)
The symbols are: ()LMZab
non-terminals M Z
Terminals :( ) a b
Enter the entries
for SPF : 2 8 8 7 1 9 4 5 9 2 4 1 7 7
SPF:
(
) L M
Z a b
f 2
8 8 7
1 9 4
g 5
9 2 4
1 7 7
Enter the input
string #b(aa)b#
Handle is a = M string is #b(Ma)b#
Handle is Ma) = L string is #b(Lb#
Handle is (L = M string is #bMb#
Handle is bMb = Z string is #Z#
String is valid
8. SIMPLE PRECEDENCE FUNCTION FOR SPM
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
Subscribe to:
Comments (Atom)