《编译原理 类型检查5》由会员分享，可在线阅读，更多相关《编译原理 类型检查5（166页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 类类 型型 检检 查查本章内容本章内容静态检查中最典型的部分静态检查中最典型的部分类型检查：类型检查：类型系统、类型检查、多态函数、重载类型系统、类型检查、多态函数、重载忽略其它的静态检查：忽略其它的静态检查：控制流检查、唯一性控制流检查、唯一性检查、关联名字检查检查、关联名字检查分析分析器器类型类型检查检查器器中间中间代码代码生成生成器器语语 法法树树语语 法法树树中间中间表示表示记记号号流流5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言介绍一些和程序运行有联系的概念介绍一些和程序运行有联系的概念5.1 类型在编程语言中的作
2、用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令非法指令错误5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会
3、被捕获的错误（trapped error）例：例：非法指令非法指令错误、非法内存、非法内存访问5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令非法指令错误、非法内存、非法内存访问、除数除数为零零5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）例：例：非
4、法指令非法指令错误、非法内存、非法内存访问、除数除数为零零引起引起计算立即停止算立即停止5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令非法指令错误、非法内存、非法内存访问、除数除数为零零引起引起计算立即停止算立即停止不会被捕获的错误不会被捕获的错误（untrapped error）5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运
5、行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令非法指令错误、非法内存、非法内存访问、除数除数为零零引起引起计算立即停止算立即停止不会被捕获的错误不会被捕获的错误（untrapped error）例：下标变量的例：下标变量的访问越越过了数了数组的末端的末端5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令非法指令错误、非法内存、非法内存访问、除数除数为零零引起引起计算立
6、即停止算立即停止不会被捕获的错误不会被捕获的错误（untrapped error）例：下标变量的例：下标变量的访问越越过了数了数组的末端的末端例：例：跳到一个跳到一个错误的地址，的地址，该地址开始的内存正地址开始的内存正好代表一个指令序列好代表一个指令序列5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令非法指令错误、非法内存、非法内存访问、除数除数为零零引起引起计算立即停止算立即停止不会被捕获的错误不会被捕获的错误
7、（untrapped error）例：下标变量的例：下标变量的访问越越过了数了数组的末端的末端例：例：跳到一个跳到一个错误的地址，的地址，该地址开始的内存正地址开始的内存正好代表一个指令序列好代表一个指令序列错误可能会有一段可能会有一段时间未引起注意未引起注意5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言良行为的程序良行为的程序不同场合对良行为的定义略有区别不同场合对良行为的定义略有区别例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错
8、误和安全语言良行为的程序良行为的程序不同场合对良行为的定义略有区别不同场合对良行为的定义略有区别例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序安全语言安全语言任何合法程序都是良行为的任何合法程序都是良行为的5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言良行为的程序良行为的程序不同场合对良行为的定义略有区别不同场合对良行为的定义略有区别例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序安全语言安全语言任何合法程序都是良行为的任何合法程序都是良行为的通常是通常是设计一个一个类型系型系统，通，通过静静态的的
9、类型型检查来拒来拒绝不会被捕不会被捕获错误5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言良行为的程序良行为的程序不同场合对良行为的定义略有区别不同场合对良行为的定义略有区别例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序安全语言安全语言任何合法程序都是良行为的任何合法程序都是良行为的通常是通常是设计一个一个类型系型系统，通，通过静静态的的类型型检查来拒来拒绝不会被捕不会被捕获错误但是，但是，设计一个一个类型系型系统，它正好只拒，它正好只拒绝不会被不会被捕捕获错误是非常困是非常困难的的5.1 类型在编程语言中的作用类型在编
10、程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言禁止错误禁止错误（forbidden error）不会被捕不会被捕获错误集合集合+会被捕会被捕获错误的一个子集的一个子集5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言禁止错误禁止错误（forbidden error）不会被捕不会被捕获错误集合集合+会被捕会被捕获错误的一个子集的一个子集为语言言设计类型系型系统的目的目标是在排除是在排除禁止错误禁止错误5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言禁止错误禁止错误（forbidd
11、en error）不会被捕不会被捕获错误集合集合+会被捕会被捕获错误的一个子集的一个子集为语言言设计类型系型系统的目的目标是在排除是在排除禁止错误禁止错误良行为程序和安全语言也可基于禁止错误来定义良行为程序和安全语言也可基于禁止错误来定义5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言变量的类型变量的类型变量在程序执行期间的取值范围变量在程序执行期间的取值范围5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言变量的类型变量的类型类型化的语言类
12、型化的语言变量都被给定类型的语言变量都被给定类型的语言并且表达式、语句等语法构造的类型都是可以静态确定并且表达式、语句等语法构造的类型都是可以静态确定的的例如，类型例如，类型boolean的变量的变量x在程序每次运行时的值只能是在程序每次运行时的值只能是布尔值布尔值，not (x)总总有意义有意义5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言变量的类型变量的类型类型化的语言类型化的语言未类型化的语言未类型化的语言不限制变量值范围的语言：不限制变量值范围的语言： 一个运算可以作用到任意的运算对象，其结果可能是一个一个
13、运算可以作用到任意的运算对象，其结果可能是一个有意义的值、一个错误、一个异常或一个语言未加定义的结有意义的值、一个错误、一个异常或一个语言未加定义的结果果例如：例如：LISP语言语言5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言变量的类型变量的类型类型化的语言类型化的语言未类型化的语言未类型化的语言显式类型化语言显式类型化语言类型是语法的一部分类型是语法的一部分5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言变量的类型变量的类型类型化的语
14、言类型化的语言未类型化的语言未类型化的语言显式类型化语言显式类型化语言隐式类型化的隐式类型化的语言语言不存在隐式不存在隐式类型化的类型化的主流语言，但可能存在忽略类型信主流语言，但可能存在忽略类型信息的程序片段，例如不需要程序员声明函数的参数类型息的程序片段，例如不需要程序员声明函数的参数类型5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型系统类型系统语言的组成部分语言的组成部分, ,由一组由一组定型规则定型规则（typing rule）构构成，这组规则用来给各种语言构造指派类型成，这组规则用来给各种语言构造指派类型5.1 类型在编程语
15、言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型系统类型系统语言的组成部分语言的组成部分, ,由一组由一组定型规则定型规则（typing rule）构构成，这组规则用来给各种语言构造指派类型成，这组规则用来给各种语言构造指派类型设计类型系统设计类型系统的根本目的是用静态检查的方式来保的根本目的是用静态检查的方式来保证合法程序运行时的良行为证合法程序运行时的良行为5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型系统类型系统语言的组成部分语言的组成部分, ,由一组由一组定型规则定型规则（typing r
16、ule）构构成，这组规则用来给各种语言构造指派类型成，这组规则用来给各种语言构造指派类型设计类型系统设计类型系统的根本目的是用静态检查的方式来保的根本目的是用静态检查的方式来保证合法程序运行时的良行为证合法程序运行时的良行为类型系统的形式化类型系统的形式化类型表达式、定型断言、定型规则类型表达式、定型断言、定型规则5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统类型系统类型系统语言的组成部分语言的组成部分, ,由一组由一组定型规则定型规则（typing rule）构构成，这组规则用来给各种语言构造指派类型成，这组规则用来给各种语言构造指派类
17、型设计类型系统设计类型系统的根本目的是用静态检查的方式来保的根本目的是用静态检查的方式来保证合法程序运行时的良行为证合法程序运行时的良行为类型系统的形式化类型系统的形式化类型表达式、定型断言、定型规则类型表达式、定型断言、定型规则类型检查算法类型检查算法通常是静态地完成类型检查通常是静态地完成类型检查5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统良类型的程序良类型的程序没有类型错误的程序没有类型错误的程序5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统良类型的程序良类型的程序没有类型错
18、误的程序没有类型错误的程序合法程序合法程序良类型程序（若语言定义中无其它方式表示的约良类型程序（若语言定义中无其它方式表示的约束）束）5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统良类型的程序良类型的程序没有类型错误的程序没有类型错误的程序合法程序合法程序良类型程序（若语言定义中无其它方式表示的约良类型程序（若语言定义中无其它方式表示的约束）束）类型可靠（类型可靠（type sound）的）的语言语言所有良所有良类型程序（合法程序）都是良行型程序（合法程序）都是良行为的的类型可靠的型可靠的语言一定是安全的语言语言一定是安全的语言5.1 类
19、型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统语法的和静态的概念语法的和静态的概念动态的概念动态的概念类型化语言类型化语言安全语言安全语言良类型程序良类型程序良行为的程序良行为的程序5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统未类型化语言未类型化语言可以通过彻底的运行时详细检查来排除所有的禁止可以通过彻底的运行时详细检查来排除所有的禁止错误错误如如LISP语言语言5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统未类型化语言未类型化语言可以
20、通过彻底的运行时详细检查来排除所有的禁止可以通过彻底的运行时详细检查来排除所有的禁止错误错误如如LISP语言语言类型化语言类型化语言类型检查也可以放在运行时完成，但影响效率类型检查也可以放在运行时完成，但影响效率一般都是静态检查，类型系统被用来支持静态检查一般都是静态检查，类型系统被用来支持静态检查静态检查语言通常也需要一些运行时的检查静态检查语言通常也需要一些运行时的检查数组访问越界检查数组访问越界检查5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全禁止错误集合没有囊括所有不会被捕获的错
21、误禁止错误集合没有囊括所有不会被捕获的错误Pascal语言语言 无标志的变体记录类型无标志的变体记录类型 函数型参数函数型参数5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全禁止错误集合没有囊括所有不会被捕获的错误禁止错误集合没有囊括所有不会被捕获的错误Pascal语言语言用用C语言的共用体（语言的共用体（union）来举例来举例unionUintu1;int u2;u;int p;u.u1=10;p=u.u2; p=0;5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化
22、语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全C语言语言还有很多不安全的并且被广泛使用的特征，如：还有很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全C语言语言还有很多不安全的并且被广泛使用的特征，如：还有很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变在语言设计的历史上，安全性考
23、虑不足是因为强调代码在语言设计的历史上，安全性考虑不足是因为强调代码的执行效率的执行效率5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全C语言语言还有很多不安全的并且被广泛使用的特征，如：还有很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变在语言设计的历史上，安全性考虑不足是因为强调代码在语言设计的历史上，安全性考虑不足是因为强调代码的执行效率的执行效率在现代语言设计上，安全性的位置越来越重要在现代语言设计上，安全性的位置越来越
24、重要5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全C语言语言还有很多不安全的并且被广泛使用的特征，如：还有很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变在语言设计的历史上，安全性考虑不足是因为强调代码在语言设计的历史上，安全性考虑不足是因为强调代码的执行效率的执行效率在现代语言设计上，安全性的位置越来越重要在现代语言设计上，安全性的位置越来越重要C的一些问题已经在的一些问题已经在C+中得以缓和中得以缓和更多一些问题在更多一些
25、问题在Java中已得到解决中已得到解决5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.3 类型化语言的优点类型化语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.3 类型化语言的优点类型化语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用编译的实惠编译的实惠程序模块可以相
26、互独立地编译程序模块可以相互独立地编译5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.3 类型化语言的优点类型化语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用编译的实惠编译的实惠程序模块可以相互独立地编译程序模块可以相互独立地编译运行的实惠运行的实惠可得到更有效的空间安排和访问方式可得到更有效的空间安排和访问方式5.2 描述类型系统的语言描述类型系统的语言类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则, ,它独立于类型检查
27、算法它独立于类型检查算法5.2 描述类型系统的语言描述类型系统的语言类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则, ,它独立于类型检查算法它独立于类型检查算法定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法5.2 描述类型系统的语言描述类型系统的语言类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则, ,它独立于类型检查算法它独立于类型检查算法定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法类型
28、系统的基本概念可用于各类语言类型系统的基本概念可用于各类语言，包括包括函数式语言、命令式语言和并行语言等函数式语言、命令式语言和并行语言等5.2 描述类型系统的语言描述类型系统的语言类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则, ,它独立于类型检查算法它独立于类型检查算法定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法类型系统的基本概念可用于各类语言类型系统的基本概念可用于各类语言，包括包括函数式语言、命令式语言和并行语言等函数式语言、命令式语言和并行语言等本节讨论用形式方法来描述类型系统本
29、节讨论用形式方法来描述类型系统5.2 描述类型系统的语言描述类型系统的语言类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则, ,它独立于类型检查算法它独立于类型检查算法定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法类型系统的基本概念可用于各类语言类型系统的基本概念可用于各类语言，包括包括函数式语言、命令式语言和并行语言等函数式语言、命令式语言和并行语言等本节讨论用形式方法来描述类型系统本节讨论用形式方法来描述类型系统然后讨论实例语言时：先定义语法，再给出类型然后讨论实例语言时：先定义语法，再给
30、出类型系统的形式描述，最后写出类型检查的翻译方案系统的形式描述，最后写出类型检查的翻译方案5.2 描述类型系统的语言描述类型系统的语言类型系统的形式化类型系统的形式化类型系统是一种逻辑系统类型系统是一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统- - 自然数表达式自然数表达式（需要定义它的语法）（需要定义它的语法） a+b,3- - 良形公式良形公式（逻辑断言，需要定义它的语法）（逻辑断言，需要定义它的语法） a+b=3,(d=3) (c10)- - 推理规则推理规则ab,bcac5.2 描述类型系统的语言描述类型系统的语言类型系统的形式化类型系统的形式化类型系统是一种逻辑系统类型系统是
31、一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统类型系统类型系统- - 自然数表达式自然数表达式类型表达式类型表达式 a+b,3intint- - 良形公式良形公式 a+b=3,(d=3) (c10)- - 推理规则推理规则ab,bcac5.2 描述类型系统的语言描述类型系统的语言类型系统的形式化类型系统的形式化类型系统是一种逻辑系统类型系统是一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统类型系统类型系统- - 自然数表达式自然数表达式类型表达式类型表达式 a+b,3intint- - 良形公式良形公式定型断言定型断言 a+b=3,(d=3) (c10)x:int|x+3:int-
32、- 推理规则推理规则(x:int叫做定型环境叫做定型环境)ab,bcac5.2 描述类型系统的语言描述类型系统的语言类型系统的形式化类型系统的形式化类型系统是一种逻辑系统类型系统是一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统类型系统类型系统- - 自然数表达式自然数表达式类型表达式类型表达式 a+b,3intint- - 良形公式良形公式定型断言定型断言 a+b=3,(d=3) (c10)x:int|x+3:int- - 推理规则推理规则定型规则定型规则 |M:int, |N:int |M +N:intab,bca0)(TypeFunction)(T1,T2 void)定型断言中的类型
33、表达式也可以用抽象语法定型断言中的类型表达式也可以用抽象语法 | T | pointer(T) | T, | N:integer | array(N,T) | T1, | T2 | T1T25.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则表达式表达式(ExpTruth)(ExpNum)(ExpId) | | truth:boolean | | num:integer 1,id:T, 2| 1,id:T, 2| id:T5.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则表达式表达式(ExpMod)(ExpIndex)(0 E2 N 1)(ExpDeref) | E1
34、:integer, | E2:integer | E1mod E2:integer | E1:array(N,T), | E2:integer | E1E2:T | E :pointer(T) | E :T5.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则表达式表达式(ExpFunCall) | E1:T1 T2, | E2:T1 | E1(E2):T25.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则语句语句(StateAssign)(T=booleanorT= integer)(StateIf)(StateWhile) | id:T, | E:T | id:=E
35、:void | E:boolean, | S:void | ifEthenS:void | E:boolean, | S:void | whileEdoS:void5.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则语句语句(StateSeq) | S1:void, | S2:void | S1;S2:void5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查设计语法制导的类型检查器设计语法制导的类型检查器设计依据是上节的类型系统设计依据是上节的类型系统类型环境类型环境 的的信息进入符号表信息进入符号表对类型表达式采用抽象语法对类型表达式采用抽象语法具体：
36、具体：arrayNofT抽象：抽象：array (N,T) Tpointer (T)考虑到报错的需要，增加了类型考虑到报错的需要，增加了类型type_error5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查声明语句声明语句D D; DD id : T addtype (id.entry, T.type)addtype：把类型信息填入符号表：把类型信息填入符号表5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查声明语句声明语句D D; DD id : T addtype (id.entry, T.type)T booleanT.type =
37、 booleanT integer T.type = integerT T1 T.type = pointer(T1.type)5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查声明语句声明语句D D; DD id : T addtype (id.entry, T.type)T booleanT.type = booleanT integer T.type = integerT T1 T.type = pointer(T1.type)T array numof T1 T.type = array(num.val, T1.type)5.3 简单类型检查器的说明简单类型检
38、查器的说明5.3.3 类型检查类型检查声明语句声明语句D D; DD id : T addtype (id.entry, T.type)T booleanT.type = booleanT integer T.type = integerT T1 T.type = pointer(T1.type)T array numof T1 T.type = array(num.val, T1.type)T T1 T2 T.type = T1.type T2.type 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E truthE.type = boolean E numE.
39、type = integerE idE.type = lookup(id.entry)5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E truthE.type = boolean E numE.type = integerE idE.type = lookup(id.entry)E E1 mod E2E.type =if E1.type = integer and E2. type = integer then integer else type_error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1E2E.type=if
40、E2.type=integerand E1.type =array(s,t)thentelsetype_error5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1E2E.type=ifE2.type=integerand E1.type =array(s,t)thentelsetype_errorE E1 E.type =ifE1.type=pointer(t)thentelsetype_error5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1E2E.type=ifE2.type=integerand E1.type =
41、array(s,t)thentelsetype_errorE E1 E.type =ifE1.type=pointer(t)thentelsetype_errorE E1(E2)E.type=ifE2.type= sand E1.type=st thentelsetype_error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S id:=E if (id.type = E.type & E.type boolean, integer) S.type = void; else S.type = type_error; 5.3 简单类型检查器的说明简单类型检查器的说明
42、类型检查类型检查语句语句S id:=E if (id.type = E.type & E.type boolean, integer) S.type = void; else S.type = type_error; SifEthenS1S.type=ifE.type=booleanthenS1.typeelsetype_error5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S while E do S1S.type =ifE.type = boolean then S1. type else type_error 5.3 简单类型检查器的说明简单类型检查器的说明类
43、型检查类型检查语句语句S while E do S1S.type =ifE.type = boolean then S1. type else type_error S S1; S2S. type =if S1. type = voidandS2. type =voidthenvoidelse type_error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查程序程序P D;S P.type=ifS.type =voidthenvoidelsetype_error5.3 简单类型检查器的说明简单类型检查器的说明5.3.4类型转换类型转换E E1opE2E.type =ifE
44、1.type=integerandE2.type=integerthenintegerelse if E1.type = integer and E2.type =realthenrealelse if E1.type = real and E2.type =integerthenrealelseifE1.type=realandE2.type=realthenrealelse type_error 5.4 多多 态态 函函 数数5.4.1为什么要使用多态函数为什么要使用多态函数例：用例：用Pascal语言写不出求表长度的通用程序语言写不出求表长度的通用程序typelink= cell;cel
45、l=recordinfo:integer;next:linkend;5.4 多多 态态 函函 数数functionlength(lptr:link):integer;varlen:integer;beginlen:=0;whilelptrnildobeginlen:=len+1;lptr:=lptr .nextend;length:=lenend;5.4 多多 态态 函函 数数用用ML语言很容易写出求表长度的程序而不必语言很容易写出求表长度的程序而不必管表元的类型管表元的类型。funlength(lptr)=ifnull(lptr)then0elselength(tl(lptr)+1;5.4
46、多多 态态 函函 数数用用ML语言很容易写出求表长度的程序而不必语言很容易写出求表长度的程序而不必管表元的类型管表元的类型。funlength(lptr)=ifnull(lptr)then0elselength(tl(lptr)+1;length(“sun”,“mon”,“tue”)length(10,9,8)都等于都等于35.4 多多 态态 函函 数数多态函数多态函数允许变元有不同的类型允许变元有不同的类型5.4 多多 态态 函函 数数多态函数多态函数允许变元有不同的类型允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）（
47、区别于重载的特征）5.4 多多 态态 函函 数数多态函数多态函数允许变元有不同的类型允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）（区别于重载的特征）多态算符多态算符用于以不同类型的变元执行的代码段用于以不同类型的变元执行的代码段5.4 多多 态态 函函 数数多态函数多态函数允许变元有不同的类型允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）（区别于重载的特征）多态算符多态算符用于以不同类型的变元执行的代码段用于以不同类型的变元执行的代码段例如：例如
48、：数组索引数组索引5.4 多多 态态 函函 数数多态函数多态函数允许变元有不同的类型允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）（区别于重载的特征）多态算符多态算符用于以不同类型的变元执行的代码段用于以不同类型的变元执行的代码段例如：例如：数组索引数组索引、函数作用函数作用5.4 多多 态态 函函 数数多态函数多态函数允许变元有不同的类型允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）（区别于重载的特征）多态算符多态算符用于以不同类型的变元执行的代
49、码段用于以不同类型的变元执行的代码段例如：例如：数组索引数组索引、函数作用、通过指针间接访问函数作用、通过指针间接访问5.4 多多 态态 函函 数数多态函数多态函数允许变元有不同的类型允许变元有不同的类型体中的语句可以在变元类型不同的情况下执行体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）（区别于重载的特征）多态算符多态算符用于以不同类型的变元执行的代码段用于以不同类型的变元执行的代码段例如：例如：数组索引数组索引、函数作用、通过指针间接访问函数作用、通过指针间接访问C语言手册中关于指针语言手册中关于指针&的论述是：的论述是：如果运算对象的类型是如果运算对象的类型是，那么结果类型
50、是指，那么结果类型是指向向的指针的指针”5.4 多多 态态 函函 数数5.4.2 类型变量类型变量length的类型可以写成的类型可以写成 .list( )integer允许使用类型变量，还便于讨论未知类型允许使用类型变量，还便于讨论未知类型在不要求标识符的声明先于使用的语言中在不要求标识符的声明先于使用的语言中，通过，通过类型变量的使用去确定程序变量的类型类型变量的使用去确定程序变量的类型5.4 多多 态态 函函 数数例：例：functionderef(p);beginreturnp end;5.4 多多 态态 函函 数数例：例：functionderef(p);-对对p的类型一无所知：的类
51、型一无所知： beginreturnp end;5.4 多多 态态 函函 数数例：例：functionderef(p);-对对p的类型一无所知：的类型一无所知： beginreturnp - =pointer( )end;5.4 多多 态态 函函 数数例：例：functionderef(p);-对对p的类型一无所知：的类型一无所知： beginreturnp - =pointer( )end;deref的类型是的类型是 .pointer( ) 5.4 多多 态态 函函 数数5.4.3一个含多态函数的语言一个含多态函数的语言P D;E 引入类型变量、笛卡引入类型变量、笛卡D D; D | id:
52、 Q 儿积类型、多态函数儿积类型、多态函数 Q type-variable. Q | T T T T | T T| unary-constructor ( T )| basic-type| type-variable| ( T )E E (E ) | E, E | id5.4 多多 态态 函函 数数5.4.3一个含多态函数的语言一个含多态函数的语言P D;E 引入类型变量、笛卡引入类型变量、笛卡D D; D | id: Q 儿积类型、多态函数儿积类型、多态函数 Q type-variable. Q | T T T T | T T 这是一个抽象语言这是一个抽象语言,| unary-constru
53、ctor ( T )忽略了函数定义的忽略了函数定义的| basic-type函数体函数体| type-variable| ( T )E E (E ) | E, E | id5.4 多多 态态 函函 数数5.4.3一个含多态函数的语言一个含多态函数的语言P D;ED D; D | id: QQ type-variable. Q | TT T T | T T| unary-constructor ( T )一个程序：一个程序：| basic-typederef: .pointer( ) ;| type-variableq:pointer(pointer(integer);| ( T )deref(
54、deref(q)E E (E ) | E, E | id5.4 多多 态态 函函 数数类型系统中增加的推理规则类型系统中增加的推理规则环境规则环境规则(EnvVar)语法规则语法规则(TypeVar)(TypeProduct) | , dom( ) , | 1, , 2| 1, , 2| | T1, | T2 | T1 T25.4 多多 态态 函函 数数类型系统中增加的推理规则类型系统中增加的推理规则语法规则语法规则(TypeParenthesis)(TypeForall)(TypeFresh) | T | (T) , | T | .T | .T , , i| , i | i / T5.4 多
55、多 态态 函函 数数类型系统中增加的推理规则类型系统中增加的推理规则定型规则定型规则 (ExpPair)(ExpFunCall)(S是是T1和和T3的最一般的合一代换的最一般的合一代换) | E1:T1， | E2:T2 | E1,E2:T1 T2 | E1:T1 T2, | E2:T3 | E1(E2):S(T2)5.4 多多 态态 函函 数数5.4.4 代换、实例和合一代换、实例和合一代换代换: : 类型表达式中的类型变量用其所代表的类型表达式中的类型变量用其所代表的类型表达式去替换类型表达式去替换5.4 多多 态态 函函 数数5.4.4 代换、实例和合一代换、实例和合一代换代换: : 类
56、型表达式中的类型变量用其所代表的类型表达式中的类型变量用其所代表的类型表达式去替换类型表达式去替换functionsubst(t :type_expression):type_expression;beginift是基本类型是基本类型thenreturntelseift是类型变量是类型变量thenreturnS(t)elseift 是是t1t2thenreturnsubst(t1)subst(t2)end5.4 多多 态态 函函 数数实例实例把把subst函数函数用于用于t后所得的类型表达式是后所得的类型表达式是t的一的一个实例，用个实例，用S (t)表示。表示。例子（例子（s t 表示表示s
57、是是t 的实例的实例）pointer(integer)pointer( )pointer(real)pointer( )integerinteger pointer( ) 5.4 多多 态态 函函 数数下面左边的类型表达式不是右边的实例下面左边的类型表达式不是右边的实例integerreal代换不能用于基本类型代换不能用于基本类型integerreal 的代换不一致的代换不一致integer 的所有出现都应该代换的所有出现都应该代换5.4 多多 态态 函函 数数合一合一如果存在某个代换如果存在某个代换S使得使得S(t1)=S(t2)，那么这那么这两个表达式两个表达式t1和和t2能够能够合一合一
58、最一般的合一代换最一般的合一代换S(t1)=S(t2)；对任何其它满足对任何其它满足S (t1)=S (t2)的代换的代换S ，代换代换S (t1)是是S(t1)的实例的实例5.4 多多 态态 函函 数数5.4.5多态函数的类型检查多态函数的类型检查多态函数和普通函数在类型检查上的区别多态函数和普通函数在类型检查上的区别( (1) )同一多态函数的不同出现无须变元有相同类型同一多态函数的不同出现无须变元有相同类型apply: oderefo:pointer( o) oapply: iderefi : pointer( i) iq:pointer(pointer(integer)deref(de
59、ref (q)的带标记的语法树的带标记的语法树5.4 多多 态态 函函 数数( (2) )必须把类型相同的概念推广到类型合一必须把类型相同的概念推广到类型合一apply: oderefo:pointer( o) oapply: iderefi : pointer( i) iq:pointer(pointer(integer)deref(deref (q)的带标记的语法树的带标记的语法树5.4 多多 态态 函函 数数( (2) )必须把类型相同的概念推广到类型合一必须把类型相同的概念推广到类型合一( (3) )要记录类型表达式合一的结果要记录类型表达式合一的结果apply: oderefo:po
60、inter( o) oapply: iderefi : pointer( i) iq:pointer(pointer(integer)deref(deref (q)的带标记的语法树的带标记的语法树5.4 多多 态态 函函 数数检查多态函数的翻译方案检查多态函数的翻译方案EE1(E2)p=mkleaf(newtypevar);unify (E1.type,mknode(,E2.type,p);E.type=pE E1,E2E.type=mknode( ,E1.type, E2.type)E idE.type=fresh(lookup(id.entry)5.4 多多 态态 函函 数数apply:
61、oderefo:pointer( o) oapply: iderefi : pointer( i) iq:pointer(pointer(integer)表表达达式式：类类型型 代代换换 q:pointer(pointer(integer)derefi:pointer( i) iderefi(q):pointer(integer) i= pointer(integer)derefo:pointer( o) oderefo(derefi (q):integer o =integer5.4 多多 态态 函函 数数确定表长度的确定表长度的ML函数函数funlength(lptr)=ifnull(lp
62、tr)then0elselength(tl(lptr)+1;5.4 多多 态态 函函 数数length: ; lptr: ;if: .boolean ;null: .list( )boolean ;tl: .list( )list( );0:integer ;1:integer;+:integer integerinteger;match: . ;match(length(lptr),if(null(lptr),0,length(tl(lptr)+1)5.4 多多 态态 函函 数数行行定定型型断断言言代代换换规规则则(1)lptr: (ExpId)(2)length: (ExpId)(3)le
63、ngth(lptr): = (ExpFunCall)(4)lptr: 从从(1)可得可得(5)null:list( n) boolean(ExpId)和和(TypeFresh)(6)null(lptr):boolean =list( n)(ExpFunCall)(7)0:integer(ExpNum)(8)lptr: list( n)从从(1)可得可得5.4 多多 态态 函函 数数行行定定型型断断言言代代换换规规则则(9)tl:list( t)list( t)(ExpId)和和(TypeFresh)(10)tl(lptr):list( n) t= n(ExpFunCall)(11)length
64、:list( n) 从从(2)可得可得(12)length(tl(lptr): (ExpFunCall)(13)1:integer(ExpNum)(14)+:integer integerinteger(ExpId)5.4 多多 态态 函函 数数行行定定型型断断言言代代换换规规则则(15)length(tl(lptr)+1:integer =integer (ExpFunCall)(16)if:boolean i i i(ExpId)和和(TypeFresh)(17)if(.):integer i=integer (ExpFunCall)(18)match: m m m(ExpId)和和(Ty
65、peFresh)(19)match():integer m=integer (ExpFunCall)5.4 多多 态态 函函 数数funlength(lptr)=ifnull(lptr)then0elselength(tl(lptr)+1;length函数的类型是函数的类型是 .list( ) integer5.5 类型表达式的等价类型表达式的等价当允许对类型表达式命名后当允许对类型表达式命名后：类型表达式是否相同就有了不同的解释类型表达式是否相同就有了不同的解释出现了结构等价和名字等价两个不同的概念出现了结构等价和名字等价两个不同的概念typelink= cell;var next :lin
66、k;last :link;p: cell;q,r : cell;5.5 类型表达式的等价类型表达式的等价5.5.1类型表达式的结构等价类型表达式的结构等价两个类型表达式完全相同（当无类型名时）两个类型表达式完全相同（当无类型名时）typelink= cell;var next :link;last :link;p: cell;q,r : cell;5.5 类型表达式的等价类型表达式的等价5.5.1类型表达式的结构等价类型表达式的结构等价两个类型表达式完全相同（当无类型名时）两个类型表达式完全相同（当无类型名时）类型表达式树一样类型表达式树一样typelink= cell;var next :l
67、ink;last :link;p: cell;q,r : cell;5.5 类型表达式的等价类型表达式的等价5.5.1类型表达式的结构等价类型表达式的结构等价两个类型表达式完全相同（当无类型名时）两个类型表达式完全相同（当无类型名时）类型表达式树一样类型表达式树一样相同的类型构造符作用于相同的子表达式相同的类型构造符作用于相同的子表达式typelink= cell;var next :link;last :link;p: cell;q,r : cell;5.5 类型表达式的等价类型表达式的等价5.5.1类型表达式的结构等价类型表达式的结构等价两个类型表达式完全相同（当无类型名时）两个类型表达式
68、完全相同（当无类型名时）把类型名都用它们定义的类型表达式代换，把类型名都用它们定义的类型表达式代换，所得两类型表达式完全相同所得两类型表达式完全相同( (类型定义无环时类型定义无环时) )typelink= cell;var next :link;last :link;p: cell;q,r : cell;5.5 类型表达式的等价类型表达式的等价类型表达式的结构等价测试类型表达式的结构等价测试sequiv(s,t)(无类型名时无类型名时)ifs和和t是相同的基本类型是相同的基本类型thenreturntrueelseifs=array(s1,s2)andt=array(t1,t2)thenre
69、turnsequiv(s1,t1)andsequiv(s2,t2)elseifs=s1 s2andt=t1 t2thenreturnsequiv(s1,t1)andsequiv(s2,t2)elseifs=pointer(s1)andt=pointer(t1)thenreturnsequiv(s1,t1)elseifs=s1s2andt=t1t2thenreturnsquiv(s1,t1)andsequiv(s2,t2)elsereturnfalse5.5 类型表达式的等价类型表达式的等价5.5.2类型表达式的名字等价类型表达式的名字等价把每个类型名看成是一个可区别的类型把每个类型名看成是一个
70、可区别的类型typelink= cell;var next :link;last :link;p: cell;q,r : cell;5.5 类型表达式的等价类型表达式的等价5.5.2类型表达式的名字等价类型表达式的名字等价把每个类型名看成是一个可区别的类型把每个类型名看成是一个可区别的类型两个类型表达式名字等价当且仅当这两个类两个类型表达式名字等价当且仅当这两个类型表达式不做名字代换就结构等价型表达式不做名字代换就结构等价typelink= cell;var next :link;last :link;p: cell;q,r : cell;5.5 类型表达式的等价类型表达式的等价Pascal的
71、许多实现用隐含的类型名和每个声明的许多实现用隐含的类型名和每个声明的标识符联系起来的标识符联系起来typelink= cell;typelink= cell;var next :link;np= cell;last :link;nqr= cell;p: cell;varnext:link;q,r : cell;last:link;p:np;q:nqr;r:nqr;5.5 类型表达式的等价类型表达式的等价注意注意: :类型名字的引入只是类型表达式的一个语法类型名字的引入只是类型表达式的一个语法约定问题，它并不像引入类型构造符或类型约定问题，它并不像引入类型构造符或类型变量那样能丰富我们所能表达的
72、类型变量那样能丰富我们所能表达的类型5.5 类型表达式的等价类型表达式的等价5.5.3记录类型记录类型(TypeRecord)(li是有区别的是有区别的)(ValRecord)(li是有区别的是有区别的)(ValRecordSelect) | T1, | Tn | record(l1:T1,ln:Tn) | M1:T1, | Mn:Tn | record (l1=M1,ln=Mn):record(l1:T1,ln:Tn) | M :record(l1:T1,ln:Tn) | M.lj :Tj (j 1.n)5.5 类型表达式的等价类型表达式的等价5.5.4类型表示中的环类型表示中的环typel
73、ink= cell;cell=recordinfo:integer;next:linkend;cell=record，:infopointernextintegercell5.5 类型表达式的等价类型表达式的等价5.5.4类型表示中的环类型表示中的环typelink= cell;cell=recordinfo:integer;next:linkend;cell=record，:infopointernextinteger5.5 类型表达式的等价类型表达式的等价 C语言对除记录（结构）以外的所有类型使语言对除记录（结构）以外的所有类型使用结构等价，而记录类型用的是名字等价，用结构等价，而记录类型
74、用的是名字等价，以避免类型图中的环。以避免类型图中的环。cell=record，:infopointernextintegercell5.6 函数和算符的重载函数和算符的重载重载符号重载符号有多个含义，但在引用点有多个含义，但在引用点的含义都是唯一的的含义都是唯一的例如：例如：加法算符加法算符+可用于不同类型，是不同的函数可用于不同类型，是不同的函数在在Ada中，中，()是重载的，是重载的，A(I)有不同含义有不同含义5.6 函数和算符的重载函数和算符的重载重载符号重载符号有多个含义，但在引用点有多个含义，但在引用点的含义都是唯一的的含义都是唯一的例如例如加法算符加法算符+可用于不同类型，是不
75、同的函数可用于不同类型，是不同的函数在在Ada中，中，()是重载的，是重载的，A(I)有不同含义有不同含义重载的消除重载的消除在重载符号的引用点，其含义能确定到唯一在重载符号的引用点，其含义能确定到唯一5.6 函数和算符的重载函数和算符的重载5.6.1子表达式的可能类型集合子表达式的可能类型集合例例Ada语言语言声明：声明：function“ ”(i,j:integer)returncomplex;function“ ”(x,y:complex)returncomplex;5.6 函数和算符的重载函数和算符的重载5.6.1子表达式的可能类型集合子表达式的可能类型集合例例Ada语言语言声明：声明
76、：function“ ”(i,j:integer)returncomplex;function“ ”(x,y:complex)returncomplex;使得算符使得算符 重载，重载，可能的类型包括：可能的类型包括：integer integerintegerinteger integer complexcomplex complexcomplex5.6 函数和算符的重载函数和算符的重载5.6.1子表达式的可能类型集合子表达式的可能类型集合例例Ada语言语言声明：声明：function“ ”(i,j:integer)returncomplex;function“ ”(x,y:complex)r
77、eturncomplex;使得算符使得算符 重载，重载，可能的类型包括：可能的类型包括：integer integerinteger2 (3 5) integer integer complexcomplex complexcomplex5.6 函数和算符的重载函数和算符的重载5.6.1子表达式的可能类型集合子表达式的可能类型集合例例Ada语言语言声明：声明：function“ ”(i,j:integer)returncomplex;function“ ”(x,y:complex)returncomplex;使得算符使得算符 重载，重载，可能的类型包括：可能的类型包括：integer inte
78、gerinteger2 (3 5) integer integer complex(3 5) z complex complexcomplexz是复型是复型5.6 函数和算符的重载函数和算符的重载以以函数应用为例，考虑类型检查函数应用为例，考虑类型检查在每个表达式都有唯一的类型在每个表达式都有唯一的类型时，函数应用时，函数应用的类型检查是：的类型检查是：EE1(E2)E.type=ifE2.type=s and E1.type=st thentelsetype_ error5.6 函数和算符的重载函数和算符的重载确定表达式可能类型的集合确定表达式可能类型的集合产产生生式式 语语义义规规则则 E
79、 E E .types=E.types E id E.types=lookup(id.entry) EE1(E2) E.types=t|E2.types中存在中存在一个一个s，使得使得st属于属于E1.types 5.6 函数和算符的重载函数和算符的重载例：表达式例：表达式3 5可能的类型集合可能的类型集合 E:i,cE:i3:iE:i5:i :i i i,i i c,c c c5.6 函数和算符的重载函数和算符的重载5.6.2 缩小可能类型的集合缩小可能类型的集合产产生生式式 语语义义规规则则 E E E .types=E.typesE. unique = if E . types = t
80、then t else type_errorE .code = E.code E id E.types=lookup(id.entry)E.code =gen(id.lexeme :E. unique)5.6 函数和算符的重载函数和算符的重载EE1(E2) E. types =s | E2. types中存在一中存在一个个s，使得使得s s 属于属于E1. typest = E. uniqueS =s | s E2. types and s t E1. types E2. unique =if S = s then s else type_errorE1. unique =if S = s t
81、hen s t else type_errorE.code = E1.code | E2.code | gen(apply: E. unique) 5.6 函数和算符的重载函数和算符的重载注意注意: :重载的函数和符号的引入使得程序员可以用重载的函数和符号的引入使得程序员可以用一个名字或符号表示多个不同类型的函数或一个名字或符号表示多个不同类型的函数或运算，它不像引入类型构造符或类型变量那运算，它不像引入类型构造符或类型变量那样能丰富我们所能表达的类型样能丰富我们所能表达的类型本本章章要要点点静态检查所涉及的内容：类型检查、控制流静态检查所涉及的内容：类型检查、控制流检查、唯一性检查和关联名字
82、检查等检查、唯一性检查和关联名字检查等类型在编程语言中的作用类型在编程语言中的作用描述类型系统的语言（类型表达式、断言、描述类型系统的语言（类型表达式、断言、定型规则）定型规则）设计完成类型检查的语法制导定义设计完成类型检查的语法制导定义多态函数的类型检查（代换、实例和合一）多态函数的类型检查（代换、实例和合一）重载函数和多态函数的区别重载函数和多态函数的区别类型表达式的等价类型表达式的等价例例题题1编译时的控制流检查的例子编译时的控制流检查的例子main()printf(“n%ldn”,gcd(4,12);continue;编译时的报错如下编译时的报错如下:continue.c:Infunc
83、tionmain:continue.c:4:continuestatementnotwithinaloop例例题题2编译时的唯一性检查的例子编译时的唯一性检查的例子main()inti;switch(i)case10:printf(“%dn”,10);break;case20:printf(“%dn”,20);break;case10:printf(“%dn”,10);break;编译时的报错如下：编译时的报错如下：switch.c:Infunctionmain:switch.c:7:duplicatecasevalueswitch.c:5:thisisthefirstentryforthat
84、value例例题题3C语言语言称称&为地址运算符，为地址运算符，&a为变量为变量a的地址的地址数组名代表数组第一个元素的地址数组名代表数组第一个元素的地址问题：问题：如果如果a是一个数组名，那么表达式是一个数组名，那么表达式a和和&a的值的值都是数组都是数组a第一个元素的地址，它们的使用是第一个元素的地址，它们的使用是否有区别的？否有区别的？例例题题3C语言语言称称&为地址运算符，为地址运算符，&a为变量为变量a的地址的地址数组名代表数组第一个元素的地址数组名代表数组第一个元素的地址问题：问题：如果如果a是一个数组名，那么表达式是一个数组名，那么表达式a和和&a的值的值都是数组都是数组a第一个
85、元素的地址，它们的使用是第一个元素的地址，它们的使用是否有区别的？否有区别的？用四个用四个C文件的编译报错或运行结果来提示。文件的编译报错或运行结果来提示。例例题题3typedefintA1020;Aa;A*fun()return(a);该该函函数数在在Linux上上用用gcc编编译译时时，报报告告的的错错误误如如下：下：第第6行行：warning: return from incompatiblepointertype例例题题3typedefintA1020;Aa;A*fun()return(&a);该函数在该函数在Linux上用上用gcc编译时，没有错误编译时，没有错误例例题题3typed
86、efintA1020;typedefintB20;Aa;B*fun()return(a);该函数在该函数在Linux上用上用gcc编译时，没有错误编译时，没有错误例例题题3typedefintA1020;Aa;fun()printf(“%d,%d,%dn”,a,a+1,&a+1);main()fun();该程序的运行结果是：该程序的运行结果是：134518112,134518192,134518912例例题题3结论结论对一个对一个t 类型的数组类型的数组ai1i2in 来说，来说，表达式表达式a的类型是：的类型是：pointer(array(0.i21,array(0.in1,t)表达式表达式
87、&a的类型是：的类型是：pointer(array(0.i11,array(0.in1,t)例例题题4在在X86/Linux机机器器上上，编编译译器器报报告告最最后后一一行行有有错误：错误：incompatibletypesinreturntypedefintA110;|A2*fun1()typedefintA210;|return(&a);A1a;|typedefstructinti;S1;|S2fun2()typedefstructinti;S2;|return(s);S1s;在在C语语言言中中，数数组组和和结结构构都都是是构构造造类类型型，为为什什么么上上面面第第2个个函函数数有有类类型型错错误误，而而第第1个个函函数没有？数没有？例例题题5编译器和连接装配器没能发现函数调用错误编译器和连接装配器没能发现函数调用错误longgcd(p,q)/*这是参数声明的传统形式这是参数声明的传统形式*/longp,q;/*现代形式是现代形式是longgcd(longp,longq)*/if(p%q=0)returnq;elsereturngcd(q,p%q);main()printf(“%ld,%ldn”,gcd(5),gcd(5,10,20);习习题题第一次：第一次：5.4,5.6第二次：第二次：5.16,5.17第三次：第三次：5.18
