第三章词法分析 (2)PPT讲稿.ppt

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

1、第三章词法分析第1页，共115页，编辑于2022年，星期二概述v本章引入词法分析器（扫描器）的构造原理和实现技术v扫描器的任务2022/9/192v讨论扫描器的设计需求和实现机制v介绍单词的内部表示，引入单词的描述工具正规式v描述识别单词的转换图和有限自动机的概念和应用v先讨论扫描器的手工构造，然后引入自动构造原理第2页，共115页，编辑于2022年，星期二2022/9/193Contents词法分析器的手工构造1正规表达式2有限自动机3词法分析器的自动生成4第3页，共115页，编辑于2022年，星期二编译阶段词法分析2022/9/194第4页，共115页，编辑于2022年，星期二编译阶段词法

2、分析v将源程序分解为单词符号串第5页，共115页，编辑于2022年，星期二2022/9/196词法分析器v词法分析的任务自左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。v词法分析器的构造手工构造自动生成Lex：词法规则（正规式）有限自动机第6页，共115页，编辑于2022年，星期二2022/9/1973.1 对词法分析器的要求功能v词法分析器的功能功能从数据输入到输出的一个变换过程或函数说明该过程（或函数）需要做什么，而非如何做扫描器的输入是代表源程序的字符串输出是单词符号（token）的内部中间表示过程是扫描输入的字符流，按词法规则

3、识别出单词第7页，共115页，编辑于2022年，星期二2022/9/198对词法分析器的要求输出形式v单词符号的种类关键字由语言定义、具有固定含义的标识符如，main,if,while,for等通常不作为程序员自定义的名字使用（保留字，基本字）标识符用于表示各种名字如，变量名、数组名、类名，函数名和过程名等常数具有某种数据类型的不变量常见的类型有整型、实型、布尔型、文字型等如，100、3.14159、TRUE、example运算符，用于表示操作如，+、-、*、/等界符，用于区分各种不同的语法单位如，“,”、“;”、“(”、“)”、“/*”、“*/”等第8页，共115页，编辑于2022年，星期二

4、对词法分析器的要求输出形式v单词符号的输出形式二元式（单词种别，单词符号的属性值）单词种别：通常用整数编码表示，不能唯一确定单词时，需用属性值：通常是指向符号表的指针（入口地址）实现上，如何划分单词种别和编码纯属技术性考虑如关键字、运算符和界符通常作为一符一种处理关键字、运算符和界符由语言定义，个数是固定的种别的整数编码可唯一确定该单词，无须属性值标识符常作为一种来处理，常数则可按类型分种需用属性值来区分不同单词的特征这些特征信息存放于相关的符号表项或常数表项中单词种别：用整数编码2022/9/199第9页，共115页，编辑于2022年，星期二词法分析器的输出示例2022/9/1910v例，C

5、+代码段：while(i=j)i-;将被转换为 while,(,id,=,=,id,),id,-,;,第10页，共115页，编辑于2022年，星期二2022/9/1911词法分析器的组织v将词法分析器作为一个独立阶段任务相对独立、简单，有高效的工具进行处理与编译过程的其它工作分开造就良设计的软件架构结构简洁、清晰、条理化v是否将词法分析器作为独立的一遍？没有必要，而且低效v与语法分析器通信的其他方式最常用的：作为一个子程序，由语法分析器在需要单词符号时调用词法分析器和语法分析器作为两个并发的过程通过pipe通信第11页，共115页，编辑于2022年，星期二词法分析器的组织示例v作为独立阶段（一

6、遍）v作为独立的子程序第12页，共115页，编辑于2022年，星期二3.2 词法分析器的设计问题v语言对程序格式的要求自由格式大部分语言不规定某个单词必须出现在程序行中的什么位置固定格式如早期的FORTRAN语言规定输入行的前6个字符是标号，最后的字符（7280列）是注释，以C开头的是注释行，等等空白（空格和tab）大多数PL，空白是有意义的FORTRAN和Algol60，空白可以加在任何地方提高可读性2022/9/1913第13页，共115页，编辑于2022年，星期二词法分析器的设计问题v缓冲区是编译器中唯一需要处理每个字符的阶段设计不合理会成为最费时和低效的阶段不能从输入文件中逐个字符读入

7、，一次读入大块文本放入一个缓冲区，由缓冲区给词法分析器提供字符词法分析器需要向前扫描时，缓冲区也有用处v关键字保留字：用户不能使用关键字作为标识符PL/l的关键字不是保留字，词法分析器要区分2022/9/1914第14页，共115页，编辑于2022年，星期二词法分析器的设计错误处理v词法分析中遇到了错误怎么处理？应急式（panic）跳过字符，直到发现一个结构良好的单词符号替换替换一个不正确的字符删除删除一个不正确的字符插入插入一个缺失的字符调换调换两个字符的位置2022/9/1915第15页，共115页，编辑于2022年，星期二3.2.1 输入、预处理v输入缓冲区为了提高效率，扫描器并非直接逐

8、个字符地读源文件每次从源文件中读出一定长度的字符串将输入的字符串放入一个输入缓冲区中v预处理对多数PL，用于正文编辑的字符一般没有实际意义如，空格、跳格、回车和换行符只是在文字常数中有意义注解的出现对程序的功能也无任何意义为了方便识别工作，编辑性字符和注解应事先删除有些PL将一个或相继多个空格用作单词之间的界符此时应事先将相继多个空格合并为一个空格预处理即在识别开始前，删去输入缓冲区中的无用字符2022/9/1916第16页，共115页，编辑于2022年，星期二输入、预处理v预处理子程序可设计一个由扫描器调用的子程序当调用时，处理出长度为N的字符串，并装入扫描缓冲区使识别工作可在此缓冲区上直接

9、进行v扫描缓冲区的结构通常采用一个长度为2N的双半区（双缓冲区）设计扫描器需维护两个指示器一个指向正在扫描单词的首字符，一个向前搜索其终点若单词被半区边界截断，则再装入N个字符到另半区单词的长度N，故语言通常限制标识符和常数的长度2022/9/1917第17页，共115页，编辑于2022年，星期二扫描缓冲区的结构2022/9/1918第18页，共115页，编辑于2022年，星期二词法分析器的结构2022/9/1919预处理子程序扫描缓冲区扫描器输入缓冲区输入列表单词符号第19页，共115页，编辑于2022年，星期二2022/9/1920 3.2.2 单词符号的识别：超前搜索v识别单词通常需要超

10、前搜索为了识别当前单词，需要扫描后继的若干个字符v关键字的识别如FORTRAN，关键字和用户字无区别；单词之间无界符1DO99K=1,10循环语句：DO关键字99结束行标号3DO99K=1.10赋值语句：DO99K为用户定义的变量名必须超前搜索至第一个界符,或.才能确定单词的种别第20页，共115页，编辑于2022年，星期二单词符号的识别：超前搜索v标识符的识别一般为字母开头的字母/数字序列，读到其它符号时可识别v常数的识别各种类型的常数一般容易识别，但有些语言需超前搜索如FORTRAN，5.EQ.M和5.E08的前缀相同v算符和界符的识别有些语言需要超前搜索如C+，Java中，+，+=，-，

11、=等2022/9/1921第21页，共115页，编辑于2022年，星期二2022/9/19223.2.3 状态转换图v如何利用转换图手工（非形式）实现扫描器转换图的作用：词法规则转换图扫描器词法规则的一种图形描述工具描述扫描器动作如，标识符可非形式地描述为字母开头的字母/数字序列其转换图为（其中0表示初始状态，双圈表示终止状态）01字母2其它字母或数字*第22页，共115页，编辑于2022年，星期二状态转换图v转换图是一张有限方向图结点：状态箭弧标记：射出结点状态下可能出现的输入字符或字符类初态和终态2022/9/192301字母2其它字母或数字*转换状态初态终态输入字符第23页，共115页，

12、编辑于2022年，星期二状态转换图v扫描器可利用转换图识别（接受）一定的字符串（单词）状态S0对应于单词识别的开始位置在Si，若存在有向边(Si，Sj),其上标记与输入字符匹配则状态转换到Sj，并将搜索指示器+1，否则失败在终止状态，表示识别出一个单词在终止状态,若多读了一个字符，应退给输入串，标记为*2022/9/1924第24页，共115页，编辑于2022年，星期二状态转换图示例2022/9/1925第25页，共115页，编辑于2022年，星期二2022/9/1926状态转换图作用v一个状态转换图可以用于识别（或接受）一定的字符串v大多数程序设计语言的单词符号都可以用转换图予以识别v状态转

13、换图是设计词法分析器的有效工具给出识别单词符号的状态转换图实现状态转换图每个状态结点对应一段程序不含回路的分叉结点对应switch或if-else语句含回路的状态结点对应while和if构成的程序段第26页，共115页，编辑于2022年，星期二状态转换图实现示例2022/9/1927第27页，共115页，编辑于2022年，星期二状态转换图实现代码 1第28页，共115页，编辑于2022年，星期二状态转换图实现代码 2第29页，共115页，编辑于2022年，星期二状态转换图实现代码 3第30页，共115页，编辑于2022年，星期二状态转换图综合应用v构造识别一个简单语言所有单词符号的转换图202

14、2/9/1931第31页，共115页，编辑于2022年，星期二状态转换图综合应用v词法处理约定1.除标识符，常数外，均为一符一种2.关键字均为保留字，不可用作用户字3.设保留字表，识别出标识符时，查表确定是否为关键字4.相邻单词之间至少存在一个界符、算符或空格按此约定，无须使用超前搜索，也无须设关键字转换图第32页，共115页，编辑于2022年，星期二状态转换图综合应用v设计思想第33页，共115页，编辑于2022年，星期二状态转换图综合应用第34页，共115页，编辑于2022年，星期二状态转换图综合应用v变量与过程1.ch，字符变量，存放最新读入的字符2.strToken，字符数组，存放组成

15、单词的字符串3.GetChar(),读入当前字符，搜索指示器指向下一输入字符4.GetBC(),若ch=,则反复调用GetChar()直至ch5.Concat(),strToken:=strToken|ch6.isletter/isDigit,若ch=letter/digit,则返回true,否false7.intReserve(),若strToken=保留字,则返回编码，否08.Retract(),搜索指示器回调一个字符，ch:=9.intInsertId(),将strToken插入符号表，返回符号表指针10.intInsertConst(),将strToken插入常数表，返回常数表指针第3

16、5页，共115页，编辑于2022年，星期二Nextv手工构造词法分析器非形式的词法规则转换图扫描器v接下来讨论如何形式化上述过程其目的在于能够自动化（机械化）该过程，即词法的形式规则 形式状态转换图 扫描器其中：描述词法的形式规则是 正规式 正规文法 描述转换图的形式工具是 有限自动机形式化也使得可以用数学方法保证结果的正确性自动自动第36页，共115页，编辑于2022年，星期二2022/9/19373.3 正规表达式与有限自动机正规式与正规集1DFA和NFA2正规文法3等价性证明4第37页，共115页，编辑于2022年，星期二3.3.1 正规式与正规集v正规集已知任何形式语言均为*的一个子集

17、程序语言的单词一般均属于*的一个特殊子集正规集已知正规集上的字符串（字）可以使用正规文法描述正规式是一种比文法更为简单、高效的方法2022/9/1938第38页，共115页，编辑于2022年，星期二2022/9/1939正规式与正规集定义v设字母表，正规式与其所表示的正规集可递归定义为1.和都是上的正规式，它们所表示的正规集分别为和;2.任何a，a都是上的一个正规式，它所表示的正规集为a；3.假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么(U|V)、(UV)和(U)*也都是正规式，它们所表示的正规集分别是L(U)L(V)、L(U)L(V)（连接积）和(L(U)*（

18、闭包）。仅由有限次使用上述三个步骤而得到的表达式才是上的正规式仅由这些正规式所表示的字集才是上的正规集v正规式运算符（优先级从高到低）*（闭包）（连接）|（或）第39页，共115页，编辑于2022年，星期二正规式与正规集例v例设字母表=a，b，部分上的正规式和正规集如下：正规式正规集aaa|ba，babab(a|b)(a|b)aa，ab，ba，bba*，a，aa，任意个a的串ba*b(a)*=b,ba,baa,a(a|b)*a(a,b)*=a*,上所有以a开头的字(a|b)*(aa|bb)(a|b)*aa,bb*,上所有包含aa或bb的字2022/9/1940第40页，共115页，编辑于202

19、2年，星期二正规式与正规集例v例令=A,B,0,1(A|B)(A|B|0|1)*上标识符的全体(0|1)(0|1)*上数的全体v例令r=letter(letter|digit)*，则其正规式表示的语言L(r)=L(letter)(L(letter)L(digit)*=A，Z，a，z(A，Z，a，z，0，9)*v例令L(x)=a，b,L(y)=c，d且r1=x|y，r2=y|x，则L(r1)=a，b，c，dL(r2)=a，b，c，dL(r1)=L(r2)第41页，共115页，编辑于2022年，星期二正规式与正规集等价性v正规式的等价性若两个正规式所表示的正规集相同，则认为两者等价两个等价的正规式

20、u和v记为u=v如，b(ab)*=(ba)*b,(a|b)*=(a*b*)*v等价性证明若要证明u=v，1.须证明L(u)=L(v)集合相等证明方法2.使用正规式的代数性质2022/9/1942第42页，共115页，编辑于2022年，星期二2022/9/1943正规式与正规集正规式的代数性质连接对|是可分配的 是连接的恒等元素性性 质质描描 述述A|B=B|A|是可交换的A|(B|C)=(A|B)|C|是可结合的A(BC)=(AB)C连接是可结合的A(B|C)=AB|AC(A|B)C=AC|BC连接对|是可分配的 A=AA =A 是连接的恒等元素 A*=(A|)*和之间的关系A*=A*幂的等价

21、性第43页，共115页，编辑于2022年，星期二正规式与正规集等价性证明v例，证明b(ab)*=(ba)*bb(ab)*=b(ab)0|(ab)1|(ab)2|)=b|b(ab)1|b(ab)2|/分配律=b|(ba)1b|(ba)2b|/结合律=(|(ba)1|(ba)2|)b/分配律=(ba)*b2022/9/1944第44页，共115页，编辑于2022年，星期二v例，证明(A*)*=A*,其中A为任意正规需证明L(A*)*)=L(A*)/注：L(A*)*)=(L(A*)*首先证明L(A*)*)L(A*)显然有L(A*)*)=L(A*)0L(A*)1L(A*)2L(A*)其次证明L(A*)

22、*)L(A*)设xL(A*)*)=(L(A*)*若x=,则xL(A*)若x,则x(L(A*)k令x=x1x2xk有xiL(A*)=(L(A)*于是有xi(L(A)mi（mi0,i=1,2,k)则x=x1x2xk(L(A)m1(L(A)m2(L(A)mk=(L(A)m1+m2+mk令m=m1+m2+mk,有x(L(A)m(L(A)*故有L(A*)*)L(A*)第45页，共115页，编辑于2022年，星期二2022/9/1946 3.3.2 确定有限自动机（DFA）v一个DFAM是一个五元式M=(S,s0,F)，其中1.S=S0,S1,Sn为有限集，SiS为状态2.为有限字母表，a为输入字符3.:

23、SS的单值（部分）映射（状态转换函数）(s,a)=s意为：现行状态为s，输入字符为a，则转换到后继状态s从转换图来看，相当于4.S0S为唯一的初态5.FS为终态集（可空）ssa第46页，共115页，编辑于2022年，星期二2022/9/1947确定有限自动机DFA的表示v五元式M=(0,1,2,3,a,b,0,3)，其中为(0,a)=1(0,b)=2(1,a)=3(1,b)=2(2,a)=1(2,b)=3(3,a)=3(3,b)=3第47页，共115页，编辑于2022年，星期二2022/9/1948确定有限自动机DFA的表示v状态转换矩阵行：状态列：输入字符矩阵元素：(s,a)的值01a3b2

24、aaa,bbbv状态转换图第48页，共115页，编辑于2022年，星期二DFA的表示DFAM=(0,1,2,3,a,b,0,3)映射状态矩阵 状态转换图2022/9/1949第49页，共115页，编辑于2022年，星期二2022/9/1950确定有限自动机DFA M识别的字v对于*上的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于，则称可为DFAM所识别（读出或接受）。v若M的初态结点同时又是终态结点，则空字可为M所识别。vDFAM所识别的字的全体记为L(M)。第50页，共115页，编辑于2022年，星期二DFA示例v是DFA吗？接受什么样的字符串？

25、2022/9/1951v是DFA吗？接受什么样的字符串？第51页，共115页，编辑于2022年，星期二DFA示例v自然数v带符号的自然数第52页，共115页，编辑于2022年，星期二DFA示例v带符号的实数v浮点数第53页，共115页，编辑于2022年，星期二DFA示例vC语言注释第54页，共115页，编辑于2022年，星期二非确定性vDFA的确定性映射:SS是单值函数任何状态sS和输入符号a,(s,a)唯一地确定了下一个状态。v例，构造识别:=,=,=的DFA构造识别三个运算符的DFA只能用唯一的初始状态将它们连接在一起2022/9/1955第55页，共115页，编辑于2022年，星期二非确

26、定性2022/9/1956第56页，共115页，编辑于2022年，星期二非确定性v如果有两个字符串以相同字符开始呢？下面的转换图是DFA吗？2022/9/1957第57页，共115页，编辑于2022年，星期二非确定性v可以用增加新状态的方法解决相同符号的冲突这个是DFA吗？与上图比较有什么优劣？2022/9/1958第58页，共115页，编辑于2022年，星期二2022/9/19593.3.3 非确定有限自动机（NFA）v非确定的有限自动机（NFA）允许是一个多值函数允许有标记的转换：表示没有输入字符直接转换状态第59页，共115页，编辑于2022年，星期二2022/9/1960NFA定义v一

27、个NFAM是一个五元式M=(S,S0,F)，其中S是一个有限状态集是一个有穷字母表，是输入字符集合是一个从S*到S的子集的映射，即:S*2SS0S，是非空初态集F S，是一个终态集（可空）第60页，共115页，编辑于2022年，星期二NFA示例v:S*2S的含义其含义为(s,)=s|sS注意：*(*=+a*与a不加区分，有|a|=12S为S的幂集，即由S的所有子集构成的集合如，S=0,1,2S=,0,1,0,1例，NFAM=(0,1,2,a,b,0,1,2)2022/9/1961第61页，共115页，编辑于2022年，星期二2022/9/1962NFA和状态转换图v含有m个状态和n个输入字符的

28、NFA可以表示为如下的状态转换图：该图有m个状态结点，每个结点可以射出若干条箭弧与别的结点相接，每条弧用*中的一个字作标记（输入字，可以是），整张图至少含有一个初态结点以及若干个终态结点。aabbb3210第62页，共115页，编辑于2022年，星期二NFA示例2022/9/1963第63页，共115页，编辑于2022年，星期二2022/9/1964NFA识别的字v对于*中的任何一个字，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于，则称可为NFAM所识别（读出或接受）。v若M的某些初态结点同时又是终态结点，或者存在一条从某个初态结点到某个终态结点的

29、通路，则空字可为M所接受。第64页，共115页，编辑于2022年，星期二DFA和NFA的编程实现v方法一：硬编码类似于转换图的实现可以用固定代码模式2022/9/1965第65页，共115页，编辑于2022年，星期二DFA和NFA的实现v方法二：状态转换表驱动的实现将状态转移用表的方式表示，如下3表示该状态不读取输入字符空白表示错误状态接受状态用标记2022/9/1966第66页，共115页，编辑于2022年，星期二DFA和NFA的实现v给定如上的转换表，对任意DFA我们可以编写下面的程序进行词法分析2022/9/1967第67页，共115页，编辑于2022年，星期二DFA和NFA的实现例C注

30、释2022/9/1968第68页，共115页，编辑于2022年，星期二DFA和NFA的实现例C注释第69页，共115页，编辑于2022年，星期二DFA和NFA的实现例C注释第70页，共115页，编辑于2022年，星期二DFA和NFA的实现例C注释第71页，共115页，编辑于2022年，星期二DFA和NFA的实现例C注释第72页，共115页，编辑于2022年，星期二正规式NFADFA词法分析器v我们的思路1.用正规式（RE）描述词法规则2.将正规式转换为NFA3.将NFA转换为DFA4.根据DFA构造词法分析程序v要考虑的问题这些表示方式是否等价？这一系列转换是否能够自动进行（有算法）？v下一步

31、：等价性证明和构造（转换）算法第73页，共115页，编辑于2022年，星期二正规式转换为NFAv每条有向边上标记为或单个字符2022/9/1974第74页，共115页，编辑于2022年，星期二NFA转换为正规式2022/9/1975第75页，共115页，编辑于2022年，星期二NFA和正规式的等价性v上述方法说明NFA和正规式是等价的每个NFAM所识别的字的全体L(M)是上的正规集每个上的正规集L(R)均可被一个NFAM所识别L(M)=L(R),称为两者是等价的原则上，若程序语言的词法用正规式描述，则可自动构造一个NFAM来识别该语言的单词NFA的非确定性使之不容易用于实现词法分析器若能消除N

32、FA的非确定性，将其转换为DFA，则容易实现2022/9/1976第76页，共115页，编辑于2022年，星期二NFA和DFA的等价性v有限自动机的等价性FAM，FAM，若L(M)=L(M)，则称两者是等价的DFA与NFA的等价性是自动机理论的一个重要定理vDFA和NFA是等价的1.DFA是NFA的特例即：DFAM，NFAM，使L(M)=L(M)DFA:SSNFA:S*2S2.需证明，NFAM存在一个DFAM使L(M)=L(M)2022/9/1977*,2S S第77页，共115页，编辑于2022年，星期二NFA转换为DFAvNFAM，DFAM，使L(M)=L(M)设NFAM=(S,S0,F)

33、将NFAM改造为NFAM引入唯一的新初态结点X和新终态结点YX到S0中所有结点均用边连接F中所有结点到Y也均用边连接反复使用图示的替换直至每条有向边上标记为或单个字符显然，L(M)=L(M)2022/9/1978第78页，共115页，编辑于2022年，星期二NFA转换为DFAv基本思想是采用一种“子集构造”算法来确定化构造一个DFAM，使其每个状态对应于NFAM的状态集使得在DFA读入a1a2an时，所处的状态对应于NFA所能到达的状态集如NFA读入a1a2an到达状态中的任意一个，则DFA到达状态集2,3,4，即状态观察NFAM：可能有边，也可能有相同标记的边要构造DFAM，必须合并这两种边

34、到达的状态2022/9/1979第79页，共115页，编辑于2022年，星期二NFA转换为DFAv子集构造方法设IS，定义_closure(I)1.qI,q_closure(I)2.qI,从q出发经任意条边可达的q_closure(I)即_closure(I)=Iq|qI旨在合并与状态集I相关的边可达状态设IS，a,定义Ia=_closure(J)qI，从q出发经a边可达的qJ2022/9/1980第80页，共115页，编辑于2022年，星期二NFA转换为DFAv确定化方法1.假定=a1,a2,ak,我们构造一张表S，S有k+1列，依次标记为I,Ia1,Ia2,Iak2.置该表的首行首列为_c

35、losure(X),X为NFAM的初态3.如果确定了第m（m1,2,）行中第一列的I，则计算Iax（x1,2,k），并填入m行中对应的列即Sm，Iax中4.检查m行上的每个状态子集Iax（x1,2,k），如果Iax，并且它还没有在表S的第一列中出现，则将其填入到空行的第一列5.重复3、4，直至所有Iax（x1,2,k）都在第一列上出现该过程一定在有限步内终止，因为M的子集数=2|S|2022/9/1981第81页，共115页，编辑于2022年，星期二NFA转换为DFAv确定化方法（示例）假设=a,b,则定义一张表S(I,Ia,Ib)其中，第i行的表元素分别为Si,I,Si,Ia,Si,Ib1.

36、置S1,I=_closure(X),X为NFAM的初态2.若Si,I,则计算Ia,Ib，填入Si,Ia,Si,Ib3.检查第i行的元素，若Si,Ia或Si,Ib还没有在第一列出现过则将Si,Ia或Si,Ib填入Sk+,I,（k表示第一个空行）；i+；返回步骤2否则算法终止2022/9/1982第82页，共115页，编辑于2022年，星期二v例(a|b)*(aa|bb)(a|b)*2022/9/1983ISIaaIbbX,5,105,3,115,4,125,3,115,3,1,2,6,Y35,4,125,4,125,3,115,4,1,2,6,Y55,3,1,2,6,Y35,3,1,2,6,Y3

37、5,4,1,6,Y45,4,1,6,Y45,3,1,6,Y65,4,1,2,6,Y55,4,1,2,6,Y55,3,1,6,Y65,4,1,2,6,Y55,3,1,6,Y65,3,1,2,6,Y35,4,1,6,Y4第83页，共115页，编辑于2022年，星期二v构造DFAM所构造的S表指定了DFAM的状态转换矩阵S表中的每个状态子集为DFAM的一个状态S表中的首行首列为初态S表中含有终态的状态子集为DFAM的终态第84页，共115页，编辑于2022年，星期二2022/9/19853.3.5 正规式与有限自动机的等价性v证明一FAM，正规式r，使得L(r)=L(M)第85页，共115页，编辑于

38、2022年，星期二正规式与有限自动机的等价性v证明二正规式r,FAM，使得L(M)=L(r)用关于正规式r中运算符个数归纳证明1.归纳基础：r中运算符数目为0即r=或r=或r=a(a)，则显然，三个NFA分别接受的正规集为,和a2.归纳假设：设r,如果r中的运算符数目为k，则存在一个FAM，使得L(M)=L(r)3.当r中有k+1个运算符时，r有三种可能：r=r1|r2,r=r1r2或r=r1*；r1和r2中的运算符数目=k.根据归纳假设，对r1和r2存在FAM1和M2使得L(M1)=L(r1)L(M2)=L(r2)2022/9/1986第86页，共115页，编辑于2022年，星期二则对于r=

39、r1|r2,构造M为其中，为M引入新的初态结点q0和终态结点f0，并从q0引出转换至q1和q2，从f1和f2引出转换至f0显然，有L(M)=L(M1)L(M2)=L(r1)L(r2)=L(r)对于r=r1r2,构造M为其中，q1为新的初态，f2为终态，并从f1引出转换至q2显然，有L(M)=L(M1)L(M2)=L(r1)L(r2)=L(r)对于r=r1*,构造M为显然，有L(M)=L(M1)*=L(r1)*=L(r)2022/9/1987第87页，共115页，编辑于2022年，星期二正规式与有限自动机的等价性v基本思想（Thompson构造算法）对正规式的各个部分构造NFA用弧连接起各个NF

40、A，构成完整的自动机2022/9/1988接受正规式a的NFA接受正规式的NFA假设接受正规式r的NFA如下接受正规式rs的NFA接受正规式r|s的NFA接受正规式r*的NFA第88页，共115页，编辑于2022年，星期二正规式与有限自动机的等价性例子v设正规式为r1=1*，r2=01*，r3=01*|12022/9/1989第89页，共115页，编辑于2022年，星期二Thompson构造算法例子v正规式ab|a的NFA2022/9/1990第90页，共115页，编辑于2022年，星期二Thompson构造算法例子v正规式letter(letter|digit)*的NFA第91页，共115页

41、，编辑于2022年，星期二正规文法与有限自动机的等价性v正规文法与正规式程序语言通常采用正规文法定义它的词法规则正规式是自动构造词法分析器的有效工具v正规（3型）文法G=(VT,VN,S,P)P:AB,A,A,BVN,VT*（右线性文法）P:AB,A,A,BVN,VT*（左线性文法）v可等价变换为p：AaB，AaA,BVN,aVT（右线性文法）p：ABa，AaA,BVN,aVT（左线性文法）v方便起见，右和左线性文法为分别记为GR和GL第92页，共115页，编辑于2022年，星期二正规文法与有限自动机的等价性v等价性对正规文法G和FAM，若L(G)=L(M),则称为G和M等价1.GR或GL，F

42、AM，L(GR)=L(M)或L(GL)=L(M)2.FAM，GR或GL，L(M)=L(GR)=L(GL)v等价性证明对右线性文法GR构造NFAM，并证明L(M)=L(GR)对左线性文法GL构造NFAM，并证明L(M)=L(GL)对DFAM构造右线性文法GR，并证明L(GR)=L(M)对DFAM构造左线性文法GL，并证明L(GL)=L(M)2022/9/1993第93页，共115页，编辑于2022年，星期二正规文法与有限自动机的等价性v等价性证明（从正规文法构造FA）基本思想设w=a1a2ak,分别考虑GR和GL的最左推导GR:Sa1B1a1a2B2a1a2ak-1Bk-1a1a2akGL:SB

43、k-1akBk-2ak-1akB1a2aka1a2ak非终结符的作用是记住字符个数，将其作为状态2022/9/1994第94页，共115页，编辑于2022年，星期二正规文法与有限自动机的等价性v从右线性文法构造FA设GR=(VT,VN,S,P),其中p：AaB，Aa令NFAM=(VNF,VT,S,F)，其中，1.若AVN,且aVT,有Aa,则令(A,a)=F2.若AVN,且aVT,有AaA1|aA2|aAk,则令(A,a)=A1,A2,Ak容易证明，该NFAM所识别的语言L(M)=L(GR)2022/9/1995第95页，共115页，编辑于2022年，星期二正规文法与有限自动机的等价性v从左线

44、性文法构造FA设GL=(VT,VN,S,P),其中P:ABa，Aa令NFAM=(VNq0,VT,q0,S)，其中，1.若AVN,且aVT,使Aa,则令(q0,a)=A2.若AVN,且aVT,使A1Aa,A2Aa,AkAa则令(A,a)=A1,A2,Ak2022/9/1996第96页，共115页，编辑于2022年，星期二正规文法与有限自动机的等价性v从DFA中构造GR设DFAM=(S,S0,F),若S0F，则令GR=(,S,S0,P),其中P为若则AaB或Aa|aB若S0F,则因(S0,)=S0,故L(M),但L(GR)引入S0代替S0作为新的开始符号，并增加P：S0S0|容易证明，L(GR)=

45、L(M)v从DFA中构造GL可用类似的方法，但需逆向构造；若BAa若Aa|S0a2022/9/1997第97页，共115页，编辑于2022年，星期二v例3.4DFAMGRNFAMGL1.设DFAM=(A,B,C,D,0,1,A,B)使用FA到正规式的算法可证明L(M)=0(10)*GR=(0,1,A,B,C,D,A,P,其中P为A0|0B|1DB0D|1CC0|0B|1DD0D|1D(D为无用产生式）2.从GR中构造NFAMM=(A,B,C,D,F,0,1,A,F)2022/9/1998第98页，共115页，编辑于2022年，星期二3.从NFAM构造GL将F作为开始符号，从终态F出发逆向构造F

46、0|A0|C0CB1B0|A0|C0D1|A1|C1|D0|D1|B0因没有有向边射入A，所以没有有关A的产生式删除无用候选式后GL=(0,1,F,B,C,D,F,P)F0|C0CB1B0|C0D1|C1|D0|D1|B0第99页，共115页，编辑于2022年，星期二2022/9/19100等价性的结论v正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。RG第100页，共115页，编辑于2022年，星期二2022/9/19101DFA的化简vDFAM的化简化简：寻找DFAM，使L(M)=L(M),且|SM|SM|最小化：寻找具有最少状态数的M，使L(M)=L(M

47、)v等价状态和可区别的状态M中的不同状态s和t是等价的如果从状态s出发能读出某个字w而停于终态，那么同样从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的w而停于终态。第101页，共115页，编辑于2022年，星期二2022/9/19102DFA的化简v状态的等价关系()设s,tSM,st,定义st,若w=a1a2ak*,有v状态的可区分关系s,tSM,st,若s，t不等价，则s，t是可区分的据关系，对SM可进行等价划分SM=S1S2Sn,SiSj=,|Si|1容易看出,s,tSi,st,而sSi,tSj,s与t是可区分的等价划分是最大划分

48、，即这样划分n为最小每个等价集中元素可读出相同的w而终止，故可合并为一个状态v最小化算法:从 SM中寻找 S1,S2,Sn,使得SiSj=,s,t Si,s t第102页，共115页，编辑于2022年，星期二DFA的化简最小化算法1.基础，令划分=I1,I2，其中I1=所有非终态结点s，I2=所有终态结点f显然，sI1,fI2,s与f可区分，因f可识别字2.设k=I1,I2,Im,且两两可区分设Ii=s1,s2,sk，其中sj为状态结点若a,使得Iai(Ii中元素经a边到达的状态)不全包含在某个Ij中，则将Ii进一步划分为两个集合Ii1=s|sIi,且s经a边可到达IjIi2=Ii-Ii120

49、22/9/19103第103页，共115页，编辑于2022年，星期二DFA的化简最小化算法3.重复2，直至不可继续划分为止4.构造最小DFAM=(SM,，,s0,F设n=I1,I2,In为等价划分令SM=n,其中每个Ii作为M的状态si设Ii=s1,s2,sk,让原M中导入s1,s2,sk边均导入Ii让原M中导出s1,s2,sk边均从Ii导出令M的初态s0=Ij,Ij包含原M中的初态s0令M的终态集F=Ij1,Ij2,Ijk,Ijm包含原M中的终态2022/9/19104第104页，共115页，编辑于2022年，星期二v例3.61=0,1,2,3,4,5,63,4,5,6a3,4,5,6,3,

50、4,5,6b3,4,5,6不可拆分0,1,2a=1,3,拆分为1,0,22=1,0,2,3,4,5,60,2b=2,5,拆分为0,23=00,11,22,3,4,5,63令SM=0,1,2,3,s0=0,F=32022/9/19105第105页，共115页，编辑于2022年，星期二例题正规式到DFA的转换v例：构造识别正规式(a|b)*abb的最小DFA解答1.给出识别该正规集的NFA2.NFA确定化3.DFA最小化第106页，共115页，编辑于2022年，星期二例题解答2022/9/19107解：（1）根据正规式，得到NFA如右图（2）确定化IIaIb11,211,21,21,31,31,2