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

第 3 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第二章词法分析节2.3 正规表达式与有限自动机简介2.4 正规表达式到优先自动机的构造2.5 词法分析器的自动生成重点掌握 有限自动机理论有限自动机的构造、确定化和化简,本讲目标,第二章 词法分析,2.1 词法分析的设计方法2.2 一个简单的词法分析器2.3 正规表达式与有限自动机简介2.4 正规表达式到有限自动机的构造2.5 词法分析器的自动生成,：有限自动机：可以自动识别单词的机器有限自动机（Finite Automation）：FA是一个状态转换图，“有限”指的是状态有限。当前状态读入一个字符后，和后继状态的转换有以下三种情形：(1)后继状态为自身(2)后继状态只有一个(3)后继状态有多个如果每次转换的后继状态是唯一的，则称它为确定有限自动机（Deterministic FA）如果每次转换的后继状态不是唯一的，则称它为非确定有限自动机（Nondeterministic FA）,2.3 正规表达式与优先自动机简介,：有限自动机1、确定有限自动机（DFA）：DFA是一个五元组，Md(S,f,s0,Z)，其中：(1)S是一个有限状态集合，它的每个元素称为一个状态(2)是一个有穷字母表，它的每个元素称为一个输入字符f是一个从S至S的单值映射，也叫状态转移函数s0S 是唯一的初态 是一个终态集,2.3 正规表达式与优先自动机简介,：有限自动机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 正规表达式与优先自动机简介,状态转换矩阵：,：有限自动机2、非确定有限自动机（NFA）：NFA是一个五元组，Md(S,f,Q,Z)，其中：(1)S是一个有限状态集合，它的每个元素称为一个状态(2)是一个有穷字母表，它的每个元素称为一个输入字符(3)f是一个从S*至S的多值映射，也叫状态转移函数(4)QS 是非空初态集(5)是一个终态集NFA相比于DFA的特征：若干个初始状态(2)f多值映射(3)允许接收字和空字符,2.3 正规表达式与优先自动机简介,：有限自动机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 正规表达式与优先自动机简介,状态转换矩阵：,：有限自动机（识别的语言）对于一个自动机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识别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.对于任意一个NFA M，一定存在一个DFA M与其等价,即L(M)=L(M);从正规式开始构造DFA的过程有以下几个步骤：1.由正规式构造NFA;2.由NFA构造与之等价的DFA（确定化）3.DFA的化简,2.4 正规表达式到有限自动机的构造（重点）,：由正规式构造等价的NFA1、对于给定的正规式R，将其表示成 称为“拓广转换图”其中X为初始状态，Y为终止状态2、对正规式中的三种运算，分别采用如下的对应转换规则,2.4 正规表达式到有限自动机的构造,Y,X,R,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)*,：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,4J中的每一个状态经过任意条通路得到_CLOSURE(J)=Ia=5,6,2,3,8,4,7,：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:,1.构造状态转换表:,X,1,2,1,2,3,1,2,4,1,2,3,1,2,4,2.确定首行首列:_CLOSURE(s0),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.重复(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 正规表达式到有限自动机的构造,：DFA的化简状态的等价：假设s1和s2是M的两个不同的状态，如果从s1出发能识别字符串而停于终态，从s2出发也能识别而停于终态。反之也是成立的。称s1和s2等价，否则称它们可区分一个确定有限自动机M的化简是指：寻找一个状态数比M少的DFA M，使得L(M)=L(M)化简后的DFA满足两个条件：(1)没有多余状态(2)状态集中不存在等价状态,2.4 正规表达式到有限自动机的构造,：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:,(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，如下所示：,2.4 正规表达式到有限自动机的构造,例2.8 求正规表达式(a|b)*(aa|bb)(a|b)*对应的DFA M,NFA M:,化简前的DFA M:,化简后的DFA M:,2.4 正规表达式到有限自动机的构造,例2.8 求正规表达式(a|b)*(aa|bb)(a|b)*对应的DFA M,NFA M:,化简前的DFA M:,化简后的DFA M:,2.4 正规表达式到有限自动机的构造,例2.12 某高级程序语言无符号数的正规表达式为 digit+(.digit+)(e(+|-)digit+)其中digit表示数字，()表示()中的内容可有可无，试给出其DMA,解答 用d表示digit，则用状态转换图表示接受无符号数的NFA：,课后习题：2.7(1)2.9,本章小结,词法分析器的设计与实现（第一次上机作业，参看实验指导书）正规表达式与有限自动机正规式（运算、性质）、正规集（表示）有限自动机的定义和特征正规表达式到有限自动机的构造由正规式构造NFA由NFA构造DFADFA的简化,