©2010-2025 宁波自信网络信息技术有限公司 版权所有
客服电话：0574-28810668 投诉电话：18658249818
浙ICP备2021020529号-1 | 浙B2-20240490
关注我们 ：
1、 课程设计报告 ( 2011--2012年度第一学期) 名 称： 编译技术课程设计 题 目： 自动机的状态转换图表示 院 系： 控制与计算机工程学院 班 级： 信安 1001 学 号： 学生姓名： 指导教师： 设计周数： 一周 成 绩： 日期：2013年 1 月1
2、2日 课程设计报告 1 课程设计的目的和要求 1.1 课程设计的目的 本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。 1.2 课程设计的要求 1. 要求设计一个具有绘图功能的程序，可以手工以状态转换图的方式绘制自动机； 2. 图形化的自动机可以保存，读取； 3. 根据状态转换图得出自动机的状态转换矩阵； 4. 根据状态转换矩阵，自动绘制出状态转换图。 2 系统描述 本次课程设计是在win 7的环境下，使用visual
3、C++6.0软件制作的一个多功能绘图软件。主要功能为描述一个确定的有限状态自动机，具体功能为绘制自动机，自动机转化为转移矩阵，转移矩阵自动转化为自动机。本课设中用圆圈表示状态，用大写字母表示，用弧线表示状态之间的转移关系，输入符号用小写字母表示，初态前面加箭头，终态集用双圆圈表示。 本次课程设计只针对简单的自动机，状态表示仅限于26个大写字符，输入符号仅限于26个小写字符，存在一定的局限性。本软件支持图形文件的读取和保存，同时，可以读取描述状态机的TXT文件（固定格式），自动绘制状态机 2.1 确定的自动机的描述 一个确定的又穷自动机M是一个五元组:M=(K，∑，f，S，Z)，其中：
4、 1， K是一个有穷状态集，这里我们用单个大写字母表示 2， ∑是一个有穷输入符号集，这里我们用单个小写字母表示 3， f是状态间的转换函数，形如：f(K, a)=D，表示K状态输入字符a之后自动转换到D状态 4， S是唯一的初态 5， Z是终态集 2.2 状态转移矩阵的描述 一个确定的有限状态自动机还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符号后将要转换成的新状态，用“—>”表示初态，终态行在表尾部标以“1”，非终态标以“0”。 3 概要设计 3.1 概要设计 打开软件界面，点击进行绘图操作，先选中图形，在界面上点击，出现一个
5、图元。选中图元，右击出现快捷菜单，选择更改图元属性或者删除图元，重复操作，直到把整个自动机绘制完成。 所有的图元都存放在CDocument类的两个链表中，这两条链分别为m_StatusList和m_RelationList，分别存放状态和关系图元。在OnDraw()函数中调用该链表进行绘图，保证图元可重复刷新和不丢失。 对关系图元，我们用两个变量分别标记它的开始图元和终止图元，以表示状态和关系之间的联系，在装换成状态装换矩阵时，我们用这种联系找到状态和输入符号之间的转换关系，做出状态转换矩阵 对于关系图元的位置，我们是根据其起始图元和终止图元的位置唯一确定的，这样，只要把状态图元的位置摆
6、好了，关系弧也就不难画出来，根据这个巧妙的结构，在由转移矩阵绘制状态图时，我先设置状态的位置，然后关系弧线也就能轻而易举地画出来了。 状态图 选择图元 点击绘制 修改属性 绘制图元 读取文件 读取状态转换矩阵 删除 保存状态图 生成状态装换矩阵 3.2 系统用例图 用户 图3-1 系统用例图 3.3 系统用例 表3-1 绘制自动机状态图 用例名称 绘制自动机状态图 简述 用鼠标点击结合键盘输入方式绘制自动机状态图 前置条件 打开软件 基本流 1. 在软件菜单或工具栏中选中需要绘制的图元 2. 鼠标光标变成十字架形状，表示
7、已经进入绘图状态 3. 若是绘制状态，鼠标左击窗口空白处，绘制相应的状态，状态默认为S；若是绘制关系，鼠标依次点击想要绘制的起点和终点，绘制相应的关系，输入符号默认为a 4. 选中绘制的状态圆或者关系弧（选中的图形会出现小方格表示选中状态），右击，出现快捷菜单，选择“删除”菜单来删除图元，选择“属性”菜单来修改图元的状态和输入符号 5. 重复步骤3,4，直到图形绘制完成 备选流 2.1 鼠标右击，取消绘图，鼠标变成箭头形式 3.1 绘制一个图形后，光标回到初始状态，绘图结束，若需要继续画图，需重新选择图元。 3.2 绘制关系弧线时，若没有选择图元，光标回到初始状态，绘图结束
8、 3.3 允许绘制从一个状态回到该状态本身的弧。 4.1 删除状态时应先删除和它联系的关系弧，否则会出错 4.2 允许一个状态既是初态又是终态，只需要在属性栏中将“初态”和“终态”多选框都选上 4.3 允许一条弧上有多个输入符号，只需要选择弧，右击选择“属性”菜单，用“重置”和 “添加”按钮设置输入符号，输入符号不允许空 后置条件 自动机状态图绘制完成 特殊需求 只能绘制指定的图元，关系只能绘制成弧线 待解决问题 3.1 由于弧线的确定是根据状态位置来的，所以不允许两个状态之间有两条同向的弧 4.1 因为弧线范围难于确定，选择弧线存在一定的误差。 4.2 因为同一条弧
9、线上允许多个输入符号，所以弧线属性的设置不是很人性化。 表3-2 状态图的文件操作 用例名称 状态图的文件操作 简述 状态图的文件操作，包括文件的新建，保存，读取 前置条件 打开软件 基本流 1， 点击新建文件，清空窗口当前内容 2， 对一个绘制好的状态图，点击保存，弹出文件对话框，选择相应的路径，输入文件文件名，保存文件 3， 点击打开文件，弹出文件对话框，选择相应的路径和文件，打开文件，在窗口显示状态图 备选流 3.1 如果打开的文件格式不同，会弹出“非预定格式文件”窗口 3.2 同一时间内只能打开一个文件 后置条件 文件新建，保存，读取完成 特殊需求
10、 只能打开本程序保存的文件 表3-3 状态图转化为状态装换矩阵 用例名称 状态图转化为状态装换矩阵 简述 状态图转化为状态装换矩阵 前置条件 自动机状态图已经绘制完成 基本流 1， 点击菜单栏中的“操作->生成状态转换矩阵”或者点击按钮，生成状态转换矩阵 后置条件 在弹出窗口显示状态转换矩阵 表3-4 状态装换矩阵转化为状态图 用例名称 状态装换矩阵转化为状态图 简述 将文件中的状态转换矩阵转换为状态图 前置条件 描述状态转换矩阵的文件已经存在 基本流 1， 点击菜单栏中的“操作->生成状态转换图”或者点击按钮，当前窗口内容清空，弹出状态转换的
11、窗口。 2， 点击打开文件按钮，打开指定格式的文件。在窗口中显示自动机的状态集，输入符号集，初态，终态集和状态转换函数。 3， 点击生成状态图，在窗口生成状态转换图 备选流 2，点击取消，不做任何处理 后置条件 由状态转换矩阵文件画出新的状态图 特殊需求 状态转换矩阵文件的格式固定，具体为：第一行，初态；第二行，终态集；第三行，状态集；第四行，输入符号集；以后是状态转换函数，格式为：SS a（S状态，a输入符号） 待解决问题 因为状态转换矩阵读取不方便，所以在状态转换矩阵文件写出了自动机的格式，方便读取和操作 3.4 开发环境 在win 7的环境下，使用vis
12、ual C++6.0的MFC标准编写完成。 4 详细设计 4.1 系统的类图 CCompilerApp CCompilerView CCompilerDoc CMainFrame 窗口类 对话框类 图元类 CStatus CRelation CAboutDlg CAutomaton CAutomToGraphDlg CRelationProDlg CStatusProDlg 4.2 主要算法的流程图 状态图 删除，修改图元 绘制图元 开始 结束 菜单 读取状态图文件 由状态转换矩阵转化 读取转换矩阵文件 状态转换矩阵 保存文
13、件 图4-1 词法分析程序流程图 4.3 数据分析与定义 4.4 数据类别 成员变量 成员类型 功能描述 CRelation m_BeginPoint，m_EndPoint; CPoint 弧线的起点和终点 xmin, xmax, ymin, ymax; int 弧线网格闭包的描述 m_nBegin m_nEnd; int 弧线起始状态和终止状态的索引 m_Marks[100] char 弧上输入符号的链表 m_pStatusList; CObArray* 状态链表指针 m_nMarkNum; int 输入符号的符号个数 CS
14、tatus m_circle; CPoint 状态的圆心坐标 m_cStatus char 状态的表示符号 m_bIsBegin BOOL 状态是否是初态 m_bIsEnd; BOOL 状态是否是终态集 CCompilerDoc m_StatusList CObArray 状态链表 m_RelationList CObArray 关系链表 CCompilerView m_bIsSelected; BOOL 表示是否选中了图形 m_nSelectedType; int 选中图形的类型 m_nSelectedIndex; int
15、选中图形在链表中的索引号 m_nGraphType; int 绘图时将要绘制的图元 m_nFirstIndex; int 画弧线时，选中的第一个点 CAutomaton m_pSList; CObArray* 状态链表指针 m_pRList; CObArray* 关系链表指针 CAutomToGraphDlg Start ，end[10]; char 初态和终态集 status[30]，mark[30] char 状态集和输入符号集 relation[30][30]; Node（自定义） 状态之间关系 m_pStatusList,
16、CObArray* 状态链表指针 m_pRelationList; CObArray* 关系链表指针 4.4 系统界面设计 系统界面设计包括菜单，工具栏，右键快捷菜单。程序界面如下： 图4-3 程序运行界面 5 测试方法和测试结果 5.1 测试用例1 测试目的：测试能否绘制自动机状态图 1，绘制一个状态 图5-1 2，选中，右键菜单修改状态属性 图5-2 3，关系弧线绘制 选择起点
17、 选择终点，绘制弧线 图 5-3 图5-4 4，关系弧属性修改 图5-5 5，重复上述过程，绘制自动机状态图 图5-6 5.2 测试用例2 测试目的：绘制状态转换矩阵 1，状态转换图 图5-7 2， 状态转换矩阵 图5-8 5.3 测试用例3 测试目的：测试文件的保存，读取，新建 1，绘制的状态图 图5-9 2，保存文件 图5-10
18、 3， 新建文件 图5-11 4， 打开文件 图5-12 图5-12 5.4 测试用例4 测试目的：测试状态转换矩阵转化为状态图 1，点击生成状态转换图按钮 图5-13 2，在外部新建指定格式的文件 图5-14 4， 点击打开文件 图5-15 5， 得到自动机 图5-16 6， 生成状态图 图5-17 20 结论和展望 结论 程序用圆表示状态，用弧线表示状态间的关系，基本上比较美观地实现了自动机的绘制。并且添加了快捷菜单，可以帮助用户方便地编辑，修改，删除图元，同时可以由已知的状态图得到状态装换矩阵。本程序还实现
19、了选作功能：由状态转换矩阵得到状态图。 虽然本次课设的内容比较简单，但是在实现过程中，依然出现了众多的问题，主要体现在弧线的绘制和坐标确定上。在状态集和输入符号集的描述上，本程序只能处理单个字符，有一定的局限性。在由状态矩阵生成状态图过程中，状态的坐标只能人为地确定在某个区域，做出来的图形比较混乱。 展望 本次实验的不足还有很多，在选中图元的过程中，由于弧线范围难于确定，因而弧线不容易选中。在状态集和输入符号集的描绘，只能使用单个字母表示，否则会出现错误。在转移矩阵的生成过程中，状态之际的顺序只能依靠程序的输入顺序，生成的转换矩阵不美观。在状态图的生成过程中，坐标只能人为地规定，生成的状
20、态图比较混乱。 收获：通过本次实验，我收获了很多东西。首先对编译有了进一步的深刻理解，对有限状态自动机有了更深刻的认识。在编程方面，我学会了如何更好地整体把握和控制程序，同时，我学会了如何更加准确地描绘一个图形，以及图形元素的结合使用。在数据结构方面，我学会了如何更准确地进行图搜索和生成图。 学习编译技术课程的体会和对本门课程的评价 在做实验的过程中，发现自己对计算机中数学原理的应用不是很娴熟，不能快速地把数学几何理论应用到程序当中来。同时，在编程过程中，发现自己总是会忽略各种细节；在整体规划上，不能有效地进行整体规划，导致前后矛盾，写了很多多余的函数和变量，不仅浪费了编程时间，也增加了
21、调试难度。 参 考 文 献 [1] 张素琴，吕映芝，蒋维杜等.编译原理（第二版）[M].北京：清华大学出版社，2012.6,55-74 [2]阎光伟，彭文，徐林茜.Visual C++程序设计教程（第三版）[M].北京：中国电力出版社，2011.8 [3]目 录 第一章 总论 1 一、项目概况 1 二、项目提出的理由与过程 6 三、项目建设的必要性 8 四、项目的可行性 12 第二章 市场预测 15 一、市场分析 15 二、市场预测 16 三、产品市场竞争力分析 19 第三章 建设规模与产品方案 22 一、建设规模 22 二、产品方案 22
22、三、质量标准 22 第四章 项目建设地点 25 一、项目建设地点选择 25 二、项目建设地条件 25 第五章 技术方案、设备方案和工程方案 28 一、技术方案 28 二、产品特点 30 三、主要设备方案 32 四、工程方案 32 第六章 原材料与原料供应 35 一、原料来源及运输方式 35 二、燃料供应与运输方式 35 第七章 总图布置、运输、总体布局与公用辅助工程 37 一、总图布置 37 二、 运输 38 三、总体布局 38 四、公用辅助工程 39 第八章 节能、节水与安全措施 44 一、主要依据及标准 44 二、节能 44 三、节水 45
23、 四、消防与安全 45 第九章 环境影响与评价 47 一、法规依据 47 二、项目建设对环境影响 48 三、环境保护措施 48 四、环境影响评价 49 第十章 项目组织管理与运行 50 一、项目建设期管理 50 二、项目运行期组织管理 52 第十一章 项目实施进度 55 第十二章 投资估算和资金筹措 56 一、投资估算 56 二、资金筹措 58 第十三章 财务评价与效益分析 61 一、项目财务评价 61 二、财务评价结论 65 三、社会效益 68 四、生态效益 68 第十四章 风险分析 70 一、主要风险分析识别 70 二、风险程度分析及防范风险的措施 70 第十五章 招标方案 72 一、招标范围 72 二、招标组织形式 72 三、招标方式 72 第十六章 结论与建议 74 一、可行性研究结论 74 二、建议 75 附 件 77 一、附表 77 二、附件 77 三、附图 77
©2010-2025 宁波自信网络信息技术有限公司 版权所有
客服电话：0574-28810668 投诉电话：18658249818
浙ICP备2021020529号-1 | 浙B2-20240490
关注我们 ：
