《编译原理第五章类型检查.》由会员分享，可在线阅读，更多相关《编译原理第五章类型检查.（132页珍藏版）》请在金锄头文库上搜索。
1、第五章 类 型 检 查 本章内容 静态检查中最典型的部分 类型检查： 类型系统、类型检查、多态函数、重载 忽略其它的静态检查：控制流检查、唯一性检查、 关联名字检查 语法 分析 器 类型 检查 器 中间 代码 生成 器 语法树 语法树 中间 表示 记号流 5.1 类型在编程语言中的作用 5.1.1 执行错误和安全语言 介绍一些和程序运行有联系的概念 5.1 类型在编程语言中的作用 5.1.1 执行错误和安全语言 1、程序运行时的执行错误分成两类 会被捕获的错误（trapped error） 5.1 类型在编程语言中的作用 5.1.1 执行错误和安全语言 1、程序运行时的执行错误分成两类 会被捕
2、获的错误（trapped error） 例：非法指令错误错误 5.1 类型在编程语言中的作用 5.1.1 执行错误和安全语言 1、程序运行时的执行错误分成两类 会被捕获的错误（trapped error） 例：非法指令错误错误 、非法内存访问访问 、除数为为零 引起计计算立即停止 5.1 类型在编程语言中的作用 5.1.1 执行错误和安全语言 1、程序运行时的执行错误分成两类 会被捕获的错误（trapped error） 例：非法指令错误错误 、非法内存访问访问 、除数为为零 引起计计算立即停止 不会被捕获的错误（untrapped error） 例：下标变量的访问访问 越过过了数组组的末端
3、5.1 类型在编程语言中的作用 5.1.1 执行错误和安全语言 2、良行为的程序 没有任何不会被捕获错误的程序 3、安全语言 任何合法程序都是良行为的 通常是设计设计 一个类类型系统统，通过过静态态的类类型检检 查查来拒绝绝不会被捕获获的错误错误 设计设计 一个类类型系统统，它正好只拒绝绝不会被捕获获 错误错误 是非常困难难的 5.1 类型在编程语言中的作用 5.1.2 类型化语言和类型系统 4、类型化的语言 变量的类型 变量在程序执行期间的取值范围 5.1 类型在编程语言中的作用 5.1.2 类型化语言和类型系统 4、类型化的语言 变量的类型 类型化的语言 变量都被给定类型的语言 表达式、语
4、句等程序构造的类型都可以静态确定 例如，类型boolean的变量x在程序每次运行时的值只能是 布尔值，not (x)总有意义 5.1 类型在编程语言中的作用 5.1.2 类型化语言和类型系统 4、类型化的语言 变量的类型 类型化的语言 未类型化的语言 不限制变量值范围的语言： 一个运算可以作用到任意的运算对象，其结果可能是一个 有意义的值、一个错误、一个异常或一个语言未加定义的结 果 例如：LISP语言 5.1 类型在编程语言中的作用 5.1.2 类型化语言和类型系统 4、类型化的语言 变量的类型 类型化的语言 未类型化的语言 显式类型化语言 类型是语法的一部分 5.1 类型在编程语言中的作用
5、 5.1.2 类型化语言和类型系统 4、类型化的语言 变量的类型 类型化的语言 未类型化的语言 显式类型化语言 隐式类型化的语言 不存在隐式类型化的主流语言，但可能存在忽略类型信 息的程序片段，例如不需要程序员声明函数的参数类型 5.1 类型在编程语言中的作用 5.1.2 类型化语言和类型系统 5、类型系统 语言的组成部分,由一组定型规则（typing rule）构 成，这组规则用来给各种程序构造指派类型 设计类型系统的根本目的是用静态检查的方式来保 证合法程序运行时的良行为 类型系统的形式化 类型表达式、定型断言、定型规则 类型检查算法 通常是静态地完成类型检查 5.1 类型在编程语言中的作
6、用 5.1.2 类型化语言和类型系统 语法的和静态的概念动态的概念 类型化语言安全语言 良类型程序良行为的程序 5.1 类型在编程语言中的作用 5.1.2 类型化语言和类型系统 6、类型检查：未类型化语言 可以通过彻底的运行时检查排除所有的禁止错误 如LISP语言 7、类型检查：类型化语言 类型检查也可以放在运行时完成，但影响效率 一般都是静态检查，类型系统被用来支持静态检查 静态检查语言通常也需要一些运行时的检查 数组访问越界检查 5.1 类型在编程语言中的作用 5.1.2 类型化语言和类型系统 实际使用的一些语言并不安全 禁止错误集合没有囊括所有不会被捕获的错误 Pascal语言 无标志的
7、变体记录类型 函数类型的参数 5.1 类型在编程语言中的作用 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语言 还有很多不安全的并且被广泛使用的特征，如： 指针算术运算、类型强制、参数个数可变 在语言设计的历史上，安全性考虑不足是因为当时强调 代码的执行效率 在现
8、代语言设计上，安全性的位置越来越重要 C的一些问题已经在C+中得以缓和 更多一些问题在Java中已得到解决 5.1 类型在编程语言中的作用 5.1.3 类型化语言的优点 从工程的观点看，类型化语言有下面一些优点 开发的实惠 较早发现错误 类型信息还具有文档作用 编译的实惠 程序模块可以相互独立地编译 运行的实惠 可得到更有效的空间安排和访问方式 5.2 描述类型系统的语言 类型系统主要用来说明编程语言的定型规则, 它独立于类型检查算法 定义一个类型系统，一种重要的设计目标是 存在有效的类型检查算法 本节讨论用形式化方法来描述类型系统 然后讨论实例语言时：先定义语法，再给出类型 系统的形式描述，
9、最后写出类型检查的翻译方案 5.2 描述类型系统的语言 类型系统的形式化 类型系统是一种逻辑系统 有关自然数的逻辑系统 - 自然数表达式（需要定义它的语法） a+b, 3 - 良形公式（逻辑断言，需要定义它的语法） a+b=3, (d=3)(c10) - 推理规则 a b, b c a c 5.2 描述类型系统的语言 类型系统的形式化 类型系统是一种逻辑系统 有关自然数的逻辑系统类型系统 - 自然数表达式类型表达式 a+b, 3 int, int int - 良形公式 a+b=3, (d=3)(c10) - 推理规则 a b, b c a c 5.2 描述类型系统的语言 类型系统的形式化 类型
10、系统是一种逻辑系统 有关自然数的逻辑系统类型系统 - 自然数表达式类型表达式 a+b, 3 int, int int - 良形公式定型断言 a+b=3, (d=3)(c10)x:int | x+3 : int - 推理规则( x:int 叫做定型环境 ) a b, b c a c 5.2 描述类型系统的语言 类型系统的形式化 类型系统是一种逻辑系统 有关自然数的逻辑系统类型系统 - 自然数表达式类型表达式 a+b, 3 int, int int - 良形公式定型断言 a+b=3, (d=3)(c10)x:int | x+3 : int - 推理规则定型规则 | M : int, | N : i
11、nt | M + N : int a b, b c a 0) 具体语法： array N of T (Type Function) (T1, T2 void) 定型断言中的类型表达式用的是抽象语法 | T | pointer(T) | T, | N : integer | array(N, T) | T1, | T2 | T1 T2 5.3 简单类型检查器的说明 定型规则表达式 (Exp Truth) (Exp Num) (Exp Id) | | truth : boolean | | num : integer 1, id : T, 2 | 1, id : T, 2 | id : T 5.3
12、 简单类型检查器的说明 定型规则表达式 (Exp Mod) (Exp Index) (0 E2 N1) (Exp Deref) | E1: integer, | E2: integer | E1 mod E2: integer | E1: array(N,T), | E2: integer | E1E2 : T | E : pointer(T) | E : T 5.3 简单类型检查器的说明 定型规则表达式 (Exp FunCall) | E1: T1 T2, | E2: T1 | E1 (E2) : T2 5.3 简单类型检查器的说明 定型规则语句 (State Assign) (T=bool
13、ean 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: void 5.3 简单类型检查器的说明 定型规则语句 (State Seq) | S1: void, | S2: void | S1; S2 : void 5.3 简单类型检查器的说明 5.3.3 类型检查 设计语法制导的类型检查器 设计依据是上节的类型系统 类型环
14、境的信息进入符号表 对类型表达式采用抽象语法 具体：array N of T抽象：array (N, T) T pointer (T) 考虑到报错的需要，增加了类型type_error 5.3 简单类型检查器的说明 5.3.3 类型检查声明语句 D D; D D id : T addtype (id.entry, T.type) addtype：把类型信息填入符号表 5.3 简单类型检查器的说明 5.3.3 类型检查声明语句 D D; D D id : T addtype (id.entry, T.type) T boolean T.type = boolean T integer T.type = integer T T1 T.type = pointer(T1.type) 5.3 简单类型检查器的说明 5.3.3 类型检查声明语句 D D; D D id : T addtype (id.entry, T.type) T boolean T.type = boolean T integer T.type = integer T T1 T.type = pointer(T1.type) T array num of T1 T.type = array(num.val,
