编译技术--实验指导书.doc

《编译技术--实验指导书.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《编译技术》实验指导书湘潭大学信息工程学院计算机工程系何春梅2015-09-01实验课时说明《编译技术》课总课时为32/8学时，其中实验课时为8学时，课时分配为：前三个实验是必做实验：其中DFA的模拟程序2学时、DFA的化简2学时、LL(1)文法判断程序4学时。后面3个实验为学生根据自己安排选做实验。目录实验1DFA模拟程序1实验2DFA化简2实验3LL(1)文法判断程序4实验4基于预测分析表法的语法分析程序(1)5实验5基于预测分析表法的语法分析程序(2)6实验6中间代码生成：逆波兰式的产生与计算8实验1词法程序设计——DFA模拟程序一、实验目的通过实验教学，加深学生对所学的关于编译的

2、理论知识的理解，增强学生对所学知识的综合应用能力，并通过实践达到对所学的知识进行验证。通过对DFA模拟程序实验，使学生掌握词法分析的实现技术，及具体实现方法。通过本实验加深对词法分析程序的功能及实现方法的理解。二、实验环境供Windows系统的PC机，可用C++/C#/Java等编程工具编写三、实验内容1、定义一个右线性正规文法，示例如(仅供参考)G[S]：S→aU

3、bVU→bV

4、aQV→aU

5、bQQ→aQ

6、bQ

7、e实验前要考虑清楚用哪种数据结构存储上述文法。2、构造其有穷确定自动机，如3、利用有穷确定自动机M=(K,Σ,f,S,Z）行为模拟程序算法，来对于任意给定的串，若属于该语言时，

8、该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”。K:=S；c:=getchar;whilec<>eofdo{K:=f(K,c);c:=getchar;};ifKisinZthenreturn(‘yes’)elsereturn(‘no’)四、实验方式与要求1、每位同学定义的语言或文法不同，上机编程实现2、实验报告格式要求书写要点：概要设计（总体设计思想）；详细设计（程序主流程、自动机的存储格式、关键函数的流程图）；结果分析（输入与输出结果、存在问题及有待改进善的地方、实验心得）。实验2DFA（确定的有穷自动机）的化简一、实验目的与要求通过设计、编写和调试将确定

9、的有穷自动机的状态数变为最少的C程序，使得学生掌握化简为有穷自动机的过程中的相关概念和方法。DFA的表现形式可以为表格或图形。二、问题描述每一个正规集都可以由一个状态数最少的DFA所识别，这个DFA是唯一的（不考虑同构的情况）。任意给定的一个DFA，根据以下算法设计一个C程序，将该DFA化简为与之等价的最简DFA。三、算法（1）构造具有两个组的状态集合的初始划分I：接受状态组F和非接受状态组Non-F。（2）对I采用下面所述的过程来构造新的划分I-new.ForI中每个组GdoBegin当且仅当对任意输入符号a,状态s和读入a后转换到I的同一组中；/*最坏情况下，一个状态就可能成为一个组

10、*/用所有新形成的小组集代替I-new中的G;end（3）如果I-new=I，令I-final=I,再执行第（4）步，否则令I=I=new,重复步骤（2）。（4）在划分I-final的每个状态组中选一个状态作为该组的代表。这些代表构成了化简后的DFA　M＇状态。令s是一个代表状态，而且假设：在DFAM中，输入为a时有从s到t转换。令t所在组的代表是r,那么在M’中有一个从s到r的转换，标记为a。令包含s0的状态组的代表是M’的开始状态，并令M’的接受状态是那些属于F的状态所在组的代表。注意,I-final的每个组或者仅含F中的状态，或者不含F中的状态。（5）如果M’含有死状态（即一个对所

11、有输入符号都有刀自身的转换的非接受状态d）,则从M’中去掉它；删除从开始状态不可到达的状态；取消从任何其他状态到死状态的转换。四、基本要求1、输入一个DFAM,输出一个与之等价的最小化的DFAM’，上机编程实现。2、实验报告格式要求书写要点：概要设计（总体设计思想）；详细设计：程序主流程、DFA的存储格式（即数据结构）、关键函数的流程图；结果分析（输入与输出结果、存在问题及有待改进善的地方、实验心得）五、测试数据输入下图的DFAM,得到其最简的DFAM’。DFAM六、实现提示：（1）可将输入的DFA存放在外部文本文件中，也可以直接从NFA转换得到。对DFA的最小化分两部分进行化简，即分别

12、对状态（结点）和路径（弧）进行最小化，最后输出最小化的DFA。（2）实现的数据结构：用链表实现DFA的构造：由结点链表和转换弧链表组成：structnode//结点的定义{intpos;//结点在哪个组中intnum；//结点的序号intaccept;//结点是否为接受状态structnode*next;}NODE;structarc//弧的定义{intstart;//开始的顶点位置charinput;//弧上所接受的输入字符int