實驗三算符優(yōu)先分析算法的設(shè)計與實現(xiàn)(8學時)一、實驗目的根據(jù)算符優(yōu)先分析法，對表達式進行語法分析，使其能夠判斷一個表達式是否正確。過算符優(yōu)先分析方法的實現(xiàn)，加深對自下而上語法分析方法的理解。二、實驗要求1、輸入文法?？梢允侨缦滤阈g(shù)表達式的文法(你可以根據(jù)需要適當改變)：ETE+T|E-T|TTtT*F|T/F|FFt(E)|i2、對給定表達式進行分析，輸出表達式正確與否的判斷。程序輸入/輸出示例：輸入：1+2;輸出：正確輸入：(1+2)/3+4-(5+6/7);輸出：正確輸入：((1-2)/3+4輸出：錯誤輸入：1+2-3+(*4/5)輸出：錯誤三、實驗步驟1、參考數(shù)據(jù)結(jié)構(gòu)char*VN=0,*VT=0;//非終結(jié)符和終結(jié)符數(shù)組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、根據(jù)文法求FIRSTVT集和LASTVT集給定一個上下文無關(guān)文法，根據(jù)算法設(shè)計一個程序，求文法中每個非終結(jié)符的FirstVT集和LastVT集。算符描述如下：/*求FirstVT集的算法*/PROCEDUREinsert(P,a);IFnotF[P,a]thenbeginF[P,a]=true;//(P,a)進棧end;ProcedureFirstVT;Beginfor對每個非終結(jié)符P和終結(jié)符adoF[P,a]=falsefor對每個形如Pa…或PTQa…的產(chǎn)生式doInsert(P,a)whilestack非空begin棧頂項出棧，記為(Q,a)for對每條形如PtQ??的產(chǎn)生式doinsert(P,a)end;end.同理，可構(gòu)造計算LASTVT的算法。3、構(gòu)造算符優(yōu)先分析表依據(jù)文法和求出的相應(yīng)FirstVT和LastVT集生成算符優(yōu)先分析表。算法描述如下：for每個形如P->X1X2???Xn的產(chǎn)生式dofori=1ton-1dobeginifXi和％+1都是終結(jié)符thenXi=Xi+1ifi<=n-2,Xi和Xi+2是終結(jié)符，但Xi+1為非終結(jié)符thenXi=Xi+2ifXj為終結(jié)符,Xi+1為非終結(jié)符thenforFirstVT中的每個元素adoXi<a;ifXj為非終結(jié)符,Xi+1為終結(jié)符thenforLastVT中的每個元素adoa>Xi+1;end4、構(gòu)造總控程序算法描述如下：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//調(diào)用出錯診察程序untila=#,5、對給定的表達式，給出準確與否的分析過程6、給出表達式的計算結(jié)果。（本步驟可選作）四、實驗報告要求寫出編程思路、源代碼（或流程圖）；寫出上機調(diào)試時發(fā)現(xiàn)的問題，以及解決的過程；寫出你所使用的測試數(shù)據(jù)及結(jié)果；談?wù)勀愕捏w會。上機8小時，完成實驗報告2小時。五、源代碼#include<iostream.h>#include<string.h>#include<stdio.h>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;elsereturn0;}intIsLetter(charintIsLetter(charch)//判斷是不是大寫字母（非終結(jié)符）if(ch>='A'&&ch<='Z')return1;elsereturn0;)//judge1是判斷是否是算符文法：若產(chǎn)生式中含有兩個相繼的非終結(jié)符則不是算符文法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))//兩個非終結(jié)符相連，不是算符文法{flag=1;break;}elsej++;}if(flag==1)//根據(jù)flag設(shè)定返回值return0;elsereturn1;}//judge2是判斷文法G是否為算符優(yōu)先文法：若不是算符文法或若文法中含空字或終結(jié)符的優(yōu)先級不唯一則不是算符優(yōu)先文法voidjudge2(intn){for(inti=0;i<=n;i++)if(str[i][3]=='~'||FLAG==1)//'~'代表空{(diào)cout<<"文法G不是算符優(yōu)先文法!"<<endl;FF=0;break;}if(i>n)cout<<"文法G是算符優(yōu)先文法!"<<endl;//searchi是查看存放終結(jié)符的數(shù)組r中是否含有重復的終結(jié)符intsearch1(charr[],intkk,chara)(for(int『0;i<kk;i++)if(r[i]==a)break;if(i==kk)return0;elsereturn1;)//createF函數(shù)是用F數(shù)組存放每個終結(jié)符與非終結(jié)符和組合，并且值每隊的標志位為數(shù)組是0;F一個結(jié)構(gòu)體voidcreateF(intn)(intk=0,i=1;charg;chart[10];//t數(shù)組用來存放非終結(jié)符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數(shù)組用來存放終結(jié)符}j++;}m=0;for(i=0;i<k;i++)for(intj=0；j<kk-1;j++)(F[m].R=t[i];F[m].r=r[j];F[m].flag=0;m++;})//search函數(shù)是將在F數(shù)組中尋找到的終結(jié)符與非終結(jié)符對的標志位值為1voidsearch(charLodew)(for(int『0;i<m;i++)if(F[i].R==w.E&&F[i].r==w.e)(F[i].flag=1;break;}}voidFirstVT(intn)//求FirstVT(charstacksta;charLodew;int『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))//產(chǎn)生式的后選式的第一個字符就是終結(jié)符的情況{w.e=a;push(sta,w);search(w);i++；}elseif(IsLetter(a)&&b!='\0'&&!IsLetter(b))//字符是非終結(jié)符的情況產(chǎn)生式的后選式的第一個(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<m){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<m)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(int『0;i<m;i++)F[i].flag=0;『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=O；while(i<m)(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<m)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)//構(gòu)造優(yōu)先表{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))//優(yōu)先及等于的情況，用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]))//優(yōu)先及等于的情況{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;2值表示小于3值表示大于I=n+1;})if(!IsLetter(aa)&&IsLetter(bb))//優(yōu)先及小于的情況，用(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))//{for(i=1;i<=kk;i++)優(yōu)先及大于的情況，用{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++;}}}2值表示小于3值表示大于}}//judge3是用來返回在歸約過程中兩個非終結(jié)符相比較的值intjudge3(chars,chara){int『1,j=1;while(ccrr2[i][0]!=s)i++;while(ccrr1[0][j]!=a)j++;if(crr[i][j]==3)return3;elseif(crr[i][j]==2)return2;elseif(crr[i][j]==1)return1;elsereturn0;}打印歸約的過程voidprint(chars[],charSTR[][20],intq,intu,intii,intk)//cout<<u<<"";for(inti=0;i<=k;i++)cout<<s[i];cout<<"打印歸約的過程for(i=q;i<=ii;i++)cout?STR[0][i];cout?"voidprocess(charSTR[][20],intii)//對輸入的字符串進行歸約的過程動作{cout?"步驟符號棧輸入串"?""?endl;動作intk=O5q=O,u=O5b,iJ;chars[40],a;s[k]='#';print(s5STR,q5u5ii5k);cout?"預備"?endl;k++;u++;s[k]=STR[0][q];q++；print(s5STR,q5u5ii5k);cout?"移進"?endl;while(q<=ii)(a=STR[0][q];if(!lsLetter(s[k]))j=k;elsej=k-1;b=judge3(s[j]5a);if(b==3)//大于的情況進行歸約(while(lsLetter(s[j-1]))j--；for(i=j;i<=k;i++)s[i]='\0';k=j；s[k]='N';u++;print(s5STR,q5u5ii5k);cout?"歸約"?endl;}elseif(b==2||b==1)//小于或等于的情況移進(k++;s[k]=a;u++;q++；

print(s5STR,q5u5ii5k);if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')cout?"接受"?endl;elsecout?"移進"?endl;}else(cout?"出錯"?endl;break;}}if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')cout?"歸約成功"?endl;elsecout?"歸約失敗"?endl;voidmain()(intn,ij;cout?"請輸入你要定義的文法G的產(chǎn)生式的個數(shù)n:H;cin?n;cout?"請輸入文法產(chǎn)生式："?endl;for(i=0;i<n;i++)(gets(str[i]);j=strlen(str[i]);str[i][j]='\O';}str[i][O]='Q';//最末行添加擴展str[i][1str[i][2]='>';str[i][3]='#';str[i][4]=str[0][0];str[i][5]='#';cout?"你定義的產(chǎn)生式如下:,*?endl;str[i][6]='\0';for(i=0;i<=n;i++)cout?str[i]?endl;if(judge1(n)==O)//判斷文法G是否為算符文法cout?"文法G不是算符文法!"?endl;if(judge1(n)==1)cout