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

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

ID:53322776

大小:224.00 KB

页数:12页

时间:2020-04-03

编译技术--实验指导书.doc_第1页
编译技术--实验指导书.doc_第2页
编译技术--实验指导书.doc_第3页
编译技术--实验指导书.doc_第4页
编译技术--实验指导书.doc_第5页
资源描述:

《编译技术--实验指导书.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。