编程语言详细课程-课件1.ppt

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 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类 会被捕获的错误会被捕获的

4、错误（trapped error）例：例：非法指令错误、非法内存访问非法指令错误、非法内存访问、除数为零除数为零 引起计算立即停止引起计算立即停止5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类 会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令错误、非法内存访问非法指令错误、非法内存访问、除数为零除数为零 引起计算立即停止引起计算立即停止 不会被捕获的错误不会被捕获的错误（untrapped error）5.1 类型在编程语言中的作用类型在编程语言中的作用5.1

5、.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类 会被捕获的错误会被捕获的错误（trapped error）例：例：非法指令错误、非法内存访问非法指令错误、非法内存访问、除数为零除数为零 引起计算立即停止引起计算立即停止 不会被捕获的错误不会被捕获的错误（untrapped error）例：下标变量的例：下标变量的访问越过了数组的末端访问越过了数组的末端5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类 会被捕获的错误会被捕获的错误（tra

6、pped error）例：例：非法指令错误、非法内存访问非法指令错误、非法内存访问、除数为零除数为零 引起计算立即停止引起计算立即停止 不会被捕获的错误不会被捕获的错误（untrapped error）例：下标变量的例：下标变量的访问越过了数组的末端访问越过了数组的末端 例：例：跳到一个错误的地址，该地址开始的内存正跳到一个错误的地址，该地址开始的内存正好代表一个指令序列好代表一个指令序列 5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言程序运行时的执行错误分成两类程序运行时的执行错误分成两类 会被捕获的错误会被捕获的错误（trapped e

7、rror）例：例：非法指令错误、非法内存访问非法指令错误、非法内存访问、除数为零除数为零 引起计算立即停止引起计算立即停止 不会被捕获的错误不会被捕获的错误（untrapped error）例：下标变量的例：下标变量的访问越过了数组的末端访问越过了数组的末端 例：例：跳到一个错误的地址，该地址开始的内存正跳到一个错误的地址，该地址开始的内存正好代表一个指令序列好代表一个指令序列 错误可能会有一段时间未引起注意错误可能会有一段时间未引起注意 5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言良行为的程序良行为的程序 不同场合对良行为的定义略有区别

8、不同场合对良行为的定义略有区别 例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言良行为的程序良行为的程序 不同场合对良行为的定义略有区别不同场合对良行为的定义略有区别 例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序安全语言安全语言任何合法程序都是良行为的任何合法程序都是良行为的5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言良行为的程序良行为的程序 不同场合对良行为的定义略有区别不同场合对良行为的定义略

9、有区别 例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序安全语言安全语言任何合法程序都是良行为的任何合法程序都是良行为的 通常是设计一个类型系统，通过静态的类型检查通常是设计一个类型系统，通过静态的类型检查来拒绝不会被捕获错误来拒绝不会被捕获错误5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言良行为的程序良行为的程序 不同场合对良行为的定义略有区别不同场合对良行为的定义略有区别 例如，没有任何不会被捕获错误的程序例如，没有任何不会被捕获错误的程序安全语言安全语言任何合法程序都是良行为的任何合法程序都是良行为的 通常是设计一

10、个类型系统，通过静态的类型检查通常是设计一个类型系统，通过静态的类型检查来拒绝不会被捕获错误来拒绝不会被捕获错误 但是，设计一个类型系统，它正好只拒绝不会被但是，设计一个类型系统，它正好只拒绝不会被捕获错误是非常困难的捕获错误是非常困难的5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言禁止错误禁止错误（forbidden error）不会被捕获错误不会被捕获错误集合集合+会被捕获错误的一个子集会被捕获错误的一个子集5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言禁止错误禁止错误（forbid

11、den error）不会被捕获错误不会被捕获错误集合集合+会被捕获错误的一个子集会被捕获错误的一个子集 为语言设计类型系统的目标是在排除为语言设计类型系统的目标是在排除禁止错误禁止错误5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.1 执行错误和安全语言执行错误和安全语言禁止错误禁止错误（forbidden error）不会被捕获错误不会被捕获错误集合集合+会被捕获错误的一个子集会被捕获错误的一个子集 为语言设计类型系统的目标是在排除为语言设计类型系统的目标是在排除禁止错误禁止错误良行为程序和安全语言也可基于禁止错误来定义良行为程序和安全语言也可基于禁止错误来定义5.1 类型在编程

12、语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言 变量的类型变量的类型 变量在程序执行期间的取值范围变量在程序执行期间的取值范围5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言 变量的类型变量的类型 类型化的语言类型化的语言变量都被给定类型的语言变量都被给定类型的语言并且表达式、语句等语法构造的类型都是可以静态确定并且表达式、语句等语法构造的类型都是可以静态确定的的例如，类型例如，类型boolean的变量的变量x在程序每次运行时的值只能是在程序每次运行时

13、的值只能是布尔值布尔值，not(x)总总有意义有意义5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言 变量的类型变量的类型 类型化的语言类型化的语言 未类型化的语言未类型化的语言不限制变量值范围的语言：不限制变量值范围的语言：一个运算可以作用到任意的运算对象，其结果可能是一一个运算可以作用到任意的运算对象，其结果可能是一个有意义的值、一个错误、一个异常或一个语言未加定义的个有意义的值、一个错误、一个异常或一个语言未加定义的结果结果例如：例如：LISP语言语言5.1 类型在编程语言中的作用类型在编程语言中的作用5.1

14、.2 类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言 变量的类型变量的类型 类型化的语言类型化的语言 未类型化的语言未类型化的语言 显式类型化语言显式类型化语言类型是语法的一部分类型是语法的一部分5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型化的语言类型化的语言 变量的类型变量的类型 类型化的语言类型化的语言 未类型化的语言未类型化的语言 显式类型化语言显式类型化语言 隐式类型化的隐式类型化的语言语言不存在隐式不存在隐式类型化的类型化的主流语言，但可能存在忽略类型信主流语言，但可能存在忽略类型信息的程序片段，例如不

15、需要程序员声明函数的参数类型息的程序片段，例如不需要程序员声明函数的参数类型5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型系统类型系统 语言的组成部分语言的组成部分,由一组由一组定型规则定型规则（typing rule）构构成，这组规则用来给各种语言构造指派类型成，这组规则用来给各种语言构造指派类型5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型系统类型系统 语言的组成部分语言的组成部分,由一组由一组定型规则定型规则（typing rule）构构成，这组规则用来给各种语言构

16、造指派类型成，这组规则用来给各种语言构造指派类型 设计类型系统设计类型系统的根本目的是用静态检查的方式来保的根本目的是用静态检查的方式来保证合法程序运行时的良行为证合法程序运行时的良行为5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型系统类型系统 语言的组成部分语言的组成部分,由一组由一组定型规则定型规则（typing rule）构构成，这组规则用来给各种语言构造指派类型成，这组规则用来给各种语言构造指派类型 设计类型系统设计类型系统的根本目的是用静态检查的方式来保的根本目的是用静态检查的方式来保证合法程序运行时的良行为证合法程序运行

17、时的良行为 类型系统的形式化类型系统的形式化类型表达式、定型断言、定型规则类型表达式、定型断言、定型规则5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统类型系统类型系统 语言的组成部分语言的组成部分,由一组由一组定型规则定型规则（typing rule）构构成，这组规则用来给各种语言构造指派类型成，这组规则用来给各种语言构造指派类型 设计类型系统设计类型系统的根本目的是用静态检查的方式来保的根本目的是用静态检查的方式来保证合法程序运行时的良行为证合法程序运行时的良行为 类型系统的形式化类型系统的形式化类型表达式、定型断言、定型规则类型表达

18、式、定型断言、定型规则 类型检查算法类型检查算法通常是静态地完成类型检查通常是静态地完成类型检查5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统良类型的程序良类型的程序 没有类型错误的程序没有类型错误的程序5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统良类型的程序良类型的程序 没有类型错误的程序没有类型错误的程序合法程序合法程序 良类型程序（若语言定义中无其它方式表示的约良类型程序（若语言定义中无其它方式表示的约束）束）5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2

19、 类型化语言和类型系统类型化语言和类型系统良类型的程序良类型的程序 没有类型错误的程序没有类型错误的程序合法程序合法程序 良类型程序（若语言定义中无其它方式表示的约良类型程序（若语言定义中无其它方式表示的约束）束）类型可靠（类型可靠（type sound）的）的语言语言 所有良类型程序（合法程序）都是良行为的所有良类型程序（合法程序）都是良行为的 类型可靠的类型可靠的语言一定是安全的语言语言一定是安全的语言5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统语法的和静态的概念语法的和静态的概念动态的概念动态的概念类型化语言类型化语言安全语言安

20、全语言良类型程序良类型程序良行为的程序良行为的程序5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统未类型化语言未类型化语言 可以通过彻底的运行时详细检查来排除所有的禁止可以通过彻底的运行时详细检查来排除所有的禁止错误错误如如LISP语言语言5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统未类型化语言未类型化语言 可以通过彻底的运行时详细检查来排除所有的禁止可以通过彻底的运行时详细检查来排除所有的禁止错误错误如如LISP语言语言类型化语言类型化语言 类型检查也可以放在运行时完成，但影响

21、效率类型检查也可以放在运行时完成，但影响效率 一般都是静态检查，类型系统被用来支持静态检查一般都是静态检查，类型系统被用来支持静态检查 静态检查语言通常也需要一些运行时的检查静态检查语言通常也需要一些运行时的检查数组访问越界检查数组访问越界检查5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全 禁止错误集合没有囊括所有不会被捕获的错误禁止错误集合没有囊括所有不会被捕获的错误 Pascal语言语言 无标志的变体记录类型无标志的变体记录类型 函数型参数函数型参数5.1 类型在编程语言中的作用类

22、型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全 禁止错误集合没有囊括所有不会被捕获的错误禁止错误集合没有囊括所有不会被捕获的错误 Pascal语言语言 用用C语言的共用体（语言的共用体（union）来举例来举例union U int u1;int u2;u;int p;u.u1=10;p=u.u2;p=0;5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全 C语言语言还有很多不安全的并且被广泛使用的特征，如：还有

23、很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全 C语言语言还有很多不安全的并且被广泛使用的特征，如：还有很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变在语言设计的历史上，安全性考虑不足是因为强调代码在语言设计的历史上，安全性考虑不足是因为强调代码的执行效率的执行效率5.1 类型在编程语言中的作用类型在编程语言中的作

24、用5.1.2 类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安全实际使用的一些语言并不安全 C语言语言还有很多不安全的并且被广泛使用的特征，如：还有很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变在语言设计的历史上，安全性考虑不足是因为强调代码在语言设计的历史上，安全性考虑不足是因为强调代码的执行效率的执行效率 在现代语言设计上，安全性的位置越来越重要在现代语言设计上，安全性的位置越来越重要5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.2 类型化语言和类型系统类型化语言和类型系统实际使用的一些语言并不安

25、全实际使用的一些语言并不安全 C语言语言还有很多不安全的并且被广泛使用的特征，如：还有很多不安全的并且被广泛使用的特征，如：指针算术运算、类型强制、参数个数可变指针算术运算、类型强制、参数个数可变在语言设计的历史上，安全性考虑不足是因为强调代码在语言设计的历史上，安全性考虑不足是因为强调代码的执行效率的执行效率 在现代语言设计上，安全性的位置越来越重要在现代语言设计上，安全性的位置越来越重要 C的一些问题已经在的一些问题已经在C+中得以缓和中得以缓和更多一些问题在更多一些问题在Java中已得到解决中已得到解决5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.3 类型化语言的优点类型化

26、语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点 开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.3 类型化语言的优点类型化语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点 开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用 编译的实惠编译的实惠程序模块可以相互独立地编译程序模块可以相互独立地编译5.1 类型在编程语言中的作用类型在编程语言中的作用5.1.3 类型化语言的优点

27、类型化语言的优点从工程的观点看，类型化语言有下面一些优点从工程的观点看，类型化语言有下面一些优点 开发的实惠开发的实惠较早发现错误较早发现错误类型信息还具有文档作用类型信息还具有文档作用 编译的实惠编译的实惠程序模块可以相互独立地编译程序模块可以相互独立地编译 运行的实惠运行的实惠可得到更有效的空间安排和访问方式可得到更有效的空间安排和访问方式5.2 描述类型系统的语言描述类型系统的语言 类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则,它独立于类型检查算法它独立于类型检查算法5.2 描述类型系统的语言描述类型系统的语言 类型系统主要用来说明编程语言的定型规则类型系

28、统主要用来说明编程语言的定型规则,它独立于类型检查算法它独立于类型检查算法 定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法5.2 描述类型系统的语言描述类型系统的语言 类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则,它独立于类型检查算法它独立于类型检查算法 定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法 类型系统的基本概念可用于各类语言类型系统的基本概念可用于各类语言，包括包括函数式语言、命令式语言和并行语言等函数式语

29、言、命令式语言和并行语言等5.2 描述类型系统的语言描述类型系统的语言 类型系统主要用来说明编程语言的定型规则类型系统主要用来说明编程语言的定型规则,它独立于类型检查算法它独立于类型检查算法 定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法 类型系统的基本概念可用于各类语言类型系统的基本概念可用于各类语言，包括包括函数式语言、命令式语言和并行语言等函数式语言、命令式语言和并行语言等 本节讨论用形式方法来描述类型系统本节讨论用形式方法来描述类型系统5.2 描述类型系统的语言描述类型系统的语言 类型系统主要用来说明编程语言的定

30、型规则类型系统主要用来说明编程语言的定型规则,它独立于类型检查算法它独立于类型检查算法 定义一个类型系统，一种重要的设计目标是定义一个类型系统，一种重要的设计目标是存在有效的类型检查算法存在有效的类型检查算法 类型系统的基本概念可用于各类语言类型系统的基本概念可用于各类语言，包括包括函数式语言、命令式语言和并行语言等函数式语言、命令式语言和并行语言等 本节讨论用形式方法来描述类型系统本节讨论用形式方法来描述类型系统 然后讨论实例语言时：先定义语法，再给出类型然后讨论实例语言时：先定义语法，再给出类型系统的形式描述，最后写出类型检查的翻译方案系统的形式描述，最后写出类型检查的翻译方案5.2 描述

31、类型系统的语言描述类型系统的语言类型系统的形式化类型系统的形式化 类型系统是一种逻辑系统类型系统是一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统-自然数表达式自然数表达式（需要定义它的语法）（需要定义它的语法）a+b,3-良形公式良形公式（逻辑断言，需要定义它的语法）（逻辑断言，需要定义它的语法）a+b=3,(d=3)(c10)-推理规则推理规则 a b,b ca c5.2 描述类型系统的语言描述类型系统的语言类型系统的形式化类型系统的形式化 类型系统是一种逻辑系统类型系统是一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统类型系统类型系统-自然数表达式自然数表达式类型表达式类型表达式

32、 a+b,3 int int-良形公式良形公式 a+b=3,(d=3)(c10)-推理规则推理规则 a b,b ca c5.2 描述类型系统的语言描述类型系统的语言类型系统的形式化类型系统的形式化 类型系统是一种逻辑系统类型系统是一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统类型系统类型系统-自然数表达式自然数表达式类型表达式类型表达式 a+b,3 int int-良形公式良形公式定型断言定型断言 a+b=3,(d=3)(c10)x:int|x+3:int-推理规则推理规则(x:int 叫做定型环境叫做定型环境)a b,b ca c5.2 描述类型系统的语言描述类型系统的语言类型系统的形

33、式化类型系统的形式化 类型系统是一种逻辑系统类型系统是一种逻辑系统有关自然数的逻辑系统有关自然数的逻辑系统类型系统类型系统-自然数表达式自然数表达式类型表达式类型表达式 a+b,3 int int-良形公式良形公式定型断言定型断言 a+b=3,(d=3)(c10)x:int|x+3:int-推理规则推理规则定型规则定型规则|M:int,|N:int|M+N:int a b,b ca 0)(Type Function)(T1,T2 void)定型断言中的类型表达式也可以用抽象语法定型断言中的类型表达式也可以用抽象语法|T|pointer(T)|T,|N:integer|array(N,T)|T1

34、,|T2|T1 T25.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则表达式表达式(Exp Truth)(Exp Num)(Exp Id)|truth:boolean|num:integer 1,id:T,2|1,id:T,2|id:T5.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则表达式表达式(Exp Mod)(Exp Index)(0 E2 N 1)(Exp Deref)|E1:integer,|E2:integer|E1 mod E2:integer|E1:array(N,T),|E2:integer|E1E2:T|E:pointer(T)|E :T5.3

35、简单类型检查器的说明简单类型检查器的说明定型规则定型规则表达式表达式(Exp FunCall)|E1:T1 T2,|E2:T1|E1(E2):T25.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则语句语句(State Assign)(T=boolean or T=integer)(State If)(State While)|id:T,|E:T|id:=E:void|E:boolean,|S:void|if E then S:void|E:boolean,|S:void|while E do S:void5.3 简单类型检查器的说明简单类型检查器的说明定型规则定型规则语句语句(S

36、tate Seq)|S1:void,|S2:void|S1;S2:void5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查设计语法制导的类型检查器设计语法制导的类型检查器 设计依据是上节的类型系统设计依据是上节的类型系统 类型环境类型环境 的的信息进入符号表信息进入符号表 对类型表达式采用抽象语法对类型表达式采用抽象语法 具体：具体：array N of T抽象：抽象：array(N,T)T pointer(T)考虑到报错的需要，增加了类型考虑到报错的需要，增加了类型type_error5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查声明

37、语句声明语句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 boolean T.type=booleanT integer T.type=integerT T1 T.type=pointer(T1.type)5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查声明语句声明语句D D;DD id:T addtype(id.en

38、try,T.type)T boolean T.type=booleanT integer T.type=integerT T1 T.type=pointer(T1.type)T array num of T1 T.type=array(num.val,T1.type)5.3 简单类型检查器的说明简单类型检查器的说明5.3.3 类型检查类型检查声明语句声明语句D D;DD id:T addtype(id.entry,T.type)T boolean T.type=booleanT integer T.type=integerT T1 T.type=pointer(T1.type)T array

39、num of 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.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=

40、if E1.type=integer and E2.type=integer then integer else type_error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1 E2 E.type=if E2.type=integer and E1.type=array(s,t)then t else type_error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1 E2 E.type=if E2.type=integer and E1.type=array(s,t)then t else type_erro

41、r E E1 E.type=if E1.type=pointer(t)then t else type_error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查表达式表达式E E1 E2 E.type=if E2.type=integer and E1.type=array(s,t)then t else type_error E E1 E.type=if E1.type=pointer(t)then t else type_error E E1(E2)E.type=if E2.type=s and E1.type=s t then t else type_error 5.

42、3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S id:=E if(id.type=E.type&E.type boolean,integer)S.type=void;else S.type=type_error;5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S id:=E if(id.type=E.type&E.type boolean,integer)S.type=void;else S.type=type_error;S if E then S1 S.type=if E.type=booleanthen S1.type else type_

43、error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S while E do S1S.type=if E.type=boolean then S1.type else type_error 5.3 简单类型检查器的说明简单类型检查器的说明类型检查类型检查语句语句S while E do S1S.type=if E.type=boolean then S1.type else type_error S S1;S2S.type=if S1.type=void andS2.type=void then voidelse type_error 5.3 简单类型检查器的说

44、明简单类型检查器的说明类型检查类型检查程序程序P D;S P.type=if S.type=void then voidelse type_error 5.3 简单类型检查器的说明简单类型检查器的说明5.3.4 类型转换类型转换E E1 op E2E.type =if E1.type=integer and E2.type=integerthen integerelse if E1.type=integer and E2.type=realthen realelse if E1.type=real and E2.type=integerthen realelse if E1.type=real

45、 and E2.type=realthen realelse type_error 5.4 多多 态态 函函 数数5.4.1 为什么要使用多态函数为什么要使用多态函数例：用例：用Pascal语言写不出求表长度的通用程序语言写不出求表长度的通用程序type link=cell;cell=record info:integer;next:link end;5.4 多多 态态 函函 数数function length(lptr:link):integer;var len:integer;beginlen:=0;while lptr nil do begin len:=len+1;lptr:=lptr

46、.nextend;length:=lenend;5.4 多多 态态 函函 数数用用ML语言很容易写出求表长度的程序而不必语言很容易写出求表长度的程序而不必管表元的类型管表元的类型。fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;5.4 多多 态态 函函 数数用用ML语言很容易写出求表长度的程序而不必语言很容易写出求表长度的程序而不必管表元的类型管表元的类型。fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;length(“sun”,“mon”,“tue”)l

47、ength(10,9,8 )都等于都等于35.4 多多 态态 函函 数数 多态函数多态函数 允许变元有不同的类型允许变元有不同的类型5.4 多多 态态 函函 数数 多态函数多态函数 允许变元有不同的类型允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）区别于重载的特征）5.4 多多 态态 函函 数数 多态函数多态函数 允许变元有不同的类型允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）区别于重载的特征）多态算符多态算符 用于以不同类型的变元执行的

48、代码段用于以不同类型的变元执行的代码段5.4 多多 态态 函函 数数 多态函数多态函数 允许变元有不同的类型允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）区别于重载的特征）多态算符多态算符 用于以不同类型的变元执行的代码段用于以不同类型的变元执行的代码段 例如：例如：数组索引数组索引5.4 多多 态态 函函 数数 多态函数多态函数 允许变元有不同的类型允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）区别于重载的特征）多态算符多态算符 用于以不

49、同类型的变元执行的代码段用于以不同类型的变元执行的代码段 例如：例如：数组索引数组索引、函数作用函数作用5.4 多多 态态 函函 数数 多态函数多态函数 允许变元有不同的类型允许变元有不同的类型 体中的语句可以在变元类型不同的情况下执行（体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）区别于重载的特征）多态算符多态算符 用于以不同类型的变元执行的代码段用于以不同类型的变元执行的代码段 例如：例如：数组索引数组索引、函数作用、通过指针间接访问函数作用、通过指针间接访问5.4 多多 态态 函函 数数 多态函数多态函数 允许变元有不同的类型允许变元有不同的类型 体中的语句可以在变元类型不

50、同的情况下执行（体中的语句可以在变元类型不同的情况下执行（区别于重载的特征）区别于重载的特征）多态算符多态算符 用于以不同类型的变元执行的代码段用于以不同类型的变元执行的代码段 例如：例如：数组索引数组索引、函数作用、通过指针间接访问函数作用、通过指针间接访问 C语言手册中关于指针语言手册中关于指针&的论述是：的论述是：如果运算对象的类型是如果运算对象的类型是，那么结果类型是指，那么结果类型是指向向的指针的指针”5.4 多多 态态 函函 数数5.4.2 类型变量类型变量length的类型可以写成的类型可以写成 .list()integer 允许使用类型变量，还便于讨论未知类型允许使用类型变量，