资源预览内容
第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
第9页 / 共31页
第10页 / 共31页
亲,该文档总共31页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第 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 正规表达式与优先自动机简介状态转换图:s2s0s1ababab状态转换矩阵:fabSs0s1s2 s1s1s2 s2s2s1u2.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,s1),状态转移函数:f(s0, a) =s2 f(s0, b) =s0,s1 f(s1, a) = f(s1, b) =s2 f(s2, a) = f(s2, b) = s1 2.3 正规表达式与优先自动机简介状态转换矩阵:fabSs0s2s0,s1 s1s2 s2s1状态转换图: s1s0s2babbbu2.3.2:有限自动机(识别的语言) FA 所识别的语言 对于一个自动机FA 而言,如果存在一条从初始状态到终止状态的通路,通路上有向边所识别的字符依次连接所得到 的字符串为, 则称可以为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:s3s0s2aabbbaabs1NFA:s3s0s2aabbbs1第二章 词法分析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 正规表达式到有限自动机的构造YXRsir1|r2 sjsir1 sjr2sir1r2 sjsir1 skr2 sjsisjr1* sisk sjr12.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 addabbYbab 13426587u2.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 正规表达式到有限自动机的构造15242.4 正规表达式到有限自动机的构造例2.7 已知一状态转换图如下图所示,且假定I=_CLOSURE(1)=1,2,试求从状态集I出发经过一条有向边a能到达的状态集J和_CLOSURE(J)6378aaa解答 状态集I经过一条a弧得到J,J = 5,3,4J中的每一个状态经过任意条通路得到_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等价的DFA2.4 正规表达式到有限自动机的构造2.4 正规表达式到有限自动机的构造例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M 解答首先根据正规式构造NFA M:Xba12345ba6Yabab1.构造状态转换表: IIa Ib X,1,21,2,31,2,41,2,31,2,42.确定首行首列: _CLOSURE(X)3.依次计算Ia和Ib 并更新首列2.4 正规表达式到有限自动机的构造Xba12345ba6YababIIa Ib X,1,21,2,31,2,41,2,31,2,41,2,3,5,6,Y1,2,41,2,3,5,6,Y1,2,31,2,4,5,6,Y1,2,4,5,6,Y1,2,3,5,6,Y1,2,4,6,Y1,2,4,6,Y1,2,3,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,4,5,6,Y 1,2,3,5,6,Y1,2,4,6,Y4.重复(3) ,直至无新状态加入首列为止5.新的状态转换矩阵Sab 01234 5613136 6322454 45Xba12345ba6YababSab 01234 5613136 6322454 45a0a123babab45ba6babba得到新的状态转换图DFA:2.4 正规表达式到有限自动机的构造_CLOSURE(X)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 正规表达式到有限自动机的构造划分原则:两个状态s1和s2属于同一子集,当且仅当对任何 输入符号a, 状态s1和s2的后继状态都属于同一子集任意取一个字符 a ,考察当前的划分:1, 2, 3 s1s2aas1s2aas1和s2等价,无需划分s1和s2需要被划分u2.4.3:DFA的化简2.4 正规表达式到有限自动机的构造例2.8 求正规表达式(a|b) *(aa|bb) (a|b) *对应的DFA M 解答 画出例2.8未化简的DFA:a0a123babab45ba6babba(1)初始划分集合1=0,1,2 ,集合2=3,4,5,6,1和2为初始划分 (2)考察3,4,5,6: 3a,4a,5a,6a在集合2;3b,4b,5b,6b在集合2;因此不进行划分。2.4 正规表达式到有限自动机的构造a0a123babab45ba6babba(3)考察0,1,2 :0a0b1a1b2a2b0,1,2被划分为:0,1,22.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 012132213333a0a123bababb2.5 词法分析器的自动生成u设计一种程序,使得其满足:输入:编程语言的词法正规式(标识符、关键字、常量)输出:自动产生词法分析程序uLEX就是这种程序,可以生成高级语言(例如C语言)的词法分 析器可单独
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号