4编译原理算符优先算法分析程序.docx
《4编译原理算符优先算法分析程序.docx》由会员分享，可在线阅读，更多相关《4编译原理算符优先算法分析程序.docx（13页珍藏版）》请在冰点文库上搜索。
4编译原理算符优先算法分析程序
#include
#include
#include
typedefstruct
{ charR;
charr;
intflag;
}array;
typedefstruct
{charE;
chare;
}charLode;
typedefstruct
{ charLode*base;
inttop;
}charstack;
charstr[80][80],arr[80][80],brr[80][80];
arrayF[20];
intm,kk,p,ppp,FF=1;
charr[10];
intcrr[20][20],FLAG=0;
charccrr1[1][20],ccrr2[20][1];
voidInitstack（charstack&s）//定义栈
{ s.base=newcharLode[20];
s.top=-1;
}
voidpush（charstack&s,charLodew） //入栈
{ s.top++;
s.base[s.top].E=w.E;
s.base[s.top].e=w.e;
}
voidpop（charstack&s,charLode&w） //出栈
{ w.E=s.base[s.top].E;
w.e=s.base[s.top].e;
s.top--;
}
intIsEmpty（charstacks） //判断是否到栈顶
{ if（s.top==-1）
return1;
else
return0;
}
intIsLetter（charch） //判断是不是大写字母（非终结符）
{ if（ch>='A'&&ch<='Z'）
return1;
else
return0;
}
intjudge1（intn）
{ intj=3,flag=0;
for（inti=0;i<=n;i++）
while（str[i][j]!
='\0'）
{ chara=str[i][j];
charb=str[i][j+1];
if（IsLetter（a）&&IsLetter（b）） //两个非终结符相连，不是算符文法
{ flag=1;
break;
}
else
j++;
}
if（flag==1） //根据flag设定返回值
return0;
else
return1;
}
voidjudge2（intn）
{ for（inti=0;i<=n;i++）
if（str[i][3]=='~'||FLAG==1）//'~'代表空
{ cout<<"文法G不是算符优先文法!
"< FF=0;
break;
}
if（i>n）
cout<<"文法G是算符优先文法!
"<}
intsearch1（charr[],intkk,chara）
{ for（inti=0;i if（r[i]==a）
break;
if（i==kk）
return0;
else
return1;
}
voidcreateF（intn）
{ intk=0,i=1;charg;
chart[10];//t数组用来存放非终结符
t[0]=str[0][0];
while（i<=n）
{ if（t[k]!
=str[i][0]）
{ k++;
t[k]=str[i][0];
g=t[k];
i++; }
elsei++; }
kk=0;
charc;
for（i=0;i<=n;i++）
{ intj=3;
while（str[i][j]!
='\0'）
{ c=str[i][j];
if（IsLetter（c）==0）
{ if（!
search1（r,kk,c））
r[kk]=c;
kk++;//r数组用来存放终结符 }
j++; } }
m=0;
for（i=0;i for（intj=0;j { F[m].R=t[i];
F[m].r=r[j];
F[m].flag=0;
m++; }}
voidsearch（charLodew）
{ for（inti=0;i if（F[i].R==w.E&&F[i].r==w.e）
{ F[i].flag=1;break; }
}
voidFirstVT（intn）//求FirstVT
{ charstacksta;
charLodew;
inti=0;
Initstack（sta）;
while（i<=n）
{ intk=3;
w.E=str[i][0];
chara=str[i][k];
charb=str[i][k+1];
if（!
IsLetter（a）） //产生式的后选式的第一个字符就是终
{ w.e=a;
push（sta,w）;
search（w）;
i++;
}
elseif（IsLetter（a）&&b!
='\0'&&!
IsLetter（b）） //产生式的后选式的第一个字符是非终结符的情况
{ w.e=b;
push（sta,w）;
search（w）;
i++; }
elsei++;
}
charLodeww;
while（!
IsEmpty（sta））
{ pop（sta,ww）;
for（i=0;i<=n;i++）
{ w.E=str[i][0];
if（str[i][3]==ww.E&&str[i][4]=='\0'）
{ w.e=ww.e;
push（sta,w）;
search（w）;
break; } } }
p=0;intk=1;i=1;
while（i { if（F[i-1].flag==1）
{ arr[p][0]=F[i-1].R;
arr[p][k]=F[i-1].r;
}
while（F[i].flag==0&&i i++;
if（F[i].flag==1）
{ if（F[i].R==arr[p][0]）
k++;
else{arr[p][k+1]='\0';p++;k=1;}
i++; } } }
voidLastVT（intn）//求LastVT
{ charstacksta;
charLodew;
for（inti=0;i F[i].flag=0;
i=0;
Initstack（sta）;
while（i<=n）
{ intk=strlen（str[i]）;
w.E=str[i][0];
chara=str[i][k-1];
charb=str[i][k-2];
if（!
IsLetter（a））
{ w.e=a;
push（sta,w）;
search（w）;
i++; }
elseif（IsLetter（a）&&!
IsLetter（b））
{ w.e=b;
push（sta,w）;
search（w）;
i++; }
elsei++; }
charLodeee;
while（!
IsEmpty（sta））
{ pop（sta,ee）;
for（i=0;i<=n;i++）
{ w.E=str[i][0];
if（str[i][3]==ee.E&&str[i][4]=='\0'）
{ w.e=ee.e;
push（sta,w）;
search（w）; } } }
intk=1;i=1;
ppp=0;
while（i { if（F[i-1].flag==1）
{ brr[ppp][0]=F[i-1].R;
brr[ppp][k]=F[i-1].r;
}
while（F[i].flag==0&&i i++;
if（F[i].flag==1）
{ if（F[i].R==arr[ppp][0]）
k++;
else{brr[ppp][k+1]='\0';ppp++;k=1;}
i++; } } }
voidcreateYXB（intn）//构造优先表
{ inti,j;
for（j=1;j<=kk;j++）
ccrr1[0][j]=r[j-1];
for（i=1;i<=kk;i++）
ccrr2[i][0]=r[i-1];
for（i=1;i<=kk;i++）
for（j=1;j<=kk;j++）
crr[i][j]=0;
intI=0,J=3;
while（I<=n）
{ if（str[I][J+1]=='\0'） //扫描右部
{ I++;
J=3;
}
else
{ while（str[I][J+1]!
='\0'）
{ charaa=str[I][J];
charbb=str[I][J+1];
if（!
IsLetter（aa）&&!
IsLetter（bb））//优先及等于的情况，用1值表示等于
{ for（i=1;i<=kk;i++）
{ if（ccrr2[i][0]==aa）
break;
}
for（j=1;j<=kk;j++）
{ if（ccrr1[0][j]==bb）
break;
}
if（crr[i][j]==0）
crr[i][j]=1;
else{ FLAG=1;
I=n+1;
}
J++;
}
if（!
IsLetter（aa）&&IsLetter（bb）&&str[I][J+2]!
='\0'&&!
IsLetter（str[I][J+2]））//优先及等于的情况
{ for（i=1;i<=kk;i++
{ if（ccrr2[i][0]==aa） break;
}
for（intj=1;j<=kk;j++）
{
if（ccrr1[0][j]==str[I][J+2]）
break;
}
if（crr[i][j]==0）
crr[i][j]=1;
else
{
FLAG=1;
I=n+1;
}
}
if（!
IsLetter（aa）&&IsLetter（bb））//优先及小于的情况，用2值表示小于
{
for（i=1;i<=kk;i++）
{
if（aa==ccrr2[i][0]）
break;
}
for（j=0;j<=p;j++）
{
if（bb==arr[j][0]）
break;
}
for（intmm=1;arr[j][mm]!
='\0';mm++）
{
for（intpp=1;pp<=kk;pp++）
{
if（ccrr1[0][pp]==arr[j][mm]）
break;
}
if（crr[i][pp]==0）
crr[i][pp]=2;
else{
FLAG=1;I=n+1;
}
}
J++;
}
if（IsLetter（aa）&&!
IsLetter（bb））//优先及大于的情况，用3值表示大于
{
for（i=1;i<=kk;i++）
{
if（ccrr1[0][i]==bb）
break;
}
for（j=0;j<=ppp;j++）
{ if（aa==brr[j][0]）
break;
}
for（intmm=1;brr[j][mm]!
='\0';mm++）
{
for（intpp=1;pp<=kk;pp++）
{
if（ccrr2[pp][0]==brr[j][mm]）
break;
}
if（crr[pp][i]==0）
crr[pp][i]=3;
else{FLAG=1;I=n+1;}
}
J++; } } }
}}
intjudge3（chars,chara）
{
inti=1,j=1;
while（ccrr2[i][0]!
=s）
i++;
while（ccrr1[0][j]!
=a）
j++;
if（crr[i][j]==3）
return3;
else
if（crr[i][j]==2）
return2;
else
if（crr[i][j]==1）
return1;
else
return0;
}
voidprint（chars[],charSTR[][20],intq,intu,intii,intk）//打印归约的过程
{
cout< for（inti=0;i<=k;i++）
cout< cout<<" ";
for（i=q;i<=ii;i++）
升级会员 