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

《计科1304班_廖成_0902130408_编译原理实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CENTRALSOUTHUNIVERSITY编译原理课程实验报告姓名：廖成学号：专业班级：计算机科学与技术1304班指导老师：张修如实验一计算FIRSTVT集一、实验目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC。二、实验内容设计一个由正规文法生成FIRSTVT集的算法动态模拟，实现以下功能：1．输入一个文法G；2．输出由文法G构造FIRSTVT集的算法；3．输出FIRSTV

2、T集。三、实验要求1．思想的正确性，采用合适的数据存储结构等；2．程序实现的正确性，程序整体结构合理、编程风格规范等；3．程序功能的完善程度，包括功能的基本实现、基本完善、完全实现；4．工作认真、独立完成实验。四、实验步骤1．问题理解和分析：充分地分析和理解问题本身，弄清要求做什么；2．确定解决问题的方法：主要是找到解决问题的主要思路，该怎么做；3．详细设计和编码：确定算法的主要流程，再进行编程；4．程序调试和运行：掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感；五、程序设计5.1基本算法：构造集合FIRSTVT(P)的算法，按FIRSTVT(P)

3、的定义，可以用如下两条归则来构造：(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)，对栈施加如下操作：弹出栈定符号对记作

4、(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集。为了简便起见，程序中又构造了一个两维布尔数组firs

5、t[M][MN]来表示推导关系。数组第一维的M个字符代表非终结符；数组第二维的前M个字符代表非终结符，后N个字符代表终结符。以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];//非终结字符与终结字符数组in

6、tstp;//堆栈栈顶指针符号栈的数据结构：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(c

7、harX,intT)voidFIRSTVT(charX,intS)voidmain()inti,j;printf("请输入文法(按两次回车结束):");for(i=0;i

8、UT[i]