《第六章：类型检查.ppt》由会员分享，可在线阅读，更多相关《第六章：类型检查.ppt（52页珍藏版）》请在三一办公上搜索。
1、1/52,第六章：类型检查,概述类型系统一个简单的类型检查器的说明,2/52,第六章：类型检查：概述,静态检查编译器必须检查源程序是否符合源语言规定的语法和语义要求动态检查：目标程序运行时进行检测并报告程序中的某些错误类型检查：操作符应作用于相容的操作数，如数据变量和函数变量不可以相加控制流检查：控制流跳转语句能够确定目标地址，如C语言中，break语句可以使控制从switch/for/switch等语句确定的最小范围中跳出唯一性检查：某些对象只能被定义一次，如case语句的标号互不相同关联名字的检查：有时要求同一个名字在特定位置出现两次或多次，如Ada语言中循环结构（或程序快）的名字可能出现
2、在该结构的开始位置及结束位置本章重点：类型检查,3/52,第六章：类型检查：概述,类型检查器的位置简单结构并入其他活动中将标识符信息填入符号表时，对该名字进行唯一性检查将静态检查、中间代码生成、语法分析结合在一起复杂结构单独的类型检查器图6-1：语法分析器=类型检查器=中间代码生成器函数和运算符的重载多态函数,4/52,第六章：类型检查,概述类型系统一个简单的类型检查器的说明,5/52,第六章：类型检查：类型系统,类型检查器的设计语法结构的信息类型的概念语法结构的类型指派规则两种类型基本类型（原子类型）布尔型、字符型、整型、实数型子界类型、枚举类型（PASCAL）构造类型数组、记录、集合指针、
3、函数,6/52,第六章：类型检查：类型系统,类型表达式定义基本类型是类型表达式类型名也是类型表达式作用于类型表达式的类型构造器也是类型表达式，类型构造器包括：数组、乘积（域无名字）、记录（域有名字）指针、函数（函数构造符-）类型表达式也可以包含其值为类型表达式的变量,7/52,第六章：类型检查：类型系统,类型表达式表示：图方法：语法制导为类型表达式构造一颗树或DAG内节点：类型操作符叶节点：基本类型、类型名、类型变量图6-2：表示charXchar-pointer(integer)的树和DAG,8/52,第六章：类型检查：类型系统,类型系统定义将类型表达式指派到程序各部分的一组规则采用语法制导
4、定义说明通过类型检查器实现,9/52,第六章：类型检查：类型系统,静态类型检查vs动态类型检查静态类型检查：由编译器完成健全的类型系统能静态地确定程序在运行时不发生错误，因此不需要动态检查。如果某一语言能保证它所接受的程序不会在运行时发生类型错误，则称该语言是强类型语言动态类型检查：目标程序运行时完成有些检查只能动态完成,10/52,第六章：类型检查：类型系统,错误恢复报告错误的性质和位置从错误中恢复，以便检查剩下的输入通常耗费大,11/52,第六章：类型检查,概述类型系统一个简单的类型检查器的说明,12/52,第六章：类型检查：一个简单的类型检查器的说明,一个简单语言的类型检查器在此语言中，
5、标识符使用前必须先说明类型检查器是一个翻译模式可以从子表达式的类型合成表达式的类型，能够处理数组、指针、语句和函数,13/52,第六章：类型检查：一个简单的类型检查器的说明,一种简单语言源语言文法：图6-3基本类型：char、integer、type_error(报错用)类型构造器：数组、指针翻译模式：图6-4保存标识符类型的部分,14/52,第六章：类型检查：一个简单的类型检查器的说明,表达式的类型检查E-literal E.type:=charE-num E.type:=integerE-id E.type:=lookup(id.entry)E-E1 mod E2 E.type:=if E
6、1.type=integer and E2.type=integer then integer else type_errorE-E1E2 E.type:=if E2.type=integer and E1.type=array(s,t)then t else type_errorE-E1 E.type:=if E1.type=pointer(t)then t else type_error,15/52,第六章：类型检查：一个简单的类型检查器的说明,语句的类型检查基本类型：void（语句类型通常没有值）图6-5：检查语句类型的翻译模式,16/52,第六章：类型检查：一个简单的类型检查器的说明,
7、函数的类型检查产生一个函数的产生式E-E（E）函数类型的定义T-T1-T2 T.type:=T1.type-T2.type函数类型的检查E-E1（E2）E.type:=if E2.type=s and E1.type=s-t then t else type_error函数有多个参数时：s可以是函数的多个参数的乘积T1XT2XTn,17/52,第七章：运行时环境,概述源语言问题存储组织存储分配策略符号表支持动态存储分配的语言措施动态存储分配技术,18/52,第七章：运行时环境：概述,如何把静态的源程序正文和实现该程序的运行时所必须发生的活动联系起来？数据：源程序正文中同样的名字可表示目标机器中
8、不同的数据对象过程：过程的每次执行称为该程序的一个活动，过程的每次调用引起一个活动，这个活动可以操纵分配给它使用的数据对象任务：考察名字和数据对象之间的关系运行时支撑程序包管理数据对象的分配和释放，数据对象运行时的表示由它的类型决定基本数据类型：由目标机器中等价的数据对象表示构造数据类型：由一组基本对象表示由一些例行子程序组成，这些子程序和所产生的目标代码一起装配支撑程序包的设计受过程的语义的影响,19/52,第七章：运行时环境,概述源语言问题存储组织存储分配策略符号表支持动态存储分配的语言措施动态存储分配技术,20/52,第七章：运行时环境：源语言问题,过程：图7-1过程定义标识符（过程名）
9、+语句（过程体）形式参数完整的程序也可以看作是一个过程过程调用当一个过程出现在可执行语句中时，称该过程在该点被调用，执行被调用过程的过程体实在参数被传递给被调用过程，取代过程体中的形式参数,21/52,第七章：运行时环境：源语言问题,活动树作用：描述过程间的控制流，如图7-2定义：如图7-3每个节点代表过程的一个活动根节点代表主程序的活动当且仅当从活动a进入活动b时，节点a是节点b的父节点当且仅当活动a的生存期先于活动b的生存期时，a节点处于b节点的左边程序的控制流对应于活动树从根节点开始的深度优先遍历,22/52,第七章：运行时环境：源语言问题,控制栈作用：保存活跃着的过程活动，表示从当前节
10、点到根节点的路径。基本思想：当活动开始时，把这个活动的节点压入控制栈；当活动结束时，弹出这个节点。例7.2：图7-4,23/52,第七章：运行时环境：源语言问题,声明的作用域一个声明起作用的那部分程序通过查询符号表实现,24/52,第七章：运行时环境：源语言问题,名字的绑定图7-5：从名字到值的两步映射图7-6：静态概念和动态概念的对应,25/52,第七章：运行时环境：源语言问题,一些影响编译器存储组织和名字绑定的问题过程能递归吗？控制从过程的活动返回时，局部变量的值发生了怎样的变化？过程能引用非局部的名字吗？过程被调用时是怎样传递参数的？过程是否可以作为参数被传递？过程能否作为结果被返回？存
11、储区能否在程序控制下动态地分配？存储区是否必须显式地释放？,26/52,第七章：运行时环境,概述源语言问题存储组织存储分配策略符号表支持动态存储分配的语言措施动态存储分配技术,27/52,第七章：运行时环境：存储组织,运行时内存的划分图7-7：一个典型划分代码：大小编译时就能决定静态数据：尽可能对数据对象实行动态分配控制栈：管理过程的活动堆：动态活动信息,28/52,第七章：运行时环境：存储组织,活动记录图7-8：一般的活动记录（PASCAL和C）在过程被调用时，把它的活动记录压入运行栈；在控制返回调用者时，把这个活动记录从栈中弹出。,29/52,第七章：运行时环境：存储组织,编译时的局部数据
12、布局局部数据域在编译过程中的声明分配数据对象的存储布局深受目标机器的寻址约束的影响对齐：填充空白区例7.3：图7-9用于两个C编译器的数据布局,30/52,第七章：运行时环境,概述源语言问题存储组织存储分配策略符号表支持动态存储分配的语言措施动态存储分配技术,31/52,第七章：运行时环境：存储分配策略,三种分配策略静态分配策略在编译时为所有数据对象分配存储单元栈式分配策略按栈方式管理运行时的存储空间堆式分配策略在运行时根据需要从堆数据区域分配和释放存储空间应用：活动记录的存储分配,32/52,第七章：运行时环境：存储分配策略,静态分配策略基本思想编译器在编译时确定活动记录在目标程序中的位置，
13、如相对于目标代码的位置。活动记录中某个名字的地址由相对于活动记录一端的偏移量表示。编译时能在目标代码中填上所要操作的数据对象的地址。同样，过程调用时保存信息的地址在编译时也是已知的。,33/52,第七章：运行时环境：存储分配策略,静态分配策略优点名字在程序编译时与存储单元绑定，不需要运行时支撑程序包。允许局部名字的值在过程活动后依然保持，即当控制再次 进入过程时，局部名字的值同控制上一次离开时一样。缺点数据对象的长度和它在内存中的位置的约束在编译时必须知道不允许递归过程，因为一个过程的所有活动使用同样的局部名字绑定数据结构不能动态建立，因为没有运行时的存储分配机制,34/52,第七章：运行时环
14、境：存储分配策略,静态分配策略Fortran的静态存储分配图7-10：一个Fortran 77程序图7-11：一个Fortran 77程序局部标识符的静态存储,35/52,第七章：运行时环境：存储分配策略,栈式分配策略基本思想把存储空间组织为栈，而且随着过程活动的开始和结束将活动记录进栈和出栈；过程每次调用时，局部量的存储空间包含在该次调用的活动记录中。每次调用时多引起新的活动记录进栈=每次活动时局部量都绑定到新的存储单元。调用返回时活动记录弹出栈局部量的存储空间被释放=活动结束时局部量的值被删除。图7-13：所有活动记录的长度在编译时已知,36/52,第七章：运行时环境：存储分配策略,栈式分
15、配策略调用序列和返回序列：图7-14调用序列过程调用通过在目标代码中生成调用序列实现，调用序列分配活动记录，并把信息填入它的域中；调用者计算实在参数调用者把返回地址和top_sp的旧值存入被调用者的活动记录中；调用者并将top_sp移过调用者的局部数据域和临时变量域以及被调用者的参数域和状态域。被调用者保存寄存器值和其它机器状态信息被调用者初始化其局部数据，并开始执行,37/52,第七章：运行时环境：存储分配策略,栈式分配策略调用序列和返回序列：图7-14返回序列返回序列恢复机器状态，使调用过程能够继续执行。被调用者将返回值放入临近调用者的活动记录的地方被调用者利用状态域中的信息恢复top_s
16、p和其它寄存器，并且按调用者代码中的返回地址返回。调用者将返回值复制到自己的活动记录中，并用它来计算表达式。,38/52,第七章：运行时环境：存储分配策略,栈式分配策略变长数据：图7-15活动记录只保存指针，并不存储这些数组。通过两个指针访问栈中的数据。缺点活动结束时不能保持局部名字的值。被调用者的活动不能比调用者的活动的生存期长。,39/52,第七章：运行时环境：存储分配策略,堆式分配策略基本思想：图7-17把连续存储域分成块，当活动记录或其它对象需要时就分配。块的释放可以按任意次序进行。主要问题：堆式分配策略的效率,40/52,第七章：运行时环境,概述源语言问题存储组织存储分配策略符号表支
17、持动态存储分配的语言措施动态存储分配技术,41/52,第七章：运行时环境：符号表,符号表作用：记录名字的作用域以及绑定信息符号表机制线性表散列表,42/52,第七章：运行时环境：符号表,符号表符号表表项根据一个名字的声明建立，可以作为一个记录来实现，存储名字的相关信息。由词法分析器建立，相关信息在编译器的随后阶段加入和使用名字字符的存储：图7-32与名字绑定的存储单元信息的存储静态分配栈式分配堆式分配,43/52,第七章：运行时环境：符号表,符号表线性符号表按遇到的顺序排列：图7-33散列符号表：图7-34用C语言编写的散列函数：图7-35,44/52,第七章：运行时环境：符号表,符号表作用域
18、简单方法：为每个作用域建立一个符号表另类方法：把过程的局部信息放在程序语法树中相应过程的节点，这样符号表就被集成到输入程序的中间表示中了。最近作用域规则的实现：为每个过程赋予一个唯一的编号来跟踪过程中局部变量的名字程序块也必须编号局部变量在符号表中的表示：名字+编号查找一个新的被扫描到的名字时，名字和编号都必须匹配才算匹配。,45/52,第七章：运行时环境,概述源语言问题存储组织存储分配策略符号表支持动态存储分配的语言措施动态存储分配技术,46/52,第七章：运行时环境：支持动态存储分配的语言措施,显式分配和释放数据的存储一般采用堆的形式new、delete例7.11和图7-38：Pascal
19、中用new进行的动态存储分配隐式分配和释放一般发生在表达式的执行结果需要保存的时候。如在Lisp中使用cons的时候，一个新单元被插入到列表中，不再使用的单元会被自动回收。,47/52,第七章：运行时环境：支持动态存储分配的语言措施,垃圾单元在程序中被分配了但是不能被引用的存储单元例：285页插入head.next:=nil;垃圾单元在程序结束之前不能被使用Lisp：具有垃圾收集操作Pascal和C：没有垃圾收集操作，必须显式地释放不需要的存储单元悬空引用在程序中引用某个已释放的存储单元图7-40：悬空引用和垃圾单元的产生,48/52,第七章：运行时环境,概述源语言问题存储组织存储分配策略符号
20、表支持动态存储分配的语言措施动态存储分配技术,49/52,第七章：运行时环境：动态存储分配技术,动态存储分配技术依赖于存储的释放方式存储是隐式释放的：运行时支持程序包负责确定存储块何时不需要存储是显式释放的：编译器不需要做什么,50/52,第七章：运行时环境：动态存储分配技术,显式存储释放固定块的显式分配：图7-41变长块的显式分配碎片的出现：图7-42最先符合法：一种分配变长存储块的方法一个变长块释放时，与相邻空闲块合并成大的空闲块，防止出现更多的内存碎片,51/52,第七章：运行时环境：动态存储分配技术,隐式存储释放需要用户程序和运行包的协调运行包知道存储块何时不再被用户程序使用这种协调通过固定存储块格式实现：图7-43块边界的识别块是否被占用的识别,52/52,第七章：运行时环境：动态存储分配技术,隐式存储释放两种方法引用次数跟踪直接指向当前块的存储块的数目引用次数为零时，释放缺点：维护引用次数的时间开销大标记技术暂时挂起目前执行的用户程序，并利用静态指针来判断哪些块被占用需要知道所有指向块的指针，通过这些指针来对堆内的存储空间作标记标记过的存储块表示被占用，其它的可以释放,
