6. OPERATOR PRECEDENCE MATRIX
(OPM)
Source code:
#include<conio.h>
#include<stdio.h>
#include<string.h>
void main()
{
char prod[30][30],nonterm[20],ch,ch1,str[30],handle[20],match[15][15],chr,chs;
char
term[20],temp[2],temp1,temp2[2],symbol[30],stor[10],stor1[10];
int i,j,n,ntcnt=0,tcnt=0,k,l,cnt,m,first[10][10],firstp[10][10],px,py,p,q;
int
last[10][10],h,equal[10][10],less[10][10],firsts[10][10];
int
mid[10][10],mid1t[10][10],greater[10][10],lasts[10][10],lastplus[10][10],opm[10][10];
int
d,x,s,lastterm[10][10],mid1[10][10],equalt[10][10],firstterm[10][10];
char symb;
int
flag,z,y;
clrscr();
printf("Enter
the number of productions \n");
scanf("%d",&n);
nonterm[0]='\0';
term[0]='\0';
symbol[0]='\0';
stor1[0]='\0';
for(i=0;i<n;i++)
{
scanf("%s",prod[i]);
}
printf("\nProductions are:");
for(i=0;i<n;i++)
{
printf("\n%s
",prod[i]);
}
/*~~~~~~~~~~~~~~~separate terminals &
nonterminals~~~~~~~~~~~~~~~~~*/
for(i=0;i<n;i++)
{
for(j=0;prod[i][j]!='\0';j++)
{
if(prod[i][j]>=65
&& prod[i][j]<=90)
{
temp[0]=prod[i][j];
temp[1]='\0';
strcat(nonterm,temp);
ntcnt++;
}
else
if (prod[i][j]!='=')
{
temp2[0]=prod[i][j];
temp2[1]='\0';
strcat(term,temp2);
tcnt++;
}
}
}
/*~~~~~~~~~~~~~~~~~~~~~~~~sorting terminals &
nonterminals~~~~~~~~~~~~*/
for(i=0;i<ntcnt;i++)
{
for(j=i+1;nonterm[j]!='\0';j++)
{
if(nonterm[i]>nonterm[j])
{
temp1=nonterm[i];
nonterm[i]=nonterm[j];
nonterm[j]=temp1;
}
}
}
for(i=0;i<tcnt;i++)
{
for(j=i+1;term[j]!='\0';j++)
{
if(term[i]>term[j])
{
temp1=term[i];
term[i]=term[j];
term[j]=temp1;
}
}
}
/* Removing duplicates from Ts & NTs */
i=1;
while(term[i-1]!=term[i] &&
i<tcnt)
{
i=i+1;
}
if(term[i-1]!=term[i])
{
i=i+1;
}
j=i-1;
while(i<tcnt)
{
i=i+1;
if(term[i-1]!=term[i])
{
j=j+1;
term[j]=term[i];
}
}
tcnt=j;
k=1;
while(nonterm[k-1]!=nonterm[k] &&
k<ntcnt)
{
k=k+1;
}
if(nonterm[k-1]!=nonterm[k])
{
k=k+1;
}
l=k-1;
while(k<ntcnt)
{
k=k+1;
if(nonterm[k-1]!=nonterm[k])
{
l=l+1;
nonterm[l]=nonterm[k];
}
}
ntcnt=l;
cnt=ntcnt+tcnt;
strcat(symbol,nonterm);
strcat(symbol,term);
printf("\n");
printf("\n
Nts=%s",nonterm);
printf("\n
Ts=%s",term);
printf("\ncnt
is=%d",cnt);
printf("\nsymbols
are=%s",symbol);
/*~~~~~~~~~~~~~~~~~matrix
initialization~~~~~~~~~~~~~~~*/
i=0;
j=0;
for(i=0;i<cnt;i++)
{
for(j=0;j<cnt;j++)
{
first[i][j]=0;
firstp[i][j]=0;
last[i][j]=0;
lastplus[i][j]=0;
equal[i][j]=0;
less[i][j]=0;
firsts[i][j]=0;
mid[i][j]=0;
lasts[i][j]=0;
greater[i][j]=0;
opm[i][j]=0;
firstterm[i][j]=0;
lastterm[i][j]=0;
mid1[i][j]=0;
mid1t[i][j]=0;
equalt[i][j]=0;
}
}
/*~~~~~~~~~~~~~~~~~Equal
matrix~~~~~~~~~~~~~~~~~~~~~~~~*/
for(i=0;i<n;i++)
{
ch=prod[i][2];
for(p=0;p<cnt;p++)
{
if(ch==symbol[p])
px=p;
}
for(k=3;prod[i][k]!='\0';k++)
{
ch=prod[i][k];
for(q=0;q<cnt;q++)
{
if(ch==symbol[q])
py=q;
}
equal[px][py]=1;
px=py;
}
}
/*~~~~~~~~~~~~~~~~~Equal than
matrix~~~~~~~~~~~~~~~~~~~~~~~~*/
for(i=0;i<n;i++)
{
k=strlen(prod[i]);
for(j=2;j<k-1;j++)
{
if(k>3)
{
ch=prod[i][j];
if(!isupper(ch))
{
for(p=0;p<cnt;p++)
{
if(ch==symbol[p])
{
px=p;
}
}
ch1=prod[i][j+1];
if(!isupper(ch1))
{
for(q=0;q<cnt;q++)
{
if(ch1==symbol[q])
{
py=q;
}
}
equalt[px][py]=1;
}
else if(j+2<k)
{
ch1=prod[i][j+2];
if(!isupper(ch1))
{
for(q=0;q<cnt;q++)
{
if(ch1==symbol[p])
{
py=q;
}
}
}
equalt[px][py]=1;
}
}
}
}
}
/*~~~~~~~~~~~~~~~~~first
matrix~~~~~~~~~~~~~~~~~~~~~~~~*/
for(i=0;i<n;i++)
{
ch=prod[i][0];
for(p=0;p<cnt;p++)
{
if(ch==symbol[p])
px=p;
}
ch=prod[i][2];
for(q=0;q<cnt;q++)
{
if(ch==symbol[q])
py=q;
}
first[px][py]=1;
}
/*~~~~~~~~~~~~~~~~~Find
FirstTerm~~~~~~~~~~~~~~~~~~*/
for(i=0;i<n;i++)
{
ch=prod[i][0];
for(p=0;p<cnt;p++)
{
if(ch==symbol[p])
px=p;
}
for(k=2;k<strlen(prod[i]);k++)
{
ch=prod[i][k];
for(m=0;term[m]!='\0';m++)
{
if(ch==term[m])
{
ch1=term[m];
for(q=0;q<cnt;q++)
{
if(ch1==symbol[q])
py=q;
}
d=strlen(prod[i]);
k=d+1;
}
}
}
firstterm[px][py]=1;
}
/*~~~~~~~~~~~~~~~~~~Last
matrix~~~~~~~~~~~~~~*/
for(i=0;i<n;i++)
{
ch=prod[i][0];
for(p=0;p<cnt;p++)
{
if(ch==symbol[p])
px=p;
}
h=strlen(prod[i]);
ch=prod[i][h-1];
for(q=0;q<cnt;q++)
{
if(ch==symbol[q])
py=q;
}
last[px][py]=1;
}
/*~~~~~~~~~~~~~~~~~~first
plus~~~~~~~~~~~~~*/
i=0;
while(i<cnt)
{
for(j=0;j<cnt;j++)
{
if(first[j][i]==1)
{
for(k=0;k<cnt;k++)
{
first[j][k]=first[j][k]||first[i][k];
}
}
}
i++;
}
/*~~~~~~~~~~~~`~~Last
plus~~~~~~~~~~~~~~~~~~~~*/
i=0;
while(i<cnt)
{
for(j=0;j<cnt;j++)
{
if(last[j][i]==1)
{
for(k=0;k<cnt;k++)
last[j][k]=last[j][k]
|| last[i][k];
}
}
i++;
}
/*~~~~~~~~~~~~~~~~~~first
star~~~~~~~~~~~~~*/
i=0;
while(i<cnt)
{
for(j=0;j<cnt;j++)
{
if(first[j][i]==1)
{
for(k=0;k<cnt;k++)
{
firsts[j][k]=first[j][k]||first[i][k];
}
}
}
i++;
}
for(j=0;j<cnt;j++)
{
for(k=0;k<cnt;k++)
{
if(j==k)
{
firsts[j][k]=1;
}
}
}
/*~~~~~~~~~~~~~~~find
lasts~~~~~~~~~~~~~~~*/
i=0;
while(i<cnt)
{
for(j=0;j<cnt;j++)
{
if(last[j][i]==1)
{
for(k=0;k<cnt;k++)
{
lasts[j][k]=last[j][k]||last[i][k];
}
}
}
i++;
}
for(j=0;j<cnt;j++)
{
for(k=0;k<cnt;k++)
{
if(j==k)
{
lasts[j][k]=1;
}
}
}
/*~~~~~~~~~~~Find lastp~~~~~~~~~~~~~*/
/* i=0;
while(i<cnt)
{
for(j=0;j<cnt;j++)
{
if(last[j][i]==1)
{
for(k=0;k<cnt;k++)
{
lastt[k][j]=last[j][k]||last[i][k];
}
}
}
i++;
}
/*~~~~~~~~~~~~~~~~~Find
lastTerm~~~~~~~~~~~~~~~~~~*/
for(i=0;i<n;i++)
{
ch=prod[i][0];
for(p=0;p<cnt;p++)
{
if(ch==symbol[p])
px=p;
}
for(k=2;k<strlen(prod[i]);k++)
{
ch=prod[i][k];
for(m=0;term[m]!='\0';m++)
{
if(ch==term[m])
{
ch1=term[m];
for(q=0;q<cnt;q++)
{
if(ch1==symbol[q])
py=q;
}
}
}
}
lastterm[px][py]=1;
}
/*~~~~~~~~~~~~~~~~~~~~find mid1=lasts*lastterm ~~~~~~~~~~~~~~~*/
for(i=0;i<cnt;i++)
{
for(j=0;j<cnt;j++)
{
if (lasts[i][j]==1)
{
for(k=0;k<cnt;k++)
{
if( lastterm[j][k]==1)
{
mid1[i][k]=1;
}
}
}
}
}
/*~~~~~~~~~~~~~~~~~~~~find
greater=mid1t*equal mat ~~~~~~~~~~~~~~~*/
for(i=0;i<cnt;i++)
{
for(j=0;j<cnt;j++)
{
if (mid1[j][i]==1)
{
for(k=0;k<cnt;k++)
{
if( equal[j][k]==1)
{
greater[i][k]=1;
}
}
}
}
}
/*~~~~~~~~~~~Find
mid=firsts*equal~~~~~~~~~~~~*/
for(i=0;i<cnt;i++)
{
for(j=0;j<cnt;j++)
{
if (equal[i][j]==1)
{
for(k=0;k<cnt;k++)
{
if( firsts[j][k]==1)
{
mid[i][k]=1;
}
}
}
}
}
/*~~~~~~~~~find less matrix~~~~~~~~~~~*/
// (<) = mid*(firstterm)
for(i=0;i<cnt;i++)
{
for(j=0;j<cnt;j++)
{
if (mid[i][j]==1)
{
for(k=0;k<cnt;k++)
{
if( firstterm[j][k]==1)
{
less[i][k]=1;
}
}
}
}
}
/*~~~~~~~~~~~~~~~~~~find
greater=mid*firsts~~~~~~~~~~~~~~~*/
/*
for(i=0;i<cnt;i++)
{
for(j=0;j<cnt;j++)
{
if (mid[i][j]==1)
{
for(k=0;k<cnt;k++)
{
if( firsts[j][k]==1)
{
greater[i][k]=1;
}
}
}
}
}
/*~~~~~~~~~~~~~print OPM matrix~~~~~~~~~~~~*/
printf("\n");
printf("OPM matrix
is\t");
printf("\n\t\t\t\t
");
for(j=3;j<strlen(symbol);j++)
{
printf("%2c",symbol[j]);
}
printf("\n");
for(i=3;i<cnt;i++)
{
printf("\n\t\t\t\t%c",symbol[i]);
for(j=3;j<cnt;j++)
{
if(greater[i][j]==1)
{
printf("
>");
}
else
if(less[i][j]==1)
{
printf("
<");
}
else
if(equalt[i][j]==1)
{
printf("
=");
}
else
printf("%2d",opm[i][j]);
}
printf("\n");
}
getch();
}
OUT
PUT:
Enter the number of productions
6
E=E+T E=T T=T*F T=F F=(E) F=E
Productions are:
E=E+T
E=T
T=T*F
T=F
F=(E)
F=E
Nts=EFT
Ts=()*+
cnt is=7
symbols are=EFT()*+
OPM matrix is
( ) * +
( < = <
<
) 0 > >
>
* < >
> >
+ < >
> >
No comments:
Post a Comment
If you have any doubts please let me know