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

1、第 3 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第二章词法分析2.3-2.5节 2.3 正规表达式与有限自动机简介 2.4 正规表达式到优先自动机的构造 2.5 词法分析器的自动生成 重点掌握 有限自动机理论 有限自动机的构造、确定化和化简,本讲目标,第二章 词法分析,2.1 词法分析的设计方法 2.2 一个简单的词法分析器 2.3 正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造 2.5 词法分析器的自动生成,2.3.2：有限自动机：可以自动识别单词的机器 有限自动机（Finite Automation）： FA是一个状态转换图，“有限”指的是状态有限。当前

2、状态读入一个字符后，和后继状态的转换有以下三种情形： (1)后继状态为自身 (2)后继状态只有一个 (3)后继状态有多个 如果每次转换的后继状态是唯一的，则称它为确定有限自动机（Deterministic FA） 如果每次转换的后继状态不是唯一的，则称它为非确定有限自动机（Nondeterministic FA）,2.3 正规表达式与优先自动机简介,2.3.2：有限自动机 1、确定有限自动机（DFA）： DFA是一个五元组，Md (S, , f, s0 , Z) ，其中： (1) S是一个有限状态集合，它的每个元素称为一个状态 (2) 是一个有穷字母表，它的每个元素称为一个输入字符 f是一个从

3、S至S的单值映射，也叫状态转移函数 s0S 是唯一的初态 是一个终态集,2.3 正规表达式与优先自动机简介,2.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,状态转换矩阵：,2.3.2：有限自动机 2、非确定有限自动机（NFA）： NF

4、A是一个五元组，Md (S, , f, Q, Z) ，其中： (1) S是一个有限状态集合，它的每个元素称为一个状态 (2) 是一个有穷字母表，它的每个元素称为一个输入字符 (3) f是一个从S*至S的多值映射，也叫状态转移函数 (4) QS 是非空初态集 (5) 是一个终态集 NFA相比于DFA的特征： 可以有若干个初始状态 (2) f多值映射 (3) 允许接收字和空字符,2.3 正规表达式与优先自动机简介,2.3.2：有限自动机 2、非确定有限自动机（例2.5）： 假定NFA Mn =(s0, s1, s2,a,b, f , s0 ,s2,s1)，状态转移函数： f(s0, a) =s2

5、f(s0, b) =s0,s1 f(s1, a) = f(s1, b) =s2 f(s2, a) = f(s2, b) = s1 ,2.3 正规表达式与优先自动机简介,状态转换矩阵：,2.3.2：有限自动机（识别的语言） FA 所识别的语言 对于一个自动机FA 而言，如果存在一条从初始状态到终止状态的通路，通路上有向边所识别的字符依次连接所得到的字符串为, 则称可以为FA 所接受或者为FA 所识别（FA所识别的字） FA 所能识别的字符串集为FA 所识别的语言，记为L(M) FA的等价 对于任意两个FA M和 FA M, 如果L(M)=L(M), 则称M和M等价 对于任意一个NFA M，一定存

6、在一个DFA M与其等价,2.3 正规表达式与优先自动机简介,2.3 课堂例题,例2.5 接受与正规式(a|b) *abb相同的语言的DFA与NFA:,DFA识别abb aabb abab 无论成功或者失败只需要 运行一次,NFA识别abb aabb abab 无论成功或者失败可能需要 运行若干次,第二章 词法分析,2.1 词法分析的设计方法 2.2 一个简单的词法分析器 2.3 正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造 2.5 词法分析器的自动生成,需要了解的等价性： 1.如果R是字母表上的一个正规式，则必然存在一个NFA M，使得L(M)=L(R); 2.对于任意一

7、个NFA M，一定存在一个DFA M与其等价 ,即L(M)=L(M); 从正规式开始构造DFA的过程有以下几个步骤： 1.由正规式构造NFA; 2.由NFA构造与之等价的DFA（确定化） 3.DFA的化简,2.4 正规表达式到有限自动机的构造（重点）,2.4.1：由正规式构造等价的NFA 1、对于给定的正规式R，将其表示成 称为“拓广转换图”其中X为初始状态，Y为终止状态 2、对正规式中的三种运算，分别采用如下的对应转换规则,2.4 正规表达式到有限自动机的构造,Y,X,R,2.4 正规表达式到有限自动机的构造,例2.6 对给定正规表达式 b*(d|ad)(b|ab)+ 构造其NFA M,X,

8、按照正规式从左到右构造NFA：,解答 先用R+=RR*改造正规表达式,b*(d|ad)(b|ab)+ = b*(d|ad)(b|ab)(b|ab)*,2.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

9、(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,2.4.2：NFA的确定化（子集法） (1) 构造一张转换表，第一列记为状态子集I，对于不同的符号 (a)，在表中单设一列Ia ； (2) 表

10、的首行首列置为_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:,1.

11、构造状态转换表:,X,1,2,1,2,3,1,2,4,1,2,3,1,2,4,2.确定首行首列: _CLOSURE(X),3.依次计算Ia和Ib 并更新首列,2.4 正规表达式到有限自动机的构造,X,1,2,1,2,3,1,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,3,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,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,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,4.重复

12、(3) ,直至无新状态加入首列为止,5.新的状态转换矩阵,0,1,2,3,4,5,6,1,3,1,3,6,6,3,2,2,4,5,4,4,5,0,1,2,3,4,5,6,1,3,1,3,6,6,3,2,2,4,5,4,4,5,得到新的状态转换图DFA:,2.4 正规表达式到有限自动机的构造,2.4.3：DFA的化简 状态的等价： 假设s1和s2是M的两个不同的状态，如果从s1出发能识别字符串而停于终态，从s2出发也能识别而停于终态。 反之也是成立的。称s1和s2等价，否则称它们可区分 一个确定有限自动机M的化简是指： 寻找一个状态数比M少的DFA M，使得L(M)=L(M) 化简后的DFA满足

13、两个条件： (1) 没有多余状态 (2) 状态集中不存在等价状态,2.4 正规表达式到有限自动机的构造,2.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) 划分结束后，一个子集只对应一个状态，作为代表状态，删去 其它一切等价状态，并将对应

14、的弧射向这个代表状态,2.4 正规表达式到有限自动机的构造,划分原则：两个状态s1和s2属于同一子集,当且仅当对任何输入符号a, 状态s1和s2的后继状态都属于同一子集,任意取一个字符 a ，考察当前的划分：1, 2, 3,s1和s2等价，无需划分,s1和s2需要被划分,2.4.3：DFA的化简,2.4 正规表达式到有限自动机的构造,例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M,解答 画出例2.8未化简的DFA:,(1)初始划分集合1=0,1,2 ，集合2=3,4,5,6，1和2为初始划分,(2)考察3,4,5,6： 3a,4a,5a,6a在集合2；3b,

15、4b,5b,6b在集合2； 因此不进行划分。,2,1,2.4 正规表达式到有限自动机的构造,2,1,(3)考察0,1,2：,0,1,2被划分为：0，1，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，如下所示：,2.5 词法分析器的自动生成,设计一种程序，使得其满足： 输入： 编程语言的词法正规式（标识符、关键字、常量） 输出： 自动产生词法分析程序 LEX就是这种程序，可以生成高级语言（例如C语言）的词法分析器 可单独使用 和YACC(根据输入生成语法分析程序) 结合使用 JavaCC也是一种可以自动生成词法分析程序和语法分析程序的软件,2.4 正规表达式到有限自动机的构造,例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M,2.