编译原理NFA转化为DFA的转换算法及实现 计算机软件及应用.doc

编译原理NFA转化为DFA的转换算法及实现 计算机软件及应用.doc

课程设计报告书 设计名称 NFA 转化为 DFA 的转换算法及实现 课程名称 编 译 原 理 学生姓名 专 业 ） 班 别 学 号 指导老师 日 期 2013 年 7 月 5 日 2 目 录 目 录 ......................................................................................................2 1 前言 ........................................................................................................3 1.1 选题的依据和必要性 ......................................................................3 1.2 课题意义 ..........................................................................................3 2 NFA 转化为 DFA 的算法及实现 .............................................................3 2.1 基本定义 ..........................................................................................3 2.1.2 DFA 的概念 .............................................................................4 2.1.3 NFA 与 DFA 的矩阵表示 .......................................................5 2.1.4 NFA 向 DFA 的转换的思路 ...................................................6 3 DFA 的化简 .........................................................................................6 3.1 化简的理论基础 ..............................................................................6 3.2 化简的基本思想 .............................................................................7 4 程序设计 ................................................................................................7 4.1 程序分析 .........................................................................................7 4.1.1 流程图 ......................................................................................7 4.1.2 子集构造法 ..............................................................................9 4.2 实现代码 ........................................................................................11 3 1 .前言 1.1 选题的依据和必要性 由于很多计算机系统都配有多个高级语言的编译程序，对有些高级语言甚 至配置了几个不同性质的编译程序。从功能上看，一个编译程序就是一个语言 翻译程序。语言翻译程序把源语言书写的程序翻译成目标语言的等价程序。经 过编译程序的设计可以大大提高学生的编程能力。 编译程序的工作过程通常是词法分析、语法分析、语义分析、代码生成、 代码优化 1。由于现在有很多词法分析程序工具都是基于有穷自动机的，而词 法分析又是语法分析的基础 2，所以我们有必要进行有穷自动机的确定化和最 小化。 1.2 课题意义 编译程序的这些过程的执行先后构成了编译程序的逻辑结构 3。有穷自动机 （也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规 文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为 词法分析程序的自动构造寻找特殊的方法和工具 4。NFA转化为DFA的理论在词 法构造至整个编译器构造过程中起着至关重要的作用，同时它们被广泛应用于 计算机科学的各个领域，它们与计算机其它学科也有着密切的联系。 2 NFA转化为DFA的算法及实现 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般 原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、 中间代码生成、存储管理、代码优化和目标代码生成。进行NFA转换为DFA的词 法分析和语法分析，首先要对目标对象有有所了解，这就需要对NFA、DFA进一 步了解。 2.1 基本定义 NFA，也称不确定的有穷自动机，是由一个五元式定义的数学模型，特点是 它的不确定性，即在当前状态下，读入同一个字符，可能有多个下一状态。 4 DFA，也称确定的有穷自动机，也是由一个五元式定义的数学模型，相对的 特点是它的确定性，即在当前状态下，读入同一个字符，最多有一个后继状态。 2.1.1 NFA 的概念 NFAnondeterministic finite-state automata即非确定有限自动机, 一个非确定的有限自动机 NFA M是一个五元式 NFA MS, , , S0, F 其中 S有限状态集 S0初态集 F终态集 转换函数 S 2S 2S --S 的幂集S 的子集构成的集合） 状态转换图如图2.1.1 1 1 0 1 0，1 图2.1.1 NFA状态转换图 2.1.2 DFA的概念 DFAdeterministic finite-state automata即确定有限自动机，一个确 定的有限自动机 DFA M 是一个五元式 MS, ，, S0, Z 其中 S 有限状态集 输入字母表 映射函数也称状态转换函数 Z S P 5 SS s,aS , S, S S, a S0 初始状态 S0 S Z终止状态集 ZS P Z P P a a b a b b a， b 图2.1.2 DFA状态转换图 2.1.3 NFA与DFA 的矩阵表示 一个NFA或者DFA还可以用一个矩阵 5表示，矩阵也可以说是状态转换表， 它的优点是可以快速访问给定的状态在给定的输入字符时能转换到的状态集。 矩阵，每个状态一行，每个输入符号和（如果有需要的）各占一列，表的第i 行中与输入符号a 对应的表项是一个状态集合，表示NFA或者DFA在状态i输入a 时所能到达的状态集合（DFA的集合唯一） ，即（i ，a ） 6。 （7） 如图2.1.1可用表2.3.1.表示 表2.3.1 NFA状态转换表 输入 状态 0 1 S P S， Z P Z Z P P 如图2.1.2可用表2.3.2表示 表2.3.2 DFA状态转换表 6 输入 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3 2.1.4 NFA向DFA 的转换的思路 从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA 的矩 阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是DFA的 每一个状态对应NFA的一组状态DFA使用它的状态记录在NFA读入一个输入符 号后可能达到的所有状态 4。 2.2 NFA 和 DFA 之间的联系 在非确定的有限自动机 NFA 中,由于某些状态的转移需从若干个可能的后续 状态中进行选择，故一个 NFA 对符号串的识别就必然是一个试探的过程。这种 不确定性给识别过程带来的反复，无疑会影响到 FA 的工作效率。而 DFA 则是确 定的,将 NFA 转化为 DFA 将大大提高工作效率,因此将 NFA 转化为 DFA 是有其一 定必要的。 3 DFA的化简 得到新的DFA之后，并没有完成任务，因为通过NFA转化成DFA不一定是最简 的，也就是说，有多余的状态可以被删除，而我们需要的是得到一个唯一的最 简的DFA 12，也就是说，NFA转化为DFA之后，还需要化简，也就是最小化。 3.1 化简的理论基础 DFA的化简是指寻找一个状态数最少的DFA M，使得L（M）L（M ） 。 化简的方法是消去DFA M中的多余状态（或无用状态） ，合并等价状态。 DFA中的多余状态是指这样的状态从开始状态出发，读入任何输入串都 不能到达的那个状态；或者从这个状态没有通路到达终态。 7 两个状态S 和T等价是指如果从状态S出发能读出某个字W而停于终态， 从T出发也能读出同样的字W而停于终态；反之，从T出发能读出同样的字W 而 停于终态，从S 出发也能读出某个字 W而停于终态。 3.2 化简的基本思想 化简DFA的基本思想是指导它的状态分成一些互不相交的子集，每一个子 集中的状态都不是等价的，不同子集中的状态可以由某个输入串来区别，最后 将不能区别的每个子集用一个状态来做代表 13-15，这种方法称为“分割法” 。具 体过程是 （1）将M的所有状态分成两个子集终态集和非终态集； （2）考察每一个子集，若发现某子集中的状态不等价，将其划分为两个集合； （3）重复第（2）步，继续考察已得到的每一个子集，直到没有任何一个子集 需要继续划分为止。这时DFA的状态被分成若干个互不相交的子集。 （4）从每个子集中选出一个状态做代表即可得到最简的DFA。 4 程序设计 通过本设计所要求达到的目的是充分理解和掌握NFA，DFA以及NFA确定化 过程的相关概念和知识，理解和掌握子集法的相关知识和应用，现在需要编程 16-18实现对输入 NFA转换成 DFA输出的功能。 4.1 程序分析 4.1.1 流程图 程序总框图如图4.1所示 8 总模块 NFA 图结构 状态转换表 DFA 图结构 初始化状态 转换矩阵 状态转换操 作 图4.1 .1 程序总框图 开始 输入 NFA，初始化 NFA 初步转化为 DFA 结束 重命名化简 9 图4.1.2 功能图 4.1.2 子集构造法 已证明非确定的有限自动机与确定的有限自动机从功能上来说是等价的， 也就是说，我们能够从 NFA M DFA M 使得 LMLM 为了使得 NFA 确定化，我们首先给出两个定义 定义 1集合 I 的 -闭包 令 I 是一个状态集的子集，定义 -closure（I）为 1）若 sI，则 s-closure（I） ； 2）若 sI，则从 s 出发经过任意条 弧能够到达的任何 状态都属于 -closure（I） 。 状态集 -closure（I）称为 I 的 -闭包 定义 2令 I 是 NFA M的状态集的一个子集, a 定义 Ia-closureJ 其中 J s,a J 是从状态子集 I 中的每个状态出发,经过标记为 a 的弧而达到的状态 集合。 Ia 是状态子集,其元素为 J 中的状态,加上从 J 中每一个状态出发通过 弧到达的状态。 给定如图 2 所示的 NFA 10 b b aa b 0 1 2 3 4 图 4.1.3 与之等价的 DFA 如图 3 b a b 0，1 2，4 4 3 a 图 4.1.4 11 开始 求开始状态闭包 标记令它为集合 C 中的唯一成员 集合 C 中存在 尚未被标记子 集 标记 对子集中的每个输 入字母求a 子集 将加入中 结束 语 是 否 图4.1.5 子集构造法的流程图 这样就完成了从正规表达式 101（0|1）*011 到 DFA 的转化。 4.2 实现代码 include include define MAXS 100 using namespace std; string NODE; //结点集合 string CHANGE; //终结符集合 12 int N; //NFA 边数 struct edge string first; string change; string last; ; struct chan string ltab; string jiheMAXS; ; void kongint a int i; fori0;ia;i cout ; //排序 void paixustring char b; forj0;ja.length;j fori0;iNODE.findai1 bai; aiai1; ai1b; void eclousechar c,string fork0;khe.length hebk.last; eclousebk.last0,he,b; 13 void movechan khe.ltab.length; lhe.jihem.length; fori0;ik;i forj0;jhe.jihem.length he.jihembj.last0; fori0;il;i forj0;jhe.jihem.length he.jihembj.last0; //输出 void outputfaint len,int h,chan *t int i,j,m; cout I ; fori0;ilen;i coutICHANGEi ; coutendl-------------------------endl; fori0;ih;i cout ti.ltab; mti.ltab.length; forj0;jlen;j kong8-m; mti.jihej.length; coutti.jihej; coutendl; void main edge *bnew edgeMAXS; int i,j,k,m,n,h,x,y,len; bool flag; string jhMAXS,endnode,ednode,sta; cout请输入 NFA 各边信息（起点 条件空为* 终点） ，以结束endl; 14 fori0;ibi.first; ifbi.first break; cinbi.changebi.last; Ni; /*forj0;jN;j coutbj.firstbj.changebj.lastendl;*/ fori0;iNODE.length NODEbi.first; ifNODE.findbi.lastNODE.length NODEbi.last; ifCHANGE.findbi.changeCHANGE.length lenCHANGE.length; cout结点中属于终态的是endnode; fori0;iNODE.length cout所输终态不在集合中，错误endl; return; //coutendnodeendnodeendl; chan *tnew chanMAXS; t0.ltabb0.first; h1; eclouseb0.first0,t0.ltab,b; //求 e-clouse //coutt0.ltabendl; fori0;ih;i forj0;jti.ltab.length;j form0;mlen;m eclouseti.ltabj,ti.jihem,b; //求 e-clouse fork0;klen;k //coutti.jihek; moveti,k,b; //求 moveI,a //coutti.jihekendl; forj0;jti.jihek.length;j 15 eclouseti.jihekj,ti.jihek,b; //求 e-clouse forj0;jlen;j paixuti.jihej; //对集合排序以便比较 fork0;kh;k flagoperatortk.ltab,ti.jihej; ifflag break; ifflag coutendl状态转换矩阵如下 endl; outputfalen,h,t; //输出状态转换矩阵 //状态重新命名 string *dnew stringh; NODE.erase; coutendl重命名endl; fori0;ih;i stati.ltab; ti.ltab.erase; ti.ltabAi; NODEti.ltab; coutstati.ltabendl; forj0;jendnode.length;j ifsta.findendnodejsta.length d1ednodeti.ltab; fork0;kh;k form0;mlen;m ifstatk.jihem tk.jihemti.ltab; fori0;iednode.length d0NODEi; endnodeednode; coutendlDFA 如下endl; outputfalen,h,t; //输出 DFA cout其中终态为endnodeendl; //DFA 最小化 16 m2; sta.erase; flag0; fori0;im;i //coutdidiendl; fork0;klen;k //coutICHANGEkendl; ym; forj0;jdi.length;j forn0;ny;n ifdn.findtNODE.finddij.jihekdn.length||tNODE.finddij.jihek.length0 iftNODE.finddij.jihek.length0 xm; else xn; ifsta.length stax48; else ifsta0x48 dmdij; flag1; di.erasej,1; //coutdiendl; j--; break; //跳出 n //n //j ifflag m; flag0; //coutstastaendl; sta.erase; 17 //k //i coutendl集合划分; fori0;im;i coutdi ; coutendl; //状态重新命名 chan *mdnew chanm; NODE.erase; coutendl重命名endl; fori0;im;i mdi.ltabAi; NODEmdi.ltab; coutdimdi.ltabendl; fori0;im;i fork0;klen;k forj0;jh;j ifdi0tj.ltab0 forn0;nm;n iftj.jihek.length break; else ifdn.findtj.jihekdn.length mdi.jihekmdn.ltab; break; ednode.erase; fori0;im;i forj0;jendnode.length;j ifdi.findendnodejdi.length endnodeednode; coutendl最小化 DFA 如下endl; outputfalen,m,md; cout其中终态为endnodeendl;