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

课程设计报告
( 2011--2012年度第一学期)
名称: 编译技术课程设计
题目: 自动机的状态转换图表示
院系: 控制与计算机工程学院
班级: 信安 1001
学号:
学生姓名:
指导教师:
设计周数: 一周
成绩:
日期:2013年 1 月12日
1 课程设计的目的和要求
课程设计的目的
本次设计的时间为1周,目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模,应涵盖本课程内容和实际应用相关的主要技术。
课程设计的要求
要求设计一个具有绘图功能的程序,可以手工以状态转换图的方式绘制自动机;
图形化的自动机可以保存,读取;
根据状态转换图得出自动机的状态转换矩阵;
根据状态转换矩阵,自动绘制出状态转换图。
2 系统描述
本次课程设计是在win 7的环境下,使用visual C++。主要功能为描述一个确定的有限状态自动机,具体功能为绘制自动机,自动机转化为转移矩阵,转移矩阵自动转化为自动机。本课设中用圆圈表示状态,用大写字母表示,用弧线表示状态之间的转移关系,输入符号用小写字母表示,初态前面加箭头,终态集用双圆圈表示。
本次课程设计只针对简单的自动机,状态表示仅限于26个大写字符,输入符号仅限于26个小写字符,存在一定的局限性。本软件支持图形文件的读取和保存,同时,可以读取描述状态机的TXT文件(固定格式),自动绘制状态机
确定的自动机的描述
一个确定的又穷自动机M是一个五元组:M=(K,∑,f,S,Z),其中:
K是一个有穷状态集,这里我们用单个大写字母表示
∑是一个有穷输入符号集,这里我们用单个小写字母表示
f是状态间的转换函数,形如:f(K, a)=D,表示K状态输入字符a之后自动转换到D状态
S是唯一的初态
Z是终态集
状态转移矩阵的描述
一个确定的有限状态自动机还可以用一个矩阵表示,该矩阵的行表示状态,列表示输入符号,矩阵元素表示相应状态和输入符号后将要转换成的新状态,用“—>”表示初态,终态行在表尾部标以“1”,非终态标以“0”。
3 概要设计
概要设计
打开软件界面,点击进行绘图操作,先选中图形,在界面上点击,出现一个图元。选中图元,右击出现快捷菜单,选择更改图元属性或者删除图元,重复操作,直到把整个自动机绘制完成。
所有的图元都存放在CDocument类的两个链表中,这两条链分别为m_StatusList和m_RelationList,分别存放状态和关系图元。在OnDraw()函数中调用该链表进行绘图,保证图元可重复刷新和不丢失。
对关系图元,我们用两个变量分别标记它的开始图元和终止图元,以表示状态和关系之间的联系,在装换成状态装换矩阵时,我们用这种联系找到状态和输入符号之间的转换关系,做出状态转换矩阵
对于关系图元的位置,我们是根据其起始图元和终止图元的位置唯一确定的,这样,只要把状态图元的位置摆好了,关系弧也就不难画出来,根据这个巧妙的结构,在由转移矩阵绘制状态图时,我先设置状态的位置,然后关系弧线也就能轻而易举地画出来了。
状态图
选择图元
点击绘制
修改属性
绘制图元
读取文件
读取状态转换矩阵
删除
保存状态图
生成状态装换矩阵
系统用例图
用户
图3-1 系统用例图
系统用例
表3-1 绘制自动机状态图
用例名称
绘制自动机状态图
简述
用鼠标点击结合键盘输入方式绘制自动机状态图
前置条件
打开软件
基本流
在软件菜单或工具栏中选中需要绘制的图元
鼠标光标变成十字架形状,表示已经进入绘图状态
若是绘制状态,鼠标左击窗口空白处,绘制相应的状态,状态默认为S;若是绘制关系,鼠标依次点击想要绘制的起点和终点,绘制相应的关系,输入符号默认为a
选中绘制的状态圆或者关系弧(选中的图形会出现小方格表示选中状态),右击,出现快捷菜单,选择“删除”菜单来删除图元,选择“属性”菜单来修改图元的状态和输入符号
重复步骤3,4,直到图形绘制完成
备选流
鼠标右击,取消绘图,鼠标变成箭头形式
绘制一个图形后,光标回到初始状态,绘图结束,若需要继续画图,需重新选择图元。
绘制关系弧线时,若没有选择图元,光标回到初始状态,绘图结束
允许绘制从一个状态回到该状态本身的弧。
删除状态时应先删除和它联系的关系弧,否则会出错
允许一个状态既是初态又是终态,只需要在属性栏中将“初态”和“终态”多选框都选上
允许一条弧上有多个输入符号,只需要选择弧,右击选择“属性”菜单,用“重置”和“添加”按钮设