第2章--编译原理词法分析课件

《第2章--编译原理词法分析课件》由会员分享，可在线阅读，更多相关《第2章--编译原理词法分析课件（114页珍藏版）》请在金锄头文库上搜索。

1、第第2 2章章 词法分析词法分析 2.1 词法分析器设计方法词法分析器设计方法 词法分析是编译的第一个阶段，其任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成为单词符号串形式的中间程序。执行词法分析的程序称为词法分析程序，也称为词法分析器或扫描器。词法分析器的功能是输入源程序，输出单词符号。第第2 2章章 词法分析词法分析 词法分析可以采用如下两种处理结构：(1)把词法分析程序作为主程序。将词法分析工作作为独立的一遍来完成，即把词法分析与语法分析明显分开，由词法分析程序将字符串形式的源程序改造成单词符号串形式的中间程序，以这个中间程序作为语法分析程序的

2、输入。在这种处理结构中，词法分析和语法分析是分别实现的，如图21(a)所示。第第2 2章章 词法分析词法分析 (2)把词法分析程序作为语法分析程序调用的子程序。在进行语法分析时，每当语法分析程序需要一个单词时便调用词法分析程序，词法分析程序每一次调用便从字符串源程序中识别出一个单词交给语法分析程序。在这种处理结构中，词法分析和语法分析实际上是交替进行的，如图21(b)所示。由于把词法分析器安排成一个子程序比较自然，因此，词法分析程序通常采用第二种处理结构。第第2 2章章 词法分析词法分析 图2-1词法分析的两种处理结构(a)词法分析程序作为主程序；(b)词法分析程序作为子程序第第2 2章章 词

3、法分析词法分析 2.1.1单词符号的分类与输出形式1单词符号分类词法分析程序简单地说就是读单词程序，该程序扫描用高级语言编写的源程序，将源程序中由单词符号组成的字符串分解出一个个单词来。因此，单词符号是程序语言的基本语法单位，具有确定的语法意义。程序语言的单词符号通常可分为下面五种：第第2 2章章 词法分析词法分析 (1)保留字(也称基本字)：如C语言中的if、else、while和do等，这些字保留了语言所规定的含义，是编译程序识别各类语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符。(2)标识符：用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义。(3)常数

4、：包括各种类型的常数，如整型常数386、实型常数0.618、布尔型常数TRUE等。第第2 2章章 词法分析词法分析 (4) 运 算 符 ： 如 “+”、 “?”、 “*”、 “/”、“”、“”等。(5)界符：在语言中是作为语法上的分界符号使用的，如“，”、“；”、“（”、“）”等。一个程序语言的保留字、运算符和界符的个数是确定的，而标识符或常数的使用则不限定个数。第第2 2章章 词法分析词法分析 2词法分析程序输出单词的形式我们知道，词法分析程序的输入是源程序字符串，而输出是与源程序等价的单词符号序列，并且所输出的单词符号通常表示成如下的二元式：（单词种别，单词自身的值）(1)单词种别。单词种

5、别表示单词的种类，它是语法分析所需要的信息。一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性问题，主要取决于处理上的方便。通常让每种单词对应一个整数码，这样可最大限度地把各个单词区别开来。第第2 2章章 词法分析词法分析 对于保留字，可将其全体视为一种，也可一字一种，采用一字一种的分类方法处理起来比较方便；标识符一般统归为一种；常数可统归为一种，也可按整型、实型、布尔型等分为几种；运算符和界符可采用一符一种的分法，也可统归为一种。第第2 2章章 词法分析词法分析 (2)单词自身的值。单词自身的值是编译中其它阶段所需要的信息。对于单词符号来说，如果一个种别只含有一个单词符号，那么对

6、于这个单词符号，其种别编码就完全代表了它自身的值。如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外还应给出单词符号自身的值，以便把同一种类的单词区别开来。注意，标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值。此外，我们也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词。例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值。第第2 2章章 词法分析词法分析 2.1.2状态转换图在词法分析中，可以用状态转换图来识别单词。状态转换图是有限的有向图，结点代表状态，用圆圈表示；结点之间

7、可由有向边连接，有向边上可标记字符。例如，图2-2表示在状态i下，若输入字符为x，则读入x并转换到状态j；若输入字符为y，则读入y并转换到状态k。状态（即结点）数是有限的，其中必有一初始状态以及若干终止状态，终止状态(终态)的结点用双圈表示以区别于其它状态。图2-3给出了用于识别标识符、无符号整数、无符号数的状态转换图，其初始状态均用0状态表示。第第2 2章章 词法分析词法分析 图22不同输入字符的状态转换第第2 2章章 词法分析词法分析 图2-3标识符及无符号数的状态转换图(a)标识符；(b)无符号整数；(c)无符号数第第2 2章章 词法分析词法分析 当到达一类单词符号的终止状态时即可给出相

8、应的单词编码。某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过程中多读入了一个符号，所以识别出单词后应将最后多读入的这个符号予以回退；我们对此类情况的处理是在终态上以“*”作为标识。对于不含回路的分支状态来说，可以让它对应一个switch()语句或一组if-else语句。例如，图2-4(a)的状态i所对应的switch语句如下：第第2 2章章 词法分析词法分析 s=getchar();switch(s)casea:caseb:casez:;/*实现状态j功能的语句*/case0:case1:case9:;/*实现状态k功能的语句*/第第2 2章章

9、词法分析词法分析 对于含回路的状态来说，可以让它对应一个while语句。例如，图2-4(b)的状态i所对应的while语句如下：getchar();while(letter()|chgit()getchar();/*实现状态j功能的语句*/终态一般对应一个return()语句；return意味着从词法分析器返回到调用段，一般指返回到语法分析器。第第2 2章章 词法分析词法分析 图2-4含有分支或回路的状态示意(a)含分支的状态i；(b)含回路的状态i第第2 2章章 词法分析词法分析 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 2.2.1C语言子集的单词符号表示一个非常重要的事实是

10、：大多数程序语言的单词符号都可以用状态转换图予以识别。作为一个综合例子，我们来构造一个C语言子集的简单词法分析器。表2.1列出了这个C语言子集的所有单词符号以及它们的种别编码和内码值。由于直接使用整数编码不利于记忆，故该例中用一些特殊符号来表示种别编码。第第2 2章章 词法分析词法分析 表2.1C语言子集的单词符号及内码值单词符号种别编码助记符内码值while1whileif2ifelse3elseswitch4switchcase5case标识符6idid在符号表中的位置常数7numnum在常数表中的位置+8+9*10*=11relopLE11relopLT=11relopEQ=12=；13

11、；第第2 2章章 词法分析词法分析 2.2.2C语言子集对应的状态转换图在设计的状态转换图中，首先对输入串做预处理，即剔除多余的空白符（在实际的词法分析中，预处理还包括剔除注释和制表换行符等编辑性字符的工作），使词法分析工作既简单又清晰。其次，将保留字作为一类特殊的标识符来处理，也即对保留字不专设对应的状态转换图，当转换图识别出一个标识符时就去查对表2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字表来进行处理。图25就是对应表2.1这个简单词法分析的状态转换图。第第2 2章章 词法分析词法分析 图25简单词法分析的状态转换图第第2 2章章 词法分析词法分析 在状态2时，所识别

12、出的标识符应先与表2.1的前五项逐一比较，若匹配，则该标识符是一个保留字，否则就是标识符。如果是标识符，应先查符号表，看表中是否有此标识符。若表中无此标识符，则将它登录到符号表中，然后返回其在符号表中的入口指针（地址）作为该标识符的内码值；若表中有此标识符，则给出重名错误信息。在状态4时，应将识别的常数转换成二进制常数并将其登录到常数表，然后返回其在常数表中的入口指针作为该常数的内码值。第第2 2章章 词法分析词法分析 2.2.3状态转换图的实现状态转换图非常容易用程序实现，最简单的办法是让每个状态对应一小段程序。对于图25的状转换图，我们首先引进一组变量和过程如下：(1)character：

13、字符变量，存放最新读入的源程序字符。(2)token：字符数组，存放构成单词符号的字符串。(3) getbe( )：若character中的字符为空白，则调用getchar()，直至character为非空白符为止。第第2 2章章 词法分析词法分析 (4)concatenation()：将token中的字符串与character中的字符连接并作为token中新的字符串。(5)letter()和digit()：判断character中的字符是否为字母和数字的布尔函数，是则返回true，否则返回false。(6)reserve()：按token数组中的字符串查表2.1中的前五项(即判别其是否为保留

14、字)，若是保留字则返回它的编码，否则返回0值。第第2 2章章 词法分析词法分析 (7)retract()：扫描指针回退一个字符，同时将character置为空白。(8)buildlist()：将标识符登录到符号表或将常数登录到常数表。(9)error()：出现非法字符，显示出错信息。相对于图2-5的词法分析器构造如下：第第2 2章章 词法分析词法分析 token=;/*对token数组初始化*/s=getchar();getbe();/*滤除空格*/switch(s)casea:caseb:casez:while(letter()digit()第第2 2章章 词法分析词法分析 concaten

15、ation();/*将当前读入的字符送入token数组*/getchar();retract();/*扫描指针回退一个字符*/c=reserve();if(c=0)buildlist();/*将标识符登录到符号表中*/return(id，指向id的符号表入口指针);第第2 2章章 词法分析词法分析 elsereturn(保留字码，null);break;case0:case1:case9:while(digit()concatenation();getchar();retract();第第2 2章章 词法分析词法分析 buildlist();/*将常数登录到常数表中*/return(num，n

16、um的常数表入口指针);break;case+:return(+，null);break;case?:return(?，null);break;case*:return(*，null);第第2 2章章 词法分析词法分析 break;case:getchar();if(character=)return(relop,LE);elseretract();return(relop，LT);break;case=:getchar();if(character=)第第2 2章章 词法分析词法分析 return(relop,EQ);elseretract();return(=,_);break;case;

17、:return(;,_);break;default:error();第第2 2章章 词法分析词法分析 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介 2.3.1正规表达式与正规集状态转换图对构造词法分析程序是行之有效的，为了便于词法分析器的自动生成，还须将状态转换图的概念加以形式化。正规表达式就是一种形式化的表示法，它可以表示单词符号的结构，从而精确地定义单词符号集。正规表达式简称为正规式，它表示的集合即为正规集。为了理解正规式与正规集的含义，我们以程序语言中的标识符为例予以说明。第第2 2章章 词法分析词法分析 程序语言中使用的标识符是一个以字母开头的字母数字串，如果字母用l

18、etter表示，数字用digit表示，则标识符可表示为letter(letterdigit)*其中，letter与(letterdigit)*的并置表示两者的连接；括号中的“”表示letter或digit两者选一；“*”表 示 零 次 或 多 次 引 用 由 “*”标 记 的 表 达 式 ；(letterdigit)*是letterdigit的零次或多次并置，即表示一 长 度 为 0、 1、 2、 的 字 母 数 字 串 ； letter(letterdigit)*表示以字母开头的字母数字串，也即标识符集。letter(letterdigit)*就是表示标识符的正规式，而标识符集就是这个正规式

19、所表示的正规集。第第2 2章章 词法分析词法分析 对于给定的字母表，正规式和正规集的递归定义如下：(1)和都是上的正规式，它们所表示的正规集分别为和。(2)对任一个a，a是上的一个正规式，它所表示的正规集为a。(3)如果R和S是上的正规式，它们所表示的正规集分别为L(R)和L(S)，则：第第2 2章章 词法分析词法分析 RS是上的正规式，它所表示的正规集为L(R)L(S)；R.S是上的正规式，它所表示的正规集为L(R)L(S)；(R)*是上的正规式，它所表示的正规集为(L(R)*；R也是上的正规式，它所表示的正规集为L(R)。第第2 2章章 词法分析词法分析 (4)仅由有限次使用规则(1)(3

20、)得到的表示式是上的正规式，它所表示的集合是上的正规集。在上述定义中，规则(1)、(2)为基础规则，规则(3)为归纳规则，规则(4)是界限规则或终止规则。此外，上的一个字是指由中的字符所构成的一个有穷序列；不包含任何字符的序列称为空字，用表示。我们用*表示上所有字的全体，则空字也在其中。例如，若=a，b，则*=，a，b，aa，ab，ba，bb，aaa，。我们还用表示不含任何元素的空集。这里需要注意、和的区别：是由空字组成的集合，而则表示不含任何字的集合。1第第2 2章章 词法分析词法分析 正规式间的运算符“”表示或，“”表示连接（通常可省略），“*”表示闭包，使用括号可以改变运算的次序。如果规

21、定“*”优先于“”，“”优先于“”，则在不出现混淆的情况下括号也可以省去。注意，*的正规式R和S的连接可以形式化地定义为RS=R&S即集合RS中的字是由R和S中的字连接而成的，且R自身的n次连接记为第第2 2章章 词法分析词法分析 我们规定R0=，并令R*=R0R1R2R3，则称R*是R的闭包；此外，令R+=RR*，并称R+是R的正闭包。闭包R*中的每个字都是由R中的字经过有限次连接而成的。对于上的正规式R和S，如果它所表示的正规集L(R)=L(S)，则称R和S等价并记为R=S。不难证明，正规式具有下列性质：(1)交换律：RS=SR。(2)结合律：R(ST)=(RS)T；R(ST)=(RS)T

22、。(3)分配律：R(ST)=RSRT；(RS)T=RTST。(4)同一律：R=R=R。第第2 2章章 词法分析词法分析 例2.1令=a,b，设R=a(ab)*是上的正规式，试求其表示的正规集。解答L(R)=L(a(ab)*)=L(a)L(ab)*)=L(a)(L(ab)*=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,例2.2判断下述正规式之间是否等价：(1)(ab)*与a*b*(2)(ab)*与a*b*(3)(ab)*与(a*b*)*第第2 2章章 词法分析词法分析 解答(1)(

23、ab)*对应的正规集其a、b可任意交替出现，如abbaaaba；而(a*b*)对应的正规集只可出现任意个a或者任意个b；因此两者不等价。(2)(ab)*对应的正规集是以任意个ab对出现的，即ababab；而a*b*对应的正规集则是先出现任意个a后接任意个b，即aabb；因此两者不等价。(3)由于(ab)*对应的正规集其a、b可任意交替出现，如aababbb；而(a*b*)*可采用如下构造方法得到字aababbb：(a*b*)2=(a*b*)0(a2b1)1(a1b3)2=aababbb反之，对(a*b*)*产生的任意字也可由(ab)*得到，即两者是等价的。第第2 2章章 词法分析词法分析 例2

24、.3证明：设L(a+)=a*?，则有a+=aa*。证明L(a+)=a*?=,a,a2,a3,?=a,a2,a3,=a,a,a2=aa*=L(a)L(a*)=L(aa*)故a+=aa*第第2 2章章 词法分析词法分析 2.3.2有限自动机有限自动机（FA）是更一般化的状态转换图，它分为确定有限自动机DFA和非确定有限自动机NFA两种。1确定有限自动机（DFA）一个确定的有限自动机Md（记为DFAMd）是一个五元组Md=（S,f,s0,Z），其中：(1)S是一个有限状态集，它的每一个元素称为一个状态；(2)是一个有穷输入字母表，它的每一个元素称为一个输入字符；第第2 2章章 词法分析词法分析 (3

25、)f是一个从S到S的单值映射，即f(si,a)=sj且有si、sjS和a；(4)s0S，是惟一的一个初态；(5)Z(S，是一个终态集。例如，对图2-6所给出的状态s1有：f(s1,a)=s2f(s1,b)=s3f(s1,c)=s4因此，f是单值映射函数。第第2 2章章 词法分析词法分析 图2-6DFA的状态转换示意第第2 2章章 词法分析词法分析 2非确定有限自动机(NFA)一个非确定有限自动机Mn（记为NFAMn）是一个五元组Mn=(S,f,Q,Z)，其中：(1)S、Z的意义与DFA相同；(2)f是一个从S*到S的子集映射；(3)Q(S，是一个非空初态集。第第2 2章章 词法分析词法分析 N

26、FA和DFA的区别主要有两点：其一是NFA可以有若干个初始状态，而DFA仅有一个初始状态；其二是NFA的状态转换函数f不是单值函数，而是一个多值函数，即f(si，a)=某些状态的集合（siS），它表示不能由当前状态和当前输入字符惟一地确定下一个要转换的状态，也即允许同一个状态对同一个输入字符可以有不同的输出边。第第2 2章章 词法分析词法分析 图27NFA的状态转换示意第第2 2章章 词法分析词法分析 例如，对图2-7所给出的状态s1有：f(s1，a)=s1，s2，s3即f是一个从S*到S的子集映射；*表示输出边上所标记的不仅是字符，也可以是字。此外，NFA还允许f(s1，)=某些状态的集合，

27、即在NFA的状态转换图中输出边上的标记还可是(空字)。第第2 2章章 词法分析词法分析 3状态转换图与状态转换矩阵DFA和NFA都可以用状态转换图表示。假定DFA（或NFA）有m个状态、n个输入字符（或字），则这个状态转换图含有m个状态，每个状态最多有n条输出边与其它状态相连接，每一条输出边用（或*）中的一个不同的输入字符（或一个输入字）作标记，整个图含有惟一一个初态（或多个初态）和若干个终态。DFA和NFA也可以用状态转换矩阵表示。状态转换矩阵的行表示状态，列表示输入符号，矩阵元素表示f(si，a)的值。第第2 2章章 词法分析词法分析 例2.4假定DFAMd=(s0，s1，s2，a，b，f

28、，s0，s2)，且有：f(s0，a)=s1 f(s0，b)=s2 f(s1，a)=s1 f(s1，b)=s2 f(s2，a)=s2 f(s2，b)=s1试给出DFAMd的状态转换图与状态转换矩阵。解答DFAMd的状态转换图见图2-8，状态转换矩阵见表2.2。第第2 2章章 词法分析词法分析 表2.2状态转换矩阵字符状态abs0s1s2s1s1s2s2s2s1第第2 2章章 词法分析词法分析 图2-8例2.4的DFAMd状态转换图第第2 2章章 词法分析词法分析 例2.5假定NFAMn=(s0，s1，s2，a，b，f，s0，s2，s1)，且有：f(s0，a)=s2 f(s0，b)=s0,s1 f

29、(s1，a)=f(s1，b)=s2 f(s2，a)=f(s2，b)=s1试给出NFAMn的状态转换图与状态矩阵。第第2 2章章 词法分析词法分析 解答NFAMn的状态转换图见图2-9，状态转换矩阵见表2.3。对于FAM和任一上的字符串（即*），如果存在一条从初始状态到终止状态的通路，通路上有向边（输出边）所标识的字符依次连接所得到的字符串恰为，则称可以为FAM所接受或称为FAM所识别。FAM所能识别的字符串集称为FAM所识别的语言，记为L(M)。第第2 2章章 词法分析词法分析 表2.3状态转换矩阵字符状态abs0s2s0，s1s1s2s2s1第第2 2章章 词法分析词法分析 图29例2.5的

30、NFAMn的状态转换图第第2 2章章 词法分析词法分析 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造 2.4.1由正规表达式构造等价的NFAM由正规表达式构造等价的NFAM的方法如下：(1)将正规表达式R表示成如图210所示的拓广转换图。(2)对正规表达式采用如图2-11所示的三条转换规则来构造NFAM。第第2 2章章 词法分析词法分析 图2-10拓广转换图第第2 2章章 词法分析词法分析 图2-11转换规则第第2 2章章 词法分析词法分析 对于给定的正规表达式R，首先将其表示成如图210所示的形式，其中X为初始状态，Y为终止状态；然后逐步将这个拓广转换图运用三条转换规则不

31、断加入新结点进行分解，直至每条有向边上仅标识有的一个字母或为止，则NFAM构造完成。例2.6对给定正规表达式b*(dad)(bab)+构造其NFAM。解答 先用R+=RR*改造题设的正规表达式为b*(dad)(bab)(bab)*，然后构造其NFAM，如图2-12所示。第第2 2章章 词法分析词法分析 图2-12NFAM第第2 2章章 词法分析词法分析 2.4.2NFAM的确定化NFA的确定化是指对给定的NFA都能相应地构造出一个与之等价的DFA，使它们能够识别相同的语言。我们采用子集法来对NFAM确定化。首先定义FAM的一个状态子集I的_闭包，即_CLOSURE(I)，则：(1)若siI，则

32、si_CLOSURE(I)；(2)若siI，则对从si出发经过通路所能到达的任何状态sj，都有sj_CLOSURE(I)。其次，对FAM的一个状态子集I，若a是中的一个字符，定义Ia=_CLOSURE(J)第第2 2章章 词法分析词法分析 其中，J是所有那些可以从I中的某一状态出发经过有向边a而能到达的状态集。例2.7已知一状态转换图如图213所示，且假定I=_1=1，2，试求从状态I出发经过一条有向边a而能到达的状态集J和_CLOSURE(J)。第第2 2章章 词法分析词法分析 图213例2.7的状态转换图第第2 2章章 词法分析词法分析 解答从状态I中的状态1或状态2出发经过一条a弧而能到

33、达的状态集J为5，3，4若siJ，则由si出发经过任意条有向边而能到达的任何状态sj_CLOSURE(J)，因此_CLOSURE(J)为5，6，2，3，8，4，7第第2 2章章 词法分析词法分析 用子集法对NFA确定化的方法如下：(1)构造一张转换表，其第一列为状态子集I，对不同的a(a)在表中单设一列Ia。(2)表的第一行第一列其状态子集I为_CLOSURE(s0)；其中，s0为初始状态。(3)根据第一列中的I为每一个a求其Ia并记入对应的Ia列中，如果此Ia不同于第一列已存在的所有状态子集I，则将其顺序列入空行中的第一列。(4)重复步骤（3）直至对每个I及a均已求得Ia，并且无新的状态子集

34、Ia加入第一列时为止；此过程可在有限步后终止。第第2 2章章 词法分析词法分析 (5)重新命名第一列的每一状态子集，则转换表便成为新的状态转换矩阵，其状态转换函数f是S到S的单值映射，即为与NFAM等价的DFAM。例2.8正规表达式（ab）*(aabb)(ab)*的NFAM如图214所示，试将其确定化为DFAM。解答用子集法将图2-14所示的NFAM确定化为表2.4。对表2.4中的所有子集重新命名，得到表2.5的状态转换矩阵及对应的状态转换图(见图2-15)。第第2 2章章 词法分析词法分析 图214例2.8的NFAM第第2 2章章 词法分析词法分析 表2.4例2.8的转换表IIaIbX,1,

35、21,2,31,2,41,2,31,2,3,5,6,Y1,2,41,2,41,2,31,2,4,5,6,Y1,2,3,5,6,Y1,2,3,5,6,Y1,2,4,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,3,5,6,Y1,2,4,6,Y第第2 2章章 词法分析词法分析 图215例2.8未化简的DFAM第第2 2章章 词法分析词法分析 表2.5例2.8的状态转换矩阵Sab012132214335464564635第第2 2章章 词法分析词法分析 2.4.3DFAM的化简对NFA确定化后所

36、得到的DFA可能含有多余的状态，因此还应对其进行化简。所谓DFAM的化简，是指寻找一个状态数比M少的DFAM，使得L(M)=L(M)。化简了的DFAM满足下述两个条件：(1)没有多余状态；(2)在其状态集中，没有两个相互等价的状态存在。第第2 2章章 词法分析词法分析 所谓两个状态相互等价是指：对一给定的DFAM，若存在状态s1、s2S且s1s2，如果从s1出发能识别字符串而停于终态，从s2出发也同样能够识别这个而停于终态；反之，若从s2出发能识别而停于终态，则从s1出发也能识别这个而停于终态，则称s1和s2是等价的，否则就是可区分的。一个DFAM的状态最小化过程是将M的状态集分割成一些不相交

37、的子集，使得任何不同的两个子集其状态都是可区分的，而同一子集中的任何两个状态都是等价的。第第2 2章章 词法分析词法分析 最后，从每个子集中选出一种状态，同时消去其它等价状态，就得到最简的DFA M且L(M)=L(M)。DFAM的化简方法如下：(1)首先将DFAM的状态集S中的终态与非终态分开，形成两个子集，即得到基本划分。(2)对当前已划分出的I(1)、I(2)、I(m)子集（属于不同子集的状态是可区分的），看每一个I是否能进一步划分；也即对某个I(i)=s1,s2,sk，若存在一个输入字符a（a）使得Ia(i)不全包含在当前划分的某一子集I(j)中（即跨越到两个子集），就将I(i)一分为二

38、（见图216）。第第2 2章章 词法分析词法分析 图216是否划分示意(a)无需划分；(b)需要划分第第2 2章章 词法分析词法分析 (3)重复步骤(2)，直到子集个数不再增加为止（即每个子集已是不可再分的了）。所谓不能划分，是指该子集或者仅有一个状态，或者虽有多个状态但这些状态均不可区分（即等价）。那么，如何进行划分呢？假定当前子集I(i)=s1,s2,，且状态s1和s2经过有向边a分别到达状态t1和t2，而t1和t2又分属于当前已划分出的两个不同子集I(j)和I(k)，则此时应将I(i)分为两部分，使得一部分含有s1：I(i1)=ssI(i)且s经有向边a到达t1第第2 2章章 词法分析词

39、法分析 而另一部分含有s2：I(i2)=I(i)I(i1)由于t1和t2是可区分的，即存在一个字符串，t1将读出而停于终态，而t2或读不出或者可以读出但不能到达终态。因此，字符串将把状态s1和s2区分开来，也就是说，I(i1)中的状态与I(i2)中的状态是可区分的。至此，我们已将I(i)划分为两个子集I(i1)和I(i2)，形成了新的划分。第第2 2章章 词法分析词法分析 例2.9化简由例2.8得到的DFA。解答(1)首先将状态集S=0，1，2，3，4，5，6划分为终态集3，4，5，6和非终态集0，1，2。(2)考察0，1，2a：因0a=2a=1，而1a=3，分属于非终态集和终态集，故将0,1

40、,2划分为0，2和1。(3)考察0，2b：0b=2，2b=4，它们分属于两个不同的状态集，故0，2划分为0和2。第第2 2章章 词法分析词法分析 (4)考察3,4,5,6a：3a=6a=33,4,5,6；4a=5a=63,4,5,6，即都属于终态集，故不进行划分。(5)考察3,4,5,6b：3b=6b=53,4,5,6；4b=5b=43,4,5,6，即都属于终态集，故不进行划分。(6) 按 顺 序 重 新 命 名 状 态 子 集 0、 1、 2、3,4,5,6为0、1、2、3，则得到化简后的状态转换矩阵（见表2.6）和DFAM(见图217)。第第2 2章章 词法分析词法分析 表2.6例2.9的

41、状态转换矩阵Sab012132213333第第2 2章章 词法分析词法分析 图217例2.9化简后的DFAM第第2 2章章 词法分析词法分析 2.4.4正规表达式到有限自动机构造示例例2.10试用DFA的等价性证明正规表达式(ab)*与(a*b*)*等价。解答(1)正规表达式(ab)*对应的NFA如图218所示。用子集法将图218的NFA确定化得到如表2.7所列的转换表，重新命名后得到如表2.8所列的状态转换矩阵。第第2 2章章 词法分析词法分析 表2.7(ab)*的转换表IIaIbX,1,Y1,Y1,Y1,Y1,Y1,Y第第2 2章章 词法分析词法分析 图218(ab)*的NFA第第2 2章

42、章 词法分析词法分析 表2.8(ab)*的状态转换矩阵Sab011111第第2 2章章 词法分析词法分析 由于状态0和状态1均为终态，故无论输入什么字符，其下一状态仍是终态，故最简DFA如图219所示。(2)正规表达式(a*b*)*对应的NFA如图220所示。用子集法将图220的NFA确定化得到如表2.9所列的转换表，重新命名得到如表2.10所列的状态转换矩阵。第第2 2章章 词法分析词法分析 表2.9(a*b*)*的转换表IIaIbX,1,2,3,Y2,3,1,Y2,3,1,Y2,3,Y2,3,1,Y2,3,1,Y第第2 2章章 词法分析词法分析 表2.10(a*b*)*的状态转换矩阵Sab

43、011111第第2 2章章 词法分析词法分析 由于表2.8和表2.10的状态转换矩阵相同，故(ab)*和(a*b*)*等价。例2.11C语言可接受的合法的文件名为device:name.extension，其中第一部分（device:）和第三部分(.extension)可缺省。若device、name和extension都是字母串，长度不限，但至少为1，试画出识别这种文件名的DFAM。解答以字母“c”代表字母，则所求正规式为(cc*:)cc*(.cc*)由此得到的NFAM如图221所示。第第2 2章章 词法分析词法分析 图221例2.11的NFAM第第2 2章章 词法分析词法分析 用子集法将N

44、FAM确定化，得到如表2.11所列的转换表；重新命名后得到如表2.12所列的状态转换矩阵和如图2-22所示的DFAM。第第2 2章章 词法分析词法分析 表2.11例2.11的转换表表2.12例2.12状态转换矩阵IIcI:I.X,21,3,Y1,3,Y1,3,Y2423,Y4Y3,Y3,Y4YY重新命名Sc:.011123243544355第第2 2章章 词法分析词法分析 图222例2.11的DFAM第第2 2章章 词法分析词法分析 例2.12某高级程序语言无符号数的正规表达式为digit+(.digit+)?(e(+)?digit+)?其中，digit表示数字，()?表()中的内容可有可无，

45、试给出其DFAM。解答我们用d代表digit，则用状态转换图表示接受无符号数的NFA如图223所示。用子集法将NFAM确定化，得到如表2.13所列的转换表；重新命名后得到如表2.14所列的状态转换矩阵和如图224所示的DFAM。第第2 2章章 词法分析词法分析 图223例2.12的NFAM第第2 2章章 词法分析词法分析 表2.13例2.12的转换表IIIdI.IeX1,Y1,Y1,Y24,523,Y4,55Y3,Y3,Y4,55YYY重新命名Sd.e011123243564435666第第2 2章章 词法分析词法分析 图224例2.12的DFAM第第2 2章章 词法分析词法分析 由状态转换矩

46、阵可以看出：状态5和状态6面对输入符号的下一状态都是相同的，但状态5为非终态，而状态6为终态，故图224的DFA已为最简。例2.13构造一个DFA，它接收=a,b上所有满足下述条件的字符串：该字符串中的每个a都有至少一个b直接跟在其右边。解答已知=a,b，根据题意得到正规表达式为b*(abb*)*。根据此正规表达式画出相应的NFAM如图225所示。第第2 2章章 词法分析词法分析 图225例2.13的NFAM第第2 2章章 词法分析词法分析 用子集法将NFAM确定化，得到如表2.15所列的转换表；重新命名后得到如表2.16所列的状态转换矩阵和如图226所示的DFAM。用DFAM的化简方法得到最

47、终划分：0,2,3、1，按顺序重新命名后得到的最终化简的DFAM如图227所示。最后需要说明的是，采用如图228所示的三条转换规则可以实现从FAM到正规表达式的转换。第第2 2章章 词法分析词法分析 表2.15例2.13的转换表表2.16例2.13的状态转换矩阵重新命名IIaIbSabX,1,2,Y31,2,Y01234,2,Y131,2,Y31,2,Y2124,2,Y34,2,Y313第第2 2章章 词法分析词法分析 用DFAM的化简方法得到最终划分：0,2,3、1，按顺序重新命名后得到的最终化简的DFAM如图227所示。最后需要说明的是，采用如图228所示的三条转换规则可以实现从FAM到正

48、规表达式的转换。第第2 2章章 词法分析词法分析 图226例2.13的DFAM图227例2.13最终化简后的DFAM第第2 2章章 词法分析词法分析 图228转换规则第第2 2章章 词法分析词法分析 2.5 词法分析器的自动生成词法分析器的自动生成由于各种不同的高级程序语言中单词的总体结构大致相同，基本上都可用一组正规表达式描述，因而人们希望构造这样的自动生成系统：只要给出某高级语言各类单词词法结构的一组正规表达式以及识别各类单词时词法分析程序应采取的语义动作，该系统便可自动产生此高级程序语言的词法分析程序。所生成的词法分析程序的作用如同一台有限自动机，可以用来识别和分析单词符号。正规表达式与

49、有限自动机的理论研究产生了自动生成词法分析程序的技术和工具。第第2 2章章 词法分析词法分析 LEX是由美国Bell实验室的M.Lesk和Schmidt于1975年用C语言研制的一个词法分析程序的自动生成工具。对任何高级程序语言，用户必须用正规表达式描述该语言的各个词法类（这一描述称为LEX的源程序），LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图229所示。第第2 2章章 词法分析词法分析 图229LEX及其编译系统的作用第第2 2章章 词法分析词法分析 一个LEX源程序由用“%”分隔的三部分组成：第一部分为正规式的辅助定义式，第二部分为识别规则，最后一部分为用户子程

50、序。其书写格式为：辅助定义式%识别规则%用户子程序第第2 2章章 词法分析词法分析 其中，辅助定义式和用户子程序是任选的，而识别规则是必需的。如果用户子程序缺省，则第二个分隔符号“%”可以省去；但如果无辅助定义式部分，第一个分隔符号“%”不能省去，因为第一个分隔符号用于指示识别规则部分的开始。第第2 2章章 词法分析词法分析 下面给出一个简单语言的单词符号的LEX源程序例子，其输出单词的类别编码用整数编码表示。AuxiliaryDefinitions/*辅助定义*/letterABCZabczdigit01239%RecognitionRules/*识别规则*/第第2 2章章 词法分析词法分析

51、 1whilereturn(1,null)2doreturn(2,null)3ifreturn(3,null)4elsereturn(4,null)5switch return(5,null)6return(6,null)7return(7,null)8(return(8,null)9)return(9,null)10+return(10,null)11return(11,null)第第2 2章章 词法分析词法分析 12*return(12,null)13/return(13,null)14=return(14,null)15；return(15,null)16letter(letterdig

52、it)*if(keyword(id)=0)return(16,null)；return(id);elsereturn(keyword(id)17digit(digit)*val=int(id)；return(17,null)；return(val)第第2 2章章 词法分析词法分析 18（letterdigit()+*/=；）*return(18，null)；inslit(id)；return(pointer，lenth)该LEX源程序中用户子程序为空；其中识别规则A18语句中调用过程“inslit(id)”是将字符串常量id存放到字符表中，“pointer”中存放该串的起始位置，“lenth”存放该串的长度。第第2 2章章 词法分析词法分析 LEX可以用两种方式来使用：一种是将LEX作为一个单独的工具，用以生成所需的识别程序；另一种是将LEX和语法分析器自动生成工具（如YACC）结合起来使用，以生成一个编译程序的扫描器和语法分析器。