朱航宇-20112878-编译原理合设计
更新时间:2024-03-21 07:59:01 阅读量: 综合文库 文档下载
- 朱航宇音乐老师推荐度:
- 相关推荐
编译原理合设计
指导教师:李宏芒专业班级:信安姓 名:朱航宇学 号:
11-1 20112878 - 1 -
1
一.课程设计目的
《编译原理》是计算机专业的一门重要的专业课程,其中包含大量软件设计
思想。大家通过课程设计,实现一些重要的算法,或设计一个完整的编译程序模型,能够进一步加深理解和掌握所学知识,对提高自己的软件设计水平具有十分重要的意义。
二.课程设计内容
(12,13题:12题 DFA 状态最少化的程序实现和13题 把NFA确定化为DFA 的算法实现,合并为一题,将NFA确定化为DFA,再将DFA化简即最小化。)
我在选择课程设计题目时,只选择了12题DFA的最小化。但由于12题工作
量较小同时为了提高我的编程能力我将13题NFA确定化为DFA,将这两题合并为一题,即NFA确定化到最小化的实现。NFA的确定化和DFA的最小化主要是为了更好地使用状态转换图构造词法分析程序和词法分析程序的自动生成。设计并实现将NFA确定化为DFA的子集构造算法以及DFA的最小化,从而更好地理解有限自动机之间的等价性,掌握词法分析器自动产生器的构造技术。 三.设计要求
构造一程序,实现:将给定的NFA M(其状态转换矩阵及初态、终态信息从键盘输入),确定化为DFA M’。(要先实现ε-CLOSURE函数和Ia函数)。输出DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。然后将由确定化后的的DFA M的有限状态集S划分成若干互不相交的子集,使得:任何不同的两个子集中的状态都是可区别的,而同一子集中的任何两个状态都是等价的(要利用Ia函数,但并不需要构造ε-CLOSURE函数,因这是DFA)。输出化简后的DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。
四.设计思路
4.1 NFA确定化为DFA 1.非确定有限自动机NFA
一个非确定有限自动机(NFA)M是一个五元式M=(S,∑,δ,S0,F)
其中(1)S是一个有限集,它的每一个元素称为一个状态;
(2) ∑是一个有穷字母表,它的每一个元素称为一个输入字符;
(3) δ是一个从S×∑*到S的子集映照; (4)S0属于∑,是一个非空初态集; (5)F属于S,是一个终态集(可空)。
显然,一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图:
该图含有m个状态结点,每个节点可射出若干条箭弧与别的结点相连接,每条弧用∑*中的一个字(不一定要相同而且可以是空字)做标记(称为输入字),整张图至少含有一个初态结点以及若干个(可以是0个)终态结点。对于∑*
2 - 2 -
中的任何一个字a,若存在一条从某一初态结点到某一终态结点的通路,且这条通路上所有弧的标记字依序连接城的字(忽略那些标记为空字ε的弧)等于啊,则称a可为NFA M所识别。若M的某些结点既是初态结点又是终态结点,后者存在一条弧从某个出台节点到某个终态结点的ε通路,则空字ε可为M所接受。
2.确定有限自动机DFA的最小化
一个确定有限自动机(NFA)M是一个五元式M=(S,∑,δ,s0,F)
其中(1)S是一个有限集,它的每一个元素称为一个状态;
(2) ∑是一个有穷字母表,它的每一个元素称为一个输入字符;
(3) δ是一个从S×∑到S的单值部分映射。δ(s,a)意味着:当现行状态为s、输入字符为a时,将转入下一个状态s’,s’是s的后继状态; (4)s0∈S,是唯一的初态;
(5)F属于S,是一个终态集(可空)。
显然,一个DFA可用一个状态转换矩阵表示,该矩阵的行表示状态,列表时
输入字符,矩阵元素表示δ(s,a)的值。一个DFA也可以表示成一张状态转换图,假设DFA M含有m个状态和n个输入字符,那么,该图含有m个状态结点,每个节点最多有n条箭弧与别的结点相连接,每条弧用∑中的一个字做标记,整张图含有唯一的一个初态结点和若干个(可以是0个)终态结点。对于∑中的任何一个字a,若存在一条从某一初态结点到某一终态结点的通路,且这条通路上所有弧的标记字依序连接城的字等于啊,则称a可为DFA M所识别。若M的某些结点既是初态结点又是终态结点,后者存在一条弧从某个出台节点到某个终态结点的ε通路,则空字ε可为M所接受。DFA M所能识别的字的全体记为L(M)。
3.NFA与DFA的联系
在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续
状态中进行选择,故一个NFA对符号串的识别必然是一个试探的过程。这种 不确定性识别过程带来的反复,无疑会影响到FA的工作效率。而DFA则是确 定的,将NFA转化为DFA大大提高工作效率,因此将NFA转化为DFA是有其 一定必要的。程序中采用子集法来实现NFA确定化为DFA。
4.2 DFA的最小化
一个有限自动机M的化简是指:寻找一个状态数比M少的DFA M’,使得
L(M)=L(M’).假定s和t是M的两个不同状态,如果分别从状态s和t出发能读出同样的某个字w而停于终态,则称s和t是等价的。如果DFA M的两个状态s
3 - 3 -
和t不等价,则称这两个状态是可区别的。一个DFA M的状态最少化过程旨在将M的状态集分割成一些不相交的子集,使得任何不同的两个字集中的状态是可区别的,而同一子集中的任何两个状态都是等价的。最后,在每个自己中选出一个代表,同时消去其他等价状态。又被删除的状态射出的弧也被删去,但是有保留下来的状态射出的弧是要全部保留的。
五.设计的基本原理
5.1总体方案设计
机状态信息的输入输出部分;二是用子集构造算法实现NFA确定化为DFA,这里面又涉及到ε_Closure(I)和转换函数Move(I,a)的实现和新生成的状态的重命名问题以及新的状态转换关系的建立;三是DFA的最小化,这里面包括等价状态的划分,等价状态的划分又涉及到终态结点和非终态结点的区分,划分之后等价状态的重命名和新的状态转换关系的建立。总体模块设计方案如下图所示:
我的程序总共分三大模块,一是有限自动机状态转换图的结构和有限自动
4 - 4 -
程序 总体 模块 5.2各模块设计
DFA最小化 结 构 有限自动机的基本状态状态结点、边和输入终结符的结构 有限自动机状态信息的输入输出 ε_closure(I) 和 转换函数move(I,a)的实现 子集构造算 法实现NFA 定化为DFA 新生成状态的命名和等价的状态转换关系的建立 区分终结状态 和非终结状态 等价状态的划分 等价状态的重命名和新的状态转换关系的建立
1.有限自动机状态转换结构的定义和状态信息的输入输出
有限状态机的状态结点,边和终结符(即输入字符)均定义为字符串,利用
C++标准模板库string中的函数来实现定义和后续操作,以方便实现和简化 程序。具体如下程序片段:
string NODE; //结点集合 string CHANGE; //终结符集合 int N; //NFA边数
struct edge
5 - 5 -
正在阅读:
朱航宇-20112878-编译原理合设计03-21
量具中分辨率与精度的区别05-30
虚假的友谊07-17
难忘的毕业典礼作文800字06-17
安全生产月主持词(精选6篇)04-03
VMware7.0下linux中自主安装VM tools05-15
网络设备的连接方式和基本配置01-07
实用文档之小学数学三年级期末考试质量分析05-20
油漆调色知识集锦08-30
学生会管理规章制度条例12-16
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 航宇
- 编译
- 20112878
- 原理
- 设计
- 水土保持工作总结案
- 第2课贞观之治
- 探究体育教学中的德育渗透
- 加拿大毕索大学有条件双录取
- 2016—2017 学年第一学期九年级阶段性学业水平检测英语试题
- 道富投资:市赚率的妙用
- 2012 - 雷达气象练习题
- 最新-公司工会主席2019年工作总结范文 精品
- 钻开油气层的钻井液
- C++实训题目
- mba经济类英语联考词汇
- 六年级数学毕业模拟检测试卷1
- 商学院专业课程设置以及就业方向 - 图文
- 跳poppin学poppin的人应该知道的
- 镀前处理和镀后处理以及在图纸中的标识方法
- PNP三极管结构及工作原理解析
- 2017-2022年汝南县体育特色小镇市场前景调查及投资咨询报告(目
- 正转控制线路教案 - 图文
- 江苏省化工行业废气污染防治技术规范(苏环办3号)
- 施工现场质量管理检查记录资料