編譯原理實(shí)驗(yàn)2-語法分析（C++代碼實(shí)現(xiàn)）

編譯原理實(shí)驗(yàn)2——語法分析（C++代碼實(shí)現(xiàn)）?、實(shí)驗(yàn)?的語法分析是編譯程序中的核?部分。本實(shí)驗(yàn)通過設(shè)計(jì)?個(gè)典型的?頂向下語法分析程序——LL(1)語法分析程序，進(jìn)?步理解并掌握語法分析的原理和實(shí)現(xiàn)技術(shù)。?、實(shí)驗(yàn)原理語法分析的主要任務(wù)是“組詞成句”，將詞法分析給出的單詞序列按語法規(guī)則構(gòu)成更?的語法單位，如“程序、語句、表達(dá)式”等；或者說，語法分析的作?是?來判斷給定輸?串是否為合乎?法的句?。按照?成語法樹的?向不同，常?的語法分析?法有兩類：?頂向下分析和?底向上分析。?頂向下分析也稱?向?標(biāo)的分析?法，也就是從?法的開始符出發(fā)，試圖推導(dǎo)出與輸?單詞串相匹配的句?。?底向上分析也稱移進(jìn)-歸約分析?法，從輸?單詞串開始，試圖歸約到?法的開始符。預(yù)測(cè)分析法（LL(1)?法）的基本思想是：從?法開始符S出發(fā)，從左到右掃描源程序，每次通過向前查看1個(gè)字符，選擇合適的產(chǎn)?式，?成句?的最左推導(dǎo)。三、實(shí)驗(yàn)步驟與要求1、復(fù)習(xí)教材第4章，進(jìn)?步理解LL(1)?法的原理和實(shí)現(xiàn)技術(shù)。根據(jù)預(yù)測(cè)分析程序的框圖（教材P94-圖5.11），編寫?個(gè)語法分析程序?？筛鶕?jù)??的能?選擇以下三項(xiàng)（由易到難）之?作為分析算法的輸?：(1)根據(jù)?法，??構(gòu)造分析表M，直接輸?表M。(2)輸??法的FIRST集和FOLLOW集，由程序?動(dòng)?成該?法的預(yù)測(cè)分析表M。(3)輸??法，由程序?動(dòng)?成該?法的預(yù)測(cè)分析表M。2、程序具有通?性，即所編制的LL（1）語法分析程序能夠適?于不同?法以及各種輸?單詞串。3、有運(yùn)?實(shí)例。對(duì)于輸?的?個(gè)?法和?個(gè)單詞串，語法分析程序應(yīng)能正確地判斷此單詞串是否為該?法的句?，并要求輸出分析過程。4、設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)，特別是?法、預(yù)測(cè)分析表、分析棧等的存儲(chǔ)結(jié)構(gòu)。四、實(shí)驗(yàn)代碼//#include"pch.h"#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>usingnamespacestd;voidGramF();//分解產(chǎn)?式程序voidGramIn();//?法輸?程序voidWordIn();//?字輸?程序boolIs(charx,chara[],intn);//是否在集合中voidGetFirst(chara);//first集求解程序voidADD(string&a,string&b);//集合相加程序集合voidADDfollow(string&a,string&b);//(follow)相加程序intBack(chara);//根據(jù)字母返回下標(biāo)程序voidGetFollow(chara);//follow集求解程序boolIsChar(chara,stringb);//判斷?個(gè)字符是否在?個(gè)集合中的程序voidFAtable();//預(yù)測(cè)分析表構(gòu)建程序voidGAnalysis();//?法分析程序voidclearF();//凈化程序voidcc();//i+()*ABCDEA->BCC->+BC|@B->DEE->*DE|@D->(A)|iinttable[100][100]={0};//預(yù)測(cè)表charVt[100]={""};//終結(jié)符charVn[100]={""};//?終結(jié)符stringGenerative[100]={""};//?法產(chǎn)?式存儲(chǔ)stringGenerativeNew[100]={""};//?法產(chǎn)?式分解后的存儲(chǔ)stringfirst[100]={""};//first集合stringfollow[100]={""};//follow集合charword[100]={""};//待測(cè)試的?字intVtNum=0;//終結(jié)符號(hào)的個(gè)數(shù)intVtNum=0;//終結(jié)符號(hào)的個(gè)數(shù)intVnNum=0;//?終結(jié)符號(hào)的個(gè)數(shù)intGenNum=0;//?法產(chǎn)?式個(gè)數(shù)intGenNumNew=0;//?法產(chǎn)?式分解后的個(gè)數(shù)stack<char>st;//預(yù)測(cè)分析棧voidcc(){inti,j,k,q,p;for(i=0;i<VnNum;i++){j=0;while(first[i][j]!='\0'){k=j+1;while(first[i][k]!='\0'){if(first[i][j]==first[i][k])first[i][k]='';k++;}j++;}q=0;while(first[i][q]!='\0'){if(first[i][q]!=''){break;}else{p=q+1;while(first[i][p]!=''){if(first[i][p]=='\0')break;else{first[i][q]=first[i][p];first[i][p]='';}}}q++;}q=0;while(first[i][q]!='\0'){if(first[i][q]=='')first[i][q]='\0';q++;}}}/*************************/分解?法產(chǎn)?式程序voidGramF(){intj,z=0,x;for(inti=0;i<GenNum;i++){x=0;while(1){charch1=Generative[i][x];if(ch1=='\0'||ch1=='|')break;GenerativeNew[z]+=Generative[i][x];x++;}z++;j=0;while(Generative[i][j]!='\0'){if(Generative[i][j]=='|'){j++;for(x=0;x<3;x++){GenerativeNew[z]+=Generative[i][x];}while(1){while(1){charch2=Generative[i][j];if(ch2=='\0'||ch2=='|')break;GenerativeNew[z]+=Generative[i][j];j++;}z++;}else{j++;}}}GenNumNew=z;}/************?法輸?程序*************/voidGramIn(){inti=0;printf("請(qǐng)輸?終結(jié)符號(hào)：\n");scanf_s("%c",Vt+i,1);while(*(Vt+i)!='\n'){i++;scanf_s("%c",Vt+i,1);}Vt[i]='#';i++;VtNum=i;//輸?結(jié)束存儲(chǔ)終結(jié)符號(hào)個(gè)數(shù)i=0;//i初始化值準(zhǔn)備輸??終結(jié)符號(hào)printf("請(qǐng)輸??終結(jié)符號(hào)：\n");scanf_s("%c",Vn+i,1);while(*(Vn+i)!='\n'){i++;scanf_s("%c",Vn+i,1);}VnNum=i;//輸?結(jié)束存儲(chǔ)?終結(jié)符號(hào)個(gè)數(shù)i=0;//i初始化值準(zhǔn)備輸??法產(chǎn)?式printf("請(qǐng)輸??法產(chǎn)?式：\n");charch;while(cin>>Generative[i]){i++;if((ch=getchar())=='\n')break;}GenNum=i;//輸?結(jié)束存儲(chǔ)?法產(chǎn)?式個(gè)數(shù)}/************?字輸?程序*************/voidWordIn(){printf("請(qǐng)輸?您需要測(cè)試的?字：\n");inti=0;//getchar();scanf_s("%c",word+i);while(*(word+i)!='\n'){i++;scanf_s("%c",word+i);}}/************是否在集合中*************/boolIs(charx,chara[],intn){for(inti=0;i<n;i++){if(a[i]==x)returntrue;}returnfalse;returnfalse;}/************first集求解程序*************/voidGetFirst(chara){intk=0;for(inti=0;i<GenNumNew;i++){if(GenerativeNew[i][0]!=a)continue;if(Is(GenerativeNew[i][3],Vt,VtNum)){//如果該?終結(jié)符產(chǎn)?式右部第?個(gè)字符是終結(jié)符,號(hào)則直接將其計(jì)?左部?終結(jié)符的FIRST集first[Back(GenerativeNew[i][0])]+=GenerativeNew[i][3];}elseif(Is(GenerativeNew[i][3],Vn,VnNum)){//如果該?終結(jié)符號(hào)右部第?個(gè)字符是?終結(jié)符,號(hào)則對(duì)該右部第?個(gè)字符的FIRST進(jìn)?求解,并將其加?左部字符的GetFirst(GenerativeNew[i][3]);FIRST集ADD(first[Back(GenerativeNew[i][0])],first[Back(GenerativeNew[i][3])]);}elseif(GenerativeNew[i][3]=='@'){//,FIRST如果該?終結(jié)符產(chǎn)?式是個(gè)空則將空加?左部字符的集intj=0;while(first[Back(GenerativeNew[i][0])][j]!='\0'){if(first[Back(GenerativeNew[i][0])][j]=='@'){k=1;break;}j++;}if(!k)first[Back(GenerativeNew[i][0])]+='@';}}}/************follow*************/集清除重復(fù)元素程序voidclearF(){inti,j,k,q,p;//follow集下?是清除for(i=0;i<VnNum;i++){j=0;while(follow[i][j]!='\0'){k=j+1;while(follow[i][k]!='\0'){if(follow[i][j]==follow[i][k])follow[i][k]='';k++;}j++;}q=0;p=0;while(follow[i][q]!='\0'){if(follow[i][q]!=''){break;}else{p=q+1;while(follow[i][p]!=''){if(follow[i][p]=='\0')break;else{follow[i][q]=follow[i][p];follow[i][p]='';}}}q++;}}q=0;while(follow[i][q]!='\0'){if(follow[i][q]=='')follow[i][q]='\0';q++;}}}/************集合相加程序*************/voidADD(string&a,string&b){inti=0,zk=1,j=0;while(b[j]!='\0'){i=0;zk=1;while(a[i]!='\0'){if(b[j]==a[i]||b[j]=='@'){zk=-1;break;}i++;}if(zk==1)a+=b[j];j++;}}/************集合(follow)相加程序*************/voidADDfollow(string&a,string&b){inti=0,zk=1,j=0;while(b[j]!='\0'){i=0;zk=1;while(a[i]!='\0'){if(b[j]==a[i]){zk=-1;break;}i++;}if(zk==1)a+=b[j];j++;}}/************follow集求解程序*************/voidGetFollow(chara){inti=Back(a),j;//if(i==0||i==1||i==2||i==3){//如果待求解字符是開始字符,則把'#'加?其//if(IsChar(a,follow[Back(a)]))follow[Back(a)]+='#';FOLLOW集for(j=0;j<GenNumNew;j++){if(GenerativeNew[j][3]==a&&GenerativeNew[j][4]!='\0'){//如果是A->Bbif(Is(GenerativeNew[j][4],Vt,VtNum)){//如果b是終結(jié)符號(hào)，直接加?follow(B)if(IsChar(GenerativeNew[j][4],follow[Back(a)]))//判斷b是否在follow(B)中continue;elsefollow[Back(a)]+=GenerativeNew[j][4];}elseif(Is(GenerativeNew[j][4],Vn,VnNum)){//如果b是?終結(jié)符號(hào)，需要判斷if(IsChar('@',first[Back(GenerativeNew[j][4])])){//如果b可以推出空'@'，則需要將follow(A)加?follow(B)GetFollow(GenerativeNew[j][0]);ADDfollow(follow[Back(a)],follow[Back(GenerativeNew[j][0])]);}ADD(follow[Back(a)],first[Back(GenerativeNew[j][4])]);ADD(follow[Back(a)],first[Back(GenerativeNew[j][4])]);}}elseif(GenerativeNew[j][4]==a&&GenerativeNew[j][5]!='\0'){//如果是A->aBbif(Is(GenerativeNew[j][5],Vt,VtNum)){//如果b是終結(jié)符號(hào)，直接加?follow(B)if(IsChar(GenerativeNew[j][5],follow[Back(a)]))//判斷b是否在follow(B)中continue;elsefollow[Back(a)]+=GenerativeNew[j][5];}elseif(Is(GenerativeNew[j][5],Vn,VnNum)){//如果b是?終結(jié)符號(hào)，需進(jìn)?判斷if(IsChar('@',first[Back(GenerativeNew[j][5])])){//如果b可以推出空'@'，則需要將follow(A)加?follow(B)GetFollow(GenerativeNew[j][0]);ADDfollow(follow[Back(a)],follow[Back(GenerativeNew[j][0])]);}ADD(follow[Back(a)],first[Back(GenerativeNew[j][5])]);}}elseif(GenerativeNew[j][4]==a&&GenerativeNew[j][5]=='\0'){//如果是A->aBGetFollow(GenerativeNew[j][0]);//直接將follow(A)加?follow(B)ADDfollow(follow[Back(a)],follow[Back(GenerativeNew[j][0])]);}}//}}/************判斷?個(gè)字符是否在?個(gè)集合中的程序*************/boolIsChar(chara,stringb){inti=0;while(b[i]!='\0'){if(a==b[i])returntrue;i++;}returnfalse;}/*************************/預(yù)測(cè)分析表構(gòu)建程序voidFAtable(){inti,j;for(i=0;i<VtNum;i++){for(j=0;j<GenNumNew;j++){if(Vt[i]==GenerativeNew[j][3])//如果終結(jié)符中則將A->a放?table[A,Vt[i]]Vt[i]A->afirst(a),在的中table[Back(GenerativeNew[j][0])][i]=j;elseif(Is(GenerativeNew[j][3],Vn,VnNum)){if(IsChar(Vt[i],first[Back(GenerativeNew[j][3])])){table[Back(GenerativeNew[j][0])][i]=j;}}elseif(GenerativeNew[j][3]=='@'){//如果當(dāng)前的產(chǎn)?式是：A->a且，a='@'，則判斷當(dāng)前的Vt[i]是否在if(IsChar(Vt[i],follow[Back(GenerativeNew[j][0])])){table[Back(GenerativeNew[j][0])][i]=j;}}}}}/************根據(jù)字母返回終結(jié)符下標(biāo)程序*************/intBBack(chara){for(inti=0;i<VtNum;i++){if(a==Vt[i])returni;}return-1;}/************根據(jù)字母返回?終結(jié)符下標(biāo)程序*************//************根據(jù)字母返回?終結(jié)符下標(biāo)程序*************/intBack(chara){for(inti=0;i<VnNum;i++){if(a==Vn[i])returni;}return-1;}/************?法分析程序*************/voidGAnalysis(){inti=0,x,y,k,error=0,n=1;chara;stringchan="";st.push('#');st.push(Vn[0]);a=st.top();while(!(a==word[i]&&a=='#')){if(Is(st.top(),Vn,VnNum)){x=Back(st.top());y=BBack(word[i]);k=table[x][y];//獲得產(chǎn)?式if(k==-1){error++;cout<<"步驟["<<n<<"]：識(shí)別錯(cuò)誤！跳過"<<word[i]<<"；\n";n++;i++;break;}else{chan=GenerativeNew[k];k=0;st.pop();while(chan[k]!='\0'){k++;}k--;if(chan[k]!='@'){while(chan[k]!='>'){st.push(chan[k]);k--;}//i++;cout<<"步驟["<<n<<"]：?"<<chan<<"的右部分逆序?棧已經(jīng)完成；\n";n++;}else{cout<<"步驟["<<n<<"]：?"<<chan<<"；\n";n++;//i++;}}}elseif(Is(st.top(),Vt,VtNum)){if(st.top()==word[i]){cout<<"步驟["<<n<<"]：匹配棧頂和當(dāng)前符號(hào)"<<word[i]<<"，成功；\n";st.pop();i++;n++;}else{cout<<"步驟["<<n<<"]：識(shí)別失?。?！\n";n++;break;}}a=st.top();a=st.top();}if(error){cout<<"步驟["<<n<<"]：識(shí)別錯(cuò)誤！！錯(cuò)誤跳過次數(shù)："<<error<<"\n";n++;}else{cout<<"步驟["<<n<<"]：識(shí)別成功！！\n";n++;}}voidChuShi(){for(inti=0;i<100;i++){for(intj=0;j<100;j++){table[i][j]=-1;}}}intmain(){usingstd::cout;cout.setf(std::ios::left);ChuShi();//初始化?維數(shù)組GramIn();//輸??終結(jié)、終結(jié)字符和?法產(chǎn)?式GramF();//?法產(chǎn)?式分析完畢inti,j;for(