编译原理词法2(NFA、DFA的确定化和化简).ppt

第 3 讲 西北农林科技大学本科教程 主讲教师：赵建邦 u第二章词法分析2.3-2.5节 l2.3 正规表达式与有限自动机简介 l2.4 正规表达式到优先自动机的构造 l2.5 词法分析器的自动生成 u重点掌握 l有限自动机理论 l有限自动机的构造、确定化和化简 本讲目标 第二章 词法分析 l2.1 词法分析的设计方法 l2.2 一个简单的词法分析器 l2.3 正规表达式与有限自动机简介 l2.4 正规表达式到有限自动机的构造 l2.5 词法分析器的自动生成 u2.3.2：有限自动机：可以自动识别单词的机器 有限自动机（Finite Automation）： FA是一个状态转换图，“有限”指的是状态有限。当前状 态读入一个字符后，和后继状态的转换有以下三种情形： (1)后继状态为自身 (2)后继状态只有一个 (3)后继状态有多个 如果每次转换的后继状态是唯一的，则称它为确定有限自 动机（Deterministic FA） 如果每次转换的后继状态不是唯一的，则称它为非确定有 限自动机（Nondeterministic FA） 2.3 正规表达式与优先自动机简介 u2.3.2：有限自动机 1、确定有限自动机（DFA）： DFA是一个五元组，Md (S, , f, s0 , Z) ，其中： (1) S是一个有限状态集合，它的每个元素称为一个状态 (2) 是一个有穷字母表，它的每个元素称为一个输入字符 (3)f是一个从S至S的单值映射，也叫状态转移函数 (4)s0S 是唯一的初态 (5) 是一个终态集 2.3 正规表达式与优先自动机简介 u2.3.2：有限自动机 1、确定有限自动机（例2.4）： 假定DFA Md =(s0, s1, s2，a,b, f , s0 ,s2 )，状态转移函数： f(s0, a) = s1 f(s0, b) = s2 f(s1, a) = s1 f(s1, b) = s2 f(s2, a) = s2 f(s2, b) = s1 2.3 正规表达式与优先自动机简介 状态转换图： s2 s0 s1 a b a b a b 状态转换矩阵： f ab S s0s1s2 s1s1s2 s2s2s1 u2.3.2：有限自动机 2、非确定有限自动机（NFA）： NFA是一个五元组，Md (S, , f, Q, Z) ，其中： (1) S是一个有限状态集合，它的每个元素称为一个状态 (2) 是一个有穷字母表，它的每个元素称为一个输入字符 (3) f是一个从S*至S的多值映射，也叫状态转移函数 (4) QS 是非空初态集 (5) 是一个终态集 NFA相比于DFA的特征： (1)若干个初始状态 (2) f多值映射 (3) 允许接收字和空字符 2.3 正规表达式与优先自动机简介 u2.3.2：有限自动机 2、非确定有限自动机（例2.5）： 假定NFA Mn =(s0, s1, s2,a,b, f , s0 ,s2,s2)，状态转移函数 ： f(s0, a) =s2 f(s0, b) =s0,s2 f(s1, a) = f(s1, b) =s2 f(s2, a) = f(s2, b) = s1 2.3 正规表达式与优先自动机简介 状态转换矩阵： f ab S s0s2s0,s2 s1s2 s2s1 状态转换图： s1 s0 s2 b a b b b u2.3.2：有限自动机（识别的语言） 对于一个自动机FA 而言，如果存在一条从初始状态到终止状 态的通路，通路上有向边所识别的字符依次连接所得到的字 符串为, 则称可以为FA 所接受或者为FA 所识别 FA 所能识别的字符串集为FA 所识别的语言，记为L(M) FA的等价：对于任意两个FA M和 FA M, 如果L(M)=L(M), 则称M和M等价 对于任意一个NFA M，一定存在一个DFA M与其等价 2.3 正规表达式与优先自动机简介 2.3 课堂例题 例2.5 接受与正规式(a|b) *abb相同的语言的DFA与NFA: DFA： s3 s0 s2 a a b b b a a b s1 NFA： s3s0s2 a a b a b s1 第二章 词法分析 l2.1 词法分析的设计方法 l2.2 一个简单的词法分析器 l2.3 正规表达式与有限自动机简介 l2.4 正规表达式到有限自动机的构造 l2.5 词法分析器的自动生成 u需要了解的等价性： 1.如果R是字母表上的一个正规式，则必然存在一个NFA M，使得L(M)=L(R); 2.对于任意一个NFA M，一定存在一个DFA M与其等价 ,即 L(M)=L(M); u从正规式开始构造DFA的过程有以下几个步骤： 1.由正规式构造NFA; 2.由NFA构造与之等价的DFA（确定化） 3.DFA的化简 2.4 正规表达式到有限自动机的构造（重点） u2.4.1：由正规式构造等价的NFA 1、对于给定的正规式R，将其表示成 称为“拓广转换图”其中X为初始状态，Y为终止状态 2、对正规式中的三种运算，分别采用如下的对应转换规则 2.4 正规表达式到有限自动机的构造 YX R si r1|r2 sj si r1 sj r2 si r1r2 sj si r1 sk r2 sj sisj r1* sisk sj r1 2.4 正规表达式到有限自动机的构造 例2.6 对给定正规表达式 b*(d|ad)(b|ab)+ 构造其NFA M X 按照正规式从左到右构造NFA： 解答 先用R+=RR*改造正规表达式 b*(d|ad)(b|ab)+ = b*(d|ad)(b|ab)(b|ab)* b a d da b b Y b a b 1 3 4 2 6 5 8 7 u2.4.2：NFA的确定化（相关概念） NFA的确定化：构造一个和NFA等价的DFA 状态集合I的_闭包 设I是FA M的状态子集，则以下状态属于_CLOSURE(I) ： (1) 若siI，则si _CLOSURE(I) ； (2) 若siI，则对从si出发经过任意条通路所能到达的 状态sj，都有sj _CLOSURE(I) 。 定义Ia = _CLOSURE(J) ，其中： I=s1, s2, sn，J = f(I,a) = f(s1,a)f(s2,a) f(sn,a) 2.4 正规表达式到有限自动机的构造 1 5 2 4 2.4 正规表达式到有限自动机的构造 例2.7 已知一状态转换图如下图所示，且假定 I=_CLOSURE(1)=1,2，试求从状态集I出发经过一条有向 边a能到达的状态集J和_CLOSURE(J) 6 3 7 8 a a a 解答 状态集I经过一条a弧得到J， J = 5,3,4 J中的每一个状态经过任意条 通路得到_CLOSURE(J) = Ia= 5,6,2,3,8,4,7 u2.4.2：NFA的确定化（子集法） (1) 构造一张转换表，第一列记为状态子集I，对于不同的符号 (a)，在表中单设一列Ia ； (2) 表的首行首列置为_CLOSURE(s0)，其中s0为初始状态； (3) 根据首行首列的I，为每个a求其Ia 并记入对应的Ia 列中， 如果此Ia 不同于第一列中已存在的所有状态子集I，则将其 顺序列入空行中的第一列； (4) 重复(3)直至对每个I及a均已求得Ia ，并且无新的状态子集 Ia加入第一列时为止； (5) 重新命名第一列的每一个状态子集，形成新的状态转换矩阵， 即为与NFA等价的DFA 2.4 正规表达式到有限自动机的构造 2.4 正规表达式到有限自动机的构造 例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M 解答首先根据正规式构造NFA M: X b a 1 2 3 4 5 b a 6 Y a b a b 1.构造状态转换表: IIa Ib X,1,21,2,31,2,4 1,2,3 1,2,4 2.确定首行首列: _CLOSURE(s0) 3.依次计算Ia和Ib 并更新首列 2.4 正规表达式到有限自动机的构造 X b a 1 2 3 4 5 b a 6 Y a b a b IIa Ib X,1,21,2,31,2,4 1,2,3 1,2,4 1,2,3,5,6,Y 1,2,4 1,2,3,5,6,Y 1,2,31,2,4,5,6,Y 1,2,4,5,6,Y 1,2,3,5,6,Y1,2,4,6,Y 1,2,4,6,Y 1,2,3,6,Y 1,2,3,6,Y 1,2,4,5,6,Y 1,2,3,6,Y1,2,4,5,6,Y 1,2,3,5,6,Y 1,2,4,6,Y 4.重复(3) ,直至无新状态加入首列为止 5.新的状态转换矩阵 Sab 0 1 2 3 4 5 6 1 3 1 3 6 6 3 2 2 4 5 4 4 5 X b a 1 2 3 4 5 b a 6 Y a b a b Sab 0 1 2 3 4 5 6 1 3 1 3 6 6 3 2 2 4 5 4 4 5 a 0 a 1 2 3 b a b a b 4 5 b a 6 b ab b a 得到新的状态转换图DFA: 2.4 正规表达式到有限自动机的构造 u2.4.3：DFA的化简 状态的等价： 假设s1和s2是M的两个不同的状态，如果从s1出发能识别字 符串而停于终态，从s2出发也能识别而停于终态。 反之 也是成立的。称s1和s2等价，否则称它们可区分 一个确定有限自动机M的化简是指： 寻找一个状态数比M少的DFA M，使得L(M)=L(M) 化简后的DFA满足两个条件： (1) 没有多余状态 (2) 状态集中不存在等价状态 2.4 正规表达式到有限自动机的构造 u2.4.3：DFA的化简（方法） (1) 首先将DFA的状态集按照终态与非终态分为两个子集，形成 初始划分H (2) 对每个子集G进行如下变换： 把G划分为新的子集，使得G的两个状态s1和s2属于同一子集 ,当且仅当对任何输入符号a,状态s1和s2的后继状态都属于同 一子集； 用G划分出的所有子集替换G，形成新的划分Hnew (3) 如果Hnew = H，执行(4);否则令H = Hnew，重复执行(2) (4) 划分结束后，一个子集只对应一个状态，作为代表状态，删 去 其它一切等价状态，并将对应的弧射向这个代表状态 2.4 正规表达式到有限自动机的构造 2.4 正规表达式到有限自动机的构造 例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M 解答 画出例2.8未化简的DFA: a 0 a 1 2 3 b a b a b 4 5 b a 6 b ab b a (1)初始划分集合1=0,1,2 ，集合2=3,4,5,6 (2)考察0,1,2：0a,0b,1b,2a 在集合1；1a, 2b在集合2； 因此划分为012； 考察3,4,5,6： 3a,4a,5a,6a在集合2；3b,4b,5b,6b在集合2； 因此不进行划分。 2.4 正规表达式到有限自动机的构造 例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M 解答 (3) 划分的最终结果为 0 、1、2、3,4,5,6； 对其进行重命名：0、1、2、3 (4) 得到新的状态转换矩阵和化简后的DFA，如下所示： Sab 012 132 213 333 a 0 a 1 2 3 b a b a b b a 0 a 1 2 3 b a b a b 4 5 b a 6 b ab b a 2.4 正规表达式到有限自动机的构造 例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M X b a 1 2 3 4 5 b a 6 Y a b a b a 0 a 1 2 3 b a b a b b NFA M: 化简前的DFA M: 化简后的DFA M: a 0 a 1 2 3 b a b a b 4 b ba 2.4 正规表达式到有限自动机的构造 例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M b a X 3 4 b a Y a b a b a 0 a 1 2 3 b a b a b b NFA M: 化简前的DFA M: 化简后的DFA M: 2.4 正规表达式到有限自动机的构造 例2.12 某高级程序语言无符号数的正规表达式为 digit+(. dig