编译课设报告

《编译课设报告》由会员分享，可在线阅读，更多相关《编译课设报告（20页珍藏版）》请在装配图网上搜索。

1、课程设计报告（2011-2012年度第一学期）名称：编译技术课程设计题目:自动机的状态转换图表示院系：控制与计算机工程学院班 级：信安1001学 号：1101290112学生姓名：王斌指导教师：王红设计周数：一周成 绩：日期：2013年1月12日1课程设计的目的和要求1.1 课程设计的目的本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论 的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。1.2 课程设计的要求1. 要求设计一个具有绘图功能的程序，可以手工以状态转换图的方式绘制自动机；2. 图形化的自动机可以保存，读取；3. 根据状态转换

2、图得出自动机的状态转换矩阵；4. 根据状态转换矩阵，自动绘制出状态转换图。2系统描述本次课程设计是在 win 7的环境下，使用visual C+6.0软件制作的一个多功能绘图软件。 主要功能为描述一个确定的有限状态自动机，具体功能为绘制自动机，自动机转化为转移矩 阵，转移矩阵自动转化为自动机。本课设中用圆圈表示状态，用大写字母表示，用弧线表示 状态之间的转移关系，输入符号用小写字母表示，初态前面加箭头，终态集用双圆圈表示。本次课程设计只针对简单的自动机，状态表示仅限于26个大写字符，输入符号仅限于26个小写字符，存在一定的局限性。本软件支持图形文件的读取和保存，同时，可以读取描 述状态机的TX

3、T文件（固定格式），自动绘制状态机2.1 确定的自动机的描述一个确定的又穷自动机 M是一个五元组：M=（K,X, f，S，Z），其中：1， K是一个有穷状态集，这里我们用单个大写字母表示2，刀是一个有穷输入符号集，这里我们用单个小写字母表示3， f是状态间的转换函数，形如：f（K, a）=D，表示K状态输入字符a之后自动转换到D状 态4， S是唯一的初态5，Z是终态集删除绘制图元选择图元点击绘制读取文件修改属性状态图保存状态图用户读取状态转换矩阵图3-1系统用例图生成状态装换矩阵V 厂 2-课程设计报告2.2 状态转移矩阵的描述一个确定的有限状态自动机还可以用一个矩阵表示，该矩阵的行表示状态，

4、列表示输入 符号，矩阵兀素表示相应状态和输入符号后将要转换成的新状态，用“一”表示初态，终态行在表尾部标以“1”，非终态标以“ 0”。3概要设计3.1 概要设计打开软件界面，点击进行绘图操作，先选中图形，在界面上点击，出现一个图元。选中 图元，右击出现快捷菜单，选择更改图元属性或者删除图元，重复操作，直到把整个自动机 绘制完成。所有的图元都存放在 CDocument类的两个链表中，这两条链分别为 m_StatusList和 m_RelationList，分别存放状态和关系图元。在OnDraw()函数中调用该链表进行绘图，保证图 元可重复刷新和不丢失。对关系图元，我们用两个变量分别标记它的开始图

5、元和终止图元，以表示状态和关系之 间的联系，在装换成状态装换矩阵时，我们用这种联系找到状态和输入符号之间的转换关系， 做出状态转换矩阵对于关系图元的位置，我们是根据其起始图元和终止图元的位置唯一确定的，这样，只 要把状态图元的位置摆好了，关系弧也就不难画出来，根据这个巧妙的结构，在由转移矩阵 绘制状态图时，我先设置状态的位置，然后关系弧线也就能轻而易举地画出来了。3.2 系统用例图3.3 系统用例表3-1绘制自动机状态图用例名称绘制自动机状态图简述用鼠标点击结合键盘输入方式绘制自动机状态图前置条件打开软件基本流1. 在软件菜单或工具栏中选中需要绘制的图兀2. 鼠标光标变成十字架形状，表示已经进

6、入绘图状态3. 若是绘制状态，鼠标左击窗口空白处，绘制相应的状态，状态默认为S;若是绘制关系，鼠标依次点击想要绘制的起点和终点，绘制相应的关系，输入符号默认为a4. 选中绘制的状态圆或者关系弧（选中的图形会出现小方格表示选中状态），右击，出现快捷菜单，选择“删除”菜单来删除图元，选择“属性”菜单来修改图元的状态和输入符号5. 重复步骤3,4，直到图形绘制完成备选流2.1鼠标右击，取消绘图，鼠标变成箭头形式3.1绘制一个图形后，光标回到初始状态，绘图结束，若需要继续画图，需重新选择图丿兀。3.2绘制关系弧线时，若没有选择图元，光标回到初始状态，绘图结束3.3允许绘制从一个状态回到该状态本身的弧。

7、4.1删除状态时应先删除和它联系的关系弧，否则会出错4.2允许一个状态既是初态又是终态，只需要在属性栏中将“初态”和“终态”多选框 都选上4.3允许一条弧上有多个输入符号，只需要选择弧，右击选择“属性”菜单，用“重置”和“添加”按钮设置输入符号，输入符号不允许空后置条件自动机状态图绘制完成特殊需求只能绘制指定的图元，关系只能绘制成弧线待解决问题3.1由于弧线的确定是根据状态位置来的，所以不允许两个状态之间有两条冋向的弧4.1因为弧线范围难于确定，选择弧线存在一定的误差。4.2因为冋一条弧线上允许多个输入符号，所以弧线属性的设置不是很人性化。V 厂.* r课程设计报告表3-2状态图的文件操作用例

8、名称状态图的文件操作简述状态图的文件操作，包括文件的新建，保存，读取前置条件打开软件基本流1，点击新建文件，清空窗口当前内容2，对一个绘制好的状态图，点击保存，弹出文件对话框，选择相应的路径，输入文件 文件名，保存文件3，点击打开文件，弹出文件对话框，选择相应的路径和文件，打开文件，在窗口显示 状态图备选流3.1如果打开的文件格式不冋，会弹出“非预定格式文件”窗口3.2同一时间内只能打开一个文件后置条件文件新建，保存，读取完成特殊需求只能打开本程序保存的文件表3-3状态图转化为状态装换矩阵用例名称状态图转化为状态装换矩阵简述状态图转化为状态装换矩阵前置条件自动机状态图已经绘制完成基本流1,点击

9、菜单栏中的“操作-生成状态转换矩阵”或者点击*按钮，生成状态转换矩阵后置条件在弹出窗口显示状态转换矩阵表3-4状态装换矩阵转化为状态图用例名称状态装换矩阵转化为状态图简述将文件中的状态转换矩阵转换为状态图前置条件描述状态转换矩阵的文件已经存在基本流1，点击菜单栏中的“操作- 生成状态转换图”或者点击按钮，当前窗口内容清空，弹出状态转换的窗口。2，点击打开文件按钮，打开指定格式的文件。在窗口中显示自动机的状态集，输入符 号集，初态，终态集和状态转换函数。3,点击生成状态图，在窗口生成状态转换图备选流2，点击取消，不做任何处理后置条件由状态转换矩阵文件画出新的状态图特殊需求状态转换矩阵文件的格式固

10、定，具体为：第一行，初态；第二行，终态集；第三行，状态集；第四行，输入符号集；以后是状态转换函数，格式为：SS a (S状态，a输入V 厂.才r课程设计报告符号）待解决问题因为状态转换矩阵读取不方便，所以在状态转换矩阵文件写出了自动机的格式，方便 读取和操作3.4 开发环境在win 7的环境下，使用 visual C+6.0的MFC标准编写完成。4详细设计4.1 系统的类图窗口类图元类对话框类4.2 主要算法的流程图开始菜单绘制图元读取状态图文件由状态转换矩阵转化删除，修改图元读取转换矩阵文件状态图状态转换矩阵保存文件结束图4-1词法分析程序流程图4.3 数据分析与定义4.4数据类别成员变量成

11、员类型功能描述CRelatio nm BeginPoint,m EndPoint;CPoi nt弧线的起点和终点xmi n, xmax, ymi n, ymax;int弧线网格闭包的描述m n Beg inm nEnd;int弧线起始状态和终止状态的叮 厂 M -几厂 课程设计报告索引m Marks100char弧上输入符号的链表m pStatusList;CObArray*状态链表指针m n MarkNum;int输入符号的符号个数CStatusm circle;CPoi nt状态的圆心坐标m cStatuschar状态的表示符号m blsBegi nBOOL状态是否是初态m blsE nd

12、;BOOL 状态是否是终态集CCompilerDocm StatusListCObArray状态链表m Relatio nListCObArray关系链表CCompilerViewm blsSelected;BOOL表示是否选中了图形m n SelectedType;int选中图形的类型m n SelectedI ndex;int选中图形在链表中的索引号m n GraphType;int绘图时将要绘制的图元m nFi rstI ndex;int画弧线时，选中的第一个点CAutomat onm pSList;CObArray*状态链表指针m pRList;CObArray*关系链表指针CAuto

13、mToGraphDIgStart ，end10;char初态和终态集status30, mark30char状态集和输入符号集relatio n3030;Node（自定 义）状态之间关系m pStatusList,CObArray*状态链表指针m pRelation List;CObArray*关系链表指针4.4 系统界面设计系统界面设计包括菜单，工具栏，右键快捷菜单。程序界面如下:图4-3程序运行界面5测试方法和测试结果5.1测试用例1测试目的：测试能否绘制自动机状态图1,绘制一个状态图5-12,选中，右键菜单修改状态属性图5-2选择终点，绘制弧线3，关系弧线绘制 选择起点图5-3图5-44

14、,关系弧属性修改图5-55,重复上述过程，绘制自动机状态图图5-65.2测试用例2测试目的：绘制状态转换矩阵1状态转换图图5-72，状态转换矩阵图5-85.3测试用例3测试目的：测试文件的保存，读取，新建1绘制的状态图图5-92,保存文件图 5-103,新建文件图 5-114,打开文件图 5-12图 5-125.4 测试用例4测试目的：测试状态转换矩阵转化为状态图1点击生成状态转换图按钮MVGfiDUP - Ccmplffr图 5-13I2,在外部新建指定格式的文件文禅洞辑樓式g】童看也I幫助凹QSLTQabSU日SV bLQ aUV bVU aVQ bQQ aQQ b图 5-144,点击打开

15、文件-: -C 二图一也： 松*(0| 壬y-M3 -ilft 1： 101- OlU.dteit *讥 Mitreddfl Wr d就“JiAuT5,得到自动机fi*srTift IT亦粗图 5-15图 5-166,生成状态图图 5-17结论和展望结论程序用圆表示状态，用弧线表示状态间的关系，基本上比较美观地实现了自动机的绘制。 并且添加了快捷菜单，可以帮助用户方便地编辑，修改，删除图元，同时可以由已知的状态 图得到状态装换矩阵。本程序还实现了选作功能：由状态转换矩阵得到状态图。虽然本次课设的内容比较简单，但是在实现过程中，依然出现了众多的问题，主要体现 在弧线的绘制和坐标确定上。在状态集和

16、输入符号集的描述上，本程序只能处理单个字符， 有一定的局限性。在由状态矩阵生成状态图过程中， 状态的坐标只能人为地确定在某个区域, 做出来的图形比较混乱。展望本次实验的不足还有很多，在选中图元的过程中，由于弧线范围难于确定，因而弧线不 容易选中。在状态集和输入符号集的描绘，只能使用单个字母表示，否则会出现错误。在转 移矩阵的生成过程中，状态之际的顺序只能依靠程序的输入顺序，生成的转换矩阵不美观。 在状态图的生成过程中，坐标只能人为地规定，生成的状态图比较混乱。收获：通过本次实验，我收获了很多东西。首先对编译有了进一步的深刻理解，对有限 状态自动机有了更深刻的认识。在编程方面，我学会了如何更好地

17、整体把握和控制程序，同 时，我学会了如何更加准确地描绘一个图形，以及图形元素的结合使用。在数据结构方面， 我学会了如何更准确地进行图搜索和生成图。学习编译技术课程的体会和对本门课程的评价在做实验的过程中，发现自己对计算机中数学原理的应用不是很娴熟，不能快速地把数 学几何理论应用到程序当中来。同时，在编程过程中，发现自己总是会忽略各种细节；在整 体规划上，不能有效地进行整体规划，导致前后矛盾，写了很多多余的函数和变量，不仅浪 费了编程时间，也增加了调试难度。参考文献1 张素琴，吕映芝，蒋维杜等编译原理（第二版）M.北京：清华大学出版社，2012.6,55-742 阎光伟，彭文，徐林茜.Visual C+程序设计教程（第三版）M.北京：中国电力出版社，2011.83