编译原理课程设计之-第二章-词法分析

1、mcy1w课程内容课程内容第一章第一章 概论概论第二章第二章 词法分析词法分析第三章第三章上下文无关文法及分析上下文无关文法及分析第四章第四章自上而下的语法分析自上而下的语法分析第五章第五章自下而上的语法分析自下而上的语法分析第六章第六章语义分析语义分析第七章第七章运行时环境运行时环境第八章第八章代码生成代码生成mcy2第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正规表达式正规表达式 2.3 有穷自动机有穷自动机2.4 从正规表达式到从正规表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析自动生成词法分析程

2、序程序单词的描单词的描述工具述工具单词单词的识的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序作业作业课程设计课程设计1 1 mcy32.1 2.1 词法分析器的作用词法分析器的作用 词法分析器词法分析器( (词法分析程序词法分析程序) )的任务的任务：从源从源代码中读取输入字符，产生单词序列代码中读取输入字符，产生单词序列(生生成独立的有意义的逻辑单元称作单词成独立的有意义的逻辑单元称作单词(token)，提交给语法分析使用。，提交给语法分析使用。mcy4任务任务：逐个读入源程序字符并按照：逐个读入源程序字符并按照构词规则构词规则切分切分成一系列单词。单词是语言中具有独立意义的成

3、一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标最小单位，包括保留字、标识符、运算符、标点符号和常量等。点符号和常量等。w识别出源程序中的单词；识别出源程序中的单词；w删除无用的空白字符及注释（空格、回车删除无用的空白字符及注释（空格、回车 等），这些信等），这些信息仅增加了源程序的可读性，便于程序员阅读和维护程息仅增加了源程序的可读性，便于程序员阅读和维护程序，而对于语法分析是完全无用的。序，而对于语法分析是完全无用的。w进行词法检查，能够检测出输入中不能形成进行词法检查，能够检测出输入中不能形成源语言任何源语言任何单词的错误字符串单词的错误字符串。mcy5Th

4、e big elephant ate the peanut.The big elephant ate the peanut. big 词法分析的结果：词法分析的结果： mcy6 token表示的字符串表示的字符串（串值或词义串值或词义）：）： if , y, ,3,then,x,=,0 token的的类型（词法）类型（词法）： 关键字（关键字（if, else, for,int,return） 操作符（操作符（+ , -, ） 数字数字 （3, 45,） 标示符（标示符（x, y, ）词法分析器的输出词法分析器的输出: : token序列序列mcy7if y3 then x=0 LT, 词法分

5、析器词法分析器例如：例如：C源代码源代码:if y3 then x=0,词法词法分析器的输出是？分析器的输出是？ mcy8定义逻辑项定义逻辑项token的数据类型的数据类型： typedef struct union char *stringval; int numval; attribute; TokenRecord; TokenType tokenval;Token类型类型Token词义词义mcy9词法分析程序的函数接口：词法分析程序的函数接口： TokenRecord getToken(void);TokengetToken()源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序

6、符号表符号表mcy10第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正规表达式正规表达式 2.3 有穷自动机有穷自动机2.4 从正规表达式到从正规表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析自动生成词法分析程序程序记号的描记号的描述工具述工具记号的识记号的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序作业作业课程设计课程设计1 1 mcy11正规表达式的引入：正规表达式的引入： 对自动生成词法分析程序而言，正规表达对自动生成词法分析程序而言，正规表达 式也是非常有用的工具。式也是非常有用的工

7、具。 所谓所谓正规表达式正规表达式就是用特定的就是用特定的运算符运算符及及运算运算对象对象按某种规则构造的表达式。例如：按某种规则构造的表达式。例如：c-语语言的词法言的词法。 正规表达式用来描述单词正规表达式用来描述单词结构结构( (定义单词定义单词) )。mcy122.2.1 基本概念和术语基本概念和术语2.2.2 正规表达式的定义正规表达式的定义2.2.3 正规表达式基本等价关系正规表达式基本等价关系2.2.4 正规表达式的扩展正规表达式的扩展2.2.5 单词的正规表达式举例单词的正规表达式举例2.22.2正规表达式正规表达式 单词的描述工具单词的描述工具mcy132.2.1 2.2.1

8、 基本概念和术语基本概念和术语字母表（符号表、符号集）字母表（符号表、符号集） 由若干元素由若干元素（符号、字母）组成的有限非空集合。（符号、字母）组成的有限非空集合。不同的语言可以有不同的字母表，例如不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点汉语的字母表中包括汉字、数字及标点符号等。符号等。mcy14 符号串符号串 由字母表中的符号组成的任何有由字母表中的符号组成的任何有穷序列称为符号串穷序列称为符号串:例如例如00 11 10 是字母表是字母表 =0，1上上的符号串。的符号串。字母表字母表A=a，b，c上的符号串有：上的符号串有： a，b，c，ab，aaca。在符

9、号串中，符号的顺序是很重要的，符在符号串中，符号的顺序是很重要的，符号串号串ab就不同于就不同于ba，abca和和aabc也不同。也不同。mcy15符号串的长度符号串的长度 如果某符号串如果某符号串x x中有中有m m个符号，个符号，则称其长度为则称其长度为m m，表示为表示为x x=m=m，如如001110001110的长度是的长度是6 6。空符号串空符号串，即不包含任何符号的符号串，用，即不包含任何符号的符号串，用表示，其长度为表示，其长度为0 0，即，即=0=0。mcy16w符号串的连接符号串的连接：设：设x和和y是符号串，它们的连是符号串，它们的连接接xy是把是把y的符号写在的符号写在

10、x的符号之后得到的符的符号之后得到的符号串。号串。 例如例如 x=ST，y=abu，则它们的连接则它们的连接 xy=STabu，x=2，y=3，xy=5由于由于的含义，显然有的含义，显然有x=x=x。w符号串的方幂符号串的方幂：符号串自身连接符号串自身连接n次得到的符次得到的符号串号串xn 定义为定义为 xxxx； n个个x x1=x, x2=xx且且x0=mcy17例；若例；若x=x=abab 则则: : x x0 0 = = x x1 1 = =abab x x2 2 = = abababab x x3 3 = = abababababab x xn n = xx= xxn-1 n-1 =

11、 x= xn-1n-1x (n0)x (n0)mcy18符号串集合符号串集合：若集合若集合A A中所有元素都是中所有元素都是某字母表某字母表 上的符号串，则称上的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。符号串集合的和与积符号串集合的和与积设设A A，B B为两个符号串集合，定义为两个符号串集合，定义和和 A A+B(+B(或或A A B)B) =w|w =w|w A A，或或w w BB积积AB=AB=xy|xxy|x A,yA,y B B mcy19v若用若用表示空集，则有：表示空集，则有： A+ = +A = A A = A = A = A = Av 例：若集合

12、例：若集合A= = ab,cde ，集合集合B = B = 0,1 ，则则AB = ab1,ab0,cde0,cde1 ；mcy20的闭包：的闭包：用用 * *表示表示 上的一切符号串（包括上的一切符号串（包括）组成的集合，组成的集合，* *称为称为的闭包的闭包。例如例如：=a,ba,b * *=,a,b,aa,ab,ba,bb,aaa,aab,a,b,aa,ab,ba,bb,aaa,aab, , 的正闭包：的正闭包： 上上除除外的所有符号串组成的外的所有符号串组成的集合记为集合记为 + + ，+ +称为称为的正闭包的正闭包。例如例如：=a,ba,b + +=a,b,aa,ab,ba,bb,a

13、aa,aaba,b,aa,ab,ba,bb,aaa,aab, , mcy212.2.1 基本概念和术语基本概念和术语2.2.2 正规表达式的定义正规表达式的定义2.2.3 正规表达式基本等价关系正规表达式基本等价关系2.2.4 正规表达式的扩展正规表达式的扩展2.2.5 单词的正规表达式举例单词的正规表达式举例2.22.2正规表达式正规表达式mcy22w正规表达式正规表达式(也称正则表达式也称正则表达式)就是用特定的就是用特定的运算运算符符及及运算对象运算对象按某种规则构造的表达式。按某种规则构造的表达式。w每个正规表达式代表一个每个正规表达式代表一个字符串的集合字符串的集合，我们，我们把其称

14、为正规集。把其称为正规集。w语言语言(Language)是字符串组成的集合，我们也可是字符串组成的集合，我们也可以把正规表达式表示的以把正规表达式表示的正规集正规集称为该正规表达称为该正规表达式表示的式表示的语言语言。2.2.22.2.2正规表达式的定义正规表达式的定义mcy23w正规表达式和它所表示的正规集正规表达式和它所表示的正规集(字符串的集字符串的集合合)的递归定义如下的递归定义如下： 设有字母表为设有字母表为，辅助字母表辅助字母表=, | , . , * , ( , ) mcy24(1)和和是是上的正规式，它们所表示的正规集上的正规式，它们所表示的正规集分别为分别为和和;(2) 若若

15、a，则则a是是上的正规式，它所表示的上的正规式，它所表示的正规集为正规集为a;(3)若若r和和s都是都是上的上的正规式正规式，且它们所表示，且它们所表示的的正规集正规集分别为分别为L(r)和和L(s)，那么：那么：mcy25 r|s 是是正规式正规式，表示的，表示的正规集正规集为为 L(r|s)=L(r)L(s) ； rs 是是正规式正规式，表示的，表示的正规集正规集为为 L(rs)=L(r)L(s) ； r *是是正规式正规式，表示的，表示的正规集正规集为为(L(r)*。 (r) 是是正规式正规式，表示的，表示的正规集正规集为为L(r)；“.”运算符运算符常省略常省略mcy26(4)仅由有限

16、次使用上述三步骤而定义的表仅由有限次使用上述三步骤而定义的表达式才是达式才是上的上的正规式正规式，仅由这些正规式仅由这些正规式所表示的符号串集合才是所表示的符号串集合才是上的上的正规集。正规集。注：算符的优先级为先注：算符的优先级为先“ * ”，再，再“ . ”最后最后“ | ” ,都是左结合的，它们满足结合都是左结合的，它们满足结合律。律。举例：举例： C-语言的词法语言的词法mcy27例例1，令，令 =a，b， 上的正规式和相应的正规集的例子：上的正规式和相应的正规集的例子：正规式正规式 正规集正规集aaa bab(a b)(a b)a a,babaa,ab,ba,bb ,a,aa, 任意

17、个任意个a的串的串(a b) a,b*即即,a,b,aa,ab,ba,bb,mcy28例例2，正规式，正规式(a)| (b) * (c)它所表示的正规集为：它所表示的正规集为： 根据运算符的优先级，上述正规式可以表示根据运算符的优先级，上述正规式可以表示成成 a|b*ca|b*c所表示的正规集为：字符串所表示的正规集为：字符串a以及由零个以及由零个或多个或多个b后跟一个后跟一个c 形成的字符串的集合形成的字符串的集合或写成或写成L(a|b*c)=a bnc | 其中其中n是大于或等是大于或等于于0的整数的整数mcy29给定一个正规式给定一个正规式, ,它唯一确定一个正规集；它唯一确定一个正规集

18、；反之不成立。即一个正规集可由多个不同反之不成立。即一个正规集可由多个不同的正规式表示。的正规式表示。aaaa a,aa, aaa,任意个任意个a的串的串a|aaa|aa a,aa, aaa,任意个任意个a的串的串例如：例如：mcy30若若二正规式二正规式描述同一正规集，则称二式描述同一正规集，则称二式等等价价( (相等相等) )。判断下列正规表达式判断下列正规表达式e e1 1和和e e2 2是否等价？是否等价？e1= (a b)， e2 = b ae1= b(ab) ,e2 =(ba) be1= (a b) , e2 =(a b ) mcy31w正规表达式正规表达式是表示模式的一种重要方法

19、，每是表示模式的一种重要方法，每个模式匹配一个字符串集合个模式匹配一个字符串集合(即正规集即正规集)。w正规集正规集是正规表达式所定义的语言。是正规表达式所定义的语言。w正规表达式正规表达式可以作为字符串集合可以作为字符串集合(即正规集即正规集)的名字。的名字。mcy322.2.1 基本概念和术语基本概念和术语2.2.2 正规表达式的定义正规表达式的定义2.2.3 正规表达式基本等价关系正规表达式基本等价关系2.2.4 正规表达式的扩展正规表达式的扩展2.2.5 单词的正规表达式举例单词的正规表达式举例2.22.2正规表达式正规表达式mcy33A1. r|s=s|r A2. r|r=rA3.

20、r| =rA4. (r|s)|t=r|(s|t)A5. (rs)t=r(st)A6. r(s|t)=rs|rtA7. (s|t)r=sr|trA8. r = r= A9. r = r=rA10. r*=( |r)*= |rr* 2.2.3 2.2.3 正规式基本等价关系正规式基本等价关系mcy342.2.1 基本概念和术语基本概念和术语2.2.2 正规表达式的定义正规表达式的定义2.2.3 正规表达式基本等价关系正规表达式基本等价关系2.2.4 正规表达式的扩展正规表达式的扩展2.2.5 单词的正规表达式举例单词的正规表达式举例2.22.2正规表达式正规表达式mcy352.2.4 2.2.4

21、正规表达式的扩展正规表达式的扩展w1.一个或多个重复（一个或多个重复（+，*）：）： 假设假设r是正则表达式是正则表达式，r的重复是通过使用标准的闭包运算来描述，的重复是通过使用标准的闭包运算来描述，写作写作r*。它允许它允许r被重复被重复0次或更多次次或更多次。用用r +表示表示r 被重复被重复1次或更多次次或更多次。因此有：。因此有： (0|1)+=(0|1)(0|1)*mcy362.任意字符（任意字符（.）: 句点句点“ .”表示可以匹配除换行符之外的任意单个符。表示可以匹配除换行符之外的任意单个符。利用这个字符就可为利用这个字符就可为所有包含至少一个所有包含至少一个b 的串的串写出写出

22、一个一个正则表达式正则表达式，如下所示：，如下所示： .*b .*3.引号引号“ ”，引号中的字符串表示文本字符，引号中的字符串表示文本字符串本身。例如：串本身。例如：“.”表示要匹配表示要匹配.字符本身。字符本身。mcy374.字符字符范围范围：表示法表示法a|b|z 表示所有小写字母；表示所有小写字母；0|1|9表示表示0到到9间的所有数字；间的所有数字；常见的表示法是利用常见的表示法是利用方括号方括号和和一个连字符一个连字符，如，如a-z是指所有小写字母，是指所有小写字母，0-9则指数字。则指数字。第二种表示法还可用作表示单个的解，第二种表示法还可用作表示单个的解，a|b|c可写成可写成

23、abc，它还可用于多个范围，它还可用于多个范围，如如 a - z A - Z 代表所有的大小写字母。代表所有的大小写字母。mcy385. 正规表达式的正规表达式的名字名字为较长的正则表达式提供一个简化的名字很有用为较长的正则表达式提供一个简化的名字很有用处，这样就不用每次使用正则表达式书写较长的处，这样就不用每次使用正则表达式书写较长的表达式本身了；表达式本身了；如要写一个正则表达式如要写一个正则表达式: a - z A - Z ( a - z A - Z 0-9 ) 它定义的正规集为：以字母打头后跟若干字母或它定义的正规集为：以字母打头后跟若干字母或数字组成的符号串的集合数字组成的符号串的集

24、合。mcy39上述正规式上述正规式定义的是程序设计语言定义的是程序设计语言标识符标识符的的词法词法规则规则，通过为，通过为正规表达式提供一个简化的名字，正规表达式提供一个简化的名字，上述正规表达式可写作：上述正规表达式可写作： letter= a - z A - Z digit=0-9 r=letter(letter digit) mcy40例：写出正则表达式例：写出正则表达式signedNatnat=0-9+signedNat=nat|+ nat|- nat对应的正规集？对应的正规集？mcy416.可选的子表达式（可选的子表达式（？）：）：w如果在特定的串中包括既可能出现又可能不出现如果在特

25、定的串中包括既可能出现又可能不出现的可选部分。例如，的可选部分。例如， nat=0-9+ signedNat=nat|+nat|-natw我们可以引入问号我们可以引入问号?来表示来表示r 匹配的串是可选的；上面的匹配的串是可选的；上面的例子可写成：例子可写成：nat=0-9 +signedNat=(+|-)？natmcy422.2.1 基本概念和术语基本概念和术语2.2.2 正规表达式的定义正规表达式的定义2.2.3 正规表达式基本等价关系正规表达式基本等价关系2.2.4 正规表达式的扩展正规表达式的扩展2.2.5 单词的正规表达式举例单词的正规表达式举例2.22.2正规表达式正规表达式mcy

26、432.2.5 2.2.5 单词的正规表达式举例单词的正规表达式举例每一种程序设计语言都有自己的字符集每一种程序设计语言都有自己的字符集( (字母表字母表) ) 。语言中的各个语言中的各个单词单词或是或是 上的单个字符上的单个字符( (如运算符、如运算符、分隔符等分隔符等) )，或是，或是 上的字符串上的字符串( (如常数、表示符和关如常数、表示符和关键字等键字等) )。程序设计语言的程序设计语言的单词单词都能用都能用正规式正规式来定义来定义. .由正规式由正规式描述的描述的单词类单词类也称为也称为正规集正规集。 例如：例如：C-语言的词法语言的词法mcy441.1.数：数： nat= 0-9

27、+signedNat=(+|-)? natnumber=signedNat(“.”nat)?(“E” signedNat)?例如：例如：3, 3.5, 2.71E-22.2.保留字：保留字：reserved=else|if |int|return|void|while mcy453.3.标示符：标示符：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*mcy46 包含单词词法描述的包含单词词法描述的语言手册语言手册是编译是编译器的程序员最常见的。在下面的示例器的程序员最常见的。在下面的示例中，被匹配的串是汉语描述，其任务中，被匹配的串是

28、汉语描述，其任务是将描述是将描述翻译为正则表达式翻译为正则表达式。mcy471)在字母表在字母表 = a, b, c中，考虑在这个字中，考虑在这个字母表上的母表上的仅包括一个仅包括一个b 的所有串的集合的所有串的集合，这个集合所对应的正则表达式为：这个集合所对应的正则表达式为： 串串b、abc、abaca、baaaac、ccbaca和和ccccccb等都是满要求的等都是满要求的符号串。符号串。(a|c)*b(a|c)*mcy482)在字母表在字母表 = a, b, c中，中，如果字符串集合是如果字符串集合是包括最包括最多一个多一个b 的所有串的所有串，则这个集合的正则表达式为：，则这个集合的正

29、则表达式为：仅包括一个仅包括一个b 的串的集合对应的正则表达式的串的集合对应的正则表达式 (a|c)*b(a|c)*不包括不包括b 的串的集合对应的正则表达式的串的集合对应的正则表达式 (a|c)*故所求表达式为：故所求表达式为：(a|c)* | (a|c)*b(a|c)*或者为或者为:(a|c)*(b| )(a|c)*mcy493)在在字母表字母表 = a, b上串上串S的集合是由一个的集合是由一个b及及在其前后有相同数目的在其前后有相同数目的a 组成：组成： S = b, aba, aabaa, aaabaaa, . . . = anban | n0 正则表达式并不能描述这个集合正则表达式

30、并不能描述这个集合，其原因在于重复运，其原因在于重复运算只有闭包运算算只有闭包运算*一种，它允许有任意次的重复。因此一种，它允许有任意次的重复。因此如要写出表达式如要写出表达式a*ba*，就不能保证在，就不能保证在b 前后的前后的a 的数的数量是否相等了。量是否相等了。mcy50w并非用简单术语描述的所有串都可由并非用简单术语描述的所有串都可由 正则表正则表达式产生，因此为了与其他集合相区分，作达式产生，因此为了与其他集合相区分，作为正则表达式描述的串集合称作正规集为正则表达式描述的串集合称作正规集(regular set)。w非正规集偶尔也作为串出现在需要由扫描程非正规集偶尔也作为串出现在需

31、要由扫描程序识别的程序设计语言中。序识别的程序设计语言中。mcy51第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正规表达式正规表达式 2.3 有穷自动机有穷自动机2.4 从正规表达式到从正规表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析程序自动生成词法分析程序记号的描记号的描述工具述工具记号的识记号的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序作业作业课程设计课程设计1 1 mcy522.3.1有穷自动机的引入有穷自动机的引入2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义

32、2.3.3非确定性有穷自动机非确定性有穷自动机(NFA) 2.32.3有穷自动机有穷自动机mcy532.3.1 2.3.1 有穷自动机的引入有穷自动机的引入有穷自动机有穷自动机( (也称有限自动机也称有限自动机) )作为一种数学模作为一种数学模型型，它能准确地识别正规集，即识别正规式所它能准确地识别正规集，即识别正规式所表示的集合。表示的集合。有穷自动机是有穷自动机是设计和实现词法分析器设计和实现词法分析器的有效的有效工具，其直观图是一种状态转换图。工具，其直观图是一种状态转换图。引入有穷自动机理论，也是为词法分析程序引入有穷自动机理论，也是为词法分析程序的自动构造寻找方法和工具。的自动构造寻

33、找方法和工具。mcy54有穷自动机有穷自动机( (Finite Automata,or finite-state machines) )有穷自动机分为两类：有穷自动机分为两类：确定的有穷自动机确定的有穷自动机( (Deterministic Finite Automata) )。不确定的有穷自动机不确定的有穷自动机( (Nondeterministic Finite Automata) )。mcy55在程序设计语言中，用正规式在程序设计语言中，用正规式定义定义的标示符的标示符如下：如下： letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)

34、* 该正规式匹配的标示符是以一个字母开头且该正规式匹配的标示符是以一个字母开头且其后为任意字母、数字序列形成的字符串。其后为任意字母、数字序列形成的字符串。mcy5612letterletterdigit标示符的有穷自动机标示符的有穷自动机变量变量xtempxtemp 识别为标示符的过程可表示为：识别为标示符的过程可表示为：1x2t2e2m2p2 标示符模式的标示符模式的识别识别过程：过程：mcy572.3.1有穷自动机的引入有穷自动机的引入2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2.3.3非确定性有穷自动机非确定性有穷自动机(NFA) 2.32.3有穷自动机有穷自动机

35、mcy582.3.22.3.2确定性有穷自动机（确定性有穷自动机（DFADFA）的定义的定义DFA(DFA(确定性有穷自动机确定性有穷自动机) )有五个部分组成：有五个部分组成：(1)(1)有限个输入符号组成的字母表有限个输入符号组成的字母表, ,记作记作 ; ;(2)(2)有限个状态的集合有限个状态的集合, ,记作记作S S; ;(3)(3)转换函数转换函数T T T: T: S S S S 即：即：T(s,c)= sT(s,c)= s 其中其中s s S S，s s S S， c c上述转换函数表示若当前状态为上述转换函数表示若当前状态为s s, ,且当前识别的输入且当前识别的输入符号为符

36、号为c c, ,识别识别c c后进入的下一个状态为后进入的下一个状态为s s ; ;mcy59(4)(4)初始状态初始状态s s0 0 S S; ;指示识别符号串的开始状态指示识别符号串的开始状态; ;(5)(5)若干个若干个识别符号串的识别符号串的接受状态接受状态( (或称为终止状或称为终止状 态态) )的集合的集合 A A S S ; ;( (由上述五个要素组成的五元式由上述五个要素组成的五元式M=(S;M=(S; ;T;s;T;s0 0;A);A)称为一称为一个确定的有限自动机个确定的有限自动机 ( (DFADFA: : D Deterministic eterministic F Fi

37、nite inite A Automatautomata) )。mcy60DFA MDFA M= =（ss1 1,s,s2 2 ,s,s3 3 ,s,s4 4,a,b,T,s,a,b,T,s1 1,s,s4 4 ）其中其中转换函数转换函数T T定义为：定义为：T(s1,a)= s2 T(s3,a)=s2 T(s1,b)=s3 T(s3,b)=s4T(s2,a)=s4 T(s4,a)=s4T(s2,b)=s3 T(s4 ,b)=s4一个一个DFA DFA 的例子：的例子：有限个状有限个状态的集合态的集合s s字母表字母表 初始状态初始状态接受状接受状态的集合态的集合A Amcy61状态转换图状态

38、转换图一个一个DFADFA可以表示成一个状态图可以表示成一个状态图( (或称或称状状态转换图态转换图) )。状态转换图是由一组矢线。状态转换图是由一组矢线连结的有限个结点所组成的有向图。连结的有限个结点所组成的有向图。例如：例如：s s0 0s s2 20s s1 110mcy62假定假定DFA MDFA M含有含有m m个状态，那么这个状态图个状态，那么这个状态图就含有就含有m m个结点；结点用小圆圈表示，个结点；结点用小圆圈表示，圆圈圆圈中标入状态的名字中标入状态的名字或编号。或编号。为了醒目起见，用为了醒目起见，用箭头指示初始状箭头指示初始状态，用双圆圈表示终止转态。态，用双圆圈表示终止

39、转态。s s结点结点s s0 0初始状态初始状态s sn n接受状态接受状态mcy63s sas s状态转换的图形表示状态转换的图形表示w若若 T(s,a)=s ，则从状态结点则从状态结点s到状态结点到状态结点s画标记为画标记为a的矢线。的矢线。表示当词法分析器处于该矢线的结点所指示的表示当词法分析器处于该矢线的结点所指示的状态状态s时，可能要识别的输入字符为时，可能要识别的输入字符为a，而矢线而矢线进入的结点进入的结点s则指示识别相应的输入字符则指示识别相应的输入字符a后后进入的下一个状态。进入的下一个状态。mcy64 例：例： M=(s0 0, s1 1, s2 2, 0,1, T, s0

40、 0, s2 2) 其其中中, ,T的定义如下：的定义如下： T(s0 0,0)= s1 1 T(s1 1,0)= s1 1 T(s1 1,1)= s2 2 s s0 0s s2 20s s1 110状态转换图举例状态转换图举例上述上述DFADFA对应的状态转换图：对应的状态转换图：mcy65w在状态转换图中，从一个结点可以同时引出若干在状态转换图中，从一个结点可以同时引出若干条矢线到有向图中的其余结点条矢线到有向图中的其余结点(也可从一结点引矢也可从一结点引矢线到其自身线到其自身)；w每一矢线上均标记一个字符或字符类记号，表示每一矢线上均标记一个字符或字符类记号，表示当词法分析器处于该矢线的

41、结点所指示的状态时，当词法分析器处于该矢线的结点所指示的状态时，可能要识别的输入字符，而矢线进入的结点则指可能要识别的输入字符，而矢线进入的结点则指示识别相应的输入字符后进入的下一个状态。示识别相应的输入字符后进入的下一个状态。mcy66DFADFA的接受集的接受集( (即识别的字符串集合即识别的字符串集合) )DFA识别的字符串识别的字符串c c1 1 c c2 2 c cn n的集合的集合满足如下满足如下条件：每个条件：每个c ci i ，且存在状态，且存在状态 s1= T(s0 ，c1), s2= T(s1 ，c2), , sn= T(sn-1 ，cn), 其中其中s0 是初态，是初态，

42、 sn 是终态。是终态。mcy67s s0 0c c1 1s s1 1c c2 2s s2 2s sn-1n-1c cn ns sn nc c3 3c cn-1n-1v字符串字符串c c1 1 c c2 2 c cn n若被若被DFA识别，则在状态识别，则在状态转换图中存在一条从初态到终态的有向路经，转换图中存在一条从初态到终态的有向路经，该路径上所有该路径上所有矢线上方的字符连接在一起即是矢线上方的字符连接在一起即是字符串字符串c c1 1 c c2 2 c cn nvDFA M识别的字符串的集合识别的字符串的集合 记作记作L(M)mcy68bs1s2s3s4abba | baa例：证明字符

43、串序列例：证明字符串序列baabbaab被下图的被下图的DFADFA所接受。所接受。任意列出它接受的另外两个输入串？任意列出它接受的另外两个输入串？任意列出它拒绝接受的两个输入串？任意列出它拒绝接受的两个输入串？mcy69证明：由于存在证明：由于存在T(sT(s1 1,b,b）= s= s3 3T(sT(s3 3,a,a）= s= s2 2T(sT(s2 2,a,a）= s= s4 4T(sT(s4 4,b,b）= s= s4 4s s4 4属于终态，得证。属于终态，得证。mcy70(1).状态转换图中的状态转换图中的状态状态可以使用可以使用任何标识任何标识系统系统来标识来标识(2).状态转换

44、图中的状态转换图中的转换转换可以使用可以使用字符集合字符集合的名字的名字标出标出关于关于DFADFA的状态转换图的的状态转换图的2 2点说明点说明startin_idletterletterdigitmcy7112digitdigit例例1：自然数的集合自然数的集合被下图所示的被下图所示的DFA接受。接受。注：注：digit=0-9DFADFA的示例的示例mcy72例例2：字母表字母表 = a, b, c上上有且仅有一个有且仅有一个b构成构成的字符串集合的字符串集合被下图所示的被下图所示的DFA接受。接受。12bnotbnotb注：注：notb= a, cmcy73例例3：字母表字母表 = a

45、, b, c上上包含最多一个包含最多一个b构构成的字符串的集合成的字符串的集合被下图所示的被下图所示的DFA接受。接受。2bnotbnotb1注：注：notb= a, cmcy74例例4：有：有C风格注释的风格注释的DFA15/other12*3*4*/other2注：注：other1other1表示除表示除* *之外的所有字符的集合的名字；之外的所有字符的集合的名字； other2 other2表示除表示除* *,/,/之外的所有字符的集合的名字。之外的所有字符的集合的名字。mcy752.3.1有穷自动机的引入有穷自动机的引入2.3.2确定性有穷自动机确定性有穷自动机(DFA)的定义的定义2

46、.3.3非确定性有穷自动机非确定性有穷自动机(NFA) 2.32.3有穷自动机有穷自动机mcy762.3.32.3.3非确定性有穷自动机（非确定性有穷自动机（NFANFA）下图是识别下图是识别 = =、, , 字符串的一个字符串的一个有穷自动机，对于输入符号有穷自动机，对于输入符号,在状态在状态0 0上上存在不止一种转换。存在不止一种转换。 153024mcy77w有穷自动机对于某个输入符号，如果有穷自动机对于某个输入符号，如果在同一个状态上存在不止一种转换，在同一个状态上存在不止一种转换，我们称该有穷自动机为不确定的有穷我们称该有穷自动机为不确定的有穷自动机。自动机。w在给出非确定性有穷自动

47、机的定义之在给出非确定性有穷自动机的定义之前先引入前先引入 - -转换转换的概念。的概念。mcy78 - -转换转换是无需考虑输入串就有可能发生的是无需考虑输入串就有可能发生的转换。它可看作是一个空串转换。它可看作是一个空串 的的“匹配匹配”， - -转换的图形表示为：转换的图形表示为：0 0 1 1 - -转换的引入转换的引入 - -转换转换可以清晰地描述出空串的匹配：可以清晰地描述出空串的匹配：0 0 1 1mcy790 - -转换转换可以通过添加一个新的初始状态来链接各个可以通过添加一个新的初始状态来链接各个自动机，从而将它们合并为一个自动机。自动机，从而将它们合并为一个自动机。将识别数

48、字将识别数字和字符的两个和字符的两个DFADFA和并为一个非确定的有穷自动机：和并为一个非确定的有穷自动机：letterletterletterletterDONE2DONE2START2START2START1START1digitdigitdigitdigitDONE1DONE1mcy800 123: := =675 = =89= =通过通过 - -转换将识别转换将识别:=:=、=、= =的的DFADFA合并为：合并为：mcy81NFA( (非确定性有穷自动机非确定性有穷自动机) )有五个部分组成：有五个部分组成：(1)(1)有限个输入符号组成的字母表有限个输入符号组成的字母表, ,记作记

49、作 ; ;(2)(2)有限个状态的集合有限个状态的集合, ,记作记作S S; ;(3)(3)转换函数转换函数T T; ; T: T: S S ( ( )(S)(S), , T(s,c)= s T(s,c)= sk1, s skm 表示若当前状态为表示若当前状态为s s S S, ,且要识别的输入符号为且要识别的输入符号为c c , , 识识别别c c后进入的状态是后进入的状态是S S的一个状态的一个状态子集子集ssk1, s skm ; ;2.3.22.3.2非确定性有穷自动机（非确定性有穷自动机（NFANFA）的定义的定义mcy82(4)(4)初始状态初始状态s s0 0 S S; ;(5)

50、(5)若干个接受状态的集合若干个接受状态的集合: : A A S S 由上述五个要素组成的五元式由上述五个要素组成的五元式 M=(SM=(S； ； T T； s s0 0 ； A )A )称为一个非确定的有限称为一个非确定的有限自动机自动机 ( (NFANFA: : Nondeterministicondeterministic F Finite inite A Automatautomata),),由上述定义由上述定义可以看出，可以看出，DFADFA是是NFANFA的一个的一个特例。特例。mcy83一个一个NFA NFA 的例子：的例子：NFA M=NFA M=（SS，P P，ZZ，00，1

51、1，T T，SS，ZZ）其中其中 T T（S S，0 0）=P; =P; T T（Z Z，0 0）=P;=P; T T（P P，1 1）=Z; T=Z; T（Z Z，1 1）=P;=P; T T（S S，1 1）=S=S，Z;Z;mcy84NFANFA的状态转换图的状态转换图例：例：M=( , = , 0，1，2，3，4，5 , T, 0, 2，4，5 ) 其中其中T的定义如下：的定义如下：T(0,) = 4 153024mcy85NFA M 的的接受集接受集记作记作L(M)L(M)L(M)定义为定义为字符串字符串c c1 1c c2 2 c cn n的集合的集合，其中每个，其中每个c ci

52、i ，且存在：，且存在：s s1 1 T(T(s s0 0 , ,c c1 1) ), ,s s2 2 T(T(s s1 1, ,c c2 2),), ,s sn n T(T(s sn-1 n-1 , ,c cn n),),其中其中s s0 0是初态，是初态， s sn n是终态集中的一个元素。是终态集中的一个元素。NFANFA的接受集的接受集mcy86例：考虑下面的例：考虑下面的NFA图。图。231a aa ab b4 这个这个NFA接受集与正接受集与正则表达式则表达式ab+|ab*|b*对应的对应的正规集相同。正规集相同。列举两个转换序列都可接受串列举两个转换序列都可接受串abb？1a2b

53、4 2b41a3 4 2b4 2b4mcy87第第2 2章章 词法分析词法分析2.1 词法分析器的作用词法分析器的作用2.2 正规表达式正规表达式 2.3 有穷自动机有穷自动机2.4 从正规表达式到从正规表达式到DFA 2.5 用代码实现有穷自动机用代码实现有穷自动机2.6 利用利用lex自动生成词法分析自动生成词法分析程序程序记号的描记号的描述工具述工具记号的识记号的识别系统别系统设计和设计和实现词实现词法分析法分析程序程序作业作业课程设计课程设计1 1 mcy882.42.4从正规表达式到从正规表达式到DFADFA正规表达式正规表达式DFA词法分析程序词法分析程序NFA正规式正规式是单词的

54、一种描述工具。由于正规是单词的一种描述工具。由于正规式的简洁性，趋向于先用式的简洁性，趋向于先用正规式来描述单正规式来描述单词词，然后，然后构造等价的有限自动机构造等价的有限自动机。有限自动机有限自动机可以描述输入串被识别的过可以描述输入串被识别的过程，我们可以根据有限自动机程，我们可以根据有限自动机构造构造我们的我们的词法分析程序词法分析程序。mcy89正规式正规式和和有限自动机有限自动机之间可以之间可以相互转换相互转换，也就是说它们之间存在着也就是说它们之间存在着等价性等价性，即，即：1)1)对于对于上的上的NFA M，可以构造一个可以构造一个上的上的正规式正规式R，使得：使得：L(R)=

55、L(M)2)2)对于对于上的每个正规式上的每个正规式R，可以构造一个可以构造一个上的上的NFA M，使得：使得：L(M)=L(R)mcy902.4.1 从正规表达式到从正规表达式到NFA2.4.2 从从NFA 到到DFA2.4.3 将将DFA中的状态数最小化中的状态数最小化2.42.4从正规表达式到从正规表达式到DFADFAmcy912.4.1 2.4.1 从正规表达式到从正规表达式到NFANFA从正规表达式到从正规表达式到NFA的转化方法按正规式的运算的转化方法按正规式的运算指引构造过程，指引构造过程，将正规式分解为一系列子表达式，将正规式分解为一系列子表达式，然后将子表达式对应的然后将子表

56、达式对应的NFA依次连接而成依次连接而成，正规正规式式R转化为转化为NFA M 的基本步骤：的基本步骤：mcy92(b)对正规式对正规式，等价的等价的NFA为：为： 0 0 1 1 (a)对正规式对正规式，等价的等价的NFA为：为： 0 01 1(c)对正规式对正规式a，等价的等价的NFA为：为： 0 0a a1 11. 基本正规式转换为基本正规式转换为NFA M的方法：的方法： mcy930 0R R1 12. 复合正规式复合正规式R转换为转换为NFA M的方法：首先将复的方法：首先将复合正规表达式表示成如下合正规表达式表示成如下拓广的状态转换图拓广的状态转换图，然后按照正规式的运算然后按照

57、正规式的运算(以下以下(a),(b),(c),(d)四种四种情况情况)递归生成递归生成NFA Mmcy94(b)若若R=rs,则将则将 代之以代之以 0 01 1rsrs0 01 1r r2 2s s(a)若若R=r|s,则将则将 代之以代之以 0 01 1r|sr|s0 01 1r rs smcy95(c)若若R=r*,则将则将 代之以代之以 0 01 1r r*0 01 12 2 r r(d)正规式正规式R=（r）的的NFA同正规式同正规式 R=r的的NFA相同相同mcy96例例1 1, ,设有正规表达式设有正规表达式R=ab|a, ,试构造试构造NFA M，使使L(R)=L(M)。（1

58、1）0 0ab|aab|a1 1（2 2）0 0abab1 1a a（3 3）0 01 1a a2 2a ab bmcy97例例2 2，设有正规表达式，设有正规表达式letter(letter|digit)letter(letter|digit)* *, ,试构造与之等试构造与之等价的价的NFANFA。（1 1）0 0letter(letter|digit)letter(letter|digit)* *1 1（2 2）0 0(letter|digit)(letter|digit)* *1 1letterletter2 2mcy98（3 3）0 0(letter|digit)(letter|di

59、git)1 1letterletter2 2 3 3（4 4）0 0letterletter1 1letterletter2 2 3 3digitdigitmcy992.4.1 从正规表达式到从正规表达式到NFA2.4.2 从从NFA 到到DFA2.4.3 将将DFA中的状态数最小化中的状态数最小化2.42.4从正规表达式到从正规表达式到DFADFAmcy1002.4.2 2.4.2 从从NFANFA 到到DFADFAw对任一对任一NFA M，总可构造一个总可构造一个DFA M，使使 L(M)=L(M)成立。这就是成立。这就是NFA与与DFA的等价性。的等价性。w定理定理 对于字母表对于字母表

60、 上的任一上的任一NFA M，必存在与必存在与M等等价的价的DFA M (即有即有 L(M)=L(M) 成立成立) 。在给出具体的构造算法之前先引入在给出具体的构造算法之前先引入状态状态s和状态和状态集合集合S的的 -闭包的概念：闭包的概念：mcy101（1）状态状态s的的 -闭包闭包：定义为从：定义为从s出发可由一系出发可由一系列的零个或多个列的零个或多个 -转换转换能达到能达到的状态的集合，的状态的集合，并将这个集合记为并将这个集合记为（2）状态集合）状态集合S的的 -闭包闭包:定义为定义为S中各个状态中各个状态的的 -闭包的并集闭包的并集s s- -mcy1021 14 42 2a a