词法分析(编译原理陈火旺).ppt

1,词法分析是编译的第一个阶段，在单词的级别上分析和翻译源程序。理论基础：有限自动机理论 有限自动机理论与正规文法、正规式之间在描 述语言方面有一一对应的关系。,第3章 词法分析,2,内容：状态转换图、正规式和有限自动机、词法分析器的自动生成掌握:正规式、状态转换图，DFN的概念、NFA的概念，将NFA转 换为DFA、DFA的化简、正规式与有限自动机间的转换。理解:正规文法与有穷自动机间的转换 词法分析器的自动产生工具LEX,第3章 词法分析,教学要求,3,本章在编译程序中的地位,4,执行词法分析的程序称为又称为词法分析器或扫描器.词法分析的任务：从左至右逐个地扫描源程序的字符串,按照词法规则识别出一个个正确的单词，并转换为相应的二元式形式，交给语法分析使用。把作为字符串的源程序改造成单词符号串的词法分析是编译的基础。,3.1 设计词法分析器时应考虑的几个问题,5,3.1.1 词法分析阶段的必要性,词法分析的工作纳入整个语法分析中一揽子地进行，原则上是可行的。在设计一个编译程序时，通常是把对源程序的结构分析分为词法分析和语法分析两个相对独立的阶段来完成。第一，描述单词的结构比描述源程序的其它语法结构要简单得多，仅使用3型文法也就基本够用了。第二，由于把词法分析和语法分析分开，可使编译程序各部分的功能更为单一，整个编译程序的结构也更加清晰，从而有利于编译程序的编写和调整。上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译程序的逻辑功能而言，而不一定指的是编译程序的执行流程。,6,3.1.2 词法分析器的输出形式,词法分析器输出的单词常常表示为二元式形式(单词种别,单词符号的属性值)单词种别提供给语法分析程序使用；单词符号的属性值提供给语义分析程序使用。具体的分类设计方法以方便语法分析程序使用为原则。,7,3.1.2 词法分析器的输出形式,程序语言的单词符号一般分为五种：关键字(保留字或基本字)：如 if,then,else,while,do等 标识符：用来表示各种名字，如 x1常量：如 256，3.14，true,abc 运算符：如、*、/等等分界符：如 逗号，分号，冒号等,8,3.1.2 词法分析器的输出形式,单词种别:一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的方便。通常，每种单词对应一个整数码。注意：保留字、运算符和界符的个数确定，标识符和常数的个数不确定。保留字：可全体视为一种，也可一字一种；标识符：统归为一种；常数：统归为一种,或按整、实、布尔等再分；运算符和界符：一符一种，或统归为一种。,9,3.1.2 词法分析器的输出形式,单词符号的属性值 单词符号的属性是指单词符号的特征值。如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因而不需要属性值。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性值。,10,3.1.2 词法分析器的输出形式,单词符号的属性值标识符和常数 标识符的内部码(如ASCII码等等)和常数本身的值(二进制，逻辑值等)来表示。标识符的符号表入口地址作为其单词符号的属性值,常量在其常量表中的入口地址作为其单词符号的属性值。每个基本字占一个单词种别，单词符号的属性值缺省。对于界符，运算符通常一个符号一个种别，单词符号的属性值缺省例:参见P42.表3.1 单词符号及种别编码,11,3.1.3 词法分析器作为独立子程序,词法分析可采用如下两种处理结构：把词法分析程序作为主程序。将词法分析作为独立的一遍来完成。把词法分析程序作为语法分析程序调用的子程序。每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析器处理。,12,3.1.4 源程序的输入、预处理及超前搜索,词法分析器工作的第一步是输入源程序文本。输入串一般放在一个输入缓冲区中。词法分析器的工作可以直接在输入缓冲区中进行。但在许多情况下，可以先预处理输入串，识别工作将更方便。（参见P40 图3.1）,13,3.1.4 源程序的输入、预处理及超前搜索,预处理的原因 源程序中包含回车,换行,多余空白符,注释行等编辑字符,它们对程序逻辑功能无任何影响，在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单。一行语句结束应配上一个特殊字符说明。有些语言要识别标号区，区分标号语句，找出续行符连接成完整语句等。输出源程序清单以便复核。预处理子程序任务 从输入缓冲区中读取源程序，预处理后送入扫描缓冲区。此时，扫描缓冲区的字符都是有效字符。词法分析程序这时可以再对扫描缓冲区进行扫描。,14,3.1.4 源程序的输入、预处理及超前搜索,超前搜索 对于有些语言，关键字不保护，关键字与用户自定义标识符间没有界符，要在上下文环境中识别单词，这时需要超前搜索方法来识别关键字。例如：FORTRAN语言：1.DO10K=1，50 2.DO10K=1.50扫描缓冲区的结构(自学),15,扫描缓冲区的结构,词法分析器对扫描缓冲区进行扫描时一般使用两个指示器，一个指向当前正在识别的单词的开始位置,即指向新单词的首字符;另一个用于向前搜索以寻找单词的终点。不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区的边界所打断。因此，扫描缓冲区最好使用如下一分为二的区域：,16,在扫描缓冲区中扫描,假定每个半个区可容120个字符，而这两个半区又是互补的。如果搜索指示器从单词起点出发搜索到一个半区的边缘但尚未达到单词的终点，那么就调用预处理子程序，令其把后续的120个字符装入另一个半区。认定在另一半区一定可以达到单词的终点。这意味着对标识符和常数的长度实际上必须加以限制，否则即使缓冲区再大也无济于事。,17,词法分析程序设计,设计方法：写出该语言的词法规则；把词法规则转换为相应的状态转换图；把各转换图的初态连在一起，构成识别该 语言的自动机；(4)设计扫描器,18,3.2 正规文法和有限自动机,这节介绍词法规则的形式表示(正规式),从正规式向有限自动机的转化.,19,3.2.1 正规文法、正规集与正规式,正规文法：是chomsky3型文法。,例如：标识符这种单词可以用下面的规则描述|（|）表示任意字母，表示任意数字,注：正规文法描述是正规集的文法，可用于描述程序设计语言的语法部分。,20,对于一个正规文法的语言提炼出一个简洁的公式，用这个式子来对它进行形式化的表示，这个式子叫正规式。正规式：也称正则表达式,是说明单词的模式的一种重要的表示法（记号）；是定义正规集的数学工具；用来描述单词符号。,3.2.1 正规文法、正规式与正规集,注：正规集是集合，可有穷也可无穷。可通过正规式来形式化表示。,正规集：由正规文法产生的语言所构成的集合。,21,3.2.1 正规文法、正规式与正规集,下面以标识符为例说明正规式与正规集:标识符是以字母开头的字母数字串。若用L表示字母,用D表示数字,则标识符可表示为:L(L|D)*其中并置表示两者的连接,|表示两者选一,*表示零次或多次引用。L(L|D)*为标识符的正规式，该正规式表示的集合为标识符的正规集。,22,下面是正规式和它所定义的正规集的递归定义。1),是 上的正规式,所表示的正规集为,;2)若 a,则 a 为正规式,所表示的正规集为 a;3)设U,V 为 上的正规式,所表示的正规集为 L(U),L(V);则 U|V为 上的正规式,所表示的正规集为 L(U)L(V);UV为 上的正规式,所表示的正规集为 L(U)L(V);V*为 上的正规式,所表示的正规集为(L(V)*;4)仅当有限次使用上述三步骤而定义的表达式,才是 上的正规式,而这些正规式所表示的字集才是上的正规集。,3.2.1 正规文法、正规式与正规集,或运算,连接积,23,说明：1上的一个字指的是由中字符构成的一个有穷序列;不包含任何字符的序列称为空字（）。*表示上所有字的全体,包括空字（）。例如,若=a,b 则*=,a,b,aa,ab,ba,bb,aaa,2 表示不含任何元素的空集。注意、和的区别：表示不包含任何字符的序列,它是正规集中的一个元素；表示不含任何字的集合,它是一个空的正规集；表示由空字组成的集合。,3.2.1 正规文法、正规式与正规集,24,3 使用括号可改变运算符的运算次序。若规定*优先于,优先于|,则在不混淆情况下,可省 去括号。4 R自身的n次连接记为 Rn=RRR5 R0=,R*=R0R1R2R3,R*为R的闭包 R+=RR*,称R+是R的正闭包。闭包R*中的每个字都是由R中的字经过有限次连接而成的。6 对于正规式R和S,若它们表示的正规集L(R)=L(S),则称R和S等价,记为R=S。,3.2.1 正规文法、正规式与正规集,25,正规式具有下列性质：(1)交换律：R|S=S|R(2)结合律：R|(S|T)=(R|S)|T,R(ST)=(RS)T(3)分配律：R(S|T)=RS|RT,(R|S)T=RT|ST(4)同一律：R=R=R,3.2.1 正规文法、正规式与正规集,例3.1=a,b,R=a(a|b)*是上正规式,试求R表示的正规集。解:L(R)=L(a(a|b)*)=L(a)L(a|b)*)=L(a)(L(a|b)*=L(a)(L(a)L(b)*=a(ab)*=aa,b*=a,a,b,aa,ab,ba,bb,aaa,=a,aa,ab,aaa,aab,aba,abb,aaaa,上所有以a为首的字,26,例3.2 判断下述正规式之间是否等价：(1)b(ab)*与(ba)*b(2)(ab)*与a*b*,解:(1)b(ab)*对应的正规集是b后面出现任意多个ab对 L(b(ab)*)=b,bab,babab,(ba)*b对应的正规集是b前面可出现任意个ba对L(ba)*b)=b,bab,babab,因此两者等价。正规式b(ab)*及(ba)*b都描述以b开头且其后跟以零个或任意多个ab所组成的字符串等。故我们说两个正规式等价，,(2)(ab)*对应的正规集以任意个ab对出现，即 ababab,而a*b*对应的正规集则是任意个a后接任意个b,即aabb,因此两者不等价。,27,例3.3:设=a,b,则正规式和正规集:ab(ab)(ab)a*(ab)*aab*,a,baa,ab,ba,bb,a,aa,aaa,aaaa,=an|n0,a,b,aa,ab,ba,bb,aaa,aab,abb,bab,bba,bbb.=a,b*a,ab,abb,abbb,abbbb,.=abn|n0,28,通过这一节的学习，要求能根据给出的简单正规式，会写出其表示的正规集。例3.4 令=a,b,其正规式和正规集如下：正规式 正规集 1.ba*2.a(a|b)*3.(a|b)*(aa|bb)(a|b)*,上所有以b为首后跟着任意多个a的字。,上所有以a为首的字。,上所有含有两个相继的a或两个相继的b 的字。,29,例3.5:令=A,B,0,1,则：正规式 正规集(A|B)(A|B|0|1)*(0|1)(0|1)*问:正规式,0,110,0|1,1*表示的正规集是?,答:正规集分别是,0,110,0,1,1,11,111,=1*=1n|n0。,上的“标识符”的全体=A,B.A,B,0,1*上“数”的全体=0,1.0,1*,30,3.2.1 正规文法、正规式与正规集,三个概念之间的关系：一个正规语言可以用正规文法来定义，也可以用正规式来定义，有些正规语言很容易用文法定义，有些则用正规式定义更容易。一个正规语言是一个集合（正规集），那么这个集合可以用正规文法来定义，也可以用正规式来定义。,31,3.2.2 有限自动机,有限自动机（Finite Automata FA）是一种识别装置，它能准确地识别正规集。它为词法分析程序的构造提供了方法和工具。是一种具有离散输入输出系统的数学模型。它具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继行为。其当前状态概括了过去处理的信息。,32,3.2.2 有限自动机,有限自动机模型：,输入带,注：状态分为初始状态、中间状态和终止状态。终止状态可以有若干个，而初始状态一般只有一个。,状态变换,33,3.2.2 有限自动机,有限自动机模型：,输入带,状态:初态,状态:中间,34,3.2.2 有限自动机,有限自动机模型：,输入带,状态:终态,状态:非终态,注：读头全部读完，且此时状态为终态，则说明此输入串正确。,注：读头全部读完，而此时状态不是终态，则说明此输入串错误。,状态的变换和符号的读入用一个图形结构来表示。（状态转换图）,35,3.2.3 状态转换图 P41,状态转换图：状态转换图是一张有限方向图，只包含有限个状态，即有限个结点。P41 1.结点代表状态，用圆圈表示 2.终止状态用双圈表示 3.初始状态前标记符号“”来表示（可省）4.状态之间用箭弧连结，箭弧上的标记代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类，箭弧标记表示状态转换的条件。5.状态图有一个初态，多个终态。6.状态转换图可识别一定的字符串（单词）。7.状态转换图用于表示单词结构,从状态转换图的初态到终态间,每条路径上字符的连接,就构成了该状态图的合法单词。,36,例3.6 P41 图3.2(a)表示：在状态1下，若输入字符为X，则读进X，并转换到状态2。若输入字符为Y，则读进Y，并转换到状态3。若输入字符非X和非Y，则此转换图不工作。,37,例3.7 P41 图3.2(b)表示：识别标识符的状态转换图如下:其中状态0为初态，2为终态；识别标识符的过程是：从初态0开始，若在状态0下输入字符为字母，则读进它，并转换到状态1。在状态1之下，若输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到发现输入字符不再是字母或数字时（这个字符已经被读进）进入状态2；状态2是终态，意味着到此已识别出一个标识符；终态上打个星号表示单词尾部多跟一个字符,应该去掉。若在状态0时输入的字符不为“字母”，则意味着这个转换图不工作。,38,例3.8 P41 图3.2(c)表示：识别无符号整数的状态转换图如下：,在状态转换图中,到达单词符号的终态时即给出相应的单词编码。若到达终态时多读入了一个符号,则识别出该单词后再将多读入的那个符号退回。对此类情况的处理方法是在终态上以*作为标识。,39,例3.9 P41 图3.2(d)表示：识别实数的状态转换图如下：,初态0终态7之间任意一个路径都表示一个实数。,小数形式的实数：,指数形式的实数：,该转换图可以识别下面形式的一些实数:123.,.123,123E3,123.456,123.45e2,.123E+10,123.456E-3 等,40,状态转换图识别字符串:综合例,一个非常重要的事实是，大多数程序语言的单词符号都可以用状态转换图予以识别。作为一个综合例子，教材P42-P46.构造了一个识别某个简单语言的所有单词符号的状态转换图，并给出了对应的词法分析程序。希望同学们好好读一下。为完成的实验-设计并实现一个小语言的词法分析程序,可以以这个例子做参考。,41,识别简单语言单词符号的转换图,参见P43.图3.3,2态：识别标识符和关键字,4态：识别整常数,8态：识别*,9态：识别*,13态：识别错误,5态：识别=,6态：识别+,42,状态转换图容易用程序实现:即容易由转换图编写词法分析程序。最简单的办法是让每个状态结点对应一小段程序。根据画出的识别单词的状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。,3.2.4 状态转换图的实现(自学),43,状态转换图实质上就是一个抽象的程序流程图。转换图忽略了程序的实现细节，着力刻画了单词符号识别的本质。转换图与程序结构之间存在下述对应关系，并可以据此构造相应的程序：初态对应程序的开始；终态对应程序的结束，一般是一条返回语句，且不同的终态对应不同的返回语句；状态转移分叉对应分情况或者条件语句；转换图中的环对应程序中的循环语句；,3.2.4 状态转换图的实现,44,3.2.4 状态转换图的实现,为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序:1)Ch 字符变量存放刚读入的源程序字符;2)Token 单词字符串存放构成单词的字符串;3)Getchar 读一个字符到 Ch中子程序;4)GetBC 读一个非空白字符到Ch中子程序;5)Concat 把Ch中字符连接到Token 之后子程序;6)isLetter 判断Ch中字符是否为字母子程序;7)isDigit 判断Ch中字符是否为数字子程序;8)Reserve 用Token中的字符串查找保留字表,并返回保留字种别码,若返回零,则非保留字子程序;9)Retract 把Ch中字符回送到缓冲区子程序;,45,状态结对应程序段的编写(1),不含回路的分叉结对应条件语句或情形语句,状态结 i 对应的程序段:Getchar();If(IsLetter()状态j的对应程 序段;Else if(IsDigit()状态k的对 应程序段;Else if(ch=/)状态l的对应程 序段;Else 错误处理程序段 或接其他状态图的程序;,46,状态结对应程序段的编写(2),含回路的状态结 对应循环语句,状态结 i 对应的程序段:Getchar();While(IsLetter()or IsDigit()Begin concat();Getchar();End;状态j的对应程序段;,47,状态结对应程序段的编写(3),终态结(如图3.3中的状态5、6、9、10、11、12、13)对应return(Code,Value)语句,返回单词符号的内部表示二元式给语法分析器。带*号的终态结(如图3.3中的状态2、4、8)多读进了一个不属于现行单词符号的字符,这个字符应退回,即搜索指示器要回调一个字符位置,这时除了Return外，还要调用Retract过程来完成这项工作。,48,状态结对应程序段的编写(4),多种单词出口的终态结，如图3.3中的状态2，既是标识符的出口又是关键字的出口，为了确认到底是关键字还是用户自定义的标识符，需要对strToken查询保留字表，这由整型函数过程Reserve来完成。若函数值为0，则表示strToken中的字符串是一个标识符；否则，表示是关键字编码。,49,状态结对应程序段的编写(5),初态结(如图3.3中的状态0)，要作一些初始化的工作,比如：设置指示器的值，对ch，strToken等进行初始化。对于某些状态(如图3.3中的状态1、3)，需要将ch的内容送进strToken拼接单词，则还要调用Concat过程。,50,本节内容及关系,51,作业：P64 8(1)(2)9(1),52,53,3.2.5 确定有限自动机,确定有限自动机（DFA）(Deterministic FA),一个确定有限自动机(DFA M)是一个五元式:DFA M=(S,s0,F),注：这里确定的含义，就是状态转换关系是一个函数，即对于给定的当前状态s和当前读入的字符a有唯一确定的下一状态s。,1.S 是有限状态集；2.是一个有穷字母表,每个元素为一字符；3.s0S,是唯一的初态;4.FS,是终态集（可空）。5.是一个单值映射函数,(s,a)=s，指明若当前的状态为s，而输入字符为a时，则下一个状态是s；,54,3.2.5 确定有限自动机,DFA表示 状态转换矩阵 状态转换图,DFA的映射关系可以用一个矩阵表示：该矩阵的行表示状态列表示输入字符，矩阵元素表示(s,a)的值该矩阵称为状态转换矩阵或状态转换表,55,例如3.10 P48 DFA M=(0,1,2,3,a,b,0,3)其中为:(0,a)=1(1,a)=3(2,a)=1(3,a)=3(0,b)=2(1,b)=2(2,b)=3(3,b)=3 状态转换矩阵可表示为:状态图可表示为:,56,DFA识别(读出,接受)字,DFA识别字：对于*中的任何一个字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字等于，则称为DFA M所识别。例:P48 图3.5的DFA识别字abbab,因为存在路径 012333；但不接受字ababa,因为不存在识别路径。,57,DFA识别字、语言L(M),DFA识别空字 若M的初态结点同时又是终态结点，则称空字可以为DFA M所识别。例:图3.5的DFA不识别空字。DFA M所能识别的字的全体记为L(M)。例：P48 图3.5的DFA M识别的字的全体 L(M)=上所有含有相继两个a或相继两个b的字,58,DFA：练习1,设有 DFA M=(0,1,2,a,b,0,1,2)其中：（0,a)=2;（0,b)=1（1,a)=;（1,b)=2（2,a)=2;（2,b)=2问：该DFA有几个状态？几个输入字符？初态？终态？画出其转换图。,解：有0，1，2共三个状态。0为初态，1和2为终态。输入字符为a,b两个。其状态转换图如:,59,3.2.6 非确定有限自动机,S是一有限状态集;是一个有穷字母表,每个元素为一字符;FS,是终态集。S0S,是初态集;是一个多值映射函数,S*2s 其含义为:在状态S,输入字时,将转换到下一状态集2s。,一个非确定有限自动机(NFA M)是一个五元式:NFA M=(S,S0,F),而DFA是字符,注：非确定主要是指后继状态可有多个。DFA是NFA的特例。,60,如:,一个NFAM也可用状态图表示。,3.2.6 非确定有限自动机,61,假定DFA有m个状态、n个输入符,则状态转换图含m个状态,每个状态最多有n条输出边与其它状态相连,每条边用中一个字符作标记，整个图含一个初态和若干个终态。假定NFA有m个状态、n个输入字,则状态转换图含m个状态,每个状态最多有n条输出边与其它状态相连,每条边用*中一个字作标记，整个图含若干个初态和若干个终态。,NFA的状态转换函数是一多值函数，即(si,)=某些状态的集合，它表示由当前状态和当前输入字符不能唯一确定下一状态，即允许同一状态对同一输入字可有不同输出边；而DFA的状态转换函数是一个单值函数。,NFA和DFA的主要区别,62,例3.11 DFA M=(s0,s1,s2,a,b,s0,s2),且(s0,a)=s1,(s0,b)=s2,(s1,a)=s1(s1,b)=s2,(s2,a)=s2,(s2,b)=s1 试给出M的状态转换图与状态转换矩阵。解：状态转换图：状态转换矩阵：,63,例3.12 NFA M=(s0,s1,s2,a,b,s0,s2,s1),且(s0,a)=s2,(s0,b)=s0,s1,(s1,a)=(s1,b)=s2,(s2,a)=,(s2,b)=s1试给出Mn的状态转换图与状态转换矩阵。解:状态转换图:状态转换矩阵：,64,NFA识别字、空字、L(M),1.NFA识别字 对于*中的任何一个字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字(忽略那些标记为的弧)等于，则称为NFA M所识别(读出或接受)。2.NFA识别空字 若M的初态结点同时又是终态结点;或者存在一条从某个初态结点到某个终态结点的通路，则称空字可以为M所识别。3.NFA M识别的上字的全体记为L(M)。,65,例3.13 P49 图3.6的 NFA M：,识别字 abbab，路径是X55142666Y X555555 X5555514 X555513 X55514 不接受字 ababa，不接受L(M)=上所有含有相继两个a或相继两个b的字,注意:图3.5的DFA与图3.6的NFA识别的字集相同，两个FA等价。,66,NFA：练习,练习1 如图的FA M是NFA吗?L(M)=?,是NFAL(M)=ambn|m0,n0,练习2 如图的FA M是NFA吗?L(M)=?,是NFAL(M)=所有含有相继两个a或相继两个b的字,67,3.3 正规式到有限自动机的构造,由正规式与有限自动机的等价性:P53(1)对任何FA M，都存在一个正规式r,使得L(r)=L(M)。(2)对任何正规式r，都存在一个FA M,使得L(M)=L(r)。,68,3.3 正规式到有限自动机的构造,3.3.1 由正规式构造等价的NFAM 3.3.2 NFA M的确定化3.3.3 具有动作NFA M的确定化 3.3.4 DFA M的化简(最小化),69,3.3.1 由正规式构造等价的NFAM,由正规式构造等价的NFA M的方法：P50(1)将正规式R构造一个如下仅有两个结点X,Y的拓广转换图。,70,(2)采用下述三条转换规则构造NFA M。,3.3.1 由正规式构造等价的NFA M,71,例3.14 构造 b*(d|ad)(b|ab)+对应的NFA。解:首先用R+=RR*把正规式改造为 b*(d|ad)(b|ab)(b|ab)*然后构造其NFA M，如下图所示：,3.3.1 由正规式构造等价的NFAM,(3)重复步骤2不断加入新结点直到每个弧上的标记是 上的一个字符或为止。,72,73,例3.15 P50 构造(a|b)*(aa|bb)(a|b)*对应的NFA。解:构造其NFA M，如下图所示：,74,3.3.2 NFA M的确定化,定理：对于每一个NFAM存在DFAM，使得L(M)=L(M)。即设L是一NFA接受的正规集，则存在一个DNF接受L。子集法：一种将NFA转换成接受同样的语言的DFA的算法。基本思想：该DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。该状态表示这个NFA的状态的一个子集T。,75,3.3.2 NFA M的确定化,算法：由NFA M=（S,f,S0,Z)构造一个等价的DFAM=(Q,I0,F)取I0=S0；若状态集Q中有状态Ii=s0,s1,，sj，skS，0kj，而且M机中有f(=s0,s1,，sj,a)=f(s0,a)f(s1,a)f(s2,a)f(sj,a)=s0,s1,st=It 若It不在Q中，则It加入Q。重复步骤2，直到Q中无新的状态加入为止。取终态F=I|IQ且IZ,76,3.3.2 NFA M的确定化,构造状态子集表上述过程也可用表格法来描述。其中列是字符集的字符，行是Q中的各状态，开始仅包含I0状态，随着算法的执行，Q的状态逐渐增多直至不再增多为止。表格的元素是映射函数。,77,3.3.2 NFA M的确定化,由状态子集表构造DFA M的状态转换表 状态子集表的每个状态子集是DFA M的一个状态-重新编号。DFA M唯一的初态是I0对应的状态子集。DFA M的终态是含有原来的终态Y的状态子集。,78,例：设有NFA M=(X,Y,0,1,f,X,Y)且f(X,0)=X,f(X,1)=Y,f(Y,0)=X,Y,f(Y,1)=X 把它确定化。解：1.M的初态：I0=X则Q中就有了I0状态；2.由Q中的状态I0=X，查看M机有 f(X,0)=X,f(X,1)=Y=I1,此时Q里就有I0，I1 由Q中的状态I1=Y，查看M机有 f(Y,0)=X，Y=I2,f(Y,1)=X=I0,此时Q里就有I0,I1,I2 由Q中的状态I2=X,Y，查看M机有 f(X,Y,0)=X，Y=I2,f(X,Y,1)=X,Y=I2,此时Q里就 有I0,I1,I2 3.F=I1,I2,79,解：1.构造状态子集表：,3.确定的DFA M：,2.重命名：,80,NFA确定化：练习1,设有NFA M=(x,y,a,b,x,y),其中定义如下:(x,a)=x,y(x,b)=y(y,a)=(y,b)=x,y试构造相应的 DFAM。解：1.构造状态子集表：,x,x,y,y,x,y,x,y,x,y,y,x,y,2.重命名：,3.确定的DFA M：,81,3.3.3 具有弧的NFA M确定化,_闭包可以从某状态或某些状态通过弧所能到达的所有状态的集合。假定I是NFA M的状态集的一个子集，状态集合I的_闭包（_CLOSURE(I)形式定义如下：(1)若siI,则si_CLOSURE(I)；(2)若siI,则从si出发经过任意段的弧所能到达的任意 状态sj属于_CLOSURE(I)。,82,例3.16：若 I=X 则_CLOSUR(I)=X,5,1 I=5,1 I=2,_CLOSUR(I)=5,1 _CLOSUR(I)=2,6,Y,83,3.3.3 具有弧的NFA M确定化,闭包间的转换：设_CLOSURE(I)=s1,s2,.，sk 当读入字母表中的字母a时，它转换到另一闭包 _CLOSURE(J)。对NFA M的任一状态子集I,若a是中的一个字符，则定义 Ia=_CLOSURE(J)其中J=q|(q,a)=q 且 qI;a 表示:J是从I中某一状态出发经过a所能到达的所有状态的集合。,84,例3.17 对下图,取I=_CLOSUREI=1,2,求从状态I出发经一条有向边a所能 到达的状态集J和_CLOSURE(J)。,J=5,3,4 Ia=_CLOSURE(J)=5,6,2,3,8,4,7,85,设有NFA M=(S,S0,Z)构造一个等价的 DFA M=(Q,I,F)设=a1,a2,ak 构造一张状态转换子集表第一行第一列为 I=_CLOSUR(S0)，以此I求 Ia1,Ia2,Iak。把没有在第一列出现过的Iai填入空行第一列，以此 Iai为新的 I，再求Ia1,Ia2，Iak。重复的过程，直到所有求出的Iai都在第一列出现为止。,3.3.3 具有弧的NFA M确定化,86,例3.17 正规式(a|b)*(aa|bb)(a|b)*的NFA M如下:试将其确定化为DFA M。,87,解:构造一张状态子集表=a,b,88,3.3.3 具有弧的NFA M确定化,由状态子集表构造DFA的状态转换表。状态子集表的每个状态子集是DFA M的一个状态-重新编号。DFA M唯一的初态是_CLOSUR(S0)对应的状态子集。DFA M的终态是含有原来的终态Y的状态子集。,89,由状态子集表构造DFA的状态转换矩阵:,90,于是得到对应的DFAM如下：,重命名：,91,NFA确定化的实质是以原有状态集上的覆盖片作为DFA上的一个状态，将原状态间的转换改为覆盖片间的转换，从而把不确定问题确定化。通常经过确定化之后，状态数增加，而且可能出现一些等价状态，这时需要化简。,92,3.3.4 DFAM的化简,NFA确定化所得的DFA可能含有多余的状态需化简。所谓一个DFA M=(S,s0,F)的化简(最少化、最小化),是指寻找一个状态数比较少的DFA M,使L(M)=L(M)。化简的原则：受的语言是等价的。思想-划分法1.把DFA M的状态集S分划成一些不相交的子集,使属于同一子集的状态都等价,属于不同子集的状态可区别。2.从每个子集选一个代表,消去其他等价状态。3.把那些原来导入子集各状态的弧都导入此代表状态。化简后的DFA M 满足下述条件：(1)无多余状态；(2)状态集中无相互等价的状态。,93,状态的等价和可区别定义,定义:设s,tS是两个不同的状态,若对任何*,从s(或t)出发能读出而停于某个终态，则称s和t是等价状态。否则，称s和t是可区别的，即不等价的。例如:终态和非终态是可区别的，因为终态能读出空字，而非终态不行。又如：P51.图3.8的DFA中的状态1和2是可区别的，因为状态1能读出a而停于终态，但状态2读出a后不能停于终态。等价状态定义了状态集合上的等价关系。因此，状态集合能被划分成等价类。,94,3.3.4 DFA M的化简,DFA M的化简方法：(1)首先将DFA M的状态集S中的终态与非终态分开,形成两个子集,得到基本划分。(2)对当前已划分出的I(1),I(2),I(m)子集,看每个I是否能进一步划分。对某个I(i)=s1,s2,sk,若存在输入字符a使得Ia(i)不全包含在当前划分的某个子集I(j)中,即跨越两个子集,则将I(i)一分为二。(3)重复(2),直到每个子集均不能再分。不能再分是指子集要么仅有一个状态，要么有多个状态但这些状态是等价的。,95,例3.15 化简由例3.14得到的DFA。,2,3,2,5,2,4,2,6,1,2,0,a,b,b,a,a,b,a,b,b,a,a,b,b,a,b,解:(1)先将状态集S=0,1,2,3,4,5,6划分为终态集3,4,5,6和非终态集0,1,2。(2.1)考察非终态0,1,2:因0,2,1,a=1,3不属于3,4,5,6和0,1,2,由于1状态经a弧到达3状态(是终态)，而状态0、2经a弧到达1状态(是非终态),故应把1状态分出，故将0,1,2分为0,2和1。,96,考察0,2:因0,2,b=2,4,不属于已划分出的某个子集,故0,2划分为0和2。(2.2)考察终态集3,4,5,6：3,4,5,6,a=3,6,属于3,4,5,6,故不划分。3,4,5,6,b=4,5,属于3,4,5,6,故不划分。(3)整个划分为4个组 0,1,2,3,4,5,6(4)令状态3代表3，4，5，6,把原来到达状态4，5，6的弧都导入3，并删除4，5，6得：,97,98,DFA的化简：练习,将如图所示的 DFA M 最小化。,A,Ba=BA,BA,Bb=C,EC,D,EC,D,Ea=BA,BC,D,Eb=D,CC,D,E分成 2个子集,选代表分别为A和C,最后得到最小化的DFA,如图示。,99,3.3.4 正规文法与有限自动机,关系定理：设G=(VN,VT,P,S)是正规文法，则存在一个有限自动机M=(S,s0,Z)使得L(G)L(M)注：1）正规文法分为右线性文法或左线性文法，但对一个正规文法，不能既是右线性，又是左线性。2）对每个自动机M都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)=L(GR)=L(GL),100,3.4 词法分析器的自动产生,回顾词法分析器的构造过程：正规式NFADFA最小化DFA词法分析器每一步都可借助成熟的算法来构造,无须人工干预。词法分析器生成器，就是将这些算法组合起来所形成的软件。利用这样的软件，只需将所需的词法分析器识别的单词符号用正规式的方式描述出来，生成器就会生成相应的词法分析器。当前最成熟、最广泛应用的词法分析器生成器是LEX和与LEX相似的工具，不妨统称为LEX。,101,3.4 词法分析器的自动生成,由于不同高级语言中单词的结构大致相同,基本上都可用一组正规式描述,因而希望构造一自动生成系统:只要给出某高级语言单词的一组正规式及识别各类单词时应采取的语义动作,该系统便可自动产生该语言的词法分析程序。,102,3.4.1 语言LEX 的一般描述,LEX 语言 LEX 是美国Bell实验室研制的一个词法分析程序的自动生成工具。对任一高级程序语言，用户必须用正规式描述该语言的各个词法类(LEX的源程序)，LEX就可自动生成该语言的词法分析程序。LEX及其编译系统作用如下:,103,3.4.1 语言LEX 的一般描述,LEX 语言 LEX 语言用正规式描述单词的词法规则,并通过LEX编译,自动生成词法扫描器。,参见P58.Pascal标识符集合的正规式定义例参见P59.Pascal无符号集合的正规式定义例参见P59.LEX源程序的识别规则形式例参见P5960.识别P42.表3.1的单词符号的LEX程序例,104,3.4.2 LEX 的实现,LEX编译的工作原理 LEX编译对源程序进行处理,产生一个词法分析器.主要有三个步骤:1 对每条识别规则Pi,构造一个非确定有限自动机 Mi,设一初态X,用边连接每个Mi的初态,构成一个总的NFAM,105,控制程序用于扫描输入字符串,控制状态的转移;(对任何转换矩阵,其控制程序是一样的)当识别出某词形Pi后,执行Ai.(返回种别码及值),2根据定理3,把 NFAM 确定化,得到一确定有限自动机 DFAM的状态转换矩阵;3产生一个控制程序；输出如下所示的词法分析器:,3.4.2 LEX 的实现,106,词法分析涉及的概念及关系,107,词法分析小结,