编译原理 实验指导书.doc

《编译原理 实验指导书.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《编译原理(E)》实验指导书计算机软件与工程系何春梅2011-12-2811目录实验1词法程序设计(1)1实验2词法程序设计(2)3实验3语法程序设计(1)4实验4语法程序设计(2)5实验5语法程序设计(3)6实验6中间代码生成811实验1词法程序设计——DFA（确定的有穷自动机）的化简一、实验目的与要求通过设计、编写和调试将确定的有穷自动机的状态数变为最少的C程序，使得学生掌握化简为有穷自动机的过程中的相关概念和方法。DFA的表现形式可以为表格或图形。二、问题描述每一个正规集都可以由一个状态数最少的DFA所识别，这个DFA是唯一的（不考虑同

2、构的情况）。任意给定的一个DFA，根据以下算法设计一个C程序，将该DFA化简为与之等价的最简DFA。三、算法（1）构造具有两个组的状态集合的初始划分I：接受状态组F和非接受状态组Non-F。（2）对I采用下面所述的过程来构造新的划分I-new.ForI中每个组GdoBegin当且仅当对任意输入符号a,状态s和读入a后转换到I的同一组中；/*最坏情况下，一个状态就可能成为一个组*/用所有新形成的小组集代替I-new中的G;end（3）如果I-new=I，令I-final=I,再执行第（4）步，否则令I=I=new,重复步骤（2）。（4）在划分I

3、-final的每个状态组中选一个状态作为该组的代表。这些代表构成了化简后的DFA　M＇状态。令s是一个代表状态，而且假设：在DFAM中，输入为a时有从s到t转换。令t所在组的代表是r,那么在M’中有一个从s到r的转换，标记为a。令包含s0的状态组的代表是M’的开始状态，并令M’的接受状态是那些属于F的状态所在组的代表。注意,I-final的每个组或者仅含F中的状态，或者不含F中的状态。（5）如果M’含有死状态（即一个对所有输入符号都有刀自身的转换的非接受状态d）,则从M’中去掉它；删除从开始状态不可到达的状态；取消从任何其他状态到死状态的转换

4、。四、基本要求1、输入一个DFAM,输出一个与之等价的最小化的DFAM’，上机编程实现。2、实验报告格式要求书写要点：概要设计（总体设计思想）；详细设计：程序主流程、DFA的存储格式（即数据结构）、关键函数的流程图；结果分析（输入与输出结果、存在问题及有待改进善的地方、实验心得）五、测试数据输入下图的DFAM,得到其最简的DFAM’。11DFAM六、实现提示：（1）可将输入的DFA存放在外部文本文件中，也可以直接从NFA转换得到。对DFA的最小化分两部分进行化简，即分别对状态（结点）和路径（弧）进行最小化，最后输出最小化的DFA。（2）实现的

5、数据结构：用链表实现DFA的构造：由结点链表和转换弧链表组成：structnode//结点的定义{intpos;//结点在哪个组中intnum；//结点的序号intaccept;//结点是否为接受状态structnode*next;}NODE;structarc//弧的定义{intstart;//开始的顶点位置charinput;//弧上所接受的输入字符intend;//结束的顶点位置structarc*next;}ARC;Structgroups//分组后各结点所在组{intn;//属于哪个组inti;//在组中的位置}GROUPs;（3）

6、实现方法：根据accept的值为0还是1进行初次划分I，将accept为0的所有结点构建成一个链表，将accept为1的所有结点构建一个链表。然后执行最小化函数，对每一个输入字符遍历以上个链表，对每个结点.num=弧.start的情况，查看该弧.end的组号是否相等，相等则不划分；若不相等，则需进一步划分，构建新的链表等。划分完成后选头结点为代表，删除结点链表上其他结点，并将弧线链表上需被删的弧.start或弧.end该为头结点。11实验2词法程序设计——DFA模拟程序一、实验目的通过实验教学，加深学生对所学的关于编译的理论知识的理解，增强学

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

8、bVU→bV

9、aQV→aU

10、bQQ→aQ

11、bQ

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

13、定的串，若属于该语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”。K:=S；c:=getchar;whilec<>eofdo{K