实验三-算符优先分析算法的设计与实现

实验三算符优先分析算法的设计与实现（8学时）一、实验目的根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。二、实验要求1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）：E→E+T|E-T|TT→T*F|T/F|FF→（E）|i2、对给定表达式进行分析，输出表达式正确与否的判断。程序输入/输出示例：输入：1+2;输出：正确输入：(1+2)/3+4-(5+6/7);输出：正确输入：((1-2)/3+4输出：错误输入：1+2-3+(*4/5)输出：错误三、实验步骤1、参考数据结构char*VN=0,*VT=0;//非终结符和终结符数组charfirstvt[N][N],lastvt[N][N],table[N][N];typedefstruct//符号对(P,a){charVn;charVt;}VN_VT;typedefstruct//栈{VN_VT*top;VN_VT*bollow;intsize;}stack;2、根据文法求FIRSTVT集和LASTVT集给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的FirstVT集和LastVT集。算符描述如下：/*求FirstVT集的算法*/PROCEDUREinsert(P,a);IFnotF[P,a]thenbeginF[P,a]=true;//(P,a)进栈end;ProcedureFirstVT;Beginfor对每个非终结符P和终结符adoF[P,a]=falsefor对每个形如Pa…或P→Qa…的产生式doInsert(P,a)whilestack非空begin栈顶项出栈，记为(Q,a)for对每条形如P→Q…的产生式doinsert(P,a)end;end.同理，可构造计算LASTVT的算法。3、构造算符优先分析表依据文法和求出的相应FirstVT和LastVT集生成算符优先分析表。算法描述如下：for每个形如P-X1X2…Xn的产生式dofori=1ton-1dobeginifXi和Xi+1都是终结符thenXi=Xi+1ifi=n-2,Xi和Xi+2是终结符,但Xi+1为非终结符thenXi=Xi+2ifXi为终结符,Xi+1为非终结符thenforFirstVT中的每个元素adoXia;ifXi为非终结符,Xi+1为终结符thenforLastVT中的每个元素adoaXi+1;end4、构造总控程序算法描述如下：stackS;k=1;//符号栈S的使用深度S[k]=‘#’REPEAT把下一个输入符号读进a中；IfS[k]VTthenj=kelsej=k-1;WhileS[j]adoBeginRepeatQ=S[j];ifS[j-1]VTthenj=j-1elsej=j-2untilS[j]Q;把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号；K=j+1;S[k]=N;endofwhileifS[j]aorS[j]=athenbegink=k+1;S[k]=aendelseerror//调用出错诊察程序untila=‘#’5、对给定的表达式，给出准确与否的分析过程6、给出表达式的计算结果。（本步骤可选作）四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。5.上机8小时，完成实验报告2小时。五、源代码#includeiostream.h#includestring.h#includestdio.htypedefstruct{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;elsereturn0;}intIsLetter(charch)//判断是不是大写字母（非终结符）{if(ch='A'&&ch='Z')return1;elsereturn0;}//judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法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;}elsej++;}if(flag==1)//根据flag设定返回值return0;elsereturn1;}//judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法voidjudge2(intn){for(inti=0;i=n;i++)if(str[i][3]=='~'||FLAG==1)//'~'代表空{cout文法G不是算符优先文法!endl;FF=0;break;}if(in)cout文法G是算符优先文法!endl;}//search1是查看存放终结符的数组r中是否含有重复的终结符intsearch1(charr[],intkk,chara){for(inti=0;ikk;i++)if(r[i]==a)break;if(i==kk)return0;elsereturn1;}//createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体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;ik;i++)for(intj=0;jkk-1;j++){F[m].R=t[i];F[m].r=r[j];F[m].flag=0;m++;}}//search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1voidsearch(charLodew){for(inti=0;im;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(im){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&&im)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;im;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(im){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&&im)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