编译原理词法分析.ppt

《编译原理词法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理词法分析.ppt（115页珍藏版）》请在三一办公上搜索。

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

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

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

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

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

6、类的单词区别开来。注意，标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值。此外，我们也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词。例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值。,2.1.2 状态转换图 在词法分析中，可以用状态转换图来识别单词。状态转换图是有限的有向图，结点代表状态，用圆圈表示；结点之间可由有向边连接，有向边上可标记字符。例如，图2-2表示在状态i下，若输入字符为x，则读入x并转换到状态j；若输入字符为y，则读入y并转换到状态k。状态（即结点）数是有限的，其中必有一初始状态以

7、及若干终止状态，终止状态(终态)的结点用双圈表示以区别于其它状态。图2-3给出了用于识别标识符、无符号整数、无符号数的状态转换图，其初始状态均用0状态表示。,图22 不同输入字符的状态转换,图2-3 标识符及无符号数的状态转换图(a)标识符；(b)无符号整数；(c)无符号数,当到达一类单词符号的终止状态时即可给出相应的单词编码。某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码的，这表明在识别单词的过程中多读入了一个符号，所以识别出单词后应将最后多读入的这个符号予以回退；我们对此类情况的处理是在终态上以“*”作为标识。对于不含回路的分支状态来说，可以让它对应一个switch

8、()语句或一组if-else语句。例如，图2-4(a)的状态i所对应的switch语句如下：,s=getchar();switch(s)case a:case b:case z:;/*实现状态j功能的语句*/case 0:case 1:case 9:;/*实现状态k功能的语句*/,对于含回路的状态来说，可以让它对应一个while语句。例如，图2-4(b)的状态i所对应的while语句如下：getchar();while(letter()|chgit()getchar();/*实现状态j功能的语句*/终态一般对应一个return()语句；return意味着从词法分析器返回到调用段，一般指返回到语

9、法分析器。,图2-4 含有分支或回路的状态示意(a)含分支的状态i；(b)含回路的状态i,2.2 一个简单的词法分析器示例,2.2.1 C语言子集的单词符号表示 一个非常重要的事实是：大多数程序语言的单词符号都可以用状态转换图予以识别。作为一个综合例子，我们来构造一个C语言子集的简单词法分析器。表2.1列出了这个C语言子集的所有单词符号以及它们的种别编码和内码值。由于直接使用整数编码不利于记忆，故该例中用一些特殊符号来表示种别编码。,表2.1 C语言子集的单词符号及内码值,2.2.2 C语言子集对应的状态转换图 在设计的状态转换图中，首先对输入串做预处理，即剔除多余的空白符（在实际的词法分析中

10、，预处理还包括剔除注释和制表换行符等编辑性字符的工作），使词法分析工作既简单又清晰。其次，将保留字作为一类特殊的标识符来处理，也即对保留字不专设对应的状态转换图，当转换图识别出一个标识符时就去查对表2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字表来进行处理。图25就是对应表2.1这个简单词法分析的状态转换图。,图25 简单词法分析的状态转换图,在状态2时，所识别出的标识符应先与表2.1的前五项逐一比较，若匹配，则该标识符是一个保留字，否则就是标识符。如果是标识符，应先查符号表，看表中是否有此标识符。若表中无此标识符，则将它登录到符号表中，然后返回其在符号表中的入口指针（地址

11、）作为该标识符的内码值；若表中有此标识符，则给出重名错误信息。在状态4时，应将识别的常数转换成二进制常数并将其登录到常数表，然后返回其在常数表中的入口指针作为该常数的内码值。,2.2.3 状态转换图的实现 状态转换图非常容易用程序实现，最简单的办法是让每个状态对应一小段程序。对于图25的状转换图，我们首先引进一组变量和过程如下：(1)character：字符变量，存放最新读入的源程序字符。(2)token：字符数组，存放构成单词符号的字符串。(3)getbe()：若character中的字符为空白，则调用getchar()，直至character为非空白符为止。,(4)concatenatio

12、n()：将token中的字符串与character中的字符连接并作为token中新的字符串。(5)letter()和digit()：判断character中的字符是否为字母和数字的布尔函数，是则返回true，否则返回false。(6)reserve()：按token数组中的字符串查表2.1中的前五项(即判别其是否为保留字)，若是保留字则返回它的编码，否则返回0值。,(7)retract()：扫描指针回退一个字符，同时将character置为空白。(8)buildlist()：将标识符登录到符号表或将常数登录到常数表。(9)error()：出现非法字符，显示出错信息。相对于图2-5的词法分析器构

13、造如下：,token=;/*对token数组初始化*/s=getchar();getbe();/*滤除空格*/switch(s)case a:case b:case z:while(letter()digit(),concatenation();/*将当前读入的字符送入token数组*/getchar();retract();/*扫描指针回退一个字符*/c=reserve();if(c=0)buildlist();/*将标识符登录到符号表中*/return(id，指向id的符号表入口指针);,elsereturn(保留字码，null);break;case 0:case 1:case 9:wh

14、ile(digit()concatenation();getchar();retract();,buildlist();/*将常数登录到常数表中*/return(num，num的常数表入口指针);break;case+:return(+，null);break;case?:return(?，null);break;case*:return(*，null);,break;case:getchar();if(character=)return(relop,LE);elseretract();return(relop，LT);break;case=:getchar();if(character=),

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

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

17、正规式和正规集的递归定义如下：(1)和都是上的正规式，它们所表示的正规集分别为和。(2)对任一个a，a是上的一个正规式，它所表示的正规集为a。(3)如果R和S是上的正规式，它们所表示的正规集分别为L(R)和L(S)，则：,RS是上的正规式，它所表示的正规集为L(R)L(S)；R.S是上的正规式，它所表示的正规集为L(R)L(S)；(R)*是上的正规式，它所表示的正规集为(L(R)*；R也是上的正规式，它所表示的正规集为L(R)。,(4)仅由有限次使用规则(1)(3)得到的表示式是上的正规式，它所表示的集合是上的正规集。在上述定义中，规则(1)、(2)为基础规则，规则(3)为归纳规则，规则(4)

18、是界限规则或终止规则。此外，上的一个字是指由中的字符所构成的一个有穷序列；不包含任何字符的序列称为空字，用表示。我们用*表示上所有字的全体，则空字也在其中。例如，若=a，b，则*=，a，b，aa，ab，ba，bb，aaa，。我们还用表示不含任何元素的空集。这里需要注意、和的区别：是由空字组成的集合，而则表示不含任何字的集合。1,正规式间的运算符“”表示或，“”表示连接（通常可省略），“*”表示闭包，使用括号可以改变运算的次序。如果规定“*”优先于“”，“”优先于“”，则在不出现混淆的情况下括号也可以省去。注意，*的正规式R和S的连接可以形式化地定义为 RS=R&S 即集合RS中的字是由R和S中

19、的字连接而成的，且R自身的n次连接记为,我们规定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。(3)分配律：R(ST)=RSRT；(RS)T=RTST。(4)同一律：R=R=R。,例2.1 令=a,b，设R=a(ab)*是上的正规式，试求其表示的正规集。解答 L(R)=L(a(ab)

20、*)=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*)*,解答(1)(ab)*对应的正规集其a、b可任意交替出现，如abbaaaba；而(a*b*)对应的正规集只可出现任意个a或者任意个b；因此两者不等价。(2)(ab)*对应的正规集是以任意个ab对出现的，即ababab；而a*b*对应的正规集则是先出现任意个a后接任

21、意个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.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.3.2 有限自动机 有限自动机（FA）是更一般化的状态转换图，它分为确定有限自动机DF

22、A和非确定有限自动机NFA两种。1确定有限自动机（DFA）一个确定的有限自动机Md（记为DFA Md）是一个五元组M d=（S,f,s0,Z），其中：(1)S是一个有限状态集，它的每一个元素称为一个状态；(2)是一个有穷输入字母表，它的每一个元素称为一个输入字符；,(3)f是一个从S到S的单值映射，即f(si,a)=sj且有si、sjS和a；(4)s0S，是惟一的一个初态；(5)Z(S，是一个终态集。例如，对图2-6所给出的状态s1有：f(s1,a)=s2 f(s1,b)=s3 f(s1,c)=s4 因此，f是单值映射函数。,图2-6 DFA的状态转换示意,2非确定有限自动机(NFA)一个非确

23、定有限自动机Mn（记为NFA Mn）是一个五元组Mn=(S,f,Q,Z)，其中：(1)S、Z的意义与DFA相同；(2)f是一个从S*到S的子集映射；(3)Q(S，是一个非空初态集。,NFA和DFA的区别主要有两点：其一是NFA可以有若干个初始状态，而DFA仅有一个初始状态；其二是NFA的状态转换函数f不是单值函数，而是一个多值函数，即f(si，a)=某些状态的集合（siS），它表示不能由当前状态和当前输入字符惟一地确定下一个要转换的状态，也即允许同一个状态对同一个输入字符可以有不同的输出边。,图27 NFA的状态转换示意,例如，对图2-7所给出的状态s1有：f(s1，a)=s1，s2，s3 即

24、f是一个从S*到S的子集映射；*表示输出边上所标记的不仅是字符，也可以是字。此外，NFA还允许f(s1，)=某些状态的集合，即在NFA的状态转换图中输出边上的标记还可是(空字)。,3状态转换图与状态转换矩阵 DFA和NFA都可以用状态转换图表示。假定DFA（或NFA）有m个状态、n个输入字符（或字），则这个状态转换图含有m个状态，每个状态最多有n条输出边与其它状态相连接，每一条输出边用（或*）中的一个不同的输入字符（或一个输入字）作标记，整个图含有惟一一个初态（或多个初态）和若干个终态。DFA和NFA也可以用状态转换矩阵表示。状态转换矩阵的行表示状态，列表示输入符号，矩阵元素表示f(si，a)

25、的值。,例2.4 假定DFA Md=(s0，s1，s2，a，b，f，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 试给出DFA Md的状态转换图与状态转换矩阵。解答 DFA Md的状态转换图见图2-8，状态转换矩阵见表2.2。,表2.2 状态转换矩阵,图2-8 例2.4的DFA Md状态转换图,例2.5 假定NFA Mn=(s0，s1，s2，a，b，f，s0，s2，s1)，且有：f(s0，a)=s2 f(s0，b)=s0,s1 f(s1，a)=f(s1，b)=s2 f(s2，a)=f(s2

26、，b)=s1 试给出NFA Mn的状态转换图与状态矩阵。,解答 NFA Mn的状态转换图见图2-9，状态转换矩阵见表2.3。对于FA M和任一上的字符串（即*），如果存在一条从初始状态到终止状态的通路，通路上有向边（输出边）所标识的字符依次连接所得到的字符串恰为，则称可以为FA M所接受或称为FA M所识别。FA M所能识别的字符串集称为FA M所识别的语言，记为L(M)。,表2.3 状态转换矩阵,图29 例2.5的NFA Mn的状态转换图,2.4 正规表达式到有限自动机的构造,2.4.1 由正规表达式构造等价的NFA M 由正规表达式构造等价的NFA M的方法如下：(1)将正规表达式R表示成

27、如图210所示的拓广转换图。(2)对正规表达式采用如图2-11所示的三条转换规则来构造NFA M。,图2-10 拓广转换图,图2-11 转换规则,对于给定的正规表达式R，首先将其表示成如图210所示的形式，其中X为初始状态，Y为终止状态；然后逐步将这个拓广转换图运用三条转换规则不断加入新结点进行分解，直至每条有向边上仅标识有的一个字母或为止，则NFA M构造完成。例2.6 对给定正规表达式b*(dad)(bab)+构造其NFA M。解答 先用R+=RR*改造题设的正规表达式为b*(dad)(bab)(bab)*，然后构造其NFA M，如图2-12所示。,图2-12 NFA M,2.4.2 NF

28、A M的确定化 NFA的确定化是指对给定的NFA都能相应地构造出一个与之等价的DFA，使它们能够识别相同的语言。我们采用子集法来对NFA M确定化。首先定义FA M的一个状态子集I的_闭包，即_CLOSURE(I)，则：(1)若siI，则si_CLOSURE(I)；(2)若siI，则对从si出发经过通路所能到达的任何状态sj，都有sj_CLOSURE(I)。其次，对FA M的一个状态子集I，若a是中的一个字符，定义 Ia=_CLOSURE(J),其中，J是所有那些可以从I中的某一状态出发经过有向边a而能到达的状态集。例2.7 已知一状态转换图如图213所示，且假定I=_1=1，2，试求从状态I

29、出发经过一条有向边a而能到达的状态集J和_CLOSURE(J)。,图213 例2.7的状态转换图,解答 从状态I中的状态1或状态2出发经过一条a弧而能到达的状态集J为 5，3，4 若siJ，则由si出发经过任意条有向边而能到达的任何状态sj_CLOSURE(J)，因此_CLOSURE(J)为 5，6，2，3，8，4，7,用子集法对NFA确定化的方法如下：(1)构造一张转换表，其第一列为状态子集I，对不同的a(a)在表中单设一列Ia。(2)表的第一行第一列其状态子集I为_CLOSURE(s0)；其中，s0为初始状态。(3)根据第一列中的I为每一个a求其Ia并记入对应的Ia列中，如果此Ia不同于第

30、一列已存在的所有状态子集I，则将其顺序列入空行中的第一列。(4)重复步骤（3）直至对每个I及a均已求得Ia，并且无新的状态子集Ia加入第一列时为止；此过程可在有限步后终止。,(5)重新命名第一列的每一状态子集，则转换表便成为新的状态转换矩阵，其状态转换函数f是S到S的单值映射，即为与NFA M等价的DFA M。例2.8 正规表达式（ab）*(aabb)(ab)*的NFA M如图214所示，试将其确定化为DFA M。解答 用子集法将图2-14所示的NFA M确定化为表2.4。对表2.4中的所有子集重新命名，得到表2.5的状态转换矩阵及对应的状态转换图(见图2-15)。,图214 例2.8的NFA

31、 M,表2.4 例2.8的转换表,图215 例2.8未化简的DFA M,表2.5 例2.8的状态转换矩阵,2.4.3 DFA M的化简 对NFA确定化后所得到的DFA可能含有多余的状态，因此还应对其进行化简。所谓DFA M的化简，是指寻找一个状态数比M少的DFA M，使得L(M)=L(M)。化简了的DFA M 满足下述两个条件：(1)没有多余状态；(2)在其状态集中，没有两个相互等价的状态存在。,所谓两个状态相互等价是指：对一给定的DFA M，若存在状态s1、s2S且s1s2，如果从s1出发能识别字符串而停于终态，从s2出发也同样能够识别这个而停于终态；反之，若从s2出发能识别而停于终态，则从

32、s1出发也能识别这个而停于终态，则称s1和s2是等价的，否则就是可区分的。一个DFA M的状态最小化过程是将M的状态集分割成一些不相交的子集，使得任何不同的两个子集其状态都是可区分的，而同一子集中的任何两个状态都是等价的。,最后，从每个子集中选出一种状态，同时消去其它等价状态，就得到最简的DFA M且L(M)=L(M)。DFA M的化简方法如下：(1)首先将DFA M的状态集S中的终态与非终态分开，形成两个子集，即得到基本划分。(2)对当前已划分出的I(1)、I(2)、I(m)子集（属于不同子集的状态是可区分的），看每一个I是否能进一步划分；也即对某个I(i)=s1,s2,sk，若存在一个输入

33、字符a（a）使得Ia(i)不全包含在当前划分的某一子集I(j)中（即跨越到两个子集），就将I(i)一分为二（见图216）。,图216 是否划分示意(a)无需划分；(b)需要划分,(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

34、经有向边a到达t1,而另一部分含有s2：I(i2)=I(i)I(i1)由于t1和t2是可区分的，即存在一个字符串，t1将读出而停于终态，而t2或读不出或者可以读出但不能到达终态。因此，字符串将把状态s1和s2区分开来，也就是说，I(i1)中的状态与I(i2)中的状态是可区分的。至此，我们已将I(i)划分为两个子集I(i1)和I(i2)，形成了新的划分。,例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,2划分为0，2和

35、1。(3)考察0，2b：0b=2，2b=4，它们分属于两个不同的状态集，故0，2划分为0和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）和DFA M(见图217)。,表2.6 例2.9的状态转换矩阵,图217 例2.9化简后的DFA M,2.4.4 正规表达式到有限自动机构造示例 例2.10

36、 试用DFA的等价性证明正规表达式(ab)*与(a*b*)*等价。解答(1)正规表达式(ab)*对应的NFA如图218所示。用子集法将图218的NFA确定化得到如表2.7所列的转换表，重新命名后得到如表2.8所列的状态转换矩阵。,表2.7(ab)*的转换表,图218(ab)*的NFA,表2.8(ab)*的状态转换矩阵,由于状态0和状态1均为终态，故无论输入什么字符，其下一状态仍是终态，故最简DFA如图219所示。(2)正规表达式(a*b*)*对应的NFA如图220所示。用子集法将图220的NFA确定化得到如表2.9所列的转换表，重新命名得到如表2.10所列的状态转换矩阵。,表2.9(a*b*)

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

38、重新命名后得到如表2.12所列的状态转换矩阵和如图2-22所示的DFA M。,表2.11 例2.11的转换表,表2.12 例2.12状态转换矩阵,图222 例2.11的DFA M,例2.12 某高级程序语言无符号数的正规表达式为digit+(.digit+)?(e(+)?digit+)?其中，digit表示数字，()?表()中的内容可有可无，试给出其DFA M。解答 我们用d代表digit，则用状态转换图表示接受无符号数的NFA如图223所示。用子集法将NFA M确定化，得到如表2.13所列的转换表；重新命名后得到如表2.14所列的状态转换矩阵和如图224所示的DFA M。,图223 例2.1

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

40、所示的DFA M。用DFA M的化简方法得到最终划分：0,2,3、1，按顺序重新命名后得到的最终化简的DFA M如图227所示。最后需要说明的是，采用如图228所示的三条转换规则可以实现从FA M到正规表达式的转换。,表2.15 例2.13的转换表 表2.16 例2.13的状态转换矩阵,用DFA M的化简方法得到最终划分：0,2,3、1，按顺序重新命名后得到的最终化简的DFA M如图227所示。最后需要说明的是，采用如图228所示的三条转换规则可以实现从FA M到正规表达式的转换。,图226 例2.13的DFA M 图227 例2.13最终化简后的DFA M,图228 转换规则,2.5 词法分

41、析器的自动生成,由于各种不同的高级程序语言中单词的总体结构大致相同，基本上都可用一组正规表达式描述，因而人们希望构造这样的自动生成系统：只要给出某高级语言各类单词词法结构的一组正规表达式以及识别各类单词时词法分析程序应采取的语义动作，该系统便可自动产生此高级程序语言的词法分析程序。所生成的词法分析程序的作用如同一台有限自动机，可以用来识别和分析单词符号。正规表达式与有限自动机的理论研究产生了自动生成词法分析程序的技术和工具。,LEX是由美国Bell实验室的M.Lesk和Schmidt于1975年用C语言研制的一个词法分析程序的自动生成工具。对任何高级程序语言，用户必须用正规表达式描述该语言的各

42、个词法类（这一描述称为LEX的源程序），LEX就可以自动生成该语言的词法分析程序。LEX及其编译系统的作用如图229所示。,图229 LEX及其编译系统的作用,一个LEX源程序由用“%”分隔的三部分组成：第一部分为正规式的辅助定义式，第二部分为识别规则，最后一部分为用户子程序。其书写格式为：辅助定义式%识别规则%用户子程序,其中，辅助定义式和用户子程序是任选的，而识别规则是必需的。如果用户子程序缺省，则第二个分隔符号“%”可以省去；但如果无辅助定义式部分，第一个分隔符号“%”不能省去，因为第一个分隔符号用于指示识别规则部分的开始。,下面给出一个简单语言的单词符号的LEX源程序例子，其输出单词的

43、类别编码用整数编码表示。Auxiliary Definitions/*辅助定义*/letterABCZabcz digit01239%Recognition Rules/*识别规则*/,1 while return(1,null)2 do return(2,null)3 if return(3,null)4 else return(4,null)5 switch return(5,null)6 return(6,null)7 return(7,null)8(return(8,null)9)return(9,null)10+return(10,null)11 return(11,null),12

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