第三章-词法分析.pptx

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

1、2023/3/201Contents词法分析器的手工构造1正规表达式2有限自动机3词法分析器的自动生成4第1页/共114页编译阶段词法分析2023/3/202第2页/共114页编译阶段词法分析将源程序分解为单词符号串第3页/共114页2023/3/204词法分析器词法分析的任务自左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。词法分析器的构造手工构造自动生成Lex：词法规则（正规式）有限自动机第4页/共114页2023/3/2053.1 对词法分析器的要求功能词法分析器的功能功能从数据输入到输出的一个变换过程或函数说明该过程（或函数）需

2、要做什么，而非如何做扫描器的输入是代表源程序的字符串输出是单词符号（token）的内部中间表示过程是扫描输入的字符流，按词法规则识别出单词第5页/共114页2023/3/206对词法分析器的要求输出形式单词符号的种类关键字由语言定义、具有固定含义的标识符如，main,if,while,for等通常不作为程序员自定义的名字使用（保留字，基本字）标识符用于表示各种名字如，变量名、数组名、类名，函数名和过程名等常数具有某种数据类型的不变量常见的类型有整型、实型、布尔型、文字型等如，100、3.14159、TRUE、example运算符，用于表示操作如，+、-、*、/等界符，用于区分各种不同的语法单位

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

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

5、0页/共114页3.2 词法分析器的设计问题语言对程序格式的要求自由格式大部分语言不规定某个单词必须出现在程序行中的什么位置固定格式如早期的FORTRAN语言规定输入行的前6个字符是标号，最后的字符（7280列）是注释，以C开头的是注释行，等等空白（空格和tab）大多数PL，空白是有意义的FORTRAN和Algol60，空白可以加在任何地方提高可读性2023/3/2011第11页/共114页词法分析器的设计问题缓冲区是编译器中唯一需要处理每个字符的阶段设计不合理会成为最费时和低效的阶段不能从输入文件中逐个字符读入，一次读入大块文本放入一个缓冲区，由缓冲区给词法分析器提供字符词法分析器需要向前扫

6、描时，缓冲区也有用处关键字保留字：用户不能使用关键字作为标识符PL/l的关键字不是保留字，词法分析器要区分2023/3/2012第12页/共114页词法分析器的设计错误处理词法分析中遇到了错误怎么处理？应急式（panic）跳过字符，直到发现一个结构良好的单词符号替换替换一个不正确的字符删除删除一个不正确的字符插入插入一个缺失的字符调换调换两个字符的位置2023/3/2013第13页/共114页输入、预处理输入缓冲区为了提高效率，扫描器并非直接逐个字符地读源文件每次从源文件中读出一定长度的字符串将输入的字符串放入一个输入缓冲区中预处理对多数PL，用于正文编辑的字符一般没有实际意义如，空格、跳格、

7、回车和换行符只是在文字常数中有意义注解的出现对程序的功能也无任何意义为了方便识别工作，编辑性字符和注解应事先删除有些PL将一个或相继多个空格用作单词之间的界符此时应事先将相继多个空格合并为一个空格预处理即在识别开始前，删去输入缓冲区中的无用字符2023/3/2014第14页/共114页输入、预处理预处理子程序可设计一个由扫描器调用的子程序当调用时，处理出长度为N的字符串，并装入扫描缓冲区使识别工作可在此缓冲区上直接进行扫描缓冲区的结构通常采用一个长度为2N的双半区（双缓冲区）设计扫描器需维护两个指示器一个指向正在扫描单词的首字符，一个向前搜索其终点若单词被半区边界截断，则再装入N个字符到另半区

8、单词的长度N，故语言通常限制标识符和常数的长度2023/3/2015第15页/共114页扫描缓冲区的结构2023/3/2016第16页/共114页词法分析器的结构2023/3/2017预处理子程序扫描缓冲区扫描器输入缓冲区输入列表单词符号第17页/共114页2023/3/2018 单词符号的识别：超前搜索识别单词通常需要超前搜索为了识别当前单词，需要扫描后继的若干个字符关键字的识别如FORTRAN，关键字和用户字无区别；单词之间无界符1DO99K=1,10循环语句：DO关键字99结束行标号3DO99K=1.10赋值语句：DO99K为用户定义的变量名必须超前搜索至第一个界符,或.才能确定单词的种

9、别第18页/共114页单词符号的识别：超前搜索标识符的识别一般为字母开头的字母/数字序列，读到其它符号时可识别常数的识别各种类型的常数一般容易识别，但有些语言需超前搜索如FORTRAN，5.EQ.M和5.E08的前缀相同算符和界符的识别有些语言需要超前搜索如C+，Java中，+，+=，-，=等2023/3/2019第19页/共114页2023/3/2020状态转换图如何利用转换图手工（非形式）实现扫描器转换图的作用：词法规则转换图扫描器词法规则的一种图形描述工具描述扫描器动作如，标识符可非形式地描述为字母开头的字母/数字序列其转换图为（其中0表示初始状态，双圈表示终止状态）01字母2其它字母或

10、数字*第20页/共114页状态转换图转换图是一张有限方向图结点：状态箭弧标记：射出结点状态下可能出现的输入字符或字符类初态和终态2023/3/202101字母2其它字母或数字*转换状态初态终态输入字符第21页/共114页状态转换图扫描器可利用转换图识别（接受）一定的字符串（单词）状态S0对应于单词识别的开始位置在Si，若存在有向边(Si，Sj),其上标记与输入字符匹配则状态转换到Sj，并将搜索指示器+1，否则失败在终止状态，表示识别出一个单词在终止状态,若多读了一个字符，应退给输入串，标记为*2023/3/2022第22页/共114页状态转换图示例2023/3/2023第23页/共114页20

11、23/3/2024状态转换图作用一个状态转换图可以用于识别（或接受）一定的字符串大多数程序设计语言的单词符号都可以用转换图予以识别状态转换图是设计词法分析器的有效工具给出识别单词符号的状态转换图实现状态转换图每个状态结点对应一段程序不含回路的分叉结点对应switch或if-else语句含回路的状态结点对应while和if构成的程序段第24页/共114页状态转换图实现示例2023/3/2025第25页/共114页状态转换图实现代码 1第26页/共114页状态转换图实现代码 2第27页/共114页状态转换图实现代码 3第28页/共114页状态转换图综合应用构造识别一个简单语言所有单词符号的转换图2

12、023/3/2029第29页/共114页状态转换图综合应用词法处理约定1.除标识符，常数外，均为一符一种2.关键字均为保留字，不可用作用户字3.设保留字表，识别出标识符时，查表确定是否为关键字4.相邻单词之间至少存在一个界符、算符或空格按此约定，无须使用超前搜索，也无须设关键字转换图第30页/共114页状态转换图综合应用设计思想第31页/共114页状态转换图综合应用第32页/共114页状态转换图综合应用变量与过程1.ch，字符变量，存放最新读入的字符2.strToken，字符数组，存放组成单词的字符串3.GetChar(),读入当前字符，搜索指示器指向下一输入字符4.GetBC(),若ch=,

13、则反复调用GetChar()直至ch5.Concat(),strToken:=strToken|ch6.isletter/isDigit,若ch=letter/digit,则返回true,否false7.intReserve(),若strToken=保留字,则返回编码，否08.Retract(),搜索指示器回调一个字符，ch:=9.intInsertId(),将strToken插入符号表，返回符号表指针10.intInsertConst(),将strToken插入常数表，返回常数表指针第33页/共114页Next手工构造词法分析器非形式的词法规则转换图扫描器接下来讨论如何形式化上述过程其目的在

14、于能够自动化（机械化）该过程，即词法的形式规则 形式状态转换图 扫描器其中：描述词法的形式规则是 正规式 正规文法 描述转换图的形式工具是 有限自动机形式化也使得可以用数学方法保证结果的正确性自动自动第34页/共114页2023/3/20353.3 正规表达式与有限自动机正规式与正规集1DFA和NFA2正规文法3等价性证明4第35页/共114页正规式与正规集正规集已知任何形式语言均为*的一个子集程序语言的单词一般均属于*的一个特殊子集正规集已知正规集上的字符串（字）可以使用正规文法描述正规式是一种比文法更为简单、高效的方法2023/3/2036第36页/共114页2023/3/2037正规式与

15、正规集定义设字母表，正规式与其所表示的正规集可递归定义为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)*（闭包）。仅由有限次使用上述三个步骤而得到的表达式才是上的正规式仅由这些正规式所表示的字集才是上的正规集正规式运算符（优先级从高到低）*（闭包）（连接）|（或）第37页/共114页正规式与正规集例例设字母表=a，b，部分上的正规式和

16、正规集如下：正规式正规集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的字2023/3/2038第38页/共114页正规式与正规集例例令=A,B,0,1(A|B)(A|B|0|1)*上标识符的全体(0|1)(0|1)*上数的全体例令r=letter(letter|digit)*，则其正规式表示的语言L(r)=L(letter)(L(letter)L(digit)*=A，Z，a，z(A，Z

17、，a，z，0，9)*例令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)第39页/共114页正规式与正规集等价性正规式的等价性若两个正规式所表示的正规集相同，则认为两者等价两个等价的正规式u和v记为u=v如，b(ab)*=(ba)*b,(a|b)*=(a*b*)*等价性证明若要证明u=v，1.须证明L(u)=L(v)集合相等证明方法2.使用正规式的代数性质2023/3/2040第40页/共114页2023/3/2041正规式与正规集正规式的代数性质连接对|是可分配的 是连接的恒等元素性性 质质描描 述述

18、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*幂的等价性第41页/共114页正规式与正规集等价性证明例，证明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)*b2023/3/2042第42页/共114页例，证明(A*)*=A*,其中A

19、为任意正规需证明L(A*)*)=L(A*)/注：L(A*)*)=(L(A*)*首先证明L(A*)*)L(A*)显然有L(A*)*)=L(A*)0L(A*)1L(A*)2L(A*)其次证明L(A*)*)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*)第43页/共114页2023/3/2044

20、确定有限自动机（DFA）一个DFAM是一个五元式M=(S,s0,F)，其中1.S=S0,S1,Sn为有限集，SiS为状态2.为有限字母表，a为输入字符3.:SS的单值（部分）映射（状态转换函数）(s,a)=s意为：现行状态为s，输入字符为a，则转换到后继状态s从转换图来看，相当于4.S0S为唯一的初态5.FS为终态集（可空）ssa第44页/共114页2023/3/2045确定有限自动机DFA的表示五元式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第45页/共114页2023/3/2

21、046确定有限自动机DFA的表示状态转换矩阵行：状态列：输入字符矩阵元素：(s,a)的值01a3b2aaa,bbbv状态转换图第46页/共114页DFA的表示DFAM=(0,1,2,3,a,b,0,3)映射状态矩阵 状态转换图2023/3/2047第47页/共114页2023/3/2048确定有限自动机DFA M识别的字对于*上的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于，则称可为DFAM所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别。DFAM所识别的字的全体记为L(M)。第48页/共114页DFA示例是DFA吗？接受什

22、么样的字符串？2023/3/2049v是DFA吗？接受什么样的字符串？第49页/共114页DFA示例自然数v带符号的自然数第50页/共114页DFA示例带符号的实数v浮点数第51页/共114页DFA示例C语言注释第52页/共114页非确定性DFA的确定性映射:SS是单值函数任何状态sS和输入符号a,(s,a)唯一地确定了下一个状态。例，构造识别:=,=,=的DFA构造识别三个运算符的DFA只能用唯一的初始状态将它们连接在一起2023/3/2053第53页/共114页非确定性2023/3/2054第54页/共114页非确定性如果有两个字符串以相同字符开始呢？下面的转换图是DFA吗？2023/3/

23、2055第55页/共114页非确定性可以用增加新状态的方法解决相同符号的冲突这个是DFA吗？与上图比较有什么优劣？2023/3/2056第56页/共114页2023/3/2057非确定有限自动机（NFA）非确定的有限自动机（NFA）允许是一个多值函数允许有标记的转换：表示没有输入字符直接转换状态第57页/共114页2023/3/2058NFA定义一个NFAM是一个五元式M=(S,S0,F)，其中S是一个有限状态集是一个有穷字母表，是输入字符集合是一个从S*到S的子集的映射，即:S*2SS0S，是非空初态集F S，是一个终态集（可空）第58页/共114页NFA示例:S*2S的含义其含义为(s,)

24、=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)2023/3/2059第59页/共114页2023/3/2060NFA和状态转换图含有m个状态和n个输入字符的NFA可以表示为如下的状态转换图：该图有m个状态结点，每个结点可以射出若干条箭弧与别的结点相接，每条弧用*中的一个字作标记（输入字，可以是），整张图至少含有一个初态结点以及若干个终态结点。aabbb3210第60页/共114页NFA示例2023/3/2061第61页/共114页2023/3/2062NFA

25、识别的字对于*中的任何一个字，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于，则称可为NFAM所识别（读出或接受）。若M的某些初态结点同时又是终态结点，或者存在一条从某个初态结点到某个终态结点的通路，则空字可为M所接受。第62页/共114页DFA和NFA的编程实现方法一：硬编码类似于转换图的实现可以用固定代码模式2023/3/2063第63页/共114页DFA和NFA的实现方法二：状态转换表驱动的实现将状态转移用表的方式表示，如下3表示该状态不读取输入字符空白表示错误状态接受状态用标记2023/3/2064第64页/共114页DFA和NFA的实现给定

26、如上的转换表，对任意DFA我们可以编写下面的程序进行词法分析2023/3/2065第65页/共114页DFA和NFA的实现例C注释2023/3/2066第66页/共114页DFA和NFA的实现例C注释第67页/共114页DFA和NFA的实现例C注释第68页/共114页DFA和NFA的实现例C注释第69页/共114页DFA和NFA的实现例C注释第70页/共114页正规式NFADFA词法分析器我们的思路1.用正规式（RE）描述词法规则2.将正规式转换为NFA3.将NFA转换为DFA4.根据DFA构造词法分析程序要考虑的问题这些表示方式是否等价？这一系列转换是否能够自动进行（有算法）？下一步：等价性

27、证明和构造（转换）算法第71页/共114页正规式转换为NFA每条有向边上标记为或单个字符2023/3/2072第72页/共114页NFA转换为正规式2023/3/2073第73页/共114页NFA和正规式的等价性上述方法说明NFA和正规式是等价的每个NFAM所识别的字的全体L(M)是上的正规集每个上的正规集L(R)均可被一个NFAM所识别L(M)=L(R),称为两者是等价的原则上，若程序语言的词法用正规式描述，则可自动构造一个NFAM来识别该语言的单词NFA的非确定性使之不容易用于实现词法分析器若能消除NFA的非确定性，将其转换为DFA，则容易实现2023/3/2074第74页/共114页NF

28、A和DFA的等价性有限自动机的等价性FAM，FAM，若L(M)=L(M)，则称两者是等价的DFA与NFA的等价性是自动机理论的一个重要定理DFA和NFA是等价的1.DFA是NFA的特例即：DFAM，NFAM，使L(M)=L(M)DFA:SSNFA:S*2S2.需证明，NFAM存在一个DFAM使L(M)=L(M)2023/3/2075*,2S S第75页/共114页NFA转换为DFANFAM，DFAM，使L(M)=L(M)设NFAM=(S,S0,F)将NFAM改造为NFAM引入唯一的新初态结点X和新终态结点YX到S0中所有结点均用边连接F中所有结点到Y也均用边连接反复使用图示的替换直至每条有向边

29、上标记为或单个字符显然，L(M)=L(M)2023/3/2076第76页/共114页NFA转换为DFA基本思想是采用一种“子集构造”算法来确定化构造一个DFAM，使其每个状态对应于NFAM的状态集使得在DFA读入a1a2an时，所处的状态对应于NFA所能到达的状态集如NFA读入a1a2an到达状态中的任意一个，则DFA到达状态集2,3,4，即状态观察NFAM：可能有边，也可能有相同标记的边要构造DFAM，必须合并这两种边到达的状态2023/3/2077第77页/共114页NFA转换为DFA子集构造方法设IS，定义_closure(I)1.qI,q_closure(I)2.qI,从q出发经任意条

30、边可达的q_closure(I)即_closure(I)=Iq|qI旨在合并与状态集I相关的边可达状态设IS，a,定义Ia=_closure(J)qI，从q出发经a边可达的qJ2023/3/2078第78页/共114页NFA转换为DFA确定化方法1.假定=a1,a2,ak,我们构造一张表S，S有k+1列，依次标记为I,Ia1,Ia2,Iak2.置该表的首行首列为_closure(X),X为NFAM的初态3.如果确定了第m（m1,2,）行中第一列的I，则计算Iax（x1,2,k），并填入m行中对应的列即Sm，Iax中4.检查m行上的每个状态子集Iax（x1,2,k），如果Iax，并且它还没有在表

31、S的第一列中出现，则将其填入到空行的第一列5.重复3、4，直至所有Iax（x1,2,k）都在第一列上出现该过程一定在有限步内终止，因为M的子集数=2|S|2023/3/2079第79页/共114页NFA转换为DFA确定化方法（示例）假设=a,b,则定义一张表S(I,Ia,Ib)其中，第i行的表元素分别为Si,I,Si,Ia,Si,Ib1.置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

32、否则算法终止2023/3/2080第80页/共114页例(a|b)*(aa|bb)(a|b)*2023/3/2081ISIaaIbbX,5,105,3,11 5,4,125,3,115,3,1,2,6,Y3 5,4,125,4,125,3,11 5,4,1,2,6,Y55,3,1,2,6,Y35,3,1,2,6,Y3 5,4,1,6,Y45,4,1,6,Y45,3,1,6,Y6 5,4,1,2,6,Y55,4,1,2,6,Y55,3,1,6,Y6 5,4,1,2,6,Y55,3,1,6,Y65,3,1,2,6,Y3 5,4,1,6,Y4第81页/共114页构造DFAM所构造的S表指定了DFAM

33、的状态转换矩阵S表中的每个状态子集为DFAM的一个状态S表中的首行首列为初态S表中含有终态的状态子集为DFAM的终态第82页/共114页2023/3/2083正规式与有限自动机的等价性证明一FAM，正规式r，使得L(r)=L(M)第83页/共114页正规式与有限自动机的等价性证明二正规式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|r

34、2,r=r1r2或r=r1*；r1和r2中的运算符数目=k.根据归纳假设，对r1和r2存在FAM1和M2使得L(M1)=L(r1)L(M2)=L(r2)2023/3/2084第84页/共114页则对于r=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)

35、*=L(r1)*=L(r)2023/3/2085第85页/共114页正规式与有限自动机的等价性v基本思想（Thompson构造算法）对正规式的各个部分构造NFA用弧连接起各个NFA，构成完整的自动机2023/3/2086接受正规式a的NFA接受正规式的NFA假设接受正规式r的NFA如下接受正规式rs的NFA接受正规式r|s的NFA接受正规式r*的NFA第86页/共114页正规式与有限自动机的等价性例子设正规式为r1=1*，r2=01*，r3=01*|12023/3/2087第87页/共114页Thompson构造算法例子正规式ab|a的NFA2023/3/2088第88页/共114页Thomp

36、son构造算法例子正规式letter(letter|digit)*的NFA第89页/共114页正规文法与有限自动机的等价性正规文法与正规式程序语言通常采用正规文法定义它的词法规则正规式是自动构造词法分析器的有效工具正规（3型）文法G=(VT,VN,S,P)P:AB,A,A,BVN,VT*（右线性文法）P:AB,A,A,BVN,VT*（左线性文法）可等价变换为p：AaB，AaA,BVN,aVT（右线性文法）p：ABa，AaA,BVN,aVT（左线性文法）方便起见，右和左线性文法为分别记为GR和GL第90页/共114页正规文法与有限自动机的等价性等价性对正规文法G和FAM，若L(G)=L(M),则

37、称为G和M等价1.GR或GL，FAM，L(GR)=L(M)或L(GL)=L(M)2.FAM，GR或GL，L(M)=L(GR)=L(GL)等价性证明对右线性文法GR构造NFAM，并证明L(M)=L(GR)对左线性文法GL构造NFAM，并证明L(M)=L(GL)对DFAM构造右线性文法GR，并证明L(GR)=L(M)对DFAM构造左线性文法GL，并证明L(GL)=L(M)2023/3/2091第91页/共114页正规文法与有限自动机的等价性等价性证明（从正规文法构造FA）基本思想设w=a1a2ak,分别考虑GR和GL的最左推导GR:Sa1B1a1a2B2a1a2ak-1Bk-1a1a2akGL:S

38、Bk-1akBk-2ak-1akB1a2aka1a2ak非终结符的作用是记住字符个数，将其作为状态2023/3/2092第92页/共114页正规文法与有限自动机的等价性从右线性文法构造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)2023/3/2093第93页/共114页正规文法与有限自动机的等价性从左线性文法构造FA设GL=(VT,VN,S,P),其中P:

39、ABa，Aa令NFAM=(VNq0,VT,q0,S)，其中，1.若AVN,且aVT,使Aa,则令(q0,a)=A2.若AVN,且aVT,使A1Aa,A2Aa,AkAa则令(A,a)=A1,A2,Ak2023/3/2094第94页/共114页正规文法与有限自动机的等价性从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)=L(M)从DFA中构造GL可用类似的方法，但需逆向构造；若BAa若Aa|S0a20

40、23/3/2095第95页/共114页例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)2023/3/2096第96页/共114页3.从NFAM构造GL将F作为开始符号，从终态F出发逆向构造F0|A0|C0CB1B0|A0|C0D1|A1|C1|D0|D1|B0因没有有向边射入A，所以没有有关A的产生式删除无用候选式后GL=(0

41、,1,F,B,C,D,F,P)F0|C0CB1B0|C0D1|C1|D0|D1|B0第97页/共114页2023/3/2098等价性的结论正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。RG第98页/共114页2023/3/2099DFA的化简DFAM的化简化简：寻找DFAM，使L(M)=L(M),且|SM|SM|最小化：寻找具有最少状态数的M，使L(M)=L(M)等价状态和可区别的状态M中的不同状态s和t是等价的如果从状态s出发能读出某个字w而停于终态，那么同样从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出

42、同样的w而停于终态。第99页/共114页2023/3/20100DFA的化简状态的等价关系()设s,tSM,st,定义st,若w=a1a2ak*,有v状态的可区分关系s,t SM,s t,若s，t不等价，则s，t是可区分的据 关系，对SM可进行等价划分 SM=S1S2 Sn,SiSj=,|Si|1容易看出,s,t Si,s t,而 s Si,t Sj,s与 t 是可区分的等价划分是最大划分，即这样划分 n 为最小每个等价集中元素可读出相同的w而终止，故可合并为一个状态最小化算法:从 SM中寻找 S1,S2,Sn,使得SiSj=,s,t Si,s t第100页/共114页DFA的化简最小化算法1

43、.基础，令划分=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边到达的状态)不全包含在某个I j中，则将Ii进一步划分为两个集合Ii1=s|sIi,且s经a边可到达I jIi2=Ii-Ii12023/3/20101第101页/共114页DFA的化简最小化算法3.重复2，直至不可继续划分为止4.构造最小DFAM=(SM,，,s0,F设n=I1,I2,In为等价划分令SM=n,其中每个Ii作为M的状态si设Ii=s1,s2

44、,sk,让原M中导入s1,s2,sk边均导入Ii让原M中导出s1,s2,sk边均从Ii导出令M的初态s0=I j,I j包含原M中的初态s0令M的终态集F=I j1,I j2,I jk,I jm包含原M中的终态2023/3/20102第102页/共114页例3.61=0,1,2,3,4,5,63,4,5,6a3,4,5,6,3,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=32023/3/20103第103页/共114页例题正规式到D

45、FA的转换例：构造识别正规式(a|b)*abb的最小DFA解答1.给出识别该正规集的NFA2.NFA确定化3.DFA最小化第104页/共114页例题解答2023/3/20105解：（1）根据正规式，得到NFA如右图（2）确定化IIaIb11,211,21,21,31,31,21,41,41,21（3）最小化，上面的DFA已经是最小的DFA重命名状态后得到DFA如下第105页/共114页3.4 词法分析器的自动产生UNIX的两个著名工具LEX&YACCLEX的主要功能是将正规式描述转换为状态转换表LEX提供一个有限状态控制器执行单词（字）的识别用户需提供子程序（C代码）指定识别单词后的动作202

46、3/3/20106第106页/共114页2023/3/20107词法分析器的自动产生LEX源程序正规式动作：一段程序，指出按正规式识别出单词符号时采取的动作。LEX程序的编译结果词法分析器状态转换表控制程序第107页/共114页2023/3/20108LEX编译系统LEX编译程序LEX源程序词法分析器L正规式动作状态转换表控制程序词法分析器L输入串单词符号串第108页/共114页2023/3/20109LEX语言的实现LEX编译程序将一个LEX源程序改造为一个词法分析器L，L将像有限自动机那样工作。LEX程序的编译过程对每条识别规则Pi构造一个相应的NFAMi引入新的初态X，通过弧连接这些NFA,得到新的NFAM将M改造为等价的DFA，必要时化简DFA第109页/共114页本章小结第110页/共114页第111页/共114页2023/3/20112课后作业详细阅读教材3.3节习题Ex7(1)EX8(1)和(2)EX9(1)Ex12，Ex14，Ex15上机习题编程实现一个简单语言TEENSY的词法分析器第112页/共114页TEENSY语言的文法和程序示例第113页/共114页感谢您的观看！第114页/共114页