第4章词法分析PPT讲稿.ppt

《第4章词法分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第4章词法分析PPT讲稿.ppt（147页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 词法分析词法分析第1页，共147页，编辑于2022年，星期一第第3章教学内容章教学内容词法分析的任务；单词，单词的分类，单词的输出形式单词的描述工具：正规文法；正规式；有穷自动机。词法分析程序的自动构造原理：正规式到有穷自动机的转换算法。如何设计和实现词法分析程序。第2页，共147页，编辑于2022年，星期一一、词法分析的任务一、词法分析的任务 人们要理解一篇文章或一句话，首先必须了人们要理解一篇文章或一句话，首先必须了解这篇文章或这句话的结构，文章包含哪些段落，解这篇文章或这句话的结构，文章包含哪些段落，每个段落包含哪些句子，每个句子又包含哪些词。每个段落包含哪些句子，每个句子又

2、包含哪些词。这些过程对于人来说没有什么难度，但对于计算这些过程对于人来说没有什么难度，但对于计算机来说就不同了，输入一段话或一个程序，计算机来说就不同了，输入一段话或一个程序，计算机得到的只是一串符号，要对这段话或这段程序机得到的只是一串符号，要对这段话或这段程序进行分析，计算机首先必须知道这段话由哪些词进行分析，计算机首先必须知道这段话由哪些词组成，或这个程序由哪些单词符号构成。这个过组成，或这个程序由哪些单词符号构成。这个过程就是词法分析。程就是词法分析。第3页，共147页，编辑于2022年，星期一识别单词识别单词词法分析的任务是：从左到右逐个字符地对源程序进行扫描和分解，根据语言的词法规

3、则识别出一个个的单词符号。词法分析是编译的基础。执行词法分析的程序就是词法分析器(扫描器)，其功能是输入源程序，输出单词符号。第4页，共147页，编辑于2022年，星期一词法分析程序的主要任务：扫描源程序，识别出单词其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，第5页，共147页，编辑于2022年，星期一二、与语法分析程序的接口方式二、与语法分析程序的接口方式方式方式1：词法分析程序作为单独的程序，输：词法分析程序作为单独的程序，输入源程序，输出单词文件，提供给语法分入源程序，输出单词文件，提供给语法分析程序使用。析程序使用。方式方式2：词法分析程序作为语法分析程序

4、的：词法分析程序作为语法分析程序的子程序，提供给语法分析程序调用，不产子程序，提供给语法分析程序调用，不产生中间文件。生中间文件。第6页，共147页，编辑于2022年，星期一 字符串字符串表示的源表示的源程序程序词法分析词法分析程序程序字符语法分析语法分析程序程序取单词回送单词词法分析程序作为子程序词法分析程序作为子程序第7页，共147页，编辑于2022年，星期一三、单词的分类三、单词的分类【单词】【单词】单词是语言中具有独立意义的最小语单词是语言中具有独立意义的最小语法单位，包括保留字、标识符、运算符、标法单位，包括保留字、标识符、运算符、标点符号和常量等。点符号和常量等。【例如】【例如】a

5、b是表达式，不是单词。是表达式，不是单词。a,b是标识符，是运算符，都是单词。是标识符，是运算符，都是单词。第8页，共147页，编辑于2022年，星期一程序设计语言的单词符号一般可分成下列程序设计语言的单词符号一般可分成下列5种：种：关关键键字字(基基本本字字，保保留留字字)：具具有有固固定定意意义义的的标标识识符符，如如PASCAL语言中的语言中的begin,end,if和和while等。等。标标识识符符:用用来来表表示示各各种种名名字字，如如常常量量名名、变变量量名名和和过程名等。过程名等。常常数数:各各种种类类型型的的常常数数，如如25，3.1415，TRUE和和“ABC”等。等。运算符

6、运算符:如如+，*，=j)i-;while(i=j)i-;经词法分析器处理后转换的单词序列为：经词法分析器处理后转换的单词序列为：while ,-(,-id id的种别码的种别码,指向指向i i的符号表项的指针的符号表项的指针 =的种别码的种别码,-,-id ),-id -,-;,-第14页，共147页，编辑于2022年，星期一四、单词的三种描述工具四、单词的三种描述工具单词有三种描述工具：单词有三种描述工具：正规文法正规文法正规式正规式有穷自动机有穷自动机第15页，共147页，编辑于2022年，星期一1.正规文法正规文法正规文法的形式：正规文法的形式：右线性文法：右线性文法：AaB或或Aa

7、其中，其中，A、B为单个的非终结符，为单个的非终结符，a为单个的终结为单个的终结符。符。第16页，共147页，编辑于2022年，星期一标识符的文法标识符的文法PASCAL语言中的标识符是字母开头，后跟字母数字串。设l表示az中的任何一英文字母，d表示09中的任一数字。描述标识符的文法为：G11I:I lB|l BlB|dB|l|d注意：一般关键字（保留字）都是由字母构成，它是标识符注意：一般关键字（保留字）都是由字母构成，它是标识符集合的子集。集合的子集。第17页，共147页，编辑于2022年，星期一无符号整数的文法无符号整数的文法描述无符号整数的文法为：GD:D dD|d给出123的推导过程

8、：D 1D 12D 123给出00123的推导过程：D 0D 00D 001D 0012D 00123描述整数的文法为：GN:N+D|D D dD|d第18页，共147页，编辑于2022年，星期一最复杂的一类单词要属无符号实数了，比如25.55e+5和2.1，它们可以由如下规则描述：无符号数d余留无符号数|.十进小数|e指数部分余留无符号数d余留无符号数|.十进小数|e指数部分|十进小数d余留十进小数余留十进小数e指数部分|d余留十进小数指数部分d余留整指数|s整指数整指数d余留整指数余留整指数d余留整指数|其中s表示正或负号(+，-)，d表示09中的任一数字。无符号实数的文法无符号实数的文法

9、第19页，共147页，编辑于2022年，星期一程序设计语言中的其它单词的文法非常简单：运算符+|-|*|/|=|界符，|；|(|)|其它的文法其它的文法第20页，共147页，编辑于2022年，星期一2、正规式、正规式正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。正规式也称正则表达式，也是表示正规集的数学工具。第21页，共147页，编辑于2022年，星期一正规式的递归定义正规式的递归定义 是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为 ；是一个正规式，它所表示的正规集为是一个正规式，它所表示的

10、正规集为；aVaVT T是一个正规式，它所表示的正规集为是一个正规式，它所表示的正规集为aa；设设e e1 1和和e e2 2分别是表示的正规集分别是表示的正规集L(eL(e1 1)和和L(eL(e2 2)的正规式的正规式,则：则：a)a)e e1 1|e|e2 2是正规式是正规式,表示的正规集为表示的正规集为L(eL(e1 1)L(e)L(e2 2););b)b)e e1 1e e2 2是正规式是正规式,表示的正规集为表示的正规集为 L(e L(e1 1)L(e)L(e2 2););c)c)e e1 1*是正规式是正规式,表示的正规集为表示的正规集为(L(e(L(e1 1)*。第22页，共1

11、47页，编辑于2022年，星期一三种运算符规定运算符的优先顺序为：规定运算符的优先顺序为：*|。正规式定义中的正规式定义中的“|”读为读为“或或”（也（也有使用有使用“+”代替代替“|”的）；的）；“”读读为为“连接连接”；“*”读为读为“闭包闭包”（即，（即，任意有限次的自重复连接）。任意有限次的自重复连接）。连接符连接符“”一般可省略不写。一般可省略不写。“*”、“”和和“|”都是左结合的。都是左结合的。第23页，共147页，编辑于2022年，星期一示例示例=a，b 上的正规式和相应的正规集如下：正规式 正规集a aabab=a,bab a b=ab(ab)(ab)a,ba,b=aa,ab

12、,ba,bba a =,a,aa,任意个a的串 =a n|n 0ba b a =ba n|n 0a|ba a,b,ba,baa,baaa,第24页，共147页，编辑于2022年，星期一示例示例 正规式 正规集(ab)a,b =,a,b,aa,ab 所有由a 和b组成的串(ab)abb 所有结尾是abb的任意a和b的串(ab)(aabb)(ab)上所有含有两个相继 的a或两个相继的b组成 的串第25页，共147页，编辑于2022年，星期一描述单词的正规式描述单词的正规式程序设计语言的单词都能用正规式来定义。Pascal语言的标识符的正规式为：字母(字母|数字)*或写作 l(l|d)*无符号整数的

13、正规式为：d*d=d+=dd*无符号实数的正规式为：d*(dd*|)(e(+|-|)dd*|)运算符的正规式为：|*|/|(|)|第26页，共147页，编辑于2022年，星期一正规式等价正规式等价若两个正规式e1和e2所表示的正规集相同,即L(e1)=L(e2),则e1和e2等价,记为e1=e2。e1=ab，e2=ba，显然等价；e1=b(ab),e2=(ba)b均为babababababab，等价；e1=(ab),e2=(ab)均表示由a和b组成的任意的符号串，所以等价。第27页，共147页，编辑于2022年，星期一正规式的性质正规式的性质设设r,s,t为正规式，正规式服从的代数规律有为正规

14、式，正规式服从的代数规律有1.r s=s r“或或”服从交换律服从交换律2.r(s t)=(r s)t“或或”的可结合律的可结合律3.(rs)t=r(st)“连连接接”的的可可结结合合律律4.r(s t)=rs rt (s t)r=sr tr分配律分配律 5.r=r,r=r 是是“连连接接”的的恒恒等等元元素素零一律零一律6.r =r 的幂等律的幂等律 第28页，共147页，编辑于2022年，星期一3、有穷自动机、有穷自动机FA有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造

15、寻找特殊的方法和工具。有有 穷穷 自自 动动 机机 分分 为为 两两 类类：确 定 的 有 穷 自 动 机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。第29页，共147页，编辑于2022年，星期一有穷自动机的模型有穷自动机的模型有穷自动机FA是具有离散输入输出系统的数学模型。系统的状态概括了对过去输入处理情况的信息。系统只需要根据当前所处的状态和面临的输入就可以决

16、定系统的后继行为。每当系统出来了当前的输入后，系统的内部状态也将发生变化。例如：电梯控制装置就是有穷系统的典型。第30页，共147页，编辑于2022年，星期一19481948年，由神经物理学家年，由神经物理学家MeCulochMeCuloch和和PittsPitts首先首先提出提出FAFA模型。模型。a1a2a3a4 an#有有 穷穷控控 制制 器器输入带输入带有穷控制器控制读头从左向有穷控制器控制读头从左向右逐个扫描并读入输入符号，右逐个扫描并读入输入符号，并且根据控制器的当前状态并且根据控制器的当前状态和当前输入符号控制转入下和当前输入符号控制转入下一个状态。一个状态。读头读头第31页，共

17、147页，编辑于2022年，星期一接收方式接收方式FA在初始状态下开始读入第一个输入符。FA接收输入串：终态方式。若读头在输入带上最后一个符号时，恰好进入某个终止状态，则宣布接收该输入串；否则，不接收。第32页，共147页，编辑于2022年，星期一确定的有穷自动机DFA【DFA定义】一个确定的有穷自动机(DFA)M是一个五元组：M=（S，f，s0，Z），其中：S是一个有穷状态集，它的每个元素称为一个状态；是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表；f是状态转换函数，是定义在SS上的单值单值映射，即若 f（q1，a）=q2，表示在当前状态为q1，输入符为a时，将转换

18、为下一个状态q2，q2称作q1的后继状态；s0 S是唯一唯一的初态；Z S是一个终态集，终态也称可接受状态或结束状态。第33页，共147页，编辑于2022年，星期一示例【例【例1】DFA M=(0,1,2,3,a,b,f,0,3)，其中：，其中：f（0,a)=1 f（0,b)=2 f（1,a)=3 f（1,b)=2 f（2,a)=1 f（2,b)=3 f（3,a)=3 f（3,b)=3第34页，共147页，编辑于2022年，星期一状态转换矩阵DFA可以用一个矩阵表示可以用一个矩阵表示:行行:表示状态表示状态q;列列:表示输入字符表示输入字符a;矩矩阵阵元元素素：表表示示f(q,a)的的值值,即

19、即在在q状态下读入输入符a时应转换到的下一个状态。ab012132213333状态输入符第35页，共147页，编辑于2022年，星期一状态转换图DFA也可以表示成一张（确定的）状态也可以表示成一张（确定的）状态转换图：转换图：结点：表示状态，用圆圈圈起来；结点：表示状态，用圆圈圈起来；箭弧箭弧：表示状态转移的方向；：表示状态转移的方向；f(q1,a)q2：状态状态初态初态终态终态 q1 q2a第36页，共147页，编辑于2022年，星期一b0123aaaba，bbDFA：第37页，共147页，编辑于2022年，星期一串串 为为DFA M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串

20、，若存在，若存在一条从初态结点到某一终态结点的通路，一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成且这条通路上所有箭弧的标记符连接成的字符串等于的字符串等于，则称，则称串串 为为DFA M所所识别识别（读出或接受）。（读出或接受）。若若M的初态结点同时又是终态结点，则的初态结点同时又是终态结点，则为为空字空字 可为可为M所识别所识别。第38页，共147页，编辑于2022年，星期一示例示例例1中串abaa的识别路径为：b0123aaaba，bb0a1b2a1a3第39页，共147页，编辑于2022年，星期一扩充转换函数扩充转换函数f若有：f（q1，a1）=q2f（q2，a

21、2）=q3f（q3，a3）=q4f（qn，an）=qn+1则可记为：f(q1，a1 a2an)=qn1第40页，共147页，编辑于2022年，星期一DFA M所能识别的语言集DFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L(M)。若DFA M=（S，f，s0，Z），则有：L(M)|f(s0，)q，q Z 第41页，共147页，编辑于2022年，星期一示例示例例1中的DFA M所识别的语言集L(M)为在a,b上所有含相继两个a或相继两个b的字符串。L(M)(a|b)*(aa|bb)(a|b)*b0123aaaba，bb第42页，共147页，编辑于2022年，星期一标识符的标识符的

22、DFA标识符e2f3的识别路径为：0e121f1310字母字母1字母或数字字母或数字中间状态第43页，共147页，编辑于2022年，星期一无符号整数的无符号整数的DFA无符号整数0123的识别路径为：0011121310数字数字1 数字数字第44页，共147页，编辑于2022年，星期一无符号实数的无符号实数的DFA无符号实数3.8e+9的识别路径为：701346527dddddddee+7031.283e4+596第45页，共147页，编辑于2022年，星期一不确定的有穷自动机NFA【NFA定义】不确定的有穷自动机NFA M是一个五元组：M=（S，f，S0，Z），其中：S是有穷状态集；是有穷输

23、入字母表；f是状态转换函数，是定义在S2S上的多值映射，即若 f（q1，a）=q2，q3，表示在当前状态为q1，输入符为a时，将转换为下一个状态q2和q3状态；S0 S是初态集；Z S是一个终态集。第46页，共147页，编辑于2022年，星期一示例【例【例2】NFA M=(1,2,3,a,b,f,1,3,2)，其中：，其中：f(1,a)=3 f(1,b)=1,2 f(2,a)=f(2,b)=3 f(3,a)=f（3,b)=2状态转换矩阵为：状态转换矩阵为：ab131,22332状态输入符第47页，共147页，编辑于2022年，星期一NFA的状态转换图1a32bbbb第48页，共147页，编辑于

24、2022年，星期一串串 为为NFA M所识别所识别对于对于*中的任何一个字符串中的任何一个字符串，若存在，若存在一条从初态结点到某一终态结点的通一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符路，且这条通路上所有箭弧的标记符连接成的字符串等于连接成的字符串等于，则称，则称串串 为为NFA M所识别所识别（读出或接受）。（读出或接受）。第49页，共147页，编辑于2022年，星期一示例示例例2中串bab的识别路径为：1b1a3b21a32bbbb第50页，共147页，编辑于2022年，星期一NFA M所能识别的语言集NFA M所能识别的字符串的全体记为所能识别的字符串的全体记为L

25、(M)。若NFA M=（S，f，S0，Z），则有：L(M)|f(q1，)q2，q1 S0,q2 Z 第51页，共147页，编辑于2022年，星期一示例示例例2中的NFA M所识别的语言集为:L(M)b*(b|ab)(bb)*1a32bbbb第52页，共147页，编辑于2022年，星期一讨论注意注意DFA与与NFA的异同点。的异同点。DFA是是NFA的特例。的特例。对于每个对于每个NFA M都一定存在一个都一定存在一个DFA M，使，使L(M)=L(M)。即：对每个即：对每个NFA M存在着与之等价的存在着与之等价的DFA M。与某一与某一NFA等价的等价的DFA不唯一。不唯一。第53页，共14

26、7页，编辑于2022年，星期一标识符的标识符的NFAI字母字母B字母或数字字母或数字F字母或数字字母或数字字母字母字母数字IB,FBB,FB,FF第54页，共147页，编辑于2022年，星期一标识符的标识符的NFA标识符e2f3的识别路径为：IeB2BfB3FI字母字母B字母或数字字母或数字F字母或数字字母或数字字母字母第55页，共147页，编辑于2022年，星期一五、词法分析器的自动生成原理五、词法分析器的自动生成原理正规式NFA转换DFA确定化化简最小DFA第56页，共147页，编辑于2022年，星期一1.1.正规式 NFA对于上的一个正规式r，可以构造一个上的NFA M，使得L(M)=L

27、(r)。转换第57页，共147页，编辑于2022年，星期一构造方法构造方法引进初始结点X和终态结点Y，把正规式r表示成拓广转换图，如下所示：分析正规式r的语法结构，使用如下规则为r中的每个基本符号构造NFA。Xr Y第58页，共147页，编辑于2022年，星期一转换规则转换规则(a)对于正规式，所构造的NFA为：(b)对于正规式，所构造的NFA为：(c)对于正规式a，a，所构造的NFA为：X Y X Y Xa Y第59页，共147页，编辑于2022年，星期一 若r是由上的正规式r1，r2为复合而成的正规式，则按如下转换规则进行转换：(a)对正规式r1 r2，所构造的NFA如下：(b)对正规式r

28、1|r2，所构造的NFA如下：Xr1 Y 1r2 Xr1 Yr2第60页，共147页，编辑于2022年，星期一(c)对正规式r1*，所构造的NFA如下：r1 X Y 1第61页，共147页，编辑于2022年，星期一整个转换过程中，可用X表示初态，Y表示终态，所有新结点均采用不同的名字标记，可依次用1、2、3等。第62页，共147页，编辑于2022年，星期一示例示例【例3】构造正规式r1 01*的NFA。X01*Y X0 Y 11*X0 11 Y 2 第63页，共147页，编辑于2022年，星期一2.NFA DFA从NFA的矩阵表示中可以看出，表项通常是多个状态的集合，而在DFA的矩阵表示中，表

29、项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每的每一个状态对应一个状态对应NFA的一组状态。的一组状态。DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。确定化方法：状态子集法。确定化第64页，共147页，编辑于2022年，星期一状态子集状态子集【状态子集状态子集I I的的-闭包：闭包：-CLOSURE(I)-CLOSURE(I)】a a)若若q qI I，则，则q q-CLOSURE-CLOSURE（I I）；）；b)b)若若q qI I，那那么么从从q q出出发发经经任任意意条条弧弧而而能能到到 达达 的的 任任 何何 状状 态态 qq都都 属属 于于

30、_CLOSURE_CLOSURE（I I）；）；【状态子集【状态子集I Ia a=_CLOSURE(J)=_CLOSURE(J)】a a，I是状态子集，是状态子集，J J是那些可从是那些可从I I中的某一状中的某一状态结点出发经过一条态结点出发经过一条a a弧而到达的状态结弧而到达的状态结点的全体。点的全体。第65页，共147页，编辑于2022年，星期一示例示例I=1,-closure(I)=1,2；Ia 1 a 5,6,2,3,8,4,7;I=5,-closure(I)=5,6,2；Ia 5 a 3,8;1,2a=-closure(5,3,4)=2,3,4,5,6,7,8；12534687a

31、aa第66页，共147页，编辑于2022年，星期一示例示例【例【例4】画出正规式：】画出正规式：（a|b)*(aa|bb)(a|b)*对应的对应的NFA。4Y32615Xaaaabbbb第67页，共147页，编辑于2022年，星期一NFA确定化为确定化为DFA:状态子集法状态子集法从从NFA M=(S,f,S0,Z)构造等价的构造等价的DFA M(K,f,k0,F)的基本方法是：的基本方法是：1.求求DFA的初态的初态k0 -closure(NFA的初态的初态)-closure(X)X，5，1第68页，共147页，编辑于2022年，星期一2.求求DFA M 的状态集的状态集K中的其它状态以及中

32、的其它状态以及状态转换函数状态转换函数f,用求用求Ia，Ib的方法：的方法：设设I k0 f(k0，a)Ia k0 af(k0，b)Ib k0 b因为因为a,b,所以只需求所以只需求Ia，Ib即可。即可。子集子集Ia，Ib求出后得到一个新状态就添加求出后得到一个新状态就添加到到DFA的状态集的状态集K中；如此继续，直至不中；如此继续，直至不再产生新的状态为止。即可得到再产生新的状态为止。即可得到DFA的的全部状态全部状态K和状态转换函数和状态转换函数f。第69页，共147页，编辑于2022年，星期一示例示例对初态对初态k0求其求其Ia，Ib子集：子集：f(k0，a)Ia X，5，1 a 5，3

33、，1 f(k0，b)Ib X，5，1 b 5，4，1所得所得5，3，1与与5，4，1均是异于均是异于k0的新状态，的新状态，因此将它们加入因此将它们加入DFA的状态集的状态集K中。中。再继续对新状态再继续对新状态5，3，1 与与5，4，1利用求利用求Ia，Ib的方法求其它的状态。的方法求其它的状态。第70页，共147页，编辑于2022年，星期一示例示例对状态对状态5，3，1求其求其Ia，Ib子集：子集：f(5，3，1，a)5，3，1 a 5，3，1，2，6，Y f(5，3，1，b)5，3，1 b 5，4，1所得所得5，3，1，2，6，Y 加入加入DFA的状的状态集态集K中。中。第71页，共14

34、7页，编辑于2022年，星期一示例示例对状态对状态5，4，1求其求其Ia，Ib子集：子集：f(5，4，1，a)5，4，1 a 5，3，1 f(5，4，1，b)5，4，1 b 5，4，1，2，6，Y所得所得5，4，1，2，6，Y 加入加入DFA的状的状态集态集K中。中。如此继续，将此过程用状态转换矩阵记录如此继续，将此过程用状态转换矩阵记录下来：下来：第72页，共147页，编辑于2022年，星期一示例示例 I Ia Ib X,5,1 5,3,1 5,4,1 5,3,1 5,3,1,2,6,Y 5,4,1 5,4,1 5,3,1 5,4,1,2,6,Y5,3,1,2,6,Y 5,3,1,2,6,Y

35、 5,4,1,6,Y5,4,1,2,6,Y 5,3,1,6,Y 5,4,1,2,6,Y5,4,1,6,Y 5,3,1,6,Y 5,4,1,2,6,Y 5,3,1,6,Y 5,3,1,2,6,Y 5,4,1,6,Y第73页，共147页，编辑于2022年，星期一示示例例对上面的表中的状态子集重新命名后的状态转换矩对上面的表中的状态子集重新命名后的状态转换矩阵阵 a b 0 1 2 1 3 2 2 1 5 3 3 4 4 6 5 5 6 5 6 3 4 第74页，共147页，编辑于2022年，星期一如何确定如何确定DFA的终态集的终态集包含原NFA的终态的子集都是DFA的终态。例如：3，4，5，6均

36、是终态。第75页，共147页，编辑于2022年，星期一所得所得DFA如下：如下：3521460baaaaabbbbbaab第76页，共147页，编辑于2022年，星期一3.DFA的化简的化简确定有穷自动机M的化简是指：寻找一个状态数比DFA M少的DFA M，使得L(M)L(M)。一个有穷自动机是化简了的，即是它没有多余状态，并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。第77页，共147页，编辑于2022年，星期一多余状态多余状态所谓有穷自动机的多余状态，是指这样的状态：从有穷自动机的初态出发，任何输入串也不能到达

37、的那个状态；或者从这个状态没有通路到达终态。第78页，共147页，编辑于2022年，星期一等价和可区别的等价和可区别的等价：如果有穷自动机DFA M的两个状态s和t能够识别同样的符号串，则称状态s和t等价。可区别的：如果有穷自动机DFA M的两个状态s和t不等价，则称这两个状态是可区别的。【例如】终态与非终态是可区别的。第79页，共147页，编辑于2022年，星期一 DFADFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFADFA最小状态最小状态DFA的含义的含义:没有多余状态没有多余状态(死状态死状态)没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）两个状态两个状

38、态s和和t可区别：不满足可区别：不满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s出发读入某个出发读入某个a a和从和从 t出发出发读入某个读入某个a到达的状态等价。到达的状态等价。第80页，共147页，编辑于2022年，星期一DFA的最小化过程：分割法的最小化过程：分割法确定有限自动机确定有限自动机M的化简的过程也就是的化简的过程也就是其状态最少化过程：其状态最少化过程：一个一个 DFA M的状态最少化过程是指将的状态最少化过程是指将 M的状态集分割成一些不相交的子集，使的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区得任何不同的两子集中的状态都

39、是可区别的，而同一子集中的任何两个状态都别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。个代表，同时消去其它等价状态。第81页，共147页，编辑于2022年，星期一例如：将前面所得的例如：将前面所得的DFA化简化简3521460baaaaabbbbbaab第82页，共147页，编辑于2022年，星期一示例示例DFA的状态集的状态集k0，1，2，3，4，5，61.首先把首先把M的状态的状态K分为两组：分为两组：终态集终态集K1=3，4，5，6非终态集非终态集K2=0，1，2显然显然K1与与K2不等价。不等价。第8

40、3页，共147页，编辑于2022年，星期一2.然后，试图然后，试图K1，K2在中寻找一个子集和在中寻找一个子集和一个输入符号使得这个子集中的状态可一个输入符号使得这个子集中的状态可区别的；若可区别，则再分割；继续，区别的；若可区别，则再分割；继续，一直到不能再分割为止。一直到不能再分割为止。讨论终态集讨论终态集K1=3，4，5，6 是否可分是否可分割：割：3，4，5，6a K1 3，4，5，6b K1 所以状态所以状态3，4，5，6均等价，因此均等价，因此K1不能再分割。不能再分割。第84页，共147页，编辑于2022年，星期一讨论非终态集讨论非终态集K2=0，1，2 是否可分割：是否可分割：

41、0，1，2a 1，3 它既不属于它既不属于K20，1，2，也不属于，也不属于K13，4，5，6，因此应将其一分为二。，因此应将其一分为二。0，2a 1 1a 3 由于由于1态经态经a弧到达弧到达3态，而且状态态，而且状态0，2经经a弧到达弧到达1态，态，所以将所以将1状态分出来，形成状态分出来，形成 K211 K220，2第85页，共147页，编辑于2022年，星期一再讨论再讨论K22=0，2 是否可分割：是否可分割：0，2b 2，5 而它未包括在而它未包括在K1，K21与与K22中，故中，故0，2应一分为二：应一分为二：K2210 K2222所以所以K分为四组分为四组3，4，5，6，0，1，

42、2。每个组都不可再分。每个组都不可再分。第86页，共147页，编辑于2022年，星期一3.最后，令状态最后，令状态3代表代表3，4，5，6。把原。把原来到达来到达4，5，6的弧都导入的弧都导入3，并删除，并删除4，5，6状态。即可得到化简后的状态。即可得到化简后的DFA。3210aaabbb,ba第87页，共147页，编辑于2022年，星期一示例示例【例【例5】正规式】正规式r(a|b)*abb1.由正规式由正规式r构造构造NFA为：为：Y34bba21Xab第88页，共147页，编辑于2022年，星期一2.NFA确定化为DFA：初态-closure(X)X，1，2IIaIb初态X,1,2X,

43、1,2 a=1,2,3X,1,2b=1,21,2,31,2,31,2,41,21,2,31,21,2,41,2,31,2,Y终态终态1,2,Y1,2,31,2第89页，共147页，编辑于2022年，星期一重命名为：重命名为：ab012113212314412状态输入符第90页，共147页，编辑于2022年，星期一DFA的状态转换图为：的状态转换图为：42ab310abbaabba第91页，共147页，编辑于2022年，星期一3.DFA的化简：的化简：DFA的状态集的状态集K0，1，2，3，41)首先把状态首先把状态K分为可区别的两组状态集：分为可区别的两组状态集：终态集终态集K1=4非终态集非

44、终态集K2=0，1，2，3第92页，共147页，编辑于2022年，星期一2)讨论K2=0，1，2，3能否分割：能否分割：0，1，2，3a 1 0，1，2，3b 2，3，4而 3b 4 K1 0，1，2b 2，3 K2所以可分割为K21=0，1，2 K22=3第93页，共147页，编辑于2022年，星期一3)讨论K21=0，1，2能否分割：能否分割：0，1，2a 1而 0，2b 2 K21 1b 3 K22所以可分割为K211=0，2 K212=1第94页，共147页，编辑于2022年，星期一4)讨论讨论K211=0，2能否分割：能否分割：0，2a 1 0，2b 2所以不可分割，所以不可分割，0

45、状态与状态与2状态等价，不状态等价，不再分割。再分割。所以最终将状态集所以最终将状态集K分割为分割为0，2，1，3，4，一共四组。，一共四组。第95页，共147页，编辑于2022年，星期一最后，令状态最后，令状态0代表代表0，2。把原来到达。把原来到达2的弧都导入的弧都导入0，并删除，并删除2状态。即可得到状态。即可得到化简后的化简后的DFA。4ab310abaabb第96页，共147页，编辑于2022年，星期一示例示例【例【例6】标识符的正规式】标识符的正规式r为为l(l|d)*1.由正规式由正规式r构造构造NFA为：为：Y1Xl2ld第97页，共147页，编辑于2022年，星期一2.NFA

46、确定化为DFA：初态-closure(X)XIIlId初态XX l=1,2,YXd=终态终态1,2,Y2,Y2,Y终态终态2,Y2,Y2,Y第98页，共147页，编辑于2022年，星期一重命名为：重命名为：ld01122222状态输入符第99页，共147页，编辑于2022年，星期一DFA的状态转换图为：的状态转换图为：2d0ll1l，d第100页，共147页，编辑于2022年，星期一3.DFA的化简：的化简：DFA的状态集的状态集K0，1，21)首先把状态首先把状态K分为可区别的两组状态集：分为可区别的两组状态集：终态集终态集K1=1，2 非终态集非终态集K2=0第101页，共147页，编辑于

47、2022年，星期一2)讨论K1=1，2能否分割：能否分割：1，2a 2 1，2b 2所以不可分割，所以不可分割，1状态与状态与2状态等价，不状态等价，不再分割。再分割。所以最终将状态集所以最终将状态集K分割为分割为0，1，2，一共两组。，一共两组。第102页，共147页，编辑于2022年，星期一最后，令状态最后，令状态1代表代表1，2。把原来到达。把原来到达2的弧都导入的弧都导入1，并删除，并删除2状态。即可得到状态。即可得到化简后的化简后的DFA。0l1l，d第103页，共147页，编辑于2022年，星期一六、正规文法六、正规文法 有穷自动机有穷自动机对于正规文法G和有穷自动机FA M，如果

48、L(G)=L(M),则称G和M等价。转换第104页，共147页，编辑于2022年，星期一右线性文法的转换方法右线性文法的转换方法引入一个终态F。设右线性文法G(VN,VT,P,S),则相应的自动机为M(VN F,VT,f,S,F)。状态转换函数f由以下规则定义：1.P中形如AaB的产生式，则有f(A,a)=B;2.P中形如Aa的产生式，则有f(A,a)=F;3.对VT中的每个a，都有f(F,a)=。第105页，共147页，编辑于2022年，星期一示例示例【例7】描述标识符的右线性文法为：G11I:I lB|l BlB|dB|l|d第106页，共147页，编辑于2022年，星期一转换为转换为NF

49、A引入一个终态引入一个终态F，则相应的，则相应的NFA为：为：M(I,B,F,l,d,f,I,F),其中其中f可确定为：可确定为：由由I lB 可得可得 f(I，l)B 由由I l 可得可得 f(I，l)F 由由B lB 可得可得 f(B，l)B 由由B dB 可得可得 f(B，d)B 由由B l 可得可得 f(B，l)F由由B d 可得可得 f(B，d)F 第107页，共147页，编辑于2022年，星期一用状态转换图表示为：用状态转换图表示为：FIlBl，dldl第108页，共147页，编辑于2022年，星期一初态-closure(I)IIIlId初态II l=B,FId=终态终态B,FB,

50、FB,F将此将此NFA确定化为确定化为DFA第109页，共147页，编辑于2022年，星期一重命名为：重命名为：ld01111状态输入符0l1l，dDFA即为：即为：第110页，共147页，编辑于2022年，星期一上述上述DFA已经是最小的已经是最小的DFA，不需要，不需要再化简。再化简。因为如果要进行化简，则首先要把因为如果要进行化简，则首先要把DFA的状态集分为可区别的两组状态集：的状态集分为可区别的两组状态集：终态集终态集K1=1非终态集非终态集K2=0而它们无法再分割，所以不需要化简，而它们无法再分割，所以不需要化简，此此DFA即是最简即是最简DFA。第111页，共147页，编辑于20