计科1304班_廖成_0902130408_编译原理实验报告

-1-CENTRALSOUTHUNIVERSITY编译原理课程实验报告姓名：廖成学号：0902130408专业班级：计算机科学与技术1304班指导老师：张修如-2-实验一计算FIRSTVT集一、实验目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC。二、实验内容设计一个由正规文法生成FIRSTVT集的算法动态模拟，实现以下功能：1．输入一个文法G；2．输出由文法G构造FIRSTVT集的算法；3．输出FIRSTVT集。三、实验要求1．思想的正确性，采用合适的数据存储结构等；2．程序实现的正确性，程序整体结构合理、编程风格规范等；3．程序功能的完善程度，包括功能的基本实现、基本完善、完全实现；4．工作认真、独立完成实验。四、实验步骤1．问题理解和分析：充分地分析和理解问题本身，弄清要求做什么；2．确定解决问题的方法：主要是找到解决问题的主要思路，该怎么做；-3-3．详细设计和编码：确定算法的主要流程，再进行编程；4．程序调试和运行：掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感；五、程序设计5.1基本算法：构造集合FIRSTVT(P)的算法，按FIRSTVT(P)的定义，可以用如下两条归则来构造：(1)若有产生式P→a…或→Qa…，则a∈FIRSTVT(P)(2)若a∈FIRSTV且有产生式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][MN]来表示推导关系。数组第一维的M个字符代表非终结符；数组第二维的前M个字符代表非终结符，后N个字符代-4-表终结符。以first数组为例，fist[i][Mj]代表非终结符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][MN],last[M][MN];//以布尔数组形式定义推导关系charvn[M],vt[N];//非终结字符与终结字符数组intstp;//堆栈栈顶指针符号栈的数据结构：structrelationintvn;intvt;//结构体用来说明终结符vt与非终结符vn之间的关系，若关系存在说明vt属于FIRSTVT(vn)六、关键代码#include#include#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(请输入文法(按两次回车结束):);for(i=0;iN;i++){for(j=0;jM,j++){scanf(%c,&INPUT[i][j]);if(INPUT[i][j]=='')break;if(INPUT[i][0]=='')break;}}//保存FIRSTVT集for(i=0;INPUT[i][0]!='';i++){-5-FIRSTVT(INPUT[i][0],i);}printf(FIRSTVTSET:);for(i=0;INPUT[i][0]!='';i++){}switch(i){case0:{printf(FIRSTVT();printf(%,INPUT[0][0]);printf()=);for(j=0;FIRSTVT0[j]!='0';j++){printf(%c,FIRSTVT0[j]);if(FIRSTVT0[j1]!='0')printf();}printf(,);break;}case1:{printf(FIRSTVT();printf(%c,INPUT[1][0]);printf()=);for(j=0;FIRSTVT1[j]!='0';j++){printf(%c,FIRSTVT1[j]);if(FIRSTVT1[j1]!='0')printf(,);}printf();break;}case2:{printf(FIRSTVT();printf(%c,INPUT[2][0]);printf()=);for(j=0;FIRSTVT2[j]!='0';j++){printf(%c,FIRSTVT2[j]);if(FIRSTVT2[j1]!='0')-6-printf(,);}printf();break;}case3:{printf(FIRSTVT();printf(%c,INPUT[3][0]);printf()=);for(j=0;FIRSTVT3[j]!='0';j++){printf(%c,FIRSTVT3[j]);if(FIRSTVT3[j1]!='0')printf(,);}printf();break;}case4:{printf(FIRSTVT();printf(%c,INPUT[4][0]);printf()=);for(j=0;FIRSTVT4[j]!='0';j++){printf(%c,FIRSTVT4[j]);if(FIRSTVT4[j1]!='0')printf(,);}printf();break;}default:break;printf();system(pause);实验二自上而下语法分析-7-一、实验目的加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。二、实验内容在实验1的基础上，用自上而下语法分析分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。三、实验要求：1.对语法规则有明确的定义；2.编写的分析程序能够对实验一的结果进行正确的语法分析；3.对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；4.实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。四、实验步骤1.定义目标语言的语法规则；2.求解预测分析方法需要的符号集和分析表；3.依次读入实验一的分析结果，根据预测分析的方法进行语法分析，直到源程序结束；4.对遇到的语法错误做出错误处理。五、设计思路和实现过程本实验是使用LL（1）方法实现的语法分析器，我是用的是MFC实现的设计思路分为以下几步：-8-1、先读入输入串，判断输入串有没有语法错误，如有语法错误，提示第几个语法错误，退出；2、将“或”语句拆开，如果有左递归，消除左递归；3、判断可以产生空字符的非终结符，将其储存在一个数组中；4、计算非终结符的first集，follow集；5、计算select集；6、创建预测分析表；7、对照预测分析表对句子进行分析，输出每一步的操作。六、错误处理1、如果未输入文法，则提示输入文法；2、如果文法有错误，既不是以类似于“S-”开头的，则提示错误发生在第几行；3、如果文法不是LL（1）文法，程序会予以提示；4、如果句子不是以“#”结尾的，或者句子中含有大写字母的，予以提示；5、计算follow集时，如果follownumkey大于某个值，则可认定求follow集陷入死循环，即有右递归或间接右递归，此时跳出去，终止死循环。七、关键代码voidCGrammaanalysisDlg::OnChange(){intn=0;UpdateData();inti,nLineCount=m_gramma1.GetLineCount();//m_gramma是与edit控件关联的变量CStringstrText;//Dumpeverylineoftextoftheeditcontrol.for(i=0;inLineCount;i++)//检测每一句文法输入是否正确{//lengthoflinei:intlen=m_gramma1.LineLength(m_gramma1.LineIndex(i));m_gramma1.GetLine(i,strText.GetBuffer(len),len);strText.ReleaseBuffer(len);if(strText.IsEmpty())break;-9-if(!getin(i,strText))//整理return;//MessageBox(strText);//输出得到的每行数据}m_gramma.Empty();Delpare();//消除左递归deduce0_colec();//将所有能推导出0的非终符放在数组colec0[30]中Select_Collection();//创建select集Estab_preanatab();//创建预测分析表key=1;}boolCGrammaanalysisDlg::getin(inti,CStringstrLine)//整理{charline_no=i+'0';if(!isupper(strLine[0])||strLine[1]!='-'||strLine[2]!=''){CStringerror=TheSyntaxonline+(CString)line_no+iswrong!pleasecheckandenteragain:\n;MessageBox(error);returnfalse;}else{intm=0;for(intj=0;jstrLine.GetLength();j++){if(strLine[j]!='|'){stotax[sto_tax][m++]=strLine[j];continue;}else{stotax[sto_tax][m]='\0';sto_tax++;stotax[sto_tax][0]=stotax[sto_tax-1][0];stotax[sto_tax][1]=stotax[sto_tax-1][1];stotax[sto_tax][2]=stotax[sto_tax-1][2];m=3;continue;-10-}}stotax[sto_tax][m]='\0';sto_tax++;i=0;startchar=stotax[0][0];returnTRUE;}}voidCGrammaanalysisDlg::Delpare()//消除左递归{ll_key=0;keylr=0;for(inti=0;isto_tax;i++)strcpy(_