第三章-词法分析优秀PPT.ppt

概述v本章引入词法分析器（扫描器）的构造原理和实现技术v扫描器的任务2022/11/51v探讨扫描器的设计需求和实现机制v介绍单词的内部表示，引入单词的描述工具正规式v描述识别单词的转换图和有限自动机的概念和应用v先探讨扫描器的手工构造，然后引入自动构造原理2022/11/52Contents词法分析器的手工构造1正规表达式2有限自动机3词法分析器的自动生成4编译阶段词法分析2022/11/53编译阶段词法分析v将源程序分解为单词符号串2022/11/55词法分析器v词法分析的任务自左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。v词法分析器的构造手工构造自动生成Lex：词法规则（正规式）有限自动机2022/11/563.1 对词法分析器的要求功能v词法分析器的功能v功能v从数据输入到输出的一个变换过程或函数v说明该过程（或函数）须要做什么，而非如何做v扫描器的输入是代表源程序的字符串v输出是单词符号（token）的内部中间表示v过程是扫描输入的字符流，按词法规则识别出单词2022/11/57对词法分析器的要求输出形式v单词符号的种类v关键字由语言定义、具有固定含义的标识符v如，main,if,while,for等v通常不作为程序员自定义的名字运用（保留字，基本字）v标识符用于表示各种名字v如，变量名、数组名、类名，函数名和过程名等v常数具有某种数据类型的不变量v常见的类型有整型、实型、布尔型、文字型等v如，100、3.14159、TRUE、examplev运算符，用于表示操作v如，+、-、*、/等v界符，用于区分各种不同的语法单位v如，“,”、“;”、“(”、“)”、“/*”、“*/”等对词法分析器的要求输出形式v单词符号的输出形式二元式（单词种别，单词符号的属性值）单词种别：通常用整数编码表示，不能唯一确定单词时，需用属性值：通常是指向符号表的指针（入口地址）实现上，如何划分单词种别和编码纯属技术性考虑如关键字、运算符和界符通常作为一符一种处理关键字、运算符和界符由语言定义，个数是固定的种别的整数编码可唯一确定该单词，无须属性值标识符常作为一种来处理，常数则可按类型分种需用属性值来区分不同单词的特征这些特征信息存放于相关的符号表项或常数表项中单词种别：用整数编码2022/11/58词法分析器的输出示例2022/11/59v例，C+代码段：while(i=j)i-;将被转换为 while,(,id,=,=,id,),id,-,;,2022/11/510词法分析器的组织v将词法分析器作为一个独立阶段v任务相对独立、简洁，有高效的工具进行处理v与编译过程的其它工作分开造就良设计的软件架构v结构简洁、清晰、条理化v是否将词法分析器作为独立的一遍？v没有必要，而且低效v与语法分析器通信的其他方式v最常用的：作为一个子程序，由语法分析器在须要单词符号时调用v词法分析器和语法分析器作为两个并发的过程通过pipe通信词法分析器的组织示例v作为独立阶段（一遍）v作为独立的子程序3.2 词法分析器的设计问题v语言对程序格式的要求v自由格式v大部分语言不规定某个单词必需出现在程序行中的什么位置v固定格式v如早期的FORTRAN语言规定输入行的前6个字符是标号，最终的字符（7280列）是注释，以C开头的是注释行，等等v空白（空格和tab）v大多数PL，空白是有意义的vFORTRAN和Algol60，空白可以加在任何地方提高可读性2022/11/512词法分析器的设计问题v缓冲区v是编译器中唯一须要处理每个字符的阶段v设计不合理睬成为最费时和低效的阶段v不能从输入文件中逐个字符读入，一次读入大块文本放入一个缓冲区，由缓冲区给词法分析器供应字符v词法分析器须要向前扫描时，缓冲区也有用处v关键字v保留字：用户不能运用关键字作为标识符vPL/l的关键字不是保留字，词法分析器要区分2022/11/513词法分析器的设计错误处理v词法分析中遇到了错误怎么处理？v应急式（panic）跳过字符，直到发觉一个结构良好的单词符号v替换替换一个不正确的字符v删除删除一个不正确的字符v插入插入一个缺失的字符v调换调换两个字符的位置2022/11/5143.2.1 输入、预处理v输入缓冲区v为了提高效率，扫描器并非干脆逐个字符地读源文件v每次从源文件中读出确定长度的字符串v将输入的字符串放入一个输入缓冲区中v预处理v对多数PL，用于正文编辑的字符一般没有实际意义v如，空格、跳格、回车和换行符只是在文字常数中有意义v注解的出现对程序的功能也无任何意义v为了便利识别工作，编辑性字符和注解应事先删除v有些PL将一个或相继多个空格用作单词之间的界符v此时应事先将相继多个空格合并为一个空格v预处理即在识别起先前，删去输入缓冲区中的无用字符2022/11/515输入、预处理v预处理子程序v可设计一个由扫描器调用的子程序v当调用时，处理出长度为N的字符串，并装入扫描缓冲区v使识别工作可在此缓冲区上干脆进行v扫描缓冲区的结构v通常接受一个长度为2N的双半区（双缓冲区）设计v扫描器需维护两个指示器v一个指向正在扫描单词的首字符，一个向前搜寻其终点v若单词被半区边界截断，则再装入N个字符到另半区v单词的长度N，故语言通常限制标识符和常数的长度2022/11/516扫描缓冲区的结构2022/11/517词法分析器的结构2022/11/518预处理子程序扫描缓冲区扫描器输入缓冲区输入列表单词符号2022/11/519 3.2.2 单词符号的识别：超前搜寻v识别单词通常须要超前搜寻v为了识别当前单词，须要扫描后继的若干个字符v关键字的识别v如FORTRAN，关键字和用户字无区分；单词之间无界符v1DO99K=1,10 循环语句：DO关键字99结束行标号v3DO99K=1.10 赋值语句：DO99K为用户定义的变量名v必需超前搜寻至第一个界符,或.才能确定单词的种别单词符号的识别：超前搜寻v标识符的识别v一般为字母开头的字母/数字序列，读到其它符号时可识别v常数的识别v各种类型的常数一般简洁识别，但有些语言需超前搜寻v如FORTRAN，5.EQ.M和5.E08的前缀相同v算符和界符的识别v有些语言须要超前搜寻v如C+，Java中，+，+=，-，=等2022/11/5202022/11/5213.2.3 状态转换图v如何利用转换图手工（非形式）实现扫描器转换图的作用：词法规则转换图扫描器词法规则的一种图形描述工具描述扫描器动作如，标识符可非形式地描述为字母开头的字母/数字序列其转换图为（其中0表示初始状态，双圈表示终止状态）01字母2其它字母或数字*状态转换图v转换图是一张有限方向图结点：状态箭弧标记：射出结点状态下可能出现的输入字符或字符类初态和终态2022/11/52201字母2其它字母或数字*转换状态初态终态输入字符状态转换图v扫描器可利用转换图识别（接受）确定的字符串（单词）v状态S0对应于单词识别的起先位置v在Si，若存在有向边(Si，Sj),其上标记与输入字符匹配v则状态转换到Sj，并将搜寻指示器+1，否则失败v在终止状态，表示识别出一个单词v在终止状态,若多读了一个字符，应退给输入串，标记为*2022/11/523状态转换图示例2022/11/5242022/11/525状态转换图作用v一个状态转换图可以用于识别（或接受）确定的字符串v大多数程序设计语言的单词符号都可以用转换图予以识别v状态转换图是设计词法分析器的有效工具v给出识别单词符号的状态转换图v实现状态转换图v每个状态结点对应一段程序v不含回路的分叉结点对应switch或if-else语句v含回路的状态结点对应while和if构成的程序段状态转换图实现示例2022/11/526状态转换图实现代码 1状态转换图实现代码 2状态转换图实现代码 3状态转换图综合应用v构造识别一个简洁语言全部单词符号的转换图2022/11/530状态转换图综合应用v词法处理约定v除标识符，常数外，均为一符一种v关键字均为保留字，不行用作用户字v设保留字表，识别出标识符时，查表确定是否为关键字v相邻单词之间至少存在一个界符、算符或空格v按此约定，无须运用超前搜寻，也无须设关键字转换图状态转换图综合应用v设计思想状态转换图综合应用状态转换图综合应用v变量与过程vch，字符变量，存放最新读入的字符vstrToken，字符数组，存放组成单词的字符串vGetChar(),读入当前字符，搜寻指示器指向下一输入字符vGetBC(),若ch=,则反复调用GetChar()直至chvConcat(),strToken:=strToken|chvisletter/isDigit,若ch=letter/digit,则返回true,否falsevintReserve(),若strToken=保留字,则返回编码，否0vRetract(),搜寻指示器回调一个字符，ch:=vintInsertId(),将strToken插入符号表，返回符号表指针vintInsertConst(),将strToken插入常数表，返回常数表指针Nextv手工构造词法分析器v非形式的词法规则转换图扫描器v接下来探讨如何形式化上述过程v其目的在于能够自动化（机械化）该过程，即v词法的形式规则形式状态转换图扫描器v其中：描述词法的形式规则是正规式正规文法v描述转换图的形式工具是有限自动机v形式化也使得可以用数学方法保证结果的正确性自动自动2022/11/5363.3 正规表达式与有限自动机正规式与正规集1DFA和NFA2正规文法3等价性证明43.3.1 正规式与正规集v正规集v已知任何形式语言均为*的一个子集v程序语言的单词一般均属于*的一个特殊子集正规集v已知正规集上的字符串（字）可以运用正规文法描述v正规式是一种比文法更为简洁、高效的方法2022/11/5372022/11/538正规式与正规集定义v设字母表，正规式与其所表示的正规集可递归定义为v和都是上的正规式，它们所表示的正规集分别为和;v任何a，a都是上的一个正规式，它所表示的正规集为a；v假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么(U|V)、(UV)和(U)*也都是正规式，它们所表示的正规集分别是L(U)L(V)、L(U)L(V)（连接积）和(L(U)*（闭包）。v仅由有限次运用上述三个步骤而得到的表达式才是上的正规式v仅由这些正规式所表示的字集才是上的正规集v正规式运算符（优先级从高到低）v*（闭包）（连接）|（或）正规式与正规集例v例设字母表=a，b，部分上的正规式和正规集如下：v正规式正规集vaava|ba，bvababv(a|b)(a|b)aa，ab，ba，bbva*，a，aa，随意个a的串vba*b(a)*=b,ba,baa,va(a|b)*a(a,b)*=a*,上全部以a开头的字v(a|b)*(aa|bb)(a|b)*aa,bb*,上全部包含aa或bb的字2022/11/539正规式与正规集例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)正规式与正规集等价性v正规式的等价性v若两个正规式所表示的正规集相同，则认为两者等价v两个等价的正规式u和v记为u=vv如，b(ab)*=(ba)*b,(a|b)*=(a*b*)*v等价性证明v若要证明u=v，v须证明L(u)=L(v)v集合相等证明方法v运用正规式的代数性质2022/11/5412022/11/542正规式与正规集正规式的代数性质连接对|是可安排的 是连接的恒等元素性性 质质描描 述述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*幂的等价性正规式与正规集等价性证明v例，证明b(ab)*=(ba)*bvb(ab)*=b(ab)0|(ab)1|(ab)2|)v=b|b(ab)1|b(ab)2|/安排律v=b|(ba)1b|(ba)2b|/结合律v=(|(ba)1|(ba)2|)b/安排律v=(ba)*b2022/11/543v例，证明(A*)*=A*,其中A为随意正规v需证明L(A*)*)=L(A*)/注：L(A*)*)=(L(A*)*v首先证明L(A*)*)L(A*)v明显有L(A*)*)=L(A*)0L(A*)1L(A*)2L(A*)v其次证明L(A*)*)L(A*)v设xL(A*)*)=(L(A*)*v若x=,则xL(A*)v若x,则x(L(A*)kv令x=x1x2xk有xiL(A*)=(L(A)*v于是有xi(L(A)mi（mi0,i=1,2,k)v则x=x1x2xk(L(A)m1(L(A)m2(L(A)mkv=(L(A)m1+m2+mkv令m=m1+m2+mk,有x(L(A)m(L(A)*v故有L(A*)*)L(A*)2022/11/545 3.3.2 确定有限自动机（DFA）v一个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为终态集（可空）ssa2022/11/546确定有限自动机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)=32022/11/547确定有限自动机DFA的表示v状态转换矩阵行：状态列：输入字符矩阵元素：(s,a)的值01a3b2aaa,bbbv状态转换图DFA的表示DFAM=(0,1,2,3,a,b,0,3)映射状态矩阵 状态转换图2022/11/5482022/11/549确定有限自动机DFA M识别的字v对于*上的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上全部弧的标记符连接成的字等于，则称可为DFAM所识别（读出或接受）。v若M的初态结点同时又是终态结点，则空字可为M所识别。vDFAM所识别的字的全体记为L(M)。DFA示例v是DFA吗？接受什么样的字符串？2022/11/550v是DFA吗？接受什么样的字符串？DFA示例v自然数v带符号的自然数DFA示例v带符号的实数v浮点数DFA示例vC语言注释非确定性vDFA的确定性映射:SS是单值函数任何状态sS和输入符号a,(s,a)唯一地确定了下一个状态。v例，构造识别:=,=,=的DFA构造识别三个运算符的DFA只能用唯一的初始状态将它们连接在一起2022/11/554非确定性2022/11/555非确定性v假如有两个字符串以相同字符起先呢？v下面的转换图是DFA吗？2022/11/556非确定性v可以用增加新状态的方法解决相同符号的冲突这个是DFA吗？与上图比较有什么优劣？2022/11/5572022/11/5583.3.3 非确定有限自动机（NFA）v非确定的有限自动机（NFA）v允许是一个多值函数v允许有标记的转换：表示没有输入字符干脆转换状态2022/11/559NFA定义v一个NFAM是一个五元式M=(S,S0,F)，其中S是一个有限状态集是一个有穷字母表，是输入字符集合是一个从S*到S的子集的映射，即:S*2SS0S，是非空初态集F S，是一个终态集（可空）NFA示例v:S*2S的含义v其含义为(s,)=s|sSv留意：*(*=+va*与a不加区分，有|a|=1v2S为S的幂集，即由S的全部子集构成的集合v如，S=0,1,2S=,0,1,0,1v例，NFAM=(0,1,2,a,b,0,1,2)2022/11/5602022/11/561NFA和状态转换图v含有m个状态和n个输入字符的NFA可以表示为如下的状态转换图：该图有m个状态结点，每个结点可以射出若干条箭弧与别的结点相接，每条弧用*中的一个字作标记（输入字，可以是），整张图至少含有一个初态结点以及若干个终态结点。aabbb3210NFA示例2022/11/5622022/11/563NFA识别的字v对于*中的任何一个字，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上全部弧的标记字依序连接成的字等于，则称可为NFAM所识别（读出或接受）。v若M的某些初态结点同时又是终态结点，或者存在一条从某个初态结点到某个终态结点的通路，则空字可为M所接受。DFA和NFA的编程实现v方法一：硬编码类似于转换图的实现可以用固定代码模式2022/11/564DFA和NFA的实现v方法二：状态转换表驱动的实现将状态转移用表的方式表示，如下3表示该状态不读取输入字符空白表示错误状态接受状态用标记2022/11/565DFA和NFA的实现v给定如上的转换表，对随意DFA我们可以编写下面的程序进行词法分析2022/11/566DFA和NFA的实现例C注释2022/11/567DFA和NFA的实现例C注释DFA和NFA的实现例C注释DFA和NFA的实现例C注释DFA和NFA的实现例C注释正规式NFADFA词法分析器v我们的思路v用正规式（RE）描述词法规则v将正规式转换为NFAv将NFA转换为DFAv依据DFA构造词法分析程序v要考虑的问题v这些表示方式是否等价？v这一系列转换是否能够自动进行（有算法）？v下一步：等价性证明和构造（转换）算法正规式转换为NFAv每条有向边上标记为或单个字符2022/11/573NFA转换为正规式2022/11/574NFA和正规式的等价性v上述方法说明NFA和正规式是等价的v每个NFAM所识别的字的全体L(M)是上的正规集v每个上的正规集L(R)均可被一个NFAM所识别vL(M)=L(R),称为两者是等价的v原则上，若程序语言的词法用正规式描述，则可自动构造一个NFAM来识别该语言的单词vNFA的非确定性使之不简洁用于实现词法分析器v若能消退NFA的非确定性，将其转换为DFA，则简洁实现2022/11/575NFA和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/11/576*,2S SNFA转换为DFAvNFAM，DFAM，使L(M)=L(M)v设NFAM=(S,S0,F)v将NFAM改造为NFAMv引入唯一的新初态结点X和新终态结点YvX到S0中全部结点均用边连接vF中全部结点到Y也均用边连接v反复运用图示的替换v直至每条有向边上v标记为或单个字符v明显，L(M)=L(M)2022/11/577NFA转换为DFAv基本思想是接受一种“子集构造”算法来确定化v构造一个DFAM，使其每个状态对应于NFAM的状态集v使得在DFA读入a1a2an时，所处的状态对应于NFA所能到达的状态集v如NFA读入a1a2an到达状态中的随意一个，则DFA到达状态集2,3,4，即状态v视察NFAM：可能有边，也可能有相同标记的边v要构造DFAM，必需合并这两种边到达的状态2022/11/578NFA转换为DFAv子集构造方法v设IS，定义_closure(I)vqI,q_closure(I)vqI,从q动身经随意条边可达的q_closure(I)v即_closure(I)=Iq|qIv旨在合并与状态集I相关的边可达状态v设IS，a,定义Ia=_closure(J)vqI，从q动身经a边可达的qJ2022/11/579NFA转换为DFAv确定化方法v假定=a1,a2,ak,我们构造一张表S，S有k+1列，依次标记为I,Ia1,Ia2,Iakv置该表的首行首列为_closure(X),X为NFAM的初态v假如确定了第m（m1,2,）行中第一列的I，则计算Iax（x1,2,k），并填入m行中对应的列即Sm，Iax中v检查m行上的每个状态子集Iax（x1,2,k），假如Iax，并且它还没有在表S的第一列中出现，则将其填入到空行的第一列v重复3、4，直至全部Iax（x1,2,k）都在第一列上出现v该过程确定在有限步内终止，因为M的子集数=2|S|2022/11/580NFA转换为DFAv确定化方法（示例）假设=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否则算法终止2022/11/581v例(a|b)*(aa|bb)(a|b)*2022/11/582ISIaaIbbX,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,Y4v构造DFAM所构造的S表指定了DFAM的状态转换矩阵S表中的每个状态子集为DFAM的一个状态S表中的首行首列为初态S表中含有终态的状态子集为DFAM的终态2022/11/5843.3.5 正规式与有限自动机的等价性v证明一FAM，正规式r，使得L(r)=L(M)正规式与有限自动机的等价性v证明二正规式r,FAM，使得L(M)=L(r)v用关于正规式r中运算符个数归纳证明v归纳基础：r中运算符数目为0v即r=或r=或r=a(a)，则v明显，三个NFA分别接受的正规集为,和av归纳假设：设r,假如r中的运算符数目为k，则存在一个FAM，使得L(M)=L(r)v当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/11/585则对于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)*=L(r1)*=L(r)2022/11/586正规式与有限自动机的等价性v基本思想（Thompson构造算法）对正规式的各个部分构造NFA用弧连接起各个NFA，构成完整的自动机2022/11/587接受正规式a的NFA接受正规式的NFA假设接受正规式r的NFA如下接受正规式rs的NFA接受正规式r|s的NFA接受正规式r*的NFA正规式与有限自动机的等价性例子v设正规式为r1=1*，r2=01*，r3=01*|12022/11/588Thompson构造算法例子v正规式ab|a的NFA2022/11/589Thompson构造算法例子v正规式letter(letter|digit)*的NFA正规文法与有限自动机的等价性v正规文法与正规式v程序语言通常接受正规文法定义它的词法规则v正规式是自动构造词法分析器的有效工具v正规（3型）文法G=(VT,VN,S,P)vP:AB,A,A,BVN,VT*（右线性文法）vP:AB,A,A,BVN,VT*（左线性文法）v可等价变换为vp：AaB，AaA,BVN,aVT（右线性文法）vp：ABa，AaA,BVN,aVT（左线性文法）v便利起见，右和左线性文法为分别记为GR和GL正规文法与有限自动机的等价性v等价性对正规文法G和FAM，若L(G)=L(M),则称为G和M等价1.GR或GL，FAM，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/11/592正规文法与有限自动机的等价性v等价性证明（从正规文法构造FA）基本思想设w=a1a2ak,分别考虑GR和GL的最左推导GR:Sa1B1a1a2B2a1a2ak-1Bk-1a1a2akGL:SBk-1akBk-2ak-1akB1a2aka1a2ak非终结符的作用是记住字符个数，将其作为状态2022/11/593正规文法与有限自动机的等价性v从右线性文法构造FAv设GR=(VT,VN,S,P),其中p：AaB，Aav令NFAM=(VNF,VT,S,F)，其中，v若AVN,且aVT,有Aa,则令(A,a)=Fv若AVN,且aVT,有AaA1|aA2|aAk,v则令(A,a)=A1,A2,Akv简洁证明，该NFAM所识别的语言L(M)=L(GR)2022/11/594正规文法与有限自动机的等价性v从左线性文法构造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/11/595正规文法与有限自动机的等价性v从DFA中构造GRv设DFAM=(S,S0,F),v若S0F，则令GR=(,S,S0,P),其中P为v若v则AaB或Aa|aBv若S0F,则因(S0,)=S0,故L(M),但L(GR)v引入S0代替S0作为新的起先符号，并增加P：S0S0|v简洁证明，L(GR)=L(M)v从DFA中构造GLv可用类似的方法，但需逆向构造；v若BAav若Aa|S0a2022/11/596v例3.4DFAMGRNFAMGLv设DFAM=(A,B,C,D,0,1,A,B)v运用FA到正规式的算法可证明L(M)=0(10)*vGR=(0,1,A,B,C,D,A,P,其中P为vA0|0B|1DB0D|1CvC0|0B|1DD0D|1D(D为无用产生式）v从GR中构造NFAMvM=(A,B,C,D,F,0,1,A,F)2022/11/5973.从NFAM构造GL4.将F作为起先符号，从终态F动身逆向构造5.F0|A0|C0CB16.B0|A0|C0D1|A1|C1|D0|D1|B07.因没有有向边射入A，所以没有有关A的产生式8.删除无用候选式后9.GL=(0,1,F,B,C,D,F,P)10.F0|C011.CB112.B0|C013.D1|C1|D0|D1|B02022/11/599等价性的结论v正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的实力上是相互等价的。RG2022/11/5100DFA的化简vDFAM的化简v化简：找寻DFAM，使L(M)=L(M),且|SM|SM|v最小化：找寻具有最少状态数的M，使L(M)=L(M)v等价状态和可区分的状态vM中的不同状态s和t是等价的v假如从状态s动身能读出某个字w而停于终态，那么同样从t动身也能读出同样的字w而停于终态；v反之，若从t动身能读出某个字w而停于终态，则从s动身也能读出同样的w而停于终态。2022/11/5101DFA的化简v状态的等价关系()设s,tSM,st,定义st,若w=a1a2ak*,有v状态的可区分关系vs,tSM,st,若s，t不等价，则s，t是可区分的v据关系，对SM可进行等价划分vSM=S1S2Sn,SiSj=,|Si|1v简洁看出,s,tSi,st,而sSi,tSj,s与t是可区分的v等价划分是最大划分，即这样划分n为最小v每个等价集中元素可读出相同的w而终止，故可合并为一个状态v最小化算法:从SM中找寻S1,S2,Sn,使得SiSj=,s,tSi,stDFA的化简最小化算法1.基础，令划分=I1,I2，其中2.I1=全部非终态结点s，I2=全部终态结点f3.明显，sI1,fI2,s与f可区分，因f可识别字4.设k=I1,I2,Im,且两两可区分5.设Ii=s1,s2,sk，其中sj为状态结点6.若a,使得Iai(Ii中元素经a边到达的状态)不全包含在7.某个Ij中，则将Ii进一步划分为两个集合8.Ii1=s|sIi,且s经a边可到达Ij9.Ii2=Ii-Ii12022/11/5102DFA的化简最小化算法3.重复2，直至不行接着划分为止4.构造最小DFAM=(SM,，,s0,F5.设n=I1,I2,In为等价划分6.令SM=n,其中每个Ii作为M的状态si7.设Ii=s1,s2,sk,让原M中导入s1,s2,sk边均导入Ii8.让原M中导出s1,s2,sk边均从Ii导出9.令M的初态s0=Ij,Ij包含原M中的初态s010.令M的终态集F=Ij1,Ij2,Ijk,Ijm包含原M中的终态2022/11/5103v例3.6v1=0,1,2,3,4,5,6v3,4,5,6a3,4,5,6,3,4,5,6b3,4,5,6不行拆分v0,1,2a=1,3,拆分为1,0,2v2=1,0,2,3,4,5,6v0,2b=2,5,拆分为0,2v3=00,11,22,3,4,5,63v令SM=0,1,2,3,s0=0,F=32022/11/5104例题正规式到DFA的转换v例：构造识别正规式(a|b)*abb的最小DFA解答1.给出识别该正规集的NFA2.NFA确定化3.DFA最小化例题解答2022/11/5106解：（1）依据正规式，得到NFA如右图（2）确定化IIaIb11,211,21,21,31,31,21,41,41,21（3）最小化，上面的DFA已经是最小的DFA重命名状态后得到DFA如下3.4 词法分析器的自动产生vUNIX的两个著名工具LEX&YACCvLEX的主要功能是将正规式描述转换为状态转换表vLEX供应一个有限状态限制器执行单词（字）的识别v用户需供应子程序（C代码）指定识别单词后的动作2022/11/51072022/11/5108词法分析器的自动产生vLEX源程序v正规式v动作：一段程序，指出按正规式识别出单词符号时实行的动作。vLEX程序的编译结果词法分析器v状态转换表限制程序2022/11/5109LEX编译系统LEX编译程序LEX源程序词法分析器L正规式动作状态转换表控制程序词法分析器L输入串单词符号串2022/11/5110LEX语言的实现vLEX编译程序将一个LEX源程序改造为一个词法分析器L，L将像有限自动机那样工作。vLEX程序的编译过程对每条识别规则Pi构造一个相应的NFAMi引入新的初态X，通过弧连接这些NFA,得到新的NFAM将M改造为等价的DFA，必要时化简DFA编译原理本章小结2022/11/5113课后作业v具体阅读教材3.3节v习题vEx7(1)vEX8(1)和(2)vEX9(1)vEx12，Ex14，Ex15v上机习题v编程实现一个简洁语言TEENSY的词法分析器TEENSY语言的文法和程序示例