编译原理第3章第1节词法分析、DFA、NFA及其转换.ppt

《编译原理第3章第1节词法分析、DFA、NFA及其转换.ppt》由会员分享，可在线阅读，更多相关《编译原理第3章第1节词法分析、DFA、NFA及其转换.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、源程序源程序目标程序目标程序词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成表表格格管管理理错错误误检检测测第三章第三章 词法分析词法分析主要内容主要内容1.1.介绍词法分析的介绍词法分析的过程过程2.2.讨论词法分析器的讨论词法分析器的设计与实现设计与实现3.3.介绍实现词法分析器的主要工具：介绍实现词法分析器的主要工具：状态转换图状态转换图状态转换图状态转换图第三章第三章 词法分析词法分析3.1 3.1 词法分析器的任务词法分析器的任务v人们理解一篇文章（或程序）起码是先在人们理解一篇文章（或程序）起码是先在单词单词级别上思考

2、。级别上思考。v编译程序要分析和翻译源程序，也先要编译程序要分析和翻译源程序，也先要区分区分一个一个的一个一个的单词单词。v词法分析程序的词法分析程序的任务任务是：从左到右逐个字符对源程序扫描，产生一个是：从左到右逐个字符对源程序扫描，产生一个单词序列，把作为字符串的源程序改造为单词符号串的中间程序。单词序列，把作为字符串的源程序改造为单词符号串的中间程序。v词法分析程序又称词法分析程序又称词法分析器或扫描器词法分析器或扫描器。除了识别单词的基本任务外，词法分析还可以完成除了识别单词的基本任务外，词法分析还可以完成以下任务以下任务：（1 1）组织源程序的输入）组织源程序的输入（2 2）删除删除

3、注释、空格及无用符号（如回车等）注释、空格及无用符号（如回车等）（3 3）行、列）行、列计数计数（4 4）列表打印源程序）列表打印源程序（5 5）发现并定位发现并定位词法错误词法错误（6 6）建立、查填）建立、查填符号表符号表3.1.1 3.1.1 单词符号的表示单词符号的表示v基本字：基本字：也称关键字，如也称关键字，如C C语言中的语言中的int,void,if,whileint,void,if,while等；等；v标识符：标识符：用来表示各种名字，如变量名、常量名、函数名等；用来表示各种名字，如变量名、常量名、函数名等；v常数：常数：如如25,3.1415926,a,“hello”,TR

4、UE25,3.1415926,a,“hello”,TRUE等；等；v算符：算符：如如+,=,+,=,等；等；v界符：界符：如逗号，分号，括号等。如逗号，分号，括号等。v基本字、运算符和界符一般确定；基本字、运算符和界符一般确定；v标识符和常数的数量一般不加限制。标识符和常数的数量一般不加限制。注：注：（1 1）程序设计语言单词的分类纯属技术性问题，可以有不同的方法）程序设计语言单词的分类纯属技术性问题，可以有不同的方法分类；分类；（2 2）除上述一般分类方法外，还有一字一类或一符一类等方法）除上述一般分类方法外，还有一字一类或一符一类等方法单词的分类，如：单词的分类，如：while(i 10)

5、i+;while(i=“)(1,指向指向j的符号表入口的符号表入口)(5,“)”)(1,指向指向i的符号表入口的符号表入口)(4,“-”)(5,“;”)数据类型数据类型 存储地址存储地址int3056int3060例：例：while(i=j)i-;单词的表示：举例单词的表示：举例3.1.2 3.1.2 词法分析器的结构词法分析器的结构字符串形式的源程序字符串形式的源程序单词串形式的源程序单词串形式的源程序词法分析器词法分析器字符字符词法分析器与语法分析器的联系词法分析器与语法分析器的联系（1 1）词法分析作为单独的一遍）词法分析作为单独的一遍3.1.2 3.1.2 词法分析器的结构词法分析器的

6、结构将词法分析器分离的考虑将词法分析器分离的考虑o使整个编译程序的结构更简洁、清晰和条理化；使整个编译程序的结构更简洁、清晰和条理化；o编译程序效率更高；编译程序效率更高；o增强编译程序的可移植性。增强编译程序的可移植性。(2)(2)词法分析作为子程序词法分析作为子程序输入串输入串词法分析器词法分析器语法分析器语法分析器符号表符号表取取下下一一单单词词返返回回下下一一单单词词词法分析器与语法分析器的联系词法分析器与语法分析器的联系3.1.2 3.1.2 词法分析器的结构词法分析器的结构扫描缓冲区扫描缓冲区1.1.预预处处理理程程序序：取取消消注注解解，剔剔除除无无用用的的空空白白、跳格、回车、

7、换行等跳格、回车、换行等2.2.输入缓冲区输入缓冲区：源程序：源程序输入缓冲区输入缓冲区3.1.2 3.1.2 词法分析器的结构词法分析器的结构v主要是为方便单词的识别工作：主要是为方便单词的识别工作：（1）剔除无用的空白符、跳格符、回车符、换行符。）剔除无用的空白符、跳格符、回车符、换行符。,t,r,n（2）剔除注释：）剔除注释：/*/,/（3）合并空白符。）合并空白符。预处理程序预处理程序例：例：int max(int x,int y)/求求x,y的最大值的最大值int z;z=(x y?x:y);return z;预处理后：预处理后：int max(int x,int y)int z;z

8、=(xy?x:y);return z;3.1.2 3.1.2 词法分析器的结构词法分析器的结构预处理程序预处理程序3.1.2 3.1.2 词法分析器的结构词法分析器的结构缓冲区的设计缓冲区的设计pp 起点指针：起点指针：用来指示正在扫描的单词的起点；用来指示正在扫描的单词的起点；pp 搜索指针：搜索指针：用于向前搜索，寻找单词的结束；用于向前搜索，寻找单词的结束；pp 缓冲区结构缓冲区结构扫扫描描缓缓冲冲区区：从从输输入入缓缓冲冲区区输输入入固固定定长长度度的的字字符符串串到到另另一一个个缓缓冲冲区区（扫扫描描缓缓冲冲区区），词词法法分分析析可可以以直直接接在在此此缓缓冲冲区区中中进进行行符符

9、号号识识别别。扫扫描描缓缓冲冲区区的的结构：结构：o假设标识符和常数的最大长度为假设标识符和常数的最大长度为256缓冲区长度：缓冲区长度：512标识符起标识符起点点(500)搜索指搜索指示器示器3.1.2 3.1.2 词法分析器的结构词法分析器的结构标识符起标识符起点点(252)搜索指搜索指示器示器缓冲区长度：缓冲区长度：256缓冲区长度：缓冲区长度：256p：设设置置左左右右两两个个缓缓冲冲区区，当当左左缓缓冲冲区区读读完完后后，新新读读入入的的字字符符存存入右缓冲区；反之，存放在左缓冲区；入右缓冲区；反之，存放在左缓冲区；缓冲区的设计缓冲区的设计小结小结v词法分析器的任务；词法分析器的任务

10、；v单词符号的分类；单词符号的分类；v单词符号的表示；单词符号的表示；v词法分析预处理；词法分析预处理；v词法分析器的工作方式；词法分析器的工作方式；v扫描缓冲区的双缓冲策略。扫描缓冲区的双缓冲策略。3.2.1 3.2.1 正规式与正规集正规式与正规集p 正规式（正规表达式）：正规式（正规表达式）：用以描述单词符号的工用以描述单词符号的工具，是说明单词的模式的一种重要的表示法具，是说明单词的模式的一种重要的表示法,是是定义正规集的工具。定义正规集的工具。p一个正规式对应一个一个正规式对应一个正规集正规集正规正规式和正规表达式式和正规表达式3.2.1 3.2.1 正规式与正规集正规式与正规集对字

11、母表对字母表：(1)(1)和和都是都是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为和和；(2)(2)aa，a a是是上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为aa；(3)(3)假定假定U U和和V V都是都是上的正规式，它们所表示的正规集分别记为上的正规式，它们所表示的正规集分别记为L(U)L(U)和和L(V)L(V)，那么那么(U|V)(U|V)、(UV)(UV)和和(U)*(U)*也是正规式，它们所对应的正规集分别为也是正规式，它们所对应的正规集分别为L(U)L(V)L(U)L(V)、L(U)L(V)L(U)L(V)和和(L(U)*(L

12、(U)*。仅由仅由有限次有限次使用上述三步骤得到的表达式才是正规式，仅由这些正规使用上述三步骤得到的表达式才是正规式，仅由这些正规式所表示的字集才是式所表示的字集才是上的正规集。上的正规集。例例3.1 令令=a，boba*上所有以上所有以b为首，后跟任意多个为首，后跟任意多个a的的字符串字符串；oa(a|b)*上所有以上所有以a为首的字符串；为首的字符串；o(a|b)*(aa|bb)(a|b)*上含两个连续上含两个连续a或两个连续或两个连续b的的字符串字符串。正规正规式和正规表达式式和正规表达式3.2.1 3.2.1 正规式与正规集正规式与正规集例例3.1 令令=a，b正规式正规式 aa|ba

13、b(a|b)(a|b)a*(a|b)*(a|b)*(aa|bb)(a|b)*正规集正规集 aa,babaa,ab,ba,bb,a,a,任意个任意个a的串的串,a,b,aa,ab 所有由所有由a和和b组成的串组成的串*上所有含有两个相继的上所有含有两个相继的a或两或两个相继的个相继的b组成的串组成的串能被能被5 5整除的十进制整数的正则表达式整除的十进制整数的正则表达式规则（规则（1）：）：表达式的头部为：表达式的头部为：-、+或或，表示整数的正、负，表示整数的正、负，表示整数的正、负，表示整数的正、负规则（规则（2）：十进制整数的尾部以：十进制整数的尾部以0或者或者5结束结束规则（规则（3）：

14、整数的中部是任意：整数的中部是任意0-9组成的数字串组成的数字串3.2.1 3.2.1 正规式与正规集正规式与正规集(+|-|)(0|1|9)*(0|5)常用的正规式常用的正规式整数：整数：(+|-|)(0|1|9)(0|1|9)(0|1|9)(0|1|9)*浮点数：浮点数：(+|-|)(0|1|9)(0|1|9)*.(0|1|9)(0|1|9).(0|1|9)(0|1|9)*标识符：标识符：(a|z|A|Z|_)(a|z|A|Z|_|0|9)*3.2.1 3.2.1 正规式与正规集正规式与正规集正规式的关系正规式的关系o交换律：交换律：U|V=V|U；o结合律：结合律：U|(V|W)=(U|

15、V)|W；U(VW)=(UV)W；o分配律：分配律：U(V|W)=UV|UW；(V|W)U=VU|WU；oU=U=U。3.2.2 3.2.2 状态转换图状态转换图(TG)(TG)转换图是一张转换图是一张有限方向图有限方向图；结点表示结点表示状态状态，用圆圈表示；，用圆圈表示；状态之间用状态之间用有向弧有向弧连接；连接；有向弧上的有向弧上的标记标记(字符字符)表示在射出结点所代表的状态下可能出现的输入符号表示在射出结点所代表的状态下可能出现的输入符号或符号串；或符号串；一张转换图只包含一张转换图只包含有限有限个状态，且有一个个状态，且有一个初态初态，至少有一个，至少有一个终态终态；一个状态转换图

16、可用于识别一个状态转换图可用于识别(或接受或接受)一定的字符串，如一定的字符串，如 (a|b)(a|b)*(aa|bb)(a|b)(aa|bb)(a|b)*。3012baabbaab状态转换图状态转换图3.2.2 3.2.2 状态转换图状态转换图(TG)(TG)状态转换图的作用：状态转换图的作用：（1 1）识别字符串是否为文法的句子（单词）识别字符串是否为文法的句子（单词）方法：方法：从文法的开始符号出发，按照与符号串预留部分中最左字符相匹配的原则游从文法的开始符号出发，按照与符号串预留部分中最左字符相匹配的原则游历状态图，直到符号串的末端为止。历状态图，直到符号串的末端为止。如果这时恰好到达

17、终止状态，则符号串为文法的句子，否则不是如果这时恰好到达终止状态，则符号串为文法的句子，否则不是3012baabbaab如利用转换图判定字符串：如利用转换图判定字符串：(1)ab(1)ab(2)aab(2)aab(3)aa(3)aa状态转换图的作用状态转换图的作用3.2.2 3.2.2 状态转换图状态转换图(TG)(TG)状态转换图的作用：状态转换图的作用：（2 2）根据状态图可构造相应的语法分析程序。）根据状态图可构造相应的语法分析程序。画出状态转化图。画出状态转化图。由正则文法或正则式构造状态转换图。由正则文法或正则式构造状态转换图。由状态转换图编写程序。由状态转换图编写程序。对于状态转换

18、图中每一个状态构造一段代码，代码对于状态转换图中每一个状态构造一段代码，代码的功能是的功能是a.a.从输入串中读入一个字符；从输入串中读入一个字符；b.b.判断读入的字符与由此状态出发的哪条弧上的标记相匹配，便转至相匹配判断读入的字符与由此状态出发的哪条弧上的标记相匹配，便转至相匹配的那条弧所指向的状态。的那条弧所指向的状态。c.c.均不匹配时便失败，即不能到达正常入口。均不匹配时便失败，即不能到达正常入口。状态转换图的作用状态转换图的作用3012baabbaab3.2.3 3.2.3 确定有限自动机确定有限自动机(DFA)(DFA)一个一个DFA MDFA M是一个五元组，是一个五元组，M=

19、(K,f,S,Z):M=(K,f,S,Z):(1)K(1)K：状态集；：状态集；(2)(2)：字母表；：字母表；(3)f(3)f：从：从KK到到K K的的单值部分映射单值部分映射，即，即f(kf(ki i,a)=k,a)=kj j；(4)SK(4)SK，是唯一的初态；，是唯一的初态；(5)Z(5)Z K K，是终态集。，是终态集。01a2a01a3当前状态和输入当前状态和输入字符只能确定下字符只能确定下一个状态一个状态3.2.3 3.2.3 确定有限自动机确定有限自动机(DFA)(DFA)vDFA M=(K,f,S,Z):(1)K=0,1,2,3;(2)=a,b;(3)f：f(0,a)=1,f

20、(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(4)S=0；(5)Z=3。ab0121322133333012baabbaab例例1 1：构造：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶数个和偶数个1 1所组成所组成(01)(01)字符字符串。串。分析问题的状态空间：分析问题的状态空间：0：包含偶数个：包含偶数个0偶数个偶数个1；1：包含偶数个：包含偶数个0奇数个奇数个1；2：包含奇数个：包含奇数个0偶数个偶数个1；3：包含奇数个：包含奇数个0奇数个奇数个1。不管串处于哪一种情况，只要再

21、添加一个不管串处于哪一种情况，只要再添加一个0或或1，就会转换到另一种情况。，就会转换到另一种情况。0123100101013.2.3 3.2.3 确定有限自动机确定有限自动机(DFA)(DFA)例例2 2：构造：构造DFADFA，使其能接受，使其能接受=0,1=0,1上能被上能被4 4整除的二进制数整除的二进制数 分析问题的状态空间：分析问题的状态空间：任意二进制数除以任意二进制数除以4，只有余数为，只有余数为0、1、2、3四种情况。四种情况。0123 一个二进制数后面加一个二进制数后面加0，相当于变为原来的，相当于变为原来的2倍；后面加倍；后面加1，相当于变为原，相当于变为原来的来的2倍加

22、倍加1。若若x mod 4=0,则：则：2x mod 4=0;(2x+1)mod 4=101若若x mod 4=1,则：则：2x mod 4=2;(2x+1)mod 4=301若若x mod 4=2,则：则：2x mod 4=0;(2x+1)mod 4=101若若x mod 4=3,则：则：2x mod 4=2;(2x+1)mod 4=3013.2.3 3.2.3 确定有限自动机确定有限自动机(DFA)(DFA)例例3 3：一个人带着狼、山羊和白菜要从一条河左岸渡到右岸。有：一个人带着狼、山羊和白菜要从一条河左岸渡到右岸。有一条船，恰好能装下人和其它三件东西中的一件。用有限自动机一条船，恰好能

23、装下人和其它三件东西中的一件。用有限自动机找出渡河方案。找出渡河方案。左岸存在的东西作为状态，初始为人、狼、羊、白菜都在左岸，接受状态为都不在左岸。左岸存在的东西作为状态，初始为人、狼、羊、白菜都在左岸，接受状态为都不在左岸。（人、狼、羊、白菜）（人、狼、羊、白菜）（人、狼、羊）（人、狼、羊）（人、狼、白菜）（人、狼、白菜）（人、羊、白菜）（人、羊、白菜）（人、狼）（人、狼）（人、羊）（人、羊）（人、白菜）（人、白菜）（狼、羊、白菜）（狼、羊、白菜）（狼、羊）（狼、羊）（狼、白菜）（狼、白菜）（羊、白菜）（羊、白菜）（人）（人）（狼）（狼）（羊）（羊）（白菜）（白菜）0 01 12 23 34

24、 45 56 67 78 89 93.2.3 3.2.3 确定有限自动机确定有限自动机(DFA)(DFA)0人人,狼狼,羊羊,白菜白菜1人人,狼狼,羊羊2人人,狼狼,白菜白菜3人人,羊羊,白菜白菜4人人,羊羊5狼狼,白菜白菜6狼狼7羊羊8白菜白菜9用用G(x)表示人表示人带带x从左岸到右从左岸到右岸，岸，R(x)表示表示从人带从人带x右岸回右岸回到左岸；到左岸；G和和R分别代表分别代表人自己去到右人自己去到右岸或回到左岸。岸或回到左岸。0123467859G(羊)G(狼狼)G(羊羊)GG(狼狼)G(白菜白菜)G(羊羊)G(白菜白菜)GG(羊羊)RR(羊羊)R(羊羊)R(白菜白菜)RR(狼狼)R

25、(白菜白菜)R(狼狼)R(羊羊)R(羊羊)0人人,狼狼,羊羊,白菜白菜1人人,狼狼,羊羊2人人,狼狼,白菜白菜3人人,羊羊,白菜白菜4人人,羊羊5狼狼,白菜白菜6狼狼7羊羊8白菜白菜90123467859G(羊羊)G(狼狼)G(羊羊)GG(狼狼)G(白菜白菜)G(羊羊)G(白菜白菜)GG(羊羊)RR(羊羊)R(羊羊)R(白菜白菜)RR(狼狼)R(白菜白菜)R(狼狼)R(羊羊)R(R(羊羊羊羊)05283749步骤：步骤：(1)G(羊羊)5(狼狼,白菜白菜)(2)R2(人人,狼狼,白菜白菜)(3)G(狼狼)8(白菜白菜)(4)R(羊羊)3(人人,羊羊,白菜白菜)(5)G(狼狼)7(羊羊)(6)R

26、4(人人,羊羊)(7)G(羊羊)9()问题：问题：v任给一个正规式，如任给一个正规式，如(a|b)(a|b)*(aa|bb)(a|b)(aa|bb)(a|b)*，如何构造其，如何构造其DFADFA？0ab1234aabb5ab(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*0a|b3a|b12aabb 0(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*1ab00,1,20,1,312324,534,54555550ab1234aabb5abNFA M=(0,1,2,3,4,5,a,b,f,0,5)f:f(0,a)=0,1,f(0,b)=0

27、,1,f(1,a)=2,f(1,b)=3,f(2,a)=4,5,f(2,b)=,f(3,a)=,f(3,b)=4,5,f(4,a)=5,f(4,b)=5,f(5,a)=5,f(5,b)=5.3.2.4 3.2.4 非确定有限自动机非确定有限自动机(NFA)(NFA)v一个一个NFA MNFA M是一个五元组，是一个五元组，M=(K,f,S,Z):M=(K,f,S,Z):(1)K(1)K：状态集；：状态集；(2)(2)：字母表；：字母表；(3)f(3)f：从：从KK*到到K K的子集映像；的子集映像；(4)S(4)S K K，是初态集；，是初态集；(5)Z(5)Z K K，是终态集。，是终态集。

28、DFA和和NFA在使用上各自的优点和缺点在哪里？在使用上各自的优点和缺点在哪里？DFA编程实现容易，但构造难编程实现容易，但构造难NFA构造容易，但编程实现有回溯构造容易，但编程实现有回溯能否找到一个从能否找到一个从NFA到到DFA的自动转换算法？的自动转换算法？3.2.4 3.2.4 非确定有限自动机非确定有限自动机(NFA)(NFA)文法、正规式、文法、正规式、DFA(NFA)DFA(NFA)之间的关系之间的关系正则文法（正则文法（3 3型文法）型文法）正规式正规式 DFADFANFANFA3.2.5 NFA3.2.5 NFA确定化为确定化为DFADFAvNFA M=(K,f,S,Z)NF

29、A M=(K,f,S,Z)，DFA MDFA M1 1=(K=(K1 1,1 1,f,f1 1,S,S1 1,Z,Z1 1)v字母表字母表不必转换；不必转换；v开始状态开始状态：DFADFA中只有一个，中只有一个，NFANFA中有多个。中有多个。v转换函数转换函数：DFADFA是从是从KK到到K K的映像的映像，而，而NFANFA是从是从KK*到到K K的子集的子集的映像。的映像。区别：区别：KK到到K K的映像的映像 K K*到到K K的子集的子集3.2.5 NFA3.2.5 NFA确定化为确定化为DFADFAv可以引入新的状态可以引入新的状态X X，作为新的，作为新的NFANFA的初始状态

30、，然后从的初始状态，然后从X X向原向原NFANFA的每个初始状态引的每个初始状态引弧。弧。01a2bX301a2b3一、多个初始状态向单个初始状态的转换：一、多个初始状态向单个初始状态的转换：二、二、K*K子集子集KKvKK*K K子集子集vK K()()K K子集子集vKKK K3.2.5 NFA3.2.5 NFA确定化为确定化为DFADFA（1）K*K子集子集 K()K子集子集ijABijA|BijA*ijAkBijABij k A3.2.5 NFA3.2.5 NFA确定化为确定化为DFADFA(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*0a|b3a|b1

31、2aabb 0(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*1例：将下面的例：将下面的TGTG进行转换，使其弧上或进行转换，使其弧上或为单个字符，或为为单个字符，或为。01(a|b)(a|b)*(aa|bb)(a|b)(aa|bb)(a|b)*0231(a|b)(a|b)*(a|b)(a|b)*aa|bbaa|bb0231a|ba|b4 bbbbaaaaa|ba|b5 02314 5 b ba ab ba a67a ab bb ba a K K*K K子集子集 K K()()K K子集子集 KKK K3.2.5 NFA3.2.5 NFA确定化为确定化为DFADFA

32、（2）K()K子集子集KK01a30Aa0134I_Closure(I)若若q I，则，则q _Closure(I)；若若q I，q=f(q,),则则q _Closure(I)。3.2.5 NFA3.2.5 NFA确定化为确定化为DFADFA01a23a0Aa若若I=S1,S2,Sk,则定义则定义move(I,a)=f(S1,a)f(S2,a)f(Sk,a),Ia=_Closure(move(I,a);013a4a5I（2）K()K子集子集KK3.2.5 NFA3.2.5 NFA确定化为确定化为DFADFA01a23a45bb0Aa45bbBb0AaIIaIb01,2,31,2,34,54,5

33、假设假设=a=a1 1,a,ak k,开始状开始状态为态为X X，线性规划算法：，线性规划算法：(1)(1)构造一个有构造一个有k+1k+1列的表；列的表；(2)(2)首行首列为首行首列为_Closure(X);_Closure(X);(3)(3)若某行第若某行第1 1列已经确定，则列已经确定，则置该行置该行i+1i+1列为列为I Iai ai;(4)(4)若该行某项未在该表第一若该行某项未在该表第一列出现，则填入该表后面空列出现，则填入该表后面空行的第一列；行的第一列；(5)(5)重复重复(3)(4)(3)(4)，直到所有项均，直到所有项均在第一列出现。在第一列出现。3.2.5 NFA3.2

34、.5 NFA确定化为确定化为DFADFA例：构造正规式例：构造正规式(a|b)*(aa|bb)(a|b)*的的DFAvStep1:Step1:构造构造NFANFA0a|b3a|b12aabb 3.2.6 3.2.6 构造正规式的构造正规式的DFADFA例：构造正规式例：构造正规式(a|b)*(aa|bb)(a|b)*的的DFAvStep2:Step2:使使NFANFA初态和终态都唯一初态和终态都唯一0a|b3a|b12aabb XY0a|ba|b12aabb 33.2.6 3.2.6 构造正规式的构造正规式的DFADFA例：构造正规式例：构造正规式(a|b)*(aa|bb)(a|b)*的的DF

35、AvStep3:Step3:使使NFANFA每条箭弧上或为单个字符每条箭弧上或为单个字符a,a,或为或为X25Y1 6 b ba ab ba a34a ab bb ba a3.2.6 3.2.6 构造正规式的构造正规式的DFADFA例：构造正规式例：构造正规式(a|b)*(aa|bb)(a|b)*的的DFAStep4:Step4:确定可合并状态确定可合并状态X25Y1 6 b ba ab ba a34a ab bb ba aIIaIbX,1,2 X212Y16 b bb b4b b 21a aa a3 1,2,321b bb b4 1,2,31,2,41,2,425Y16 a aa a3a a

36、 1,2,3,5,6,Y1,2,3,5,6,Y21b bb b4 1,2,421a aa a3 1,2,3Y2516 b bb b4b b 1,2,4,5,6,Y1,2,4,5,6,Y25Y16 a aa a3a aa a 1,2,3,5,6,Y2Y16 b bb b4b b 1,2,4,6,Y1,2,4,6,Y2Y16 a aa a3a a 1,2,3,6,Y1,2,3,6,Y25Y16 b bb b4b bb b 1,2,4,5,6,Y2Y16 a aa a3a a 1,2,3,6,Y25Y16 b bb b4b bb b 1,2,4,5,6,Y25Y16 a aa a3a aa a 1,

37、2,3,5,6,Y 1,2,4,6,Y3.2.6 3.2.6 构造正规式的构造正规式的DFADFAIIaIbX,1,21,2,31,2,31,2,41,2,41,2,3,5,6,Y1,2,3,5,6,Y1,2,41,2,31,2,4,5,6,Y1,2,4,5,6,Y1,2,3,5,6,Y 1,2,4,6,Y1,2,4,6,Y1,2,3,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y 1,2,4,5,6,Y1,2,3,5,6,Y 1,2,4,6,YSab0X,1,2011,2,31,2,31,2,30611111121,2,41,2,41,2,42222221,2,3,5,6,

38、Y31,2,3,5,6,Y1,2,3,5,6,Y1,2,3,5,6,Y3333333341,2,4,5,6,Y1,2,4,5,6,Y1,2,4,5,6,Y1,2,4,5,6,Y444444441,2,4,6,Y51,2,4,6,Y1,2,4,6,Y5555551,2,3,6,Y61,2,3,6,Y1,2,3,6,Y66 666Step5:Step5:合并状态合并状态例：构造正规式例：构造正规式(a|b)*(aa|bb)(a|b)*的的DFA3.2.6 3.2.6 构造正规式的构造正规式的DFADFASab011122233334444555666012123124021ab3354464566

39、354b6a021ab3b21a21a4b3b21a21a4b4b6a3a5b3a5b456ba456ba356ab b356a例：构造正规式例：构造正规式(a|b)*(aa|bb)(a|b)*的的DFAvStep6:Step6:构造构造DFADFA021ab4b6a021ab3b21a21a4b3a5b456ba356abX,1,21,2,31,2,41,2,3,5,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,3,6,Y0X,1,211,2,321,2,431,2,3,5,6,Y41,2,4,5,6,Y51,2,4,6,Y61,2,3,6,Y3456例：构造正规式例：构造正规式(a

40、|b)*(aa|bb)(a|b)*的的DFAvStep7:Step7:确定初态和终态确定初态和终态3.2.6 3.2.6 构造正规式的构造正规式的DFADFA总结：总结：NFANFA确定化为确定化为DFADFA使初态和终态均使初态和终态均唯一唯一；使使NFANFA的每个箭弧上或为的每个箭弧上或为单个单个字符，或为字符，或为；NFANFA中，中，=a=a1 1,a,ak k,将将NFANFA确定化：确定化：（1 1）构造一张含有）构造一张含有k+1k+1列的表，置该表首行首列为列的表，置该表首行首列为_Closure(X)_Closure(X)；（2 2）若某一行第一列已确定，则置第）若某一行第

41、一列已确定，则置第i+1i+1列为列为I Iaiai，若该行某列未在该表，若该行某列未在该表第一列出现过，就将其加入到该表第一列最后一行；第一列出现过，就将其加入到该表第一列最后一行；（3 3）重复上述过程，直至出现在第）重复上述过程，直至出现在第i+1i+1列上的所有状态子集均在第一列上列上的所有状态子集均在第一列上出现过；出现过；（4 4）将每个状态子集合并为一个状态，根据得到的状态转换矩阵构造）将每个状态子集合并为一个状态，根据得到的状态转换矩阵构造DFADFA。DFADFA的初态为的初态为首行首列首行首列的状态，终态为那些含有原终态的状态子集。的状态，终态为那些含有原终态的状态子集。与

42、原来给出例题的比较与原来给出例题的比较021ab4b6a021ab3b21a21a4b3a5b456ba356ab34563012baabbaab有四个终态有四个终态只有一个终态只有一个终态1、DFA是否可化简？是否可化简？2、如、如何化简？何化简？3、怎样才是最简、怎样才是最简DFA？例：构造例：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶和偶数个数个1 1所组成串。所组成串。Step1：构造：构造NFA正规式：正规式：(00|11|(01|10)(00|11)*(01|10)*01(00|11|(01|10)(00|11)*(01|10)*0100|11|(0

43、1|10)(00|11)*(01|10)2 01(01|10)(00|11)*(01|10)20011Step2 使每条弧上或为使每条弧上或为，或为单个字符，或为单个字符 01(01|10)(00|11)*(01|10)20011 012(00|11)*3401|1001|10050161例：构造例：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶和偶数个数个1 1所组成串。所组成串。012(00|11)*3401|1001|10050161 01205016130110410017 00|11Step2 使每条弧上或为使每条弧上或为，或为单个字符，或为单个字符例：构

44、造例：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶和偶数个数个1 1所组成串。所组成串。01205016130110410015 00|11 012050161347 0891101011001110121301Step2 使每条弧上或为使每条弧上或为，或为单个字符，或为单个字符Step3 使初态和终态都唯一使初态和终态都唯一 012050161347 0891101011001110121301例：构造例：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶和偶数个数个1 1所组成串。所组成串。Step4 寻找可合并状态寻找可合并状态 01

45、2050161347 0891101011001110121301II0I10,1,21 012 250085,85,8216916,96,9 120581,21,25347 83,4,73,4,706347 93,4,7 126191,25,86,90471001210,1210,121471113111,1311,13047 124,74,7 121011,2 121101,2 147134,710,1211,13Step5 Step5 合并状态合并状态II0I10,1,25,85,86,96,91,21,23,4,73,4,73,4,71,25,86,910,1210,1211,1311

46、,134,74,71,21,24,710,1211,130,1,203,4,7II0I10 05,815,85,81111116,926,96,92222221,231,21,21,21,233333333333,4,743,4,744444410,12510,1210,1255555511,13611,1311,136666664,774,74,7777777例：构造例：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶和偶数个数个1 1所组成串。所组成串。II0I1011122233333444555666777Step6 Step6 构造构造DFADFA12323

47、4134456567357367012012013401010156017010101例：构造例：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶和偶数个数个1 1所组成串。所组成串。Step7 Step7 确定初态和终态：原终态为确定初态和终态：原终态为1 10156010120134010170101010,1,25,86,91,23,4,710,1211,134,70,1,205,816,921,233,4,7410,12511,1364,7703例：构造例：构造DFADFA，使其能接受所有由偶数个，使其能接受所有由偶数个0 0和偶和偶数个数个1 1所组成串。所组成串。