第三章 词法分析(3).ppt

《第三章 词法分析(3).ppt》由会员分享，可在线阅读，更多相关《第三章 词法分析(3).ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、南京邮电大学计算机学院蒋凌云 教材：编译技术原理及其实现方法王汝传 编著编编 译译 原原 理理 Compiler Principles1 1 第三章 词 法 分 析3.1 3.1 引言引言 一、词法分析基本思想 二、词法分析任务 三、词法分析方式 四、词法分析方法3.2 3.2 单词的内部编码单词的内部编码 一、单词 二、内部编码3.3 3.3 正规文法和状态转换图正规文法和状态转换图 一、正规文法 二、状态转换图 三、正规文法与状态转换图3.4 3.4 词法分析程序设计与实现词法分析程序设计与实现 一、源程序的输入 二、缓冲区及预处理 三、超前搜索 四、由词法语法规则画状态转换图 五、词法分

2、析程序的设计与实现3.5 3.5 正规文法和有穷自动机正规文法和有穷自动机 一、用正规文法描述单词 二、由正规文法构造状态转换图 三、有穷自动机FA 四、有穷自动机和正规文法的关系 五、DFA与NFA的关系3.6 3.6 正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义 二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机 四、由正规表达式构造确定有穷自动机 五、确定有穷自动机的化简3.7 3.7 词法分析程序的自动生成词法分析程序的自动生成 一、问题的提出 二、语言LEX一般描述 三、LEX编译程序的实现 四、LEX目标程序2 2 第三章 词 法 分 析3.6

3、3.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自

4、动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法3 33.63.6正规表达式和有穷自动机正规表达式和有穷自动机 由正规文法构造状态转换图，再根据状态转换由正规文法构造状态转换图，再根据状态转换图可以构造有穷自动机，往往很麻烦，但是，图可以构造有穷自动机，往往很麻烦，但是，对于一些复杂的正规文法，如果将其先转换成对于一些复杂的正规文法，如果将其先转换成正规表达式，再由正规表达式来产生有穷自动正规表达式，再由正规表达式来产生有穷自动机就方便得多。而且正规表达式的引入有助于机就方便得多。而且正规表达式的引入有助于词法分析程序的自动生成

5、，它还广泛应用于模词法分析程序的自动生成，它还广泛应用于模式识别和文献目录检索等。式识别和文献目录检索等。为什么引入正规表达式？为什么引入正规表达式？4 4什么叫正规表达式？什么叫正规表达式？首先我们来看一个例子，如：对于数字集合首先我们来看一个例子，如：对于数字集合首先我们来看一个例子，如：对于数字集合首先我们来看一个例子，如：对于数字集合D=0D=0D=0D=0，1 1 1 1，2 2 2 2，9999，现在要用一个表达式刻画符号串现在要用一个表达式刻画符号串现在要用一个表达式刻画符号串现在要用一个表达式刻画符号串20202020这个数，可以将这个数，可以将这个数，可以将这个数，可以将20

6、202020看成看成看成看成2 2 2 2和和和和0 0 0 0组成的符号串，也可以用组成的符号串，也可以用组成的符号串，也可以用组成的符号串，也可以用4*54*54*54*5表示，或用表示，或用表示，或用表示，或用0+1+2+3+4+9+9-80+1+2+3+4+9+9-80+1+2+3+4+9+9-80+1+2+3+4+9+9-8表示。同样，在词法分析阶段，我们也要表示。同样，在词法分析阶段，我们也要表示。同样，在词法分析阶段，我们也要表示。同样，在词法分析阶段，我们也要解决某字母表解决某字母表解决某字母表解决某字母表 上语言的表示问题（所谓语言就是上语言的表示问题（所谓语言就是上语言的表

7、示问题（所谓语言就是上语言的表示问题（所谓语言就是 *上一个上一个上一个上一个子集，即某些符号串集合。）子集，即某些符号串集合。）子集，即某些符号串集合。）子集，即某些符号串集合。）例如：例如：例如：例如：0,10,10,10,1上一个语言上一个语言上一个语言上一个语言L(G)=xL(G)=xL(G)=xL(G)=xx x x x以以以以0 0 0 0开头后面跟任开头后面跟任开头后面跟任开头后面跟任意个意个意个意个1 1 1 1，这可以采用如下方法表示：这可以采用如下方法表示：这可以采用如下方法表示：这可以采用如下方法表示：枚举法：枚举法：枚举法：枚举法：L L L L（G G G G）=0=

8、0=0=0，01010101，011011011011，0111011101110111 文法生成法文法生成法文法生成法文法生成法 Z=0|Z1Z=0|Z1Z=0|Z1Z=0|Z1自动机识别法：可以构造一个自动机识别法：可以构造一个自动机识别法：可以构造一个自动机识别法：可以构造一个DFADFADFADFA来识别该语言来识别该语言来识别该语言来识别该语言正规表达式：正规表达式：正规表达式：正规表达式：可用正规表达式来表示一个正规语言，象用可用正规表达式来表示一个正规语言，象用可用正规表达式来表示一个正规语言，象用可用正规表达式来表示一个正规语言，象用4*54*54*54*5表示表示表示表示20

9、202020一样，可以用一样，可以用一样，可以用一样，可以用0 0 0 0（1 1 1 1）*表示表示表示表示0 0 0 0后跟若干个后跟若干个后跟若干个后跟若干个1 1 1 1的二进制的二进制的二进制的二进制数。数。数。数。5 5 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达

10、式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法6 6 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正

11、规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法7 7 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式

12、和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念

13、等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法8 83.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集定义一、正规表达式和正规集定义 1.1.非形式定义非形式定义非形式定义非形式定义 用来表示字母表用来表示字母表用来表示字母表用来表示字母表 上字符串集合上字符串集合上字符串集合上字符串集合 *某些子集，经过运算符某些子集，经过运算符某些子集，经过运算符某些子集，经过运算符|（和）、（和）、（和）、（和）、（连接）、（连接）、（连接）、（连接）、*（闭包）以及决定运算顺序的括号组合成一个有意义的集合运（闭包）以及决定运算顺序的括号组合成

14、一个有意义的集合运（闭包）以及决定运算顺序的括号组合成一个有意义的集合运（闭包）以及决定运算顺序的括号组合成一个有意义的集合运算式，称为正规表达式；算式，称为正规表达式；算式，称为正规表达式；算式，称为正规表达式；正规表达式的值称正规集。正规表达式的值称正规集。正规表达式的值称正规集。正规表达式的值称正规集。注意注意注意注意：正规表达式是表示运算的一个式子，而正规集是一个符号串集：正规表达式是表示运算的一个式子，而正规集是一个符号串集：正规表达式是表示运算的一个式子，而正规集是一个符号串集：正规表达式是表示运算的一个式子，而正规集是一个符号串集合，是正规表达式的运算结果。合，是正规表达式的运算

15、结果。合，是正规表达式的运算结果。合，是正规表达式的运算结果。例如上面的例子，例如上面的例子，例如上面的例子，例如上面的例子，0,10,10,10,1其其其其0 0 0 0（1 1 1 1）*是正规表达式，是正规表达式，是正规表达式，是正规表达式，而集合而集合而集合而集合0000，01010101，011011011011，0111011101110111 是是是是0 0 0 0开头后面跟任意个开头后面跟任意个开头后面跟任意个开头后面跟任意个1 1 1 1，是，是，是，是正规集，也可正规集，也可正规集，也可正规集，也可以写成以写成以写成以写成 0 0 0 0（1 1 1 1）*0000，010

16、10101，011011011011，0111011101110111 运算优先级：运算优先级：*,|,|9 9 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动

17、机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法10103.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集定义一、正规表达式和正规集定义 2.2.2.2.递归定义递归定义递归定义递归定义 令令令令为为为为有有有有穷穷穷穷字母表，字母表，字母表，字母表，则则则则上的正上的正上的正上的正规规规规式和正式和正式和正式和正规规规规集可集可集可集可递归递归递归递归定定定

18、定义义义义如下：如下：如下：如下：.和和和和是是是是上的正上的正上的正上的正规规规规式，式，式，式，则则则则它它它它们们们们相相相相应应应应正正正正规规规规集分集分集分集分别为别为别为别为和和和和；.对对对对于每一于每一于每一于每一aaaa，a a a a是是是是上一个正上一个正上一个正上一个正规规规规式，式，式，式，则则则则它所表示相它所表示相它所表示相它所表示相应应应应正正正正规规规规集集集集为为为为a a a a；.如果如果如果如果e1e1e1e1和和和和e e e e是是是是上的正上的正上的正上的正规规规规式，式，式，式，则则则则相相相相应应应应正正正正规规规规集分集分集分集分别为别为

19、别为别为L L L L（e1)e1)e1)e1)和（和（和（和（e2)e2)e2)e2)，则则则则 (1)(e1)(1)(e1)(1)(e1)(1)(e1)是正规式，其相应的正规集为是正规式，其相应的正规集为是正规式，其相应的正规集为是正规式，其相应的正规集为L L L L（e1e1e1e1）=L=L=L=L（e1e1e1e1）（2 2 2 2）e1e1e1e1e e e e是是是是正正正正规规规规式式式式，其其其其相相相相应应应应正正正正规规规规集集集集为为为为（e1e1e1e1e e e e）（e1e1e1e1）（e e e e）;（3 3 3 3）e1e1e1e1 e2e2e2e2是正规

20、式，其相应正规集为（是正规式，其相应正规集为（是正规式，其相应正规集为（是正规式，其相应正规集为（e1e1e1e1 e2e2e2e2）（e1e1e1e1）（e2e2e2e2）；）；）；）；（4 4 4 4）（）（）（）（e1e1e1e1）*是正规式，其相应正规集为（是正规式，其相应正规集为（是正规式，其相应正规集为（是正规式，其相应正规集为（e1e1e1e1）*）(（e e e e）)*。1111例例例例3.5 3.5 3.5 3.5 设设设设a,ba,ba,ba,b，下列各式：下列各式：下列各式：下列各式：a a a a*babababa*a a a ababababa*aaaaaaaabb

21、bbbbbbababababbabababa a(a a(a a(a a(ab)b)b)b)*(a (a (a (ab)b)b)b)*(aaaaaaaabb)(abb)(abb)(abb)(ab)b)b)b)*(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)*均是均是均是均是上正规式，则它们相应的正规集分别是上正规式，则它们相应的正规集分别是上正规式，则它们相应的正规集分别是上正规式，则它们相应的正规集分别是(a(a(a(a*）（）（）（）（(a(a(a(a）*a a a a*,a,

22、aa,aaa,a,aa,aaa,a,aa,aaa,a,aa,aaa,(babababa*）(b(b(b(b）L(aL(aL(aL(a*)b,ba,baab,ba,baab,ba,baab,ba,baa,(a(a(a(ababababa*）（）（）（）（a a a a）L(baL(baL(baL(ba*)*)*)*)a,b,ba,baaa,b,ba,baaa,b,ba,baaa,b,ba,baa,L(aaL(aaL(aaL(aabbbbbbbbababababbabababa)L(aa)L(bb)L(ab)L(baL(aa)L(bb)L(ab)L(baL(aa)L(bb)L(ab)L(baL(a

23、a)L(bb)L(ab)L(ba)aa,bb,ab,baaa,bb,ab,baaa,bb,ab,baaa,bb,ab,ba （a(aa(aa(aa(ab)b)b)b)*）L(a)(L(a)L(bL(a)(L(a)L(bL(a)(L(a)L(bL(a)(L(a)L(b)*aa,baa,baa,baa,b *（(a(a(a(ab)b)b)b)*(aaaaaaaabb)(abb)(abb)(abb)(ab)b)b)b)*）a,ba,ba,ba,b *aa,bba,baa,bba,baa,bba,baa,bba,b *L(a|b)(a|b)(a|b)(a|bL(a|b)(a|b)(a|b)(a|bL(

24、a|b)(a|b)(a|b)(a|bL(a|b)(a|b)(a|b)(a|b)*)=)=)=)=L(a|b)L(a|b)L(a|b)L(a|bL(a|b)L(a|b)L(a|b)L(a|bL(a|b)L(a|b)L(a|b)L(a|bL(a|b)L(a|b)L(a|b)L(a|b)*)=a,ba,ba,ba,ba,ba,ba,ba,ba,ba,ba,ba,ba,ba,ba,ba,b *1212 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达

25、式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法1313 第三章 词 法 分 析3.63.6正规表达式和有穷

26、自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等

27、价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法14143.63.6正规表达式和有穷自动机正规表达式和有穷自动机 二、正规表达式的性质二、正规表达式的性质1.1.1.1.若两个正规式所表示正规集相同，则认为两者等价若两个正规式所表示正规集相同，则认为两者等价若两个正规式所表示正规集相同，则认为两者等价若两个正规式所表示正规集相同，则认为两者等价。两个正规式两个正规式两个正规式两个正规式e1e1e1e1和和和和e2e2e2e2等价，记为等价，记为等价，记为等价，记为e1e1e1e1e2 e2 e2 e2。例如：例如：例如：例如：e1=e1=e1=e1=

28、b(abb(abb(abb(ab)*,e2=(,e2=(,e2=(,e2=(babababa)*b b b b因为因为因为因为 L(e1)=L(e1)=L(e1)=L(e1)=L(b(abL(b(abL(b(abL(b(ab)*)=)=)=)=L(b)(L(abL(b)(L(abL(b)(L(abL(b)(L(ab)*=babbabbabbab *=b,bab,bababb,bab,bababb,bab,bababb,bab,babab,L(e2)=L(e2)=L(e2)=L(e2)=L(baL(baL(baL(ba)*b)=(b)=(b)=(b)=(L(baL(baL(baL(ba)*L(b

29、)=L(b)=L(b)=L(b)=babababa *b=b=b=b=b,bab,bababb,bab,bababb,bab,bababb,bab,babab 所以所以所以所以 e1=e2,e1=e2,e1=e2,e1=e2,它它它它们们们们所所所所表表表表示示示示的的的的正正正正规规规规集集集集都都都都是是是是以以以以b b b b开开开开头头头头其其其其后后后后跟跟跟跟零零零零个个个个或或或或任任任任意意意意多多多多个个个个abababab所组成的。所组成的。所组成的。所组成的。即即即即L=b(ab)L=b(ab)L=b(ab)L=b(ab)n n n n|n|n|n|n 00001515

30、 2.2.其他性质其他性质 （1 1）e1e1e2e2e2e2e1e1 （2 2）e1e1（e2e2e3e3）（）（e1e1e2e2）e3e3 （3 3）e1e1（e2e3e2e3）（）（e1e2e1e2）e3 e3 （4 4）e1e1（e2e2e3e3）e1e2e1e2e1e3e1e3 （5 5）e1e1e1e1e1e1 （6 6）e1e1e1e1 （7 7）（）（e1e1*）*e1e1*（8 8）（）（e1e1）*e1 e1*根根据据定定义义比比较较容容易易证证明明上上述述性性质质，利利用用这这些些性性质质可可以以化化简简正正规规式式，证证明明正规式的等价关系正规式的等价关系说明：说明：说

31、明：说明：*上的某些集合若不能用正规表达式表示，则该集合不是正规集。上的某些集合若不能用正规表达式表示，则该集合不是正规集。上的某些集合若不能用正规表达式表示，则该集合不是正规集。上的某些集合若不能用正规表达式表示，则该集合不是正规集。如：如：如：如：=a,b,L(G)=a,b,L(G)=a,b,L(G)=a,b,L(G)=a a a an n n nb b b bn n n n|n n n n 0000就不是正规集，因为它不能用正规式表示。就不是正规集，因为它不能用正规式表示。就不是正规集，因为它不能用正规式表示。就不是正规集，因为它不能用正规式表示。（可以用上下文无关文法（可以用上下文无关

32、文法（可以用上下文无关文法（可以用上下文无关文法Z Z Z Z=aZb|ab|aZb|ab|aZb|ab|aZb|ab|产生）产生）产生）产生）可以可以可以可以证证证证明明明明，凡是由正规文法，凡是由正规文法，凡是由正规文法，凡是由正规文法所产生的语言一定是正规集，即可由正规式表示所产生的语言一定是正规集，即可由正规式表示所产生的语言一定是正规集，即可由正规式表示所产生的语言一定是正规集，即可由正规式表示 。1616 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定

33、义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法1717 第三章 词 法 分 析3.

34、63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷

35、自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法18183.63.6正规表达式和有穷自动机正规表达式和有穷自动机三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 正规文法、正规表达式与有穷自动机的关系可以通过如下正规文法、正规表达式与有穷自动机的关系可以通过如下KleenKleen定理描述：定理描述：定理：定理：L是正规集是正规集存在一个有穷自动机（存在一个有穷自动机（FA）M，使得使得L=L（M）存在一个正规文法存在一个正规文法G，使得使得L（M）=L（G）存在一个正规表达式存在一个正规表

36、达式e，使得使得 L（e）=L（G）1919 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造

37、正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法2020 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规

38、表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法21213.63.6正规表达式和有穷自动机正规表达式和有穷自动机 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机DFADFADFADFA 由由由由KleenKleenKl

39、eenKleen定理知，对应于一个正规表达式，总存在一个定理知，对应于一个正规表达式，总存在一个定理知，对应于一个正规表达式，总存在一个定理知，对应于一个正规表达式，总存在一个DFADFADFADFA，使得该使得该使得该使得该DFADFADFADFA所所所所识别的语言就是正规表达式的值（正规集）。下面我们就来介绍由正规识别的语言就是正规表达式的值（正规集）。下面我们就来介绍由正规识别的语言就是正规表达式的值（正规集）。下面我们就来介绍由正规识别的语言就是正规表达式的值（正规集）。下面我们就来介绍由正规表达式构造有穷自动机的方法步骤：表达式构造有穷自动机的方法步骤：表达式构造有穷自动机的方法步骤

40、：表达式构造有穷自动机的方法步骤：正规表达式正规表达式正规表达式正规表达式构造转换系统构造转换系统构造转换系统构造转换系统 NFANFANFANFA（状态转换图）状态转换图）状态转换图）状态转换图）NFANFANFANFA DFA DFA DFA DFA 步骤步骤步骤步骤 ，我们已经简单介绍过，下面主要介绍我们已经简单介绍过，下面主要介绍我们已经简单介绍过，下面主要介绍我们已经简单介绍过，下面主要介绍 步骤步骤步骤步骤 ，。2222 第三章 词 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义

41、 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法2323 第三章 词

42、 法 分 析3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 一、正规表达式和正规集的定义一、正规表达式和正规集的定义 1.非形式定义非形式定义 2.2.递归定义递归定义 二、正规表达式的性质二、正规表达式的性质 三、正规文法、正规表达式与有穷自动机的关系三、正规文法、正规表达式与有穷自动机的关系 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机 1.1.由正规表达式由正规表达式e e构造转换系统构造转换系统 2.2.由转换系统构造确定有穷自动机由转换系统构造确定有穷自动机(子集法子集法)3.3.由正规文法构造正规表达式由正规文法构造正规表达式 五、确定有穷自动机的

43、化简五、确定有穷自动机的化简 1.1.等价和可区分的概念等价和可区分的概念 2.2.确定有穷自动机的化简方法确定有穷自动机的化简方法2424 1.由正规表达式由正规表达式e e构造转换系统构造转换系统（广义转换图）（广义转换图）(1)转换系统的定义转换系统的定义所谓转换系统是一个具有唯一开始状态和唯一最终状态的一种所谓转换系统是一个具有唯一开始状态和唯一最终状态的一种特殊状态图。其条件是：特殊状态图。其条件是：1)1)没有弧引向开始状态没有弧引向开始状态 只引出只引出2)2)没有弧从终止状态引出没有弧从终止状态引出 只引入只引入3)3)转换系统的弧可以用空符号转换系统的弧可以用空符号标记。标记

44、。如如:S SZ ZS S1 1S SZ Z1 12 2a ab b3.63.6正规表达式和有穷自动机正规表达式和有穷自动机 四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机四、由正规表达式构造确定有穷自动机2525（2 2）转换系统与有穷自动机状态转换图的区别转换系统与有穷自动机状态转换图的区别转换系统与有穷自动机状态转换图的区别转换系统与有穷自动机状态转换图的区别1)1)1)1)有穷自动机状态转换图开始状态和终止状态有穷自动机状态转换图开始状态和终止状态有穷自动机状态转换图开始状态和终止状态有穷自动机状态转换图开始状态和终止状态不唯一不

45、唯一不唯一不唯一2)2)2)2)有穷自动机状态转换图弧上有穷自动机状态转换图弧上有穷自动机状态转换图弧上有穷自动机状态转换图弧上没有空符号没有空符号没有空符号没有空符号标记标记标记标记3)3)3)3)有穷自动机状态转换图有穷自动机状态转换图有穷自动机状态转换图有穷自动机状态转换图开始状态有引入开始状态有引入开始状态有引入开始状态有引入，终止状态有引出终止状态有引出终止状态有引出终止状态有引出（3 3 3 3）有穷自动机状态转换图与转换系统的关系有穷自动机状态转换图与转换系统的关系有穷自动机状态转换图与转换系统的关系有穷自动机状态转换图与转换系统的关系 定定定定理理理理：对对对对于于于于任任任任

46、何何何何一一一一个个个个有有有有穷穷穷穷自自自自动动动动机机机机状状状状态态态态转转转转换换换换图图图图存存存存在在在在一一一一个个个个相相相相应应应应转转转转换系统。换系统。换系统。换系统。2626由状态图构造转换系统方法如下：由状态图构造转换系统方法如下：设设状状态态图图具具有有，n n的的开开始始状状态态,，m m的终的终态态。1)首首先先，我我们们增增加加一一个个新新状状态态作作为为转转换换系系统统唯唯一一开开始始状状态态，并增加并增加n条标记为条标记为，分分别引到别引到，n n的弧。的弧。2)然然后后再再增增加加一一个个新新状状态态作作为为转转换换系系统统最最终终状状态态，并并增增加

47、加m条标记为条标记为的弧自的弧自，m m引到。引到。2727对于任一个状态图，我们可以构造一个相应的转换系统，使它们接受相同对于任一个状态图，我们可以构造一个相应的转换系统，使它们接受相同对于任一个状态图，我们可以构造一个相应的转换系统，使它们接受相同对于任一个状态图，我们可以构造一个相应的转换系统，使它们接受相同的符号串集合。如图的符号串集合。如图的符号串集合。如图的符号串集合。如图上图（上图（上图（上图（a a）是是是是有穷自动机有穷自动机有穷自动机有穷自动机状态图，状态图，状态图，状态图，上图（上图（上图（上图（b b）是等价的是等价的是等价的是等价的转换系统。转换系统。转换系统。转换系

48、统。从该从该从该从该转换系统可以看出它符合定义的三个条件：开始状态没有引入；转换系统可以看出它符合定义的三个条件：开始状态没有引入；转换系统可以看出它符合定义的三个条件：开始状态没有引入；转换系统可以看出它符合定义的三个条件：开始状态没有引入；终止状态没有引出；可以用终止状态没有引出；可以用终止状态没有引出；可以用终止状态没有引出；可以用 标记。显然，标记。显然，标记。显然，标记。显然，上图（上图（上图（上图（b b）与与与与上图（上图（上图（上图（a a）是是是是等价的，因为等价的，因为等价的，因为等价的，因为上图（上图（上图（上图（b b）只比只比只比只比上图（上图（上图（上图（a a）增

49、加了增加了增加了增加了n n条条条条 弧，不影响接受弧，不影响接受弧，不影响接受弧，不影响接受的句子。的句子。的句子。的句子。S S1 1Z Z1 1S S2 2X XZ Z2 2S S1 1Z Z1 1S S2 2X XZ Z2 2S SZ Z图图图图（a a）图（图（图（图（b b）2828（4）由正规表达式由正规表达式e构造转换系统构造转换系统定理：定理：对于每一个正规式对于每一个正规式e，存在一个接受正规集存在一个接受正规集L（e）的转换系统。的转换系统。设和是转换系统的开始状态和最终状态，构造字母表设和是转换系统的开始状态和最终状态，构造字母表a1,a2,，an上正规表达式转换系统方

50、法下图所示。上正规表达式转换系统方法下图所示。S SZ Z正规式正规式正规式正规式 转换系统转换系统转换系统转换系统S SZ ZS SZ Za a a ai i i ia a a ai i i iS SZ Ze e e ee e e eS SZ Ze e e e1 1 1 1e e e e1 1 1 1|e|e|e|e2 2 2 2S SZ Ze e e e1 1 1 1e e e e2 2 2 2e e e e2 2 2 2e e e e1 1 1 1e e e e2 2 2 2S SZ Ze e e e*e e e e2929例例例例3.9 3.9 3.9 3.9 设字母表设字母表设字母表