《第二章词法分析非确定有限自动机优秀课件.ppt》由会员分享，可在线阅读，更多相关《第二章词法分析非确定有限自动机优秀课件.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章词法分析非确定有限自动机第1 页，本讲稿共29 页第2 章 outlinep 一、词法分析概述 1，词法分析程序的功能 2，词法分析相关的一些问题p 二、正则表达式p 三、有限自动机 1，确定有限自动机DFA 2，非确定有限自动机NFA，NFA 到DFA 的转换 3，DFA 的化简 4，正则表达式到NFA 的转换p 四、词法分析程序构造第2 页，本讲稿共29 页2、非确定有限自动机 确定有限自动机是五元组(SS,S0,TS)确定性体现：初始状态唯一、转换函数是单值函数 非确定有限自动机：也是五元组(SS,S0,TS)其中 SS=S0,S1,Sn是状态集 是字母表 S0 SS是初始状态集,
2、不能为空 是转换函数，但不要求是单值的:SS()2SS TS SS是终止状态集，可为空。第3 页，本讲稿共29 页非确定有限自动机的例子=a,b SS:S0,S1,S2,S3 初始状态集:S0,S1 终止状态集:S3:(S0,a)S1,S3,(S0,)S2,(S1,b)S1,(S1,)S2,(S2,)S3,(S3,b)S3 NFA 也可以用状态转换图或状态转换矩阵表示第4 页，本讲稿共29 页非确定有限自动机的例子S0aS2S3abbS1a bS+S1,S3 S2S1+S1 S2S2 S3S3-S3状态集合第5 页，本讲稿共29 页NFA 接受的字符串 NFA 接受的字符串 如果M 是一个NF
3、A,a1 a2 an 是一个字符串，如果存在一个状态序列(S0,S1,Sn),满足 S0 S1,S1 S2,Sn-1 Sn其中 S0 是开始状态之一，Sn 是接受状态之一，则串a1 a2 an 被NFA M 接受.NFA 定义的串的集合(NFA 接受的语言)NFA M 接受的所有串的集合，称为M 定义的语言，记为 L(M)a1 a2an第6 页，本讲稿共29 页NFA 与DFA 的比较DFA NFA初始状态 一个初始状态 初始状态集合 边 不允许 允许(S,a)S or S1,Sn or 实现 容易 有不确定性 对于确定的输入串，DF A 只有一条路径接受它 NF A 则可能需要在多条路径中进
4、行选择！第7 页，本讲稿共29 页NFA 到DFA 的转换 例如输入串：100 NFA NFA 需要在多条路径中选择，因此的效率低！但NFA 描述问题方便。NFA 和DFA 都识别正则语言。NFA 可转换成DFA。S PQ010101第8 页，本讲稿共29 页NFA 到DFA 的转换 对任意NFA，都存在一个DFA 与之等价。转换的思想：消除不确定性 合并初始状态集成一个状态 消除 边 消除多重定义的边。123aa12,3a454，5第9 页，本讲稿共29 页-closure(空闭包)对于给定的 NFA A,和它的一个状态集合 SS,SS 的空闭包计算如下：第一步：令-closure(SS)=
5、SS;第二步：如果在状态集SS 中存在状态s,s 到状态s 存在一条 边，并且s-closure(SS),则将s 加入SS 的空闭包-closure(SS);重复第二步,直到再没有状态可加入-closure(SS).第10 页，本讲稿共29 页-closure 的例子S0aS1S2S3abc-closure(S0,S1)=S0,S1 S0,S1,S2 S0,S1,S2 S0,S1,S2,S3第1 1 页，本讲稿共29 页转向状态 对于NFA A 中的给定状态集合SS 和符号 a,NextStates(SS,a)=s|对于状态集SS 中的一个状态s1,如果A 中存在一条从s1 到s 的a 转换边
6、SSS2S3S1SSaa(S1,S2,S3,a)=S,S第12 页，本讲稿共29 页转向状态的例子S0aS1S2S3abc NextStates(S0,S1,a)=S1,S3 NextStates(S0,S1,b)=S1第13 页，本讲稿共29 页NFA 到DFA 的转换算法(子集法)给定一个 NFA A=,SS,SS0,TS 生成等价的 DFA A=,SS,S0,TS 步骤(1)令S0=-closure(SS0),将S0 加入 SS;(2)从SS 中选择一个状态s,对于任意 a,若有 s=-closure(NextStates(s,a),令(s,a)s。若s SS,将s 加入SS;(3)重复
7、第二步，直到SS 中的所有状态都被处理过;(4)对于SS 中的一个状态s,如s=S1,.,Sn,如果有状态 Si TS,则s是 A 的一个接受状态,将s加入 TS;第14 页，本讲稿共29 页NFA 到DFA 转换的例子 例1：=a,b,c,S0=-closure(S0,S10)=S0,S10,S2,S*,a b c S 0,S1,S2,S 3+-S1,S 3,S2 S1,S 3,S2 S 3 S1,S 3,S2-S1,S 3,S2 S 3 S 3-S 3 S0aS1S2S3abc第15 页，本讲稿共29 页NFA 到DFA 转换的例子 例2：0 1S0+S0,S1 S0S0,S1-S0,S1
8、,S2 S0S0,S1,S2-S0,S1,S2 S0S0 S1S2S PQ010101第16 页，本讲稿共29 页NFA 到DFA 转换的例子 例3：q0q1q4q6q2q3q5aaabbba,ba bq0+q1,q3q1,q3 q1,q3 q2,q4,q6,q5q2,q4,q6,q5-q4,q6,q5 q6,q5,q4q4,q6,q5-q6,q5,q4 q6,q5,q4第17 页，本讲稿共29 页DFA 的化简 NFA 转换成的DFA，有时候会有一些等价状态，这些等价状态会使分析效率降低，因此应合并。合并了所有等价状态后的DFA 称为最简自动机。q0aqA qcqBaa,bbabDFA M1
9、第18 页，本讲稿共29 页等价DFA 和最简DFA 的定义 等价 DFAs 如果两个DFA 接受的字符串的集合是相同的;在接受相同字符串集的DFA 中，最小DFA 指的是状态数最少的DFAq0aqAqca,bbDFA M2a第19 页，本讲稿共29 页等价的DFAsS0aS1S4*bdS3*S2dS0aS1bdS*两个DFA等价，是因为在这两个DFA中存在接受相同字符串的状态!第20 页，本讲稿共29 页主要思想 等价状态 对于DFA 中的任意两个状态 s1 和 s2，如果分别将 s1 和s2 当作开始状态，它们接受的字符串集合相同，则称 s1 和 s2 是等价状态;DFA 化简的两种方式
10、合并等价状态;(状态合并法)分离不等价状态;(状态分离法)第21 页，本讲稿共29 页状态分离法化简DFA 给定一个DFA A=,SS,S0,TS：要生成与其等价的 DFA A=,SS,S0,TS 分离步骤：(1)将A 的所有状态分成两组：非终止状态,终止状态;(2)选择一组状态 SSi=Si1,Sin,用split(SSi)替换SSi;(3)重复第(2)步，直到所有组都被处理过;(4)令SS=组的集合;(5)S0：包含S0 的组作为S0;(6)TS:包含A 的终止状态的组，作为A 的终止状态;(7):（SSi,a）=SSj,若在A中有Si Sj,且 si SSi,sj SSja第22 页，本
11、讲稿共29 页分离状态 给定一个DFA A=,SS,S0,TS：假定状态集合SS 分成了m 组：SS1,SSm,SS1 SSm=SS,SS1 SSm=;任取一个状态组SSi=Si1,Sin,考察SSi是否可继续分离 split(SSi)：判断SSi 是否需要分裂，是则将SSi 分裂成两组G1 和G2,过程如下：初始 G1=Sip,1 p n,即任取SSi中的一个状态放入G1,G2=.for j=1 to n(假设 SSi 有n 个状态)对于所有 a,任意的Sij SSi,若有(Sip,a)=Sk，(Sij,a)=Sq，如果 Sk和Sq属于同一个组 SSt,则将 Sij 加入组 G1;否则将 S
12、ij 加入组 G2;第23 页，本讲稿共29 页简单例子S0aS1S4*bdS3*S2dS0,S1,S2,S3*,S4*S0,S1,S2,S3*,S4*第24 页，本讲稿共29 页DFA 化简的例子 例1：0，1，2，3 和4 0,1,3,2 和4 0,3,1,2 和40 1 234a abb abbb0 1 24a abbbb第25 页，本讲稿共29 页DFA 化简的例子 例2：0，1，2，3，4 0，2、1，3，4 0，2，1，3，4a 4 012aababbb3a，b 4 012aababba，b第26 页，本讲稿共29 页DFA 化简的例子 例3：A,D,E,B,C A,E,D 和B,C第27 页，本讲稿共29 页课后练习 NFA 到DFA 的转化0123a a ba,b a,b a,b0123a b b a第28 页，本讲稿共29 页课后练习 DFA 的化简:1,3,2,4,5,61 24653ababb bbba第29 页，本讲稿共29 页