编译技术PPT课件.ppt

1、编译技术,主编：陈意云 张昱,2020/7/5,中国科大,1,课程性质： 编译技术是计算机专业必修课之一，目的是使学生掌握编译程序构造的一般原理，了解编译程序的基本设计方法和主要实现技术。其任务是让学生系统有效地了解编译程序的有关理论，以及整个编译程序的构造过程。,2020/7/5,中国科大,2,课时分配：共56学时，包括： 一、理论教学：50学时 第一章 引论（2学时） 第二章 词法分析 （12学时） 第三章 语法分析（20学时） 第四章 语义分析 （4学时） 第六章 运行时存储空间的组织和管理 （4学时） 第七章 中间代码生成（4学时） 第八章 目标代码生成（2学时） 复习：2学时,二、实

2、践教学：6学时 1、词法分析程序设计 2、语法分析程序设计,2020/7/5,中国科大,3,第一节 编译器概述,第一章 引论,一、程序设计语言的种类,、低级语言：机器语言，汇编语言；,、高级语言：BASIC、PASCAL、C 语言等。,2020/7/5,中国科大,4,二、语言处理程序,、含义：使计算机能理解并执行用某一种程序设计语言编写的程序，这样的程序称为语言处理程序。,、种类,（1）解释程序：直接执行源程序或其内部形式，不产生目标程序。,（2）翻译程序：将源程序翻译成与之等价的目标程序，分为“编译程序”和“汇编程序”两种。 其中：,2020/7/5,中国科大,5,编译程序：也称为编译器。指

3、高级语言的翻译程序。,高级语言采用“解释方式”和“编译方式” 执行的图示如下：,汇编程序：指汇编语言的翻译程序。,2020/7/5,中国科大,6,（解释方式示意图）,（编译方式示意图）,2020/7/5,中国科大,7,第二节 编译器的组成,2020/7/5,中国科大,8,一、词法分析器,1、功能：逐个读入源程序的字符序列，按照词法规则将它们翻译成由词法单元构成的词法记号流-token的形式。,2、词法记号的表示：,指同类词法单元共用的名称,指用来区别同类中其他词法单元的特征值,词法单元又称单词，指源程序中能够形成一个词法记号的字符串序列,2020/7/5,中国科大,9,例1： 给定C语言的赋值

4、语句： position=initial+rate*60 ，其中每个标识符为实数类型，将其翻译成词法记号流为：,1） id,1 (标识符position),说明：在编译器中，将将标识符表示为id，该语句经过词法分析后将变成如下形式：,2） = ( 赋值号),3）id,2 (标识符initial),4） + (加号),5）id,3 (标识符rate),6） * (乘号),7） 60 (数60),代表标识符position在符号表中的条目，如名字、类型等。,2020/7/5,中国科大,10,说明：编译器的词法分析也叫做线性分析或扫描。,2020/7/5,中国科大,11,二、语法分析器,1、功能：依

5、据语法规则检查词法分析输出的记号流是否符合正确，然后再将词法记号流按层次分组，用各记号的第一个元素形成一种树形中间表示。因此，语法分析也称为分析。,2、表示方法：语法树内部结点表示运算，子结点表示运算对象。,2020/7/5,中国科大,12, 语法树,前例赋值语句的语法树如下图:,2020/7/5,中国科大,13,练习1 画出赋值语句：count=total-day*12 的语法树。,练习2 画出赋值语句：pay:=6*con+sum 的语法树。,2020/7/5,中国科大,14,三、语义分析器,说明：类型检查是语义分析的一个重要部分，它指编译器检查每个运算符的运算对象，看它们的类型是否合适。

6、 请看下图：,功能：检查程序的语义是否正确，以保证程序各部分能有意义地结合在一起，并为以后的代码生成阶段收集类型信息。,2020/7/5,中国科大,15,“inttoreal”是将整数变成实数的运算符。因为程序中的标识符定义为实数类型，所以经过语义分析后，要将整数60变成实数。,整数60,实数60,2020/7/5,中国科大,16,四、中间代码生成器,说明：通常，中间代码采用三地址代码-类似于汇编语言，由三地址语句序列组成。每个三地址语句最多有三个操作数。,功能：产生源程序的中间代码表示，要求该中间代码必须容易产生并且易于翻译成目标程序。,2020/7/5,中国科大,17,三地址代码的特点：

7、(1)除赋值算符外，每个语句最多只有一个算符。 (2)用临时变量保存计算结果。 (3)每个语句最多有三个操作数。,临时变量,2020/7/5,中国科大,18,五、代码优化器,功能：改进中间代码，以产生执行较快的目标代码。,2020/7/5,中国科大,19,六、目标代码生成器,功能：为源程序的每个变量选择寄存器或内存单元，并且把中间代码翻译成等价的机器代码或汇编代码。,2020/7/5,中国科大,20,t1=id3*60.0 id1=id2+t1,把地址id3的内容放入寄存器R2中,把寄存器R2的内容乘以常数60.0,把地址id2的内容放入寄存器R1中,把寄存器R2、R1的内容相加,把寄存器R1

8、的值放入地址id1中,“F”表示指令处理浮点数,汇编指令一般格式： 操作符 源操作数 目的操作数,2020/7/5,中国科大,21,七、符号表管理器,说明：符号表指记录源程序中每个标识符及其属性的表格，当词法分析器发现源程序的标识符时，把该标识符填入符号表，但此时不能确定其属性；在语法分析等其它阶段，再将该标识符的其它信息填入符号表，以备编译程序的各个阶段使用。,功能：用来生成并完善源程序的符号表。 注:符号表指记录源程序中每个标识符及其属性值的表格。,2020/7/5,中国科大,22,八、阶段的分组,说明：有些编译程序通常把编译的几个阶段用一遍或多遍扫描来实现。例如可以把前端作为一遍扫描进行

9、编译，再把后端作为一遍扫描进行编译，直到将源程序翻译成目标程序。,在编译过程中，所有阶段被分成两部分：,1、前端：包括词法分析、语法分析、语义分析、符号表操作，前端依赖于源语言； 2、后端：中间代码生成、代码优化、目标代码生成、符号表操作；后端则独立于源语言，而与中间语言有关。,2020/7/5,中国科大,23,解：赋值语句：year=mon*16+any 的语法树：,作业：,1、编译器由哪几部分组成？各部分的功能是什么？ 2、画出语句： year=mon*16+any的语法树。,2020/7/5,中国科大,24,第二章 词法分析,本章内容： 词法分析器的任务：把源程序的字符流翻译成记号流，还

10、完成和用户接口的一些任务 正规式、状态转换图和有限自动机的相关知识 词法分析器的自动生成方法,2020/7/5,中国科大,25,第2.1节 词法记号及属性,图2.1 词法分析器与语法分析器相互作用,2020/7/5,中国科大,26,词法分析器的任务:,(1) 把源程序的字符流翻译成记号流；,(2) 删除源程序的注解和空白；,(3)将编译器各阶段的错误信息和源程序联系起来。,同用户接口的任务,2020/7/5,中国科大,27,1、词法记号：简称记号，指源程序经过词法分析后形成的内部输出形式。属性值可以省略，记号名用黑体表示。 （包括:关键字、算符、标识符、常数、字符串、标点符号等）,说明：词法记

11、号用黑体字 表示，一个词法记号通常包括一个或多个词法单元。如下表：,3、模式：指词法记号的模式，是描述某个词法记号所包含的词法单元集合的规则。,一、相关概念,2、词法单元 ：又称单词，指源程序中能够形成一个词法记号的字符串序列，是词法记号的实例。 （包括：标识符、保留字、运算符、常量等）,2020/7/5,中国科大,28,词法记号包括的词法单元模式的描述方法 if if 字符i，f for for字符f，o，r relation , = , = , 或 = 或 = 或 id sum, count, D5由字母开头的字母数字串 num 3.1, 10, 2.8E2 任何数值常数 literal

12、“seg. error” 双引号之间的任意字符串,用黑体字表示词法记号,一个词法记号包括多个词法单元,2020/7/5,中国科大,29,二、 词法记号的属性,请看下面例句：,作用：一个词法记号可能包括多个词法单元，因此，用词法记号的属性值来确定该词法记号所代表的具体词法单元。,2020/7/5,中国科大,30,例2.1 C赋值语句：position= initial + rate*60 其记号名和属性值 用下面二元组 序列表示：,id，1 ：代表标识符position,= : 指赋值号，二元组因没有属性值而变成一元组,id，2 ： 代表标识符 initial,+： 代表加法算符,id，3 ：

13、代表标识符 rate,* ： 代表乘法算符,num，60 ： 代表数值常数60,2020/7/5,中国科大,31,三、 词法错误,例词法分析器很难发现下面的错误： fi (a = f (x) ) ，,词法分析几乎不能发现源程序的错误，因为词法分析器对源程序采取非常局部的观点进行分析，将源程序翻译成词法记号流。,原因：词法分析器只是局部地从第一个字符f分析到第三个字符(空格),就将fi看作是标识符,而不能从全局的观点出发,从第一个字符f分析到该行最后一个字符,把它翻译成关键字。因此词法分析很难发现此类错误。,2020/7/5,中国科大,32,例当规定实数是“a .b”格式（即实数必须有整数部分和

14、小数部分）的时候，词法分析可以发现下面的错误:,123.,能够发现缺少小数部分的简单错误,2020/7/5,中国科大,33,第2.2节 词法记号的描述与识别,一、 相关定义 1、符号：也称为字符，指英文字母、数字、标点符号等。 2、字母表：也称为符号表，是符号的有限集合。 例： = 0,1 3、字符串：是符号的有穷序列，简称串。 例：0110,abdf， 说明:串s的长度指串s所含有的字符的个数，特别规定：空串是长度为0的串，用 表示 。,2020/7/5,中国科大,34,4、语言：是字母表上的一个由若干个字符串所组成的集合。,如：,0,00,000, , ,5、句子：属于某语言的字符串称为该

15、语言的句子，也称为字。,说明：在本书中，名词“字符串、符号串、串、句子、字”具有相同的含义。,2020/7/5,中国科大,35,二、字符串的相关运算,1、字符串的连接：给定x , y都是串，那么 x和y的连接表示成串xy,它是把串y加到串x的末尾形成的串。,说明：对连接运算，空串是恒等元素，即s= s= s,例1 已知字符串x=“abd”,y=“208”,计算字符串xy=?,解：xy=“abd208”,2020/7/5,中国科大,36,结论：串的方幂运算就是串的连接运算的特殊形式-即相同串的连接。,2、字符串的方幂：s0 =，si =si -1s（i 0）,例2 已知字符串x=“abd”， 计

16、算x5=?,解：x5=x5-1x =x4x=x4-1xx=x3xx=x3-1xxx=xxxxx,练习： 已知s=“I like ”， t=“swiming ” ,计算(st)5=?,解:(st)= “I like swiming ”(st)5= (st)(st)(st)(st)(st)=“I like swiming I like swiming I like swiming I like swiming I like swiming ”,2020/7/5,中国科大,37,三、语言的运算 设 L和 M表示某种语言，主要运算有:,LM = s | s L 或 s M ,例1 L=a,b , M=

17、1,6 , 求LM = ?,LM =a,b,1,6 ,(1)L与M的并（合）:,(2)L与M的连接：,LM = st | s L 且 t M ,例2 L=a,b , M=1,6 , 求LM = ?,LM=a,b1,6=a1, a6,b1,b6 ,2020/7/5,中国科大,38,(3)L的方幂：,L0 =，Li =Li -1L,例3 L=a,b , 求L0= ?, L5= ?,L0=, L5=L5-1L=L4L=L4-1LL=L3LL=L3-1LLL =L2LLL=L2-1LLLL=LLLLL,结论：L的i次冥就是i个的连接运算。,例4 L=a,b 求L3 = ?,L3=a,ba,ba,b=a

18、a, ab,ba,bba,b,=aaa, aab,aba,abb,baa,bab,bba,bbb,2020/7/5,中国科大,39,L的星闭包：,表示为L，其值为：,结论：L的星闭包表示零个或多个L连接的并集 。,(4)L的闭包：,有两种类型：,闭包指多个集合的并运算；,结论： L的正闭包表示一个或多个L连接的并集 。,L= L0L1L2Ln=LLLLLLLLLL LLLLL,L的正闭包：,表示为L+，其值为：,L+=L1L2Ln=LLLLLLLLLL LLLLL,2020/7/5,中国科大,40,例2.2 令L 和D 分别表示下面集合： L= A, B, , Z, a, b, , z , D

19、= 0, 1, , 9 ，如何描述下面的运算？,(1)LD,(2)LD,=A,B,C,a,b,z,0,1,29,它表示由字母和数字所组成的符号集合。,因此，LD表示一个字母后跟一个数字所构成的串组成的集合。,=A0,A1,A2,A9,B0,B1,B2B9,C0,C1z0,z1,z2z9,=A,B,C,Z,a,b,z, 0,1,29,2020/7/5,中国科大,41,(4)L*,(3)L3,因此, L3表示由3个字母所构成的串组成的集合。,=LLL,=A,B,Z,a,b,zA,B,Z,a,b,z A,B,Z,a,b,z,因此，L*表示仅由字母所构成的串(含)组成的集合,= L0L1L2Ln,=A

20、A,AB,AZ,Aa,Ab,Az,BA,BB,BZ,BaA,B,Z,a,b,z =AAA,AABAAZ,AAa,AAbAAz,ABA,ABBABZ,ABa,L1表示由一个字母所构成的串组成的集合,Ln表示由n个字母所构成的串组成的集合,2020/7/5,中国科大,42,(5) L(LD )*,(6) D+,因此，该式表示以字母开头的所有字母数字串组成的集合。,L表示由一个字母所构成的串组成的集合,D表示由一个数字所构成的串组成的集合,因此， D+表示所有数字串（不含空串）组成的集合。,= D1D2Dn,Dn表示由n个数字所构成的串组成的集合,2020/7/5,中国科大,43,定义：又称正规表达

21、式，是字母表中字符串的集合，用来表示简单的语言，也叫做正规集。 说明：一个正规式r 表示一个语言(r)。例如： 正规式所表示的语言备注 aa a (r)L(r) r是正规式 (r) | (s)L(r)L(s) r和s是正规式 (r)(s) L(r)L(s) r和s是正规式 (r)*(L(r)* r是正规式,四、 正规式,2020/7/5,中国科大,44,正规式运算的约定： (1)闭包运算最优先并且是左结合运算。 (2)连接运算（算符省略不写，正规式并列放置）的优先级次之也是左结合运算。 (3)选择运算（算符为“|”）的优先级最低也是左结合运算。,此约定可以简化正规式的书写，如(a)(b)*)|

22、(c )可以简化写成ab*|c 。,2020/7/5,中国科大,45,例2.3 令字母表=a, b，下面正规式的含义是什么？,(2)正规式(a | b)(a | b ):,(1)正规式a | b,：表示集合a, b；,选择运算符 “|” 表示集合的并集,(3)正规式aa | ab | ba | bb,表示集合aa, ab, ba, bb,(4)正规式a*,：表示集合aa, ab, ba, bb,因此a*表示由字母a构成的所有串的集合，包括空串。,=, a, aa, aaa, aaaa, ,2020/7/5,中国科大,46,(5)正规式(a|b)*,a b0 =,ab2 =aa,ab,ba,bb

23、,ab3 =aaa,aab,aba,abb,baa,bab,bba,bbb,(a|b)*= a, b* = a, b0 a, b1 a, b2a, bn = , a, b, aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,。,结果：(a|b)*表示由a 和b 构成的所有串的集合，包括空串。,2020/7/5,中国科大,47,五、 正规定义 指对正规式概念的一种形式化描述，其中包括对正规式名字及表现形式的描述，定义后就可以用正规式的名字来表示相应的正规式。 设是字母表， r1 、r2 . ri是上的正规式，则正规定义是指将形式为d1 = r1 , d2 =

24、 r2 dn = rn 的正规式表示为如下的形式： d1 r1 ( 表示d1定义为r1的形式， d1是正规式的名字) d2 r2 ( 表示d2定义为r2的形式， d2是正规式的名字) . . . . . . dn rn ( 表示dn定义为rn的形式，dn是正规式的名字),约定：正规定义中，用黑体字表示名字。,符号“”表示“定义为”的意义,2020/7/5,中国科大,48,例2.4 C语言的标识符是以字母开头的字母、数字和下划线组成的字符串，写出其正规定义。,letter A | B | | Z | a | b | | z|,说明：标识符的正规定义就是对标识符概念的一种形式化描述，定义中的 le

25、tter、 digit、 id 要用黑体字形式。,digit 0 | 1 | | 9,idletter ( letter | digit )*,2020/7/5,中国科大,49,例2.5 C语言的无符号数是形如1946,11.28,63.6E8,1.99E6 的集合，写出其正规定义。,digit 0 | 1 | | 9,运算符“+”表示一个或多个实例,运算符“？”表示零个或一个实例,digits digit digit* (表示整数部分),optional_fraction .digits| (表示小数部分),optional_exponent (E ( + | | ) digits ) |

26、( 表示指数部分),numdigits optional_fraction optional_exponent,num digit+ (.digit+)? (E(+|)? digit+)?,其简化形式为：,digit 0 | 1 | | 9,2020/7/5,中国科大,50,说明：无符号数的正规定义就是对无符号数概念的一种形式化描述，定义中的 num、 digit、 optional_fraction 、optional_exponent 要用黑体字形式。,2020/7/5,中国科大,51,例2.6 写出 C语言中保留字、关系算符、的正规定义。,while while (保留字),do do

27、(保留字),relop | | = (关系算符),2020/7/5,中国科大,52,约定：,1、符号“+” 表示一个或多个实例。,2、符号“？”表示零个或一个实例。,3、用字符组abc 表示正规式a|b|c，即集合a,b,c ；,4、用缩写字符组a - z 表示正规式a|b|c|.|z ，即集合a,b,c,d,e,f,z ；,5、用正规式A - Z a - zA Z a - z0-9* 来描述标识符。,2020/7/5,中国科大,53,六、 状态转换图,1、含义：又称转换图，用来识别源程序中各词法单元,2、组成：,一个开始状态-用圆圈表示；,一个或多个终止状态(也称接受状态)-用双圆圈表示；,

28、连接各状态的边-用箭头表示；,待识别的输入串中的符号-标于各边上。,例如，正规定义： relop | | = 的状态转换图如下：,2020/7/5,中国科大,54,图2.2 关系运算符的状态转换图,指小于等于号“=”,指关系运算符,表示指向输入字符的指针回移一个字符,指大于号“”,若离开状态s的某个边上标记other，则它表示离开状态s 的其它边上所标记字符以外的其它字符。,2020/7/5,中国科大,55,例2.7 画出标识符和保留字的转换图。,表示指向输入字符的指针回移一个字符,它是一个过程，它首先查看保留字表，如果当前词法单元是保留字，则返回相应的词法记号；否则该词法单元是标识符。该过程

29、再查标识符表，如果该词法单元已在标识符表中，则返回其指针，否则将该词法单元填入标识符表。,若离开状态s的某个边上标记other，则它表示离开状态s 的其它边上所标记字符以外的其它字符。,idletter ( letter | digit )*,2020/7/5,中国科大,56,例2.8 无符号数的转换图,它是一个过程，它的功能是：将词法单元（指无符号数本身，如整数126、实数6.89）填入无符号数表中，并且返回该无符号数的存储地址；同时词法分析器返回记号num和其存储地址。,图2.4 无符号数转换图,num digit+ (.digit+)? (E(+|)? digit+)?,2020/7/5

30、,中国科大,57,delim blank | tab | newline,表示输入串上指示输入字符的指针回移一个字符,图2.5 空格ws的状态转换图,词法单元之间的分隔符,例2.9 写出词法单元之间空格ws的正规定义，画出其转换图。,指一个空格,指一个制表符,指一个换行符,指词法单元之间的空格,ws delim+,P23-转换图的作用,2020/7/5,中国科大,58,第2.3节 有 限 自 动 机,语言的识别器：是一个程序，具有如下功能：用串x作为输入，当x是该语言的句子时，它返回“是”，否则返回“不是”。,有限自动机的含义：是一种数学模型，表现为状态转换图的形式，用来识别正规式所表达的语言

31、，即用来识别正规式的识别器。,2020/7/5,中国科大,59,有限自动机的种类：,说明：有限自动机简称自动机。主要用来描述程序设计语言中的词法单元，它不能用来描述像表达式、语句等复杂的语法结构。,(1)确定的有限自动机,(2)不确定的有限自动机,2020/7/5,中国科大,60,1、构成: (1)一个状态集合S； (2)一个输入符号集合； (3)一个状态转换函数move : S（)P(S)；它把状态和符号转换为状态的集合（因为转换后不是一个状态，故称为不确定的自动机）。 (4)一个开始状态 s0 ； (5)F是接受(也称终止)状态的集合，且F S 。,一、 不确定的有限自动机（简称NFA）,

32、新状态的集合,2020/7/5,中国科大,61,图2.6 识别语言(a|b)*ab 的NFA,2、表示方法,终止状态,NFA通常用状态转换图来表示，其中，结点表示状态，带有标记的边表示转换函数。,如图：,此NFA的状态集合是0,1,2，输入符号集合是a,b。,2020/7/5,中国科大,62,3、NFA在计算机中的实现方法,用状态转换表，表中每个状态占一行，每个输入符号各占一列，表中第i行的元素是状态i在接受某输入符号后所能达到的所有状态的集合。,如下面NFA的状态转换表：,2020/7/5,中国科大,63,表2.5 图2.6的NFA的状态转换表,图2.6 识别语言(a|b)*ab 的NFA,

33、状态,2020/7/5,中国科大,64,例2.9 给定识别正规式aa*|bb*的NFA，判断该NFA是否能识别串aaa。,图2.7 识别aa*|bb*的NFA,判断方法： 由状态0状态1状态2状态2 状态2，分别接受 ,a,a,a，它们拼成aaa， 而aaa=aaa， 因此，该NFA能识别串aaa。,2020/7/5,中国科大,65,二、 确定的有限自动机（简称DFA) 1、构成：,(1)一个状态集合S；,如P25-算法2.1,(2)一个输入字母表；,(3)一个状态转换函数move : S S；,(4) 唯一的开始状态 s0 S；,(5) 终止状态的集合F S。,如下图：,2020/7/5,中

34、国科大,66,图2.9 识别语言(a | b)*ab 的DFA,2、表示方法：,用状态转换图来表示，与不确定的有限自动机不同的是：确定的有限自动机从任何状态出发，对于任何输入符号，最多只有一个转换；且任何状态都没有 转换即没有任何状态可以不接受输入符号就直接进入下一个状态。,2020/7/5,中国科大,67,3、DFA在计算机中的实现方法,用状态转换表，表中每个状态占一行，每个输入符号各占一列，表中第i 行的元素为状态i 在接受某输入符号后所能达到的状态。,如下面DFA的状态转换表：,2020/7/5,中国科大,68,图2.9 识别语言(a | b)*ab 的DFA,表2.6 图2.9的DFA

35、的状态转换表,状态,2020/7/5,中国科大,69,说明：同NFA相比，DFA很容易确定是否接受某输入串即识别某语言，因为从开始状态起，最多只有一条到达某个终止状态的路径标记为所要识别的串。,2020/7/5,中国科大,70,例：给定下面DFA，判断它能识别哪些字符串。,答案：接受 由0和1构成的且个数都是偶数的字符串。,2020/7/5,中国科大,71,总结：,确定的有限自动机：指有限自动机从任何状态出发，对于任何输入符号，最多只有一个转换；,不确定的有限自动机：指有限自动机存在某个状态，对于某个输入符号，存在多种转换；,因此，由确定的有限自动机识别语言要比由等价的不确定的有限自动机识别该

36、语言快得多；但确定的有限自动机比不确定的有限自动机占用更多的存储空间。,2020/7/5,中国科大,72,三、 NFA到DFA的转换,子集构造法：令所构造的DFA在接受某输入字符串后所到达的状态是原NFA在接受该输入字符串后能到达的所有状态的集合。即：,1、DFA的开始状态是原NFA从开始状态出发，经过 转换所到达的所有状态的集合；,2、DFA的一个状态是原NFA的一个状态集合，即读了输入字符串a1a2 an后，若NFA能到达的所有状态是：s1, s2 , , sk，则由该NFA转换成的DFA到达状态s1, s2 , , sk；若其中含有原NFA的一个接受状态，则它就是该DFA的一个接受状态。

37、,P26 - 算法2.2,2020/7/5,中国科大,73,例2.11 给定识别(a|b)*ab的NFA如下图2.12，用子集构造法构造其等价的DFA。,2020/7/5,中国科大,74,按子集构造法，构造过程如下：,1 首先计算其等价DFA的开始状态A :它等于原NFA的开始状态“0”经过 转换后所得到的状态的集合， 即:,A= -closure(0)=0,1,2,4,7,由于 转换的路径可以没有边，因此规定：任意状态s的转换包括它本身-即s-closure(s) 。,2020/7/5,中国科大,75,2、标记A：(1)先计算A中的每个状态经过a 转换后所得到的状态的集合: move(A,a

38、) ；再对该集合中每个状态求其 转换后所得到的状态的集合，它们的并集就是DFA的新状态，设该新状态为B，计算如下：,move(A,a)=3,8 B=-closure(move(A,a) = -closure(3,8) =-closure(3)-closure(8) =1,2,3,4,6,78=1,2,3,4,6,7,8,2020/7/5,中国科大,76,(2)再计算A中的每个状态经过b 转换后所得到的状态的集合: move(A,b) ；再对该集合中每个状态求其 转换后所得到的状态的集合，它们的并集就是DFA的新的状态，设该新状态为C，计算如下：,move(A,b)=5 C=-closure(m

39、ove(A,b) = -closure(5) =-closure(5) =1,2,4,5,6,7,2020/7/5,中国科大,77,说明：状态A对原NFA的两个输入符号a、b都进行了转换；接下来应对状态B、C进行标记，并分别计算它们在接受输入符号a、b后所能到达的状态集合，直到求得的DFA的所有状态都已标记过。,2020/7/5,中国科大,78,3、标记B：(1)先计算B中的每个状态经过a 转换后所得到的状态的集合: move(B,a) ；再对该集合中每个状态求其 转换后所得到的状态的集合，求出它们的并集，计算如下：,move(B,a)=3,8,由上面计算得：move(A,a)=3,8 mov

40、e(B,a)= move(A,a) , B= -closure(move(A,a) 不必计算其 转换，即：-closure(move(B,a)=B，因此没有新状态。,2020/7/5,中国科大,79,(2)再计算B中的每个状态经过b 转换后所得到的状态的集合: move(B,b) ；再对该集合中每个状态求其 转换后所得到的状态的集合，它们的并集就是DFA的新的状态，设该新状态为D，即：,move(B,b)=5,9,计算其 转换，得到 新状态D： D=-closure(move(B,b) = -closure(5,9) =-closure(5)-closure(9) =1,2,4,5,6,79=

41、1,2,4,5,6,7,9,2020/7/5,中国科大,80,4、标记C：(1)先计算C中的每个状态经过a 转换后所得到的状态的集合: move(C,a) ；再对该集合中每个状态求其 转换后所得到的状态的集合，求出它们的并集，计算如下：,move(C,a)=3,8,由上面计算得：move(A,a)=3,8 move(C,a)= move(A,a) , B= -closure(move(A,a) 不必计算其 转换，即：-closure(move(C,a)=B，因此没有新状态。,2020/7/5,中国科大,81,(2)再计算C中的每个状态经过b 转换后所得到的状态的集合: move(C,b) ；再

42、对该集合中每个状态求其 转换后所得到的状态的集合，求出它们的并集，计算如下：,由上面计算得：move(A,b)=5 move(C,b)= move(A,b) , C= -closure(move(A,b) 不必计算其 转换，即：-closure(move(C,b)=C，因此没有新状态。,move(C,b)=5,2020/7/5,中国科大,82,5、标记D：(1)先计算D中的每个状态经过a 转换后所得到的状态的集合: move(D,a) ；再对该集合中每个状态求其 转换后所得到的状态的集合，求出它们的并集，计算如下：,move(D,a)=3,8,由上面计算得：move(A,a)=3,8 move

43、(D,a)= move(A,a) , B= -closure(move(A,a) 不必计算其 转换，即：-closure(move(D,a)=B，因此没有新状态。,2020/7/5,中国科大,83,(2)再计算D中的每个状态经过b 转换后所得到的状态的集合: move(D,b) ；再对该集合中每个状态求其 转换后所得到的状态的集合，求出它们的并集，计算如下：,由上面计算得：move(A,b)=5 move(D,b)= move(A,b) , C= -closure(move(A,b) 不必计算其 转换，即：-closure(move(D,b)=C，因此没有新状态。,move(D,b)=5,20

44、20/7/5,中国科大,84,说明：,2、D含有原NFA的一个接受状态“9”，因此，它是转换后DFA的终止状态-即新的DFA的状态集为A,B,C,D,其中，A为开始状态，D为接受状态。,1、所有状态均已标记，再没有新的状态产生，到此构造过程结束。,图示如下：,2020/7/5,中国科大,85,状态,构造过程如下：,2020/7/5,中国科大,86,状态,A = 0, 1, 2, 4, 7,2020/7/5,中国科大,87,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8,2020/7/5,中国科大,88,状态,A = 0, 1, 2, 4, 7 B =

45、1, 2, 3, 4, 6, 7, 8,2020/7/5,中国科大,89,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2020/7/5,中国科大,90,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2020/7/5,中国科大,91,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,2020/7/5,中国科大,92,状态,A = 0, 1, 2

46、, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2020/7/5,中国科大,93,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2020/7/5,中国科大,94,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2020/7/5,中

47、国科大,95,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,2020/7/5,中国科大,96,结论：识别一种语言的自动机有多个。,状态,2020/7/5,中国科大,97,识别语言(a|b)*ab 的四种自动机：二个DFA，二个NFA,2020/7/5,中国科大,98,练习：将下面的NFA转换成DFA。,2020/7/5,中国科大,99,按子集构造法，构造过程如下：,1 首先计算其等价DFA的开始状态A :它等于原NFA的开始状态“0”经过 转换后所得到的状态的集

48、合， 即:,A= -closure(0)=0,1,2,4,由于 转换的路径可以没有边，因此规定：任意状态s的转换包括它本身，即s-closure(s) 。,2020/7/5,中国科大,100,2、标记A：(1)先计算A中的每个状态经过a 转换后所得到的状态的集合: move(A,a) ；再对该集合中每个状态求其 转换后所得到的状态的集合，它们的并集就是DFA的新状态，设该新状态为B，计算如下：,move(A,a)=3 B=-closure(move(A,a) = -closure(3) =-closure(3) =3,6,7,2020/7/5,中国科大,101,(2)再计算A中的每个状态经过b

49、 转换后所得到的状态的集合: move(A,b) ；再对该集合中每个状态求其 转换后所得到的状态的集合，它们的并集就是DFA的新的状态，设该新状态为C，计算如下：,move(A,b)=5 C=-closure(move(A,b) = -closure(5) =-closure(5) =5,6,7,2020/7/5,中国科大,102,说明：状态A对原NFA的两个输入符号a、b都进行了转换；接下来应对状态B、C进行标记，并分别计算它们在接受输入符号a、b后所能到达的状态集合，直到求得的DFA的所有状态都已标记过。,2020/7/5,中国科大,103,3、标记B：(1)先计算B中的每个状态经过a 转

50、换后所得到的状态的集合: move(B,a) ；再对该集合中每个状态求其 转换后所得到的状态的集合，求出它们的并集，得到新状态，设该新状态为D,计算如下：,move(B,a)=8; D=-closure(move(B,a)=-closure(8)=8;,2020/7/5,中国科大,104,(2)再计算B中的每个状态经过b 转换后所得到的状态的集合: move(B,b) ；计算如下:,move(B,b)=，,因此不必计算其 转换，没有 新状态产生；,2020/7/5,中国科大,105,4、标记C：(1)先计算C中的每个状态经过a 转换后所得到的状态的集合: move(C,a) ；计算如下：,mo

51、ve(C,a)=8,move(B,a)=8， -closure(move(B,a)=D 没有新状态产生。,2020/7/5,中国科大,106,(2)再计算C中的每个状态经过b 转换后所得到的状态的集合: move(C,b) ；计算如下：,move(C,b)=，,因此不必计算其 转换，没有新状态产生；,2020/7/5,中国科大,107,5、标记D：(1)先计算D中的每个状态经过a 转换后所得到的状态的集合: move(D,a) ；计算如下：,move(D,a)=，,因此不必计算其 转换，没有新状态产生；,2020/7/5,中国科大,108,(2)再计算D中的每个状态经过b 转换后所得到的状态的

52、集合: move(D,b) ；再对该集合中每个状态求其 转换后所得到的状态的集合，求出它们的并集，得到新状态，设该状态为E，计算如下：,E=-closure(move(D,b)=9，,move(D,b)=9,2020/7/5,中国科大,109,6、标记E：(1)先计算E中的每个状态经过a 转换后所得到的状态的集合: move(E,a) ；计算如下：,move(E,a)=，,因此不必计算其 转换，没有新状态产生；,2020/7/5,中国科大,110,（2）再计算E中的每个状态经过b 转换后所得到的状态的集合: move(E,b) ；计算如下：,move(E,b)=，,因此不必计算其 转换，没有新

53、状态产生；,2020/7/5,中国科大,111,说明：,2、状态E含有原NFA的一个接受状态“9”，因此，它就是转换后DFA的终止状态。因此，新的DFA的状态集为A,B,C,D,E，其中，A为开始状态，E为接受状态。,1、所有状态均已标记，再没有新的状态产生，到此构造过程结束。,其转换表和转换图如下：,2020/7/5,中国科大,112,C,C,B,D,D,D,E,E,2020/7/5,中国科大,113,第2.5节 词法分析器的生成器（课外选修）,Lex编译器：即Lex，它是用C语言研制的运行在UNIX操作系统下的词法分析器的自动生成程序。对任何高级语言，用户必须用正规式描述该语言的各个词法类

54、，并以此构成lex源程序，然后再将该lex源程序经过lex编译程序的编译后，生成词法分析程序。其描绘方式如下图：,2020/7/5,中国科大,114,生成步骤如下：,1、 在UNIX操作系统下，输入命令“lex”，进入到Lex环境中，输入构成lex源程序lex.l的所有符号串 ，作为词法分析器的说明-其中包括变量说明、常量定义和正规定义；,2、程序lex.l通过Lex编译器，产生C语言程序lex.yy.c，该C程序包括从程序lex.l的正规式构造出的状态转换图及由该转换图识别词法单元的标准子程序；,3、程序lex.yy.c被C编译器编译成目标程序a.out，它就是把输入串变成内部记号流toke

55、n的词法分析器。,2020/7/5,中国科大,115,Lex程序lex.l的三个组成部分： 1、说明(包括变量说明、常量定义和正规定义) （指两个部分的间隔符号） 2、翻译规则 3、辅助过程 说明：翻译规则是形式如下的语句： p1动作1 p2动作2 pn动作n 这里，每个pi是一个正规式，每个动作i是用C语言编写的程序段。,2020/7/5,中国科大,116,例2.14 下面是识别书中P18-表2.4中记号的Lex源程序lex.l。 第一部分：说明部分如下： % /* 常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义*/ % /

56、* 正规定义 */ delim t n wsdelim+ letterA Za z digit09 idletter(letter|digit)* numberdigit+( .digit +)?(E+?digit +)?,2020/7/5,中国科大,117,第二部分：翻译规则如下： ws/* 没有动作，也不返回 */ whilereturn (WHILE); doreturn (DO); idyylval = install_id ( ); return (ID); numberyylval=install_num( ); return (NUMBER); “ ”yylval = NE; r

57、eturn (RELOP); “ ”yylval = GT; return (RELOP); “ = ”yylval = GE; return (RELOP);,指返回的词法记号,指返回的词法记号,指返回的词法记号,是全局变量名，用来存放词法记号的属性，它在文件lex.yy.c中被定义。,2020/7/5,中国科大,118,第三部分：辅助过程的定义: 1、install_ id ( ) 功能:它是一个过程，它首先查看保留字表，如果当前词法单元是保留字，则返回相应的词法记号；否则该词法单元是标识符，该过程再查标识符表，如果该词法单元已在标识符表中，则返回其指针，否则将该词法单元填入标识符表。 2

58、、install_num ( ) 功能：它是一个过程，它的功能是将词法单元填入无符号数表中，并且返回该无符号数的存储地址；同时词法分析器返回记号num和作为其属性值的这个地址。 说明：这两个辅助过程都省略了其详细代码.,2020/7/5,中国科大,119,答案：它描述的语言是：所有不含子串001的由字符0和1组成的串。其状态转换图如下：,例题1，给定正规式：(1|01)* 0*，叙述该正规式所描述的语言，并画出接受该语言的最简DFA的状态转换图。,2020/7/5,中国科大,120,例题2 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,2020/7/5,中国科大,121,例题2 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,2020/7/5,中国科大,122,例题2 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,2020/7/5,中国科大,123,例题2 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA。,2020/7/5,中国科大,124,第三章 语法分析,本章内容 上下文无关文法 自上而下分析方法 自下而上分析方法,2020/7/5,中国科大,125,复习： 1、正规式用来定义较简单的语言，只能表示给定结构的固定次数的重复或者没有指定次数的重复。 例：正规式：a (ba)5, a (