北方工业大学计算机专业编译原理实验报告——语法分析器详细代码报告

编译原理实验报告实验题目：语法分析器构造指导教师：杨健姓名：班级：学号：实验成绩：实验题目语法分析器构造实验目的和要求编译器实现技术是一大宝库，一方面以编译器的实现为背景可以实践几乎全部在数据结构与算法分析课程中学到的主要数据结构与算法；另一方面，编译器设计中使用的问题求解方法、处理问题的思路被广泛地用于自动数据处理（转换）及其它一些新的研究领域。没有编译器的出现就没有现代数字计算机的发展。本次课设即以“语法规则的存储与显示”、“句子的生成”、“语法（分析）树的建立”等等这些编译器中的一些基本功能的实现为题，对高级程序设计语言在计算机中的表达和相关的处理有一个初步认识，提前领略“数据的自动转换与处理”这一计算机问题求解的核心技术。尽管这些功能的实现并不涉及较深入的编译技术，但也需要带着问题预先学习、掌握有关形式语言、编译原理与技术的若干基本概念。借助于词法分析程序提供的分析结果，编写一个算符优先语法分析程序，程序能进行语法结构分析和错误检查并产生相应的归约信息。同时给出出错信息和错误类型，从而加深对语法分析的理解。设计思想与框架1.算符优先文法定义：设有不含空串的一文法G，如果G中没有形如G……BC……的产生式，其中B和C为非终结符，且对任意两个终结符a，b之间之多只有，，=，三种关系的一种成立，则称G是一个算符优先文法。非终结符的FIRSTVT集合和LASTVT集合FIRSTVT（B）={b|B→b…或B→Cb…}LASTVT（B）={b|B→…a或B→…aC}2.算符优先矩阵算符优先关系矩阵，判断输入是否满足已知文法的依据。根据非终结符的FIRSTVT集合和LASTVT集合产生。1.“=”关系若A→…ab…或A→…aBb…，则a=b；2.“”关系若A→…aB…，对每一个b属于FIRSTVT（B），有ab；3.“”关系若A→…Bb…，对每一个a属于LASTVT（B），有ab。3.如何归约在分析过程中，利用分析栈存放已识别的那部分句型，而句型的其余部分由剩余输入串组成，通过比较栈顶符号和下一个输入符号之间的关系，可以判别栈顶符号是否为句柄尾符号。如果是句柄尾，则沿栈顶向下，在栈内寻找句柄头。关系和关系之间包括的符号串就是句柄，然后把它们弹出栈，并代之以归约后的非终结符。这样就完成了一次归约过程。4.算符优先分析方法的局限性由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。此外，通常一个适用语言的文法也很难满足算符优先文法的条件，因而致使算符优先分析法仅适用于表达式的语法分析。输入:所给文法的源程序字符串。输出：二元组构成的序列。实现过程:算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。算符优先文法的执行过程为：输入已知文法，分析其正确性，提取非终结符和终结符，构造非终结符的FIRSTVT集和LASTVT集，再次基础上构造算符优先关系矩阵，并用来判断表达式是否符合该文法。（1）输入已知文法，生成文法矩阵，判断该文法是否是算符优先文法。（2）用程序自动生成该文法的算符优先关系矩阵。（3）对人工输入的句型或句子，分析该句型或句子是否合法，能否用已知文法推出。（4）具有通用性。所开发的程序可适用于不同的文法和任意输入串，且能判断该文法是否为算符优先文法。（5）有运行实例。对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。核心算法voidprior_analysis(){inti,j,m;charq,str,ch[20];push('#');print(0,-1);u:readvt(&a);if(IsVT(stack[top]))j=top;elsej=top-1;do{while(big(j,a)&&strcmp(stack,#N)!=0){do{q=stack[j];if(IsVT(stack[j-1]))j=j-1;elsej=j-2;}while(!less(j,q));i=-1;while((top-j)!=0){ch[++i]=pop();}ch[i+1]='\0';for(m=0;m=5;m++){if(strcmp(word[m],ch)==0)str='N';}push(str);print(1,1);}if(less(j,a)){push(a);print(0,-1);if(stack[top]!='#')gotou;}else{if(equal(j,a)){push(a);print(0,0);if(stack[top]!='#')gotou;}else{error(j);a='#';}}}while(a!='#');}源程序及注释//实验二语法分析//算术表达式-项|算术表达式+项|算术表达式-项//项-因子|项*因子|项/因子//因子-变量|常数|(算术表达式)//算符优先关系表//----------------------------------//+-*/()i#//+//-//*/////(=?//)??//i??//#?=//----------------------------------#includeiostream#includecstdio#includeiomanipusingnamespacestd;#defineN100#defineNULL0FILE*fp;//预处理文件指针//定义符号栈的大小与输入字符串的大小以及算术表达式字符串的大小charstack[N],strings[N],oldstrings[N];chara;inttop=-1,k=0,step=1,n=0,No[N],id=1;//二维数组定义字符之间的优先关系(1表示,-1表示,0表示=,-2表示错误)intM[N][N]={{1,1,-1,-1,-1,1,-1,1},{1,1,-1,-1,-1,1,-1,1},{1,1,1,1,-1,1,-1,1},{1,1,1,1,-1,1,-1,1},{-1,-1,-1,-1,-1,0,-1,-2},{1,1,1,1,-2,1,-2,1},{1,1,1,1,-2,1,-2,1},{-1,-1,-1,-1,-1,-2,-1,0}};char*word[6]={N+N,N-N,N*N,N/N,)N(,i};//可归约字符串intprint(intt,intm){cout\nstep++setw(10);coutstacksetw(10);if(m==1)coutsetw(8);elseif(m==0)cout=setw(8);elsecoutsetw(8);coutasetw(10);cout&strings[k]setw(10);if(t){cout归约setw(8);No[n++]=step-1;}elsecout移进setw(8);return0;}voidpush(charch){stack[++top]=ch;}charpop(){chara;a=stack[top--];stack[top+1]='\0';returna;}intch_di(charch){switch(ch){case'+':return1;case'-':return2;case'*':return3;case'/':return4;case'(':return5;case')':return6;case'i':return7;case'#':return8;default:return0;}}intIsVT(charch){if(ch=='N')return0;elsereturn1;}intreadvt(char*a){if(IsVT(strings[k])){(*a)=strings[k];k++;return1;}else{k++;return0;}}intbig(intt,chara){if(M[ch_di(stack[t])-1][ch_di(a)-1]==1)return1;elsereturn0;}intless(intt,chara){if(M[ch_di(stack[t])-1][ch_di(a)-1]==-1)return1;elsereturn0;}intequal(intt,chara){if(M[ch_di(stack[t])-1][ch_di(a)-1]==0)return1;elsereturn0;}voiderror(intt){if(ch_di(stack[t])==6||ch_di(stack[t])==7){printf(\n错误e2:缺少运算符!);}elseif(ch_di(stack[t])==5){printf(\n错误e1:非法左括号!);}elseprintf(\n错误e3:非法右括号!);}voidprior_analysis(){inti,j,m;charq,str,ch[20];push('#');print(0,-1);u:readvt(&a);if(IsVT(stack[top]))j=top;elsej=top-1;do{while(big(j,a)&&strcmp(stack,#N)!=0){do{q=stack[j];if(IsVT(stack[j-1]))j=j-1;elsej=j-2;}while(!less(j,q));i=-1;while((top-j)!=0){ch[++i]=pop();}ch[i+1]='\0';for(m=0;m=5;m++){if(strcmp(word[m],ch)==0)str='N';}push(str);print(1,1);}if(less(j,a)){push(a);print(0,-1);if(stack[top]!='#')gotou;}else{if(equal(j,a)){push(a);print(0,0);if(stack[top]!='#')gotou;}else{error(j);a='#';}}}while(a!='#');}voidmain(){cout*********算符优先语法分析程序*********endl;coutE-E+T|E-T|Tendl;coutT-T*F|T/F|Fendl;coutF-(E)|iendl;coutE表示算术表达式.T表示项.F表示因子.i表示变量或常数.endl;cout优先表endl;cout+-*/()i#endl;cout+endl;cout-endl;cout*endl;cout/endl;cout(=e1endl;cout)e2e2endl;coutie2e2endl;cout#e3=endl;if((fp=fopen(预处理.txt,r))==NULL)//如果预处理文件中是空的{cout请先将实验1文件夹中的预处理.txt文件复制到实验2文件夹中!endl;system(pause);exit(0);}charch=fgetc(fp);charch1;while(ch!='#'){inti=-1,j=0,m=-1;while(ch!='='&&ch!='#'){ch1=ch;ch=fgetc(fp);if((ch1==''||ch1=='')&&ch=='=')ch=fgetc(fp);}if(ch==