编译技术课程设计--自动机的状态转换图表示.doc

课程设计报告 ( 2011-2012年度第一学期)名 称： 编译技术课程设计 题 目： 自动机的状态转换图表示 院 系： 控制与计算机工程学院 班 级： 信安 1001 学 号： 学生姓名： 指导教师： 设计周数： 一周 成 绩： 日期：2013年 1 月12日 课程设计报告1 课程设计的目的和要求1.1 课程设计的目的本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。1.2 课程设计的要求1. 要求设计一个具有绘图功能的程序，可以手工以状态转换图的方式绘制自动机；2. 图形化的自动机可以保存，读取；3. 根据状态转换图得出自动机的状态转换矩阵；4. 根据状态转换矩阵，自动绘制出状态转换图。2 系统描述本次课程设计是在win 7的环境下，使用visual C+6.0软件制作的一个多功能绘图软件。主要功能为描述一个确定的有限状态自动机，具体功能为绘制自动机，自动机转化为转移矩阵，转移矩阵自动转化为自动机。本课设中用圆圈表示状态，用大写字母表示，用弧线表示状态之间的转移关系，输入符号用小写字母表示，初态前面加箭头，终态集用双圆圈表示。本次课程设计只针对简单的自动机，状态表示仅限于26个大写字符，输入符号仅限于26个小写字符，存在一定的局限性。本软件支持图形文件的读取和保存，同时，可以读取描述状态机的TXT文件（固定格式），自动绘制状态机2.1 确定的自动机的描述一个确定的又穷自动机M是一个五元组:M=(K，f，S，Z)，其中：1， K是一个有穷状态集，这里我们用单个大写字母表示2， 是一个有穷输入符号集，这里我们用单个小写字母表示3， f是状态间的转换函数，形如：f(K, a)=D，表示K状态输入字符a之后自动转换到D状态4， S是唯一的初态5， Z是终态集2.2 状态转移矩阵的描述一个确定的有限状态自动机还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符号后将要转换成的新状态，用“”表示初态，终态行在表尾部标以“1”，非终态标以“0”。3 概要设计3.1 概要设计打开软件界面，点击进行绘图操作，先选中图形，在界面上点击，出现一个图元。选中图元，右击出现快捷菜单，选择更改图元属性或者删除图元，重复操作，直到把整个自动机绘制完成。所有的图元都存放在CDocument类的两个链表中，这两条链分别为m_StatusList和m_RelationList，分别存放状态和关系图元。在OnDraw()函数中调用该链表进行绘图，保证图元可重复刷新和不丢失。对关系图元，我们用两个变量分别标记它的开始图元和终止图元，以表示状态和关系之间的联系，在装换成状态装换矩阵时，我们用这种联系找到状态和输入符号之间的转换关系，做出状态转换矩阵对于关系图元的位置，我们是根据其起始图元和终止图元的位置唯一确定的，这样，只要把状态图元的位置摆好了，关系弧也就不难画出来，根据这个巧妙的结构，在由转移矩阵绘制状态图时，我先设置状态的位置，然后关系弧线也就能轻而易举地画出来了。状态图选择图元点击绘制修改属性绘制图元读取文件读取状态转换矩阵删除保存状态图生成状态装换矩阵3.2 系统用例图用户图3-1 系统用例图3.3 系统用例表3-1 绘制自动机状态图用例名称绘制自动机状态图简述用鼠标点击结合键盘输入方式绘制自动机状态图前置条件打开软件基本流1. 在软件菜单或工具栏中选中需要绘制的图元2. 鼠标光标变成十字架形状，表示已经进入绘图状态3. 若是绘制状态，鼠标左击窗口空白处，绘制相应的状态，状态默认为S；若是绘制关系，鼠标依次点击想要绘制的起点和终点，绘制相应的关系，输入符号默认为a4. 选中绘制的状态圆或者关系弧（选中的图形会出现小方格表示选中状态），右击，出现快捷菜单，选择“删除”菜单来删除图元，选择“属性”菜单来修改图元的状态和输入符号5. 重复步骤3,4，直到图形绘制完成备选流2.1 鼠标右击，取消绘图，鼠标变成箭头形式3.1 绘制一个图形后，光标回到初始状态，绘图结束，若需要继续画图，需重新选择图元。3.2 绘制关系弧线时，若没有选择图元，光标回到初始状态，绘图结束3.3 允许绘制从一个状态回到该状态本身的弧。4.1 删除状态时应先删除和它联系的关系弧，否则会出错4.2 允许一个状态既是初态又是终态，只需要在属性栏中将“初态”和“终态”多选框都选上4.3 允许一条弧上有多个输入符号，只需要选择弧，右击选择“属性”菜单，用“重置”和 “添加”按钮设置输入符号，输入符号不允许空后置条件自动机状态图绘制完成特殊需求只能绘制指定的图元，关系只能绘制成弧线待解决问题3.1 由于弧线的确定是根据状态位置来的，所以不允许两个状态之间有两条同向的弧4.1 因为弧线范围难于确定，选择弧线存在一定的误差。4.2 因为同一条弧线上允许多个输入符号，所以弧线属性的设置不是很人性化。表3-2 状态图的文件操作用例名称状态图的文件操作简述状态图的文件操作，包括文件的新建，保存，读取前置条件打开软件基本流1， 点击新建文件，清空窗口当前内容2， 对一个绘制好的状态图，点击保存，弹出文件对话框，选择相应的路径，输入文件文件名，保存文件3， 点击打开文件，弹出文件对话框，选择相应的路径和文件，打开文件，在窗口显示状态图备选流3.1 如果打开的文件格式不同，会弹出“非预定格式文件”窗口3.2 同一时间内只能打开一个文件后置条件文件新建，保存，读取完成特殊需求只能打开本程序保存的文件表3-3 状态图转化为状态装换矩阵用例名称状态图转化为状态装换矩阵简述状态图转化为状态装换矩阵前置条件自动机状态图已经绘制完成基本流1， 点击菜单栏中的“操作-生成状态转换矩阵”或者点击按钮，生成状态转换矩阵后置条件在弹出窗口显示状态转换矩阵表3-4 状态装换矩阵转化为状态图用例名称状态装换矩阵转化为状态图简述将文件中的状态转换矩阵转换为状态图前置条件描述状态转换矩阵的文件已经存在基本流1， 点击菜单栏中的“操作-生成状态转换图”或者点击按钮，当前窗口内容清空，弹出状态转换的窗口。2， 点击打开文件按钮，打开指定格式的文件。在窗口中显示自动机的状态集，输入符号集，初态，终态集和状态转换函数。3， 点击生成状态图，在窗口生成状态转换图备选流2，点击取消，不做任何处理后置条件由状态转换矩阵文件画出新的状态图特殊需求状态转换矩阵文件的格式固定，具体为：第一行，初态；第二行，终态集；第三行，状态集；第四行，输入符号集；以后是状态转换函数，格式为：SS a（S状态，a输入符号）待解决问题因为状态转换矩阵读取不方便，所以在状态转换矩阵文件写出了自动机的格式，方便读取和操作3.4 开发环境在win 7的环境下，使用visual C+6.0的MFC标准编写完成。4 详细设计4.1 系统的类图CCompilerAppCCompilerViewCCompilerDocCMainFrame窗口类对话框类图元类CStatusCRelationCAboutDlgCAutomatonCAutomToGraphDlgCRelationProDlgCStatusProDlg4.2 主要算法的流程图状态图删除，修改图元绘制图元开始结束菜单读取状态图文件由状态转换矩阵转化读取转换矩阵文件状态转换矩阵保存文件图4-1 词法分析程序流程图4.3 数据分析与定义4.4数据类别成员变量成员类型功能描述CRelationm_BeginPoint，m_EndPoint;CPoint弧线的起点和终点xmin, xmax, ymin, ymax;int弧线网格闭包的描述m_nBegin m_nEnd;int弧线起始状态和终止状态的索引m_Marks100 char弧上输入符号的链表m_pStatusList;CObArray*状态链表指针m_nMarkNum; int输入符号的符号个数CStatusm_circle;CPoint状态的圆心坐标m_cStatuschar状态的表示符号m_bIsBeginBOOL状态是否是初态m_bIsEnd;BOOL状态是否是终态集CCompilerDocm_StatusListCObArray状态链表m_RelationListCObArray关系链表CCompilerViewm_bIsSelected;BOOL表示是否选中了图形m_nSelectedType;int 选中图形的类型m_nSelectedIndex;int 选中图形在链表中的索引号m_nGraphType;int 绘图时将要绘制的图元m_nFirstIndex;int 画弧线时，选中的第一个点CAutomatonm_pSList;CObArray*状态链表指针m_pRList;CObArray*关系链表指针CAutomToGraphDlgStart ，end10;char初态和终态集status30，mark30char状态集和输入符号集relation3030;Node（自定义）状态之间关系m_pStatusList,CObArray*状态链表指针m_pRelationList;CObArray*关系链表指针4.4 系统界面设计系统界面设计包括菜单，工具栏，右键快捷菜单。程序界面如下：图4-3 程序运行界面5 测试方法和测试结果5.1 测试用例1测试目的：测试能否绘制自动机状态图1，绘制一个状态 图5-12，选中，右键菜单修改状态属性 图5-23，关系弧线绘制选择起点 选择终点，绘制弧线 图 5-3 图5-44，关系弧属性修改图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，点击生成状态转换图按钮图5-132，在外部新建指定格式的文件图5-144， 点击打开文件图5-155， 得到自动机图5-166， 生成状态图图5-1719结论和展望结论程序用圆表示状态，用弧线表示状态间的关系，基本上比较美观地实现了自动机的绘制。并且添加了快捷菜单，可以帮助用户方便地编辑，修改，删除图元，同时可以由已知的状态图得到状态装换矩阵。本程序还实现了选作功能：由状态转换矩阵得到状态图。虽然本次课设的内容比较简单，但是在实现过程中，依然出现了众多的问题，主要体现在弧线的绘制和坐标确定上。在状态集和输入符号集的描述上，本程序只能处理单个字符，有一定的局限性。在由状态矩阵生成状态图过程中，状态的坐标只能人为地确定在某个区域，做出来的图形比较混乱。展望本次实验的不足还有很多，在选中图元的过程中，由于弧线范围难于确定，因而弧线不容易选中。在状态集和输入符号集的描绘，只能使用单个字母表示，否则会出现错误。在转移矩阵的生成过程中，状态之际的顺序只能依靠程序的输入顺序，生成的转换矩阵不美观。在状态图的生成过程中，坐标只能人为地规定，生成的状态图比较混乱。收获：通过本次实验，我收获了很多东西。首先对编译有了进一步的深刻理解，对有限状态自动机有了更深刻的认识。在编程方面，我学会了如何更好地整体把握和控制程序，同时，我学会了如何更加准确地描绘一个图形，以及图形元素的结合使用。在数据结构方面，我学会了如何更准确地进行图搜索和生成图。学习编译技术课程的体会和对本门课程的评价在做实验的过程中，发现自己对计算机中数学原理的应用不是很娴熟，不能快速地把数学几何理论应用到程序当中来。同时，在编程过程中，发现自己总是会忽略各种细节；在整体规划上，不能有效地进行整体规划，导致前后矛盾，写了很多多余的函数和变量，不仅浪费了编程时间，也增加了调试难度。参 考 文 献1 张素琴，吕映芝，蒋维杜等.编译原理（第二版）M.北京：清华大学出版社，2012.6,55-742阎光伟，彭文，徐林茜.Visual C+程序设计教程（第三版）M.北京：中国电力出版社，2011.83