编译原理实验2-语法分析（C++代码实现）

编译原理实验2——语法分析（C++代码实现）⼀、实验⽬的语法分析是编译程序中的核⼼部分。本实验通过设计⼀个典型的⾃顶向下语法分析程序——LL(1)语法分析程序，进⼀步理解并掌握语法分析的原理和实现技术。⼆、实验原理语法分析的主要任务是“组词成句”，将词法分析给出的单词序列按语法规则构成更⼤的语法单位，如“程序、语句、表达式”等；或者说，语法分析的作⽤是⽤来判断给定输⼊串是否为合乎⽂法的句⼦。按照⽣成语法树的⽅向不同，常⽤的语法分析⽅法有两类：⾃顶向下分析和⾃底向上分析。⾃顶向下分析也称⾯向⽬标的分析⽅法，也就是从⽂法的开始符出发，试图推导出与输⼊单词串相匹配的句⼦。⾃底向上分析也称移进-归约分析⽅法，从输⼊单词串开始，试图归约到⽂法的开始符。预测分析法（LL(1)⽅法）的基本思想是：从⽂法开始符S出发，从左到右扫描源程序，每次通过向前查看1个字符，选择合适的产⽣式，⽣成句⼦的最左推导。三、实验步骤与要求1、复习教材第4章，进⼀步理解LL(1)⽅法的原理和实现技术。根据预测分析程序的框图（教材P94-图5.11），编写⼀个语法分析程序。可根据⾃⼰的能⼒选择以下三项（由易到难）之⼀作为分析算法的输⼊：(1)根据⽂法，⼈⼯构造分析表M，直接输⼊表M。(2)输⼊⽂法的FIRST集和FOLLOW集，由程序⾃动⽣成该⽂法的预测分析表M。(3)输⼊⽂法，由程序⾃动⽣成该⽂法的预测分析表M。2、程序具有通⽤性，即所编制的LL（1）语法分析程序能够适⽤于不同⽂法以及各种输⼊单词串。3、有运⾏实例。对于输⼊的⼀个⽂法和⼀个单词串，语法分析程序应能正确地判断此单词串是否为该⽂法的句⼦，并要求输出分析过程。4、设计合理的数据结构，特别是⽂法、预测分析表、分析栈等的存储结构。四、实验代码//#include"pch.h"#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>usingnamespacestd;voidGramF();//分解产⽣式程序voidGramIn();//⽂法输⼊程序voidWordIn();//⽂字输⼊程序boolIs(charx,chara[],intn);//是否在集合中voidGetFirst(chara);//first集求解程序voidADD(string&a,string&b);//集合相加程序集合voidADDfollow(string&a,string&b);//(follow)相加程序intBack(chara);//根据字母返回下标程序voidGetFollow(chara);//follow集求解程序boolIsChar(chara,stringb);//判断⼀个字符是否在⼀个集合中的程序voidFAtable();//预测分析表构建程序voidGAnalysis();//⽂法分析程序voidclearF();//净化程序voidcc();//i+()*ABCDEA->BCC->+BC|@B->DEE->*DE|@D->(A)|iinttable[100][100]={0};//预测表charVt[100]={""};//终结符charVn[100]={""};//⾮终结符stringGenerative[100]={""};//⽂法产⽣式存储stringGenerativeNew[100]={""};//⽂法产⽣式分解后的存储stringfirst[100]={""};//first集合stringfollow[100]={""};//follow集合charword[100]={""};//待测试的⽂字intVtNum=0;//终结符号的个数intVtNum=0;//终结符号的个数intVnNum=0;//⾮终结符号的个数intGenNum=0;//⽂法产⽣式个数intGenNumNew=0;//⽂法产⽣式分解后的个数stack<char>st;//预测分析栈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++;}}}/*************************/分解⽂法产⽣式程序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("请输⼊终结符号：\n");scanf_s("%c",Vt+i,1);while(*(Vt+i)!='\n'){i++;scanf_s("%c",Vt+i,1);}Vt[i]='#';i++;VtNum=i;//输⼊结束存储终结符号个数i=0;//i初始化值准备输⼊⾮终结符号printf("请输⼊⾮终结符号：\n");scanf_s("%c",Vn+i,1);while(*(Vn+i)!='\n'){i++;scanf_s("%c",Vn+i,1);}VnNum=i;//输⼊结束存储⾮终结符号个数i=0;//i初始化值准备输⼊⽂法产⽣式printf("请输⼊⽂法产⽣式：\n");charch;while(cin>>Generative[i]){i++;if((ch=getchar())=='\n')break;}GenNum=i;//输⼊结束存储⽂法产⽣式个数}/************⽂字输⼊程序*************/voidWordIn(){printf("请输⼊您需要测试的⽂字：\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)){//如果该⾮终结符产⽣式右部第⼀个字符是终结符,号则直接将其计⼊左部⾮终结符的FIRST集first[Back(GenerativeNew[i][0])]+=GenerativeNew[i][3];}elseif(Is(GenerativeNew[i][3],Vn,VnNum)){//如果该⾮终结符号右部第⼀个字符是⾮终结符,号则对该右部第⼀个字符的FIRST进⾏求解,并将其加⼊左部字符的GetFirst(GenerativeNew[i][3]);FIRST集ADD(first[Back(GenerativeNew[i][0])],first[Back(GenerativeNew[i][3])]);}elseif(GenerativeNew[i][3]=='@'){//,FIRST如果该⾮终结符产⽣式是个空则将空加⼊左部字符的集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*************/集清除重复元素程序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是终结符号，直接加⼊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是⾮终结符号，需要判断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是终结符号，直接加⼊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是⾮终结符号，需进⾏判断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])]);}}//}}/************判断⼀个字符是否在⼀个集合中的程序*************/boolIsChar(chara,stringb){inti=0;while(b[i]!='\0'){if(a==b[i])returntrue;i++;}returnfalse;}/*************************/预测分析表构建程序voidFAtable(){inti,j;for(i=0;i<VtNum;i++){for(j=0;j<GenNumNew;j++){if(Vt[i]==GenerativeNew[j][3])//如果终结符中则将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]=='@'){//如果当前的产⽣式是：A->a且，a='@'，则判断当前的Vt[i]是否在if(IsChar(Vt[i],follow[Back(GenerativeNew[j][0])])){table[Back(GenerativeNew[j][0])][i]=j;}}}}}/************根据字母返回终结符下标程序*************/intBBack(chara){for(inti=0;i<VtNum;i++){if(a==Vt[i])returni;}return-1;}/************根据字母返回⾮终结符下标程序*************//************根据字母返回⾮终结符下标程序*************/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];//获得产⽣式if(k==-1){error++;cout<<"步骤["<<n<<"]：识别错误！跳过"<<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<<"的右部分逆序⼊栈已经完成；\n";n++;}else{cout<<"步骤["<<n<<"]：⽤"<<chan<<"；\n";n++;//i++;}}}elseif(Is(st.top(),Vt,VtNum)){if(st.top()==word[i]){cout<<"步骤["<<n<<"]：匹配栈顶和当前符号"<<word[i]<<"，成功；\n";st.pop();i++;n++;}else{cout<<"步骤["<<n<<"]：识别失败！！\n";n++;break;}}a=st.top();a=st.top();}if(error){cout<<"步骤["<<n<<"]：识别错误！！错误跳过次数："<<error<<"\n";n++;}else{cout<<"步骤["<<n<<"]：识别成功！！\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();//初始化⼆维数组GramIn();//输⼊⾮终结、终结字符和⽂法产⽣式GramF();//⽂法产⽣式分析完毕inti,j;for(