中南大学编译原理实验报告

CENTRALSOUTHUNIVERSITY编译原理实验报告学生姓名专业班级学号学院信息科学与工程学院指导教师张修如实验时间2015年5月1实验一计算FIRSTVT集一、实验目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC/JAVA/C#/.NET。二、实验内容设计一个由正规文法生成FIRSTVT集的算法动态模拟，实现以下功能：1．输入一个文法G；2．输出由文法G构造FIRSTVT集的算法；3．输出FIRSTVT集。三、实验要求1．思想的正确性，采用合适的数据存储结构等；2．程序实现的正确性，程序整体结构合理、编程风格规范等；3．程序功能的完善程度，包括功能的基本实现、基本完善、完全实现；4．工作认真、独立完成实验。四、实验步骤1．问题理解和分析：充分地分析和理解问题本身，弄清要求做什么；2．确定解决问题的方法：主要是找到解决问题的主要思路，该怎么做；3．详细设计和编码：确定算法的主要流程，再进行编程；4．程序调试和运行：掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感；5．完成实验报告。五、程序设计5.1基本算法构造集合FIRSTVT(P)的算法按FIRSTVT(P)的定义，可以用如下两条归则来构造：2(1)若有产生式P→a…或→Qa…，则a∈FIRSTVT(P)(2)若a∈FIRSTVT(Q)，且有产生式P→Q…，则a∈FIRSTVT(P)构造算法：建立一个二维布尔数组F[P,a]，使得F[P,a]为真的条件适当且仅当a∈FIRSTVT(P)；再用一个栈STACK，把所有初值为真的数组元素F[P,a]的符号对(P,a)全都放到栈中；算法如下：(1)将布尔矩阵各元素置假；栈置空；(2)按照归则(1)查看产生式，对于P→a…或P→Qa..，置相应F[P,a]为真，符号对(P,a)入栈；(3)按规则(2)，对栈施加如下操作：弹出栈定符号对记作(Q,a)，查看所有产生式是否有形如P→Q…产生式，若有，且a∈FIRSTVT(P)，则将F[P,a]置为真，并把(P,a)入栈；(4)重复(3)，直到栈空为止。5.2定义数据结构在程序中，用两个字符数组vn[M]和vt[N]分别用来存储所有的非终结字符集与终结字符集。为了记录非终结符的FIRSTVT集，为此建立一个布尔数组F[M][N]，记录非终结符的FIRSTVT集。比如，F[i][j]=true表示vt[j]属于FIRSTVT(vn[i])，值为false表示相应的终结符不属于非终结符的FIRSTVT集。为了简便起见，程序中又构造了一个两维布尔数组first[M][M+N]来表示推导关系。数组第一维的M个字符代表非终结符；数组第二维的前M个字符代表非终结符，后N个字符代表终结符。以first数组为例，fist[i][M+j]代表非终结符vn[i]=P与非终结符vt[j]=a有推导关系P→a…；fist[i][j]代表非终结符vn[i]=P与非终结符vt[j]=Q有推导关系或P→Qa..。相关的数据结构定义如下：charvn[M],vt[N];//非终结字符与终结字符数组boolfirst[M][M+N],last[M][M+N];//以布尔数组形式定义推导关系charvn[M],vt[N];//非终结字符与终结字符数组intstp;//堆栈栈顶指针符号栈的数据结构：structrelation{intvn;intvt;};//结构体用来说明终结符vt与非终结符vn之间的关系，若关系存在说明vt属于FIRSTVT(vn)六、关键代码3#includestdio.h#includeiostream#defineN10#defineM10usingnamespacestd;//用于存储FIRSTVT集charFIRSTVT0[N],FIRSTVT1[N],FIRSTVT2[N],FIRSTVT3[N],FIRSTVT4[N];//接受输入charINPUT[N][M];//存储FIRSTVT集voidsetFIRSTVT(charX,intT){}voidFIRSTVT(charX,intS){}voidmain(){inti,j;printf(请输入文法(按两次回车结束):\n);for(i=0;iN;i++){for(j=0;jM;j++){scanf(%c,&INPUT[i][j]);if(INPUT[i][j]=='\n')break;}if(INPUT[i][0]=='\n')break;}//保存FIRSTVT集for(i=0;INPUT[i][0]!='\n';i++){FIRSTVT(INPUT[i][0],i);}printf(FIRSTVTSET:\n);for(i=0;INPUT[i][0]!='\n';i++){switch(i){case0:printf(FIRSTVT();printf(%c,INPUT[0][0]);printf()={);for(j=0;FIRSTVT0[j]!='\0';j++){printf(%c,FIRSTVT0[j]);if(FIRSTVT0[j+1]!='\0')printf(,);4}printf(}\n);break;case1:printf(FIRSTVT();printf(%c,INPUT[1][0]);printf()={);for(j=0;FIRSTVT1[j]!='\0';j++){printf(%c,FIRSTVT1[j]);if(FIRSTVT1[j+1]!='\0')printf(,);}printf(}\n);break;case2:printf(FIRSTVT();printf(%c,INPUT[2][0]);printf()={);for(j=0;FIRSTVT2[j]!='\0';j++){printf(%c,FIRSTVT2[j]);if(FIRSTVT2[j+1]!='\0')printf(,);}printf(}\n);break;case3:printf(FIRSTVT();printf(%c,INPUT[3][0]);printf()={);for(j=0;FIRSTVT3[j]!='\0';j++){printf(%c,FIRSTVT3[j]);if(FIRSTVT3[j+1]!='\0')printf(,);}printf(}\n);break;case4:printf(FIRSTVT();printf(%c,INPUT[4][0]);printf()={);for(j=0;FIRSTVT4[j]!='\0';j++){printf(%c,FIRSTVT4[j]);if(FIRSTVT4[j+1]!='\0')printf(,);}printf(}\n);break;default:break;5}}printf(\n);system(pause);}七、实验结果与总结7.1实验结果上图FIRSTVT集的关系矩阵中，{}内的终结字符属于对应的非终结字符的FIRSTVT集，从上面两个步骤可知用程序运算的结果和分析得到的FIRSTVT集相符合。7.2实验总结通过此次实验，我复习巩固了自下而上的分析方法，其中重点复习了算符优先分析算法，对词法、文法的判断有了较深刻的认识，对算符优先分析算法的FirstVT集和LastVT集的构造有了更加深刻的理解，对其中数据的流向和数据的输出操作有了很清晰的认识，对数据在该实验中的存储和运算有了深刻的理解。同时，此次实验还增强了我的编码能力。6实验二自上而下的语法分析--预测分析法设计与实现一、实验目的加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。二、实验内容用预测分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。三、实验要求1.对语法规则有明确的定义；2.编写的分析程序能够对实验一的结果进行正确的语法分析；3.对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；4.实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。四、实验步骤1.定义目标语言的语法规则；2.求解预测分析方法需要的符号集和分析表；3.依次读入符号串，根据预测分析的方法进行语法分析，直到源程序结束；4.对遇到的语法错误做出错误处理。五、程序设计所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL（1）分析器。7我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了JAVA语言来编写，其逻辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析过程。（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。六、关键代码LL1_Analysis.javapackageanalyse;输出a1a2a3……ai……an#输入串（源程序）总控程序预测分析表MX1┇Xn-1Xn#STACK分析栈8importjava.io.*;importjava.util.Stack;publicclassLL1_Analysis{Stringterminator;//终结符StringnonTerminator;//非终结符String[][]analysisTable;//分析表publicStackStringstack=null;StringBufferstrArray;//字符数组intindex=0;//字符数组索引值//匹配结果：无效输入，成功（均为#），两字符相等（且不等于#），弹栈（产生式为ε），压栈（将产生式反序入栈），错误（栈值为null）enumType{INVALID_STR,SUCCESS,EQUAL,POP_STACK,PUSH_STR,ERROR}FileWriterwriter=null;voidtemp(){}/***执行预测分析法*/publicvoidrun(){initialization();analysis();}publicStringfind(Stringstr1,Stringstr2){}voidanalysis(){}//从输入串数组读一个StringStringreadFromStrArray(StringBufferstrArray){}//输入串指针前移voidindexFo