Microsoft PowerPoint - typecheck

Size: px

Start display at page:

Download "Microsoft PowerPoint - typecheck"

苏经
5 years ago
Views:

1 本章内容类型检查编译原理和技术张昱中国科学技术大学计算机科学与技术学院记号流语法分析器语法树语法树类型中间代码中间检查器生成器表示符号表语义检查中最典型的部分类型检查类型系统类型检查符号表的作用多态函数重载其他的静态检查 ( 不详细介绍 ) 控制流检查唯一性检查关联名字检查张昱 : 编译原理和技术语法制导的翻译 2 程序运行时的执行错误 5.1 类型在编程语言中的作用执行错误与安全语言类型化语言与类型系统类型的作用会被捕获的错误 (trapped error) 例 : 非法指令错误非法内存访问除数为零引起计算立即停止不会被捕获的错误 (untrapped error) 例 : 下标变量的访问越过了数组的末端 ; 跳到一个错误的地址, 该地址开始的内存正好代表一个指令序列错误可能会有一段时间未引起注意希望可执行的程序不存在不会被捕获的错误张昱 : 编译原理和技术语法制导的翻译 4 安全语言良行为的 (well-behaved) 程序没有统一的定义如 : 良行为的程序定义为没有任何不会被捕获的程序安全语言 (safe language) 定义 : 安全语言的任何合法程序都是良行为的设计类型系统, 通过静态类型检查拒绝不会被捕获错误设计正好只拒绝不会被捕获错误的类型系统是困难的禁止错误 (forbidden error) 不会被捕获错误集合 + 会被捕获错误的一个子集张昱 : 编译原理和技术语法制导的翻译 5 类型化的语言变量的类型限定了变量在程序执行期间的取值范围类型化的语言 (typed language) 变量都被给定类型的语言表达式语句等程序构造的类型都可以静态确定例如, 类型 boolean 的变量 x 在程序每次运行时的值只能是布尔值,not (x) 总有意义 no static types 未类型化的语言 (untyped language) 不限制变量值范围的语言, 如 LISP JavaScript Perl 张昱 : 编译原理和技术语法制导的翻译 6 1

2 类型化的语言显式类型化语言类型是语法的一部分隐式类型化的语言不存在隐式类型化的主流语言, 但可能存在忽略类型信息的程序片段, 如不需要程序员声明函数的参数类型类型系统语言的组成部分, 其构成成分是一组定型规则 (typing rule), 用来给各种程序构造指派类型设计目的用静态检查的方式来保证合法程序在运行时的良行为类型系统的形式化类型表达式定型断言定型规则类型检查算法通常是静态地完成类型检查张昱 : 编译原理和技术语法制导的翻译 7 张昱 : 编译原理和技术语法制导的翻译 8 类型可靠的语言良类型的程序 (well-typed program) 没有类型错误的程序, 也称合法程序类型可靠 (type sound) 的语言所有良类型程序 ( 合法程序 ) 都是良行为的类型可靠的语言一定是安全的语言语法的和静态的概念类型化语言良类型程序动态的概念安全语言良行为的程序若语言定义中, 除类型系统外, 没有用其它方式表示对程序的约束张昱 : 编译原理和技术语法制导的翻译 9 类型检查未类型化语言可以通过运行时的类型推断和检查来排除禁止错误类型化语言类型检查也可以放在运行时完成, 但影响效率一般都是静态检查, 类型系统被用来支持静态检查通常也需要一些运行时的检查, 如数组访问越界检查张昱 : 编译原理和技术语法制导的翻译 10 一些实际的编程语言并不安全禁止错误集合没有囊括所有不会被捕获的错误例 C 语言的共用体 union U { int u1; int u2; u; int p; u.u1 = 10; p = u.u2; p =0; 一些实际的编程语言并不安全 C 语言有很多不安全但被广泛使用的特征, 如 : 指针算术运算类型强制参数个数可变在语言设计的历史上, 安全性考虑不足是因为当时强调代码的执行效率在现代语言设计上, 安全性的位置越来越重要 C 的一些问题已经在 C++ 中得以缓和更多一些问题在 Java 中已得到解决张昱 : 编译原理和技术语法制导的翻译 11 张昱 : 编译原理和技术语法制导的翻译 12 2

3 类型化语言的优点具体语法从工程的观点看开发的实惠 : 较早发现错误类型信息具有文档作用编译的实惠 : 程序模块可以相互独立地编译运行的实惠 : 可得到更有效的空间安排和访问方式抽象语法变量 / 函数等声明 extern float a( ); int b; 表达式等语句 b = a( ); 更新类型信息取类型信息进行检查符号表 (a,extern, void float) (b,, int ) 5.2 描述类型系统的语言类型系统的形式化断言推理规则类型检查和类型推断张昱 : 编译原理和技术语法制导的翻译 13 类型系统的形式化类型系统是一种逻辑系统有关自然数的逻辑系统自然数表达式 ( 需要定义它的语法 ) a+b, 3 良形公式 ( 逻辑断言, 需要定义它的语法 ) a+b=3, (d=3) (c<10) 推理规则前提 a < b, b < c a < c 结论张昱 : 编译原理和技术语法制导的翻译 15 类型系统的形式化类型系统是一种逻辑系统有关自然数的逻辑系统自然数表达式 a+b, 3 良形公式 a+b=3, (d=3) (c<10) 推理规则 a < b, b < c a < c 定型环境 ( 符号表 ) 类型系统类型表达式 int, int int 定型断言 (typing assertion) x:int x+3 : int 定型规则 (typing rules) M : int, N : int M + N : int 张昱 : 编译原理和技术语法制导的翻译 16 断言断言的形式 S S 的所有自由变量都声明在中其中是一个静态定型环境 ( 编译器实现中的符号表 ), 如 x 1 :T 1,, x n :T n S 的形式随断言形式的不同而不同断言有三种具体形式张昱 : 编译原理和技术语法制导的翻译 17 断言的种类环境断言该断言表示是良形的环境将用推理规则来定义环境的语法 ( 而不是用文法 ) 语法断言 nat 在环境下,nat 是类型表达式将用推理规则来定义类型表达式的语法定型断言 M : T 在环境下, M 具有类型 T 例 : true : boolean x : nat x+1 : nat 将用推理规则来确定程序构造实例的类型张昱 : 编译原理和技术语法制导的翻译 18 3

4 断言的有效性推理规则断言的有效性有效断言 (valid assertion) true : boolean 无效断言 (invalid assertion) true : nat 推理规则 (inference rules) 1 S 1,, n S n S 前提 (premise) 结论(conclusion) 公理 (axiom)( 前提为空 ) 推理规则张昱 : 编译原理和技术语法制导的翻译 19 推理规则 ( 规则名 ) ( 注释 ) 推理规则 ( 注释 ) 环境规则 (Env ) 语法规则 (Type Bool) 在环境下, M + N 是 int 类型定型规则 (Val +) boolean M : int, N : int M + N : int 空环境是良形的环境 boolean 是类型表达式张昱 : 编译原理和技术语法制导的翻译 20 类型检查类型检查 (type checking) 用语法制导的方式, 根据上下文有关的定型规则来判定程序构造是否为良类型的程序构造的过程可以边解析边检查, 也可以在访问 AST 时进行检查 5.3 简单类型检查器的说明类型推断 (type inference) 类型信息不完全情况下的定型判定问题例如 :f (x : t) = E 和 f (x) = E 的区别一个简单的语言及类型系统类型检查张昱 : 编译原理和技术语法制导的翻译 21 一个简单的语言 P D ; S D D ; D id : T T boolean integer array [num ] of T T T T S id := E if E then S while E do S S ; S E truth num id E mod E E [ E ] E E (E ) 例 i : integer; j : integer; j := i mod 2000 张昱 : 编译原理和技术语法制导的翻译 23 类型系统环境规则 (Env ) (Decl Var) T, id dom ( ), id : T 其中 id : T 是该简单语言的一个声明语句遇到一个声明语句, 则向定型环境 ( 符号表 ) 中增加一个符号定型张昱 : 编译原理和技术语法制导的翻译 24 4

5 类型系统语法规则 (Type Bool) (Type Int) boolean integer (Type Void) void void 用于表示语句类型编程语言和定型断言的类型表达式并非完全一致类型系统语法规则 (Type Ref) (T void) 具体语法 : T (Type Array) (T void) 具体语法 :array [N] oft (Type Function) (T 1, T 2 void) T pointer(t) T, N : integer array(n, T) 定型断言中的类型表达式用的是抽象语法 T 1, T 2 T 1 T 2 (N>0) 张昱 : 编译原理和技术语法制导的翻译 25 张昱 : 编译原理和技术语法制导的翻译 26 类型系统 -- 定型规则类型系统 -- 定型规则定型规则表达式 (Exp Truth) truth : boolean 定型规则表达式 (Exp Mod) E 1 : integer, E 2 : integer E 1 mod E 2 : integer (Exp Num) (Exp Id) num : integer 1, id : T, 2 1, id : T, 2 id : T (Exp Index) (Exp Deref) (Exp FunCall) E 1 : array(n,t), E 2 : integer E 1 [E 2 ] : T (0 E 2 N 1) E : pointer(t) E : T E 1 : T 1 T 2, E 2 : T 1 E 1 (E 2 ) : T 2 张昱 : 编译原理和技术语法制导的翻译 27 张昱 : 编译原理和技术语法制导的翻译 28 类型系统 -- 定型规则定型规则语句 (State Assign) (T=boolean or T= integer) (State If) (State While) (State Seq) 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 S 1 : void, S 2 : void S 1 ; S 2 : void 张昱 : 编译原理和技术语法制导的翻译 29 类型检查设计语法制导的类型检查器设计依据 : 前面定义的类型系统类型环境的信息进入符号表对类型表达式采用抽象语法具体 :array [N] of T 抽象 :array (N, T) T pointer (T) 考虑到报错的需要, 增加了类型 type_error 张昱 : 编译原理和技术语法制导的翻译 30 5

6 类型检查声明语句类型检查声明语句 D D; D //D1 D id : T {addtype (id.entry, T.type) //D2 addtype: 把类型信息填入符号表如果是在访问 AST 时进行类型检查, 该怎么做呢? 如, 可以在 exitd2 ( ast ) 中增加对 addtype 的调用如何表达多个声明 D1 呢?(lab1-3) 组织成 list ( 可以用现成的表示线性表的容器类等 ) 如何处理多个声明 D1 呢? 对 list 中元素的迭代访问 ( 可以用现成的 Iterator 等 ) 张昱 : 编译原理和技术语法制导的翻译 31 D D; D D id : T {addtype (id.entry, T.type) T boolean {T.type = boolean (Bool,--) T integer {T.type = integer (Int, --) T T 1 {T.type = pointer(t 1.type) (Pointer,T1) T array [num] of T 1 {T.type = array(num.val, T 1.type) (Array,T1,num) T T 1 T 2 {T.type = T 1.type T 2.type (Fun,T1, T2) 如何表示不同的类型? ( 类型类别, 该类别类型的其他信息 ) 张昱 : 编译原理和技术语法制导的翻译 32 类型检查表达式类型检查表达式 E truth {E.type = boolean E num {E.type = integer E id {E.type = lookup(id.entry) 查符号表, 获取 id 的类型 E truth {E.type = boolean E num {E.type = integer E id {E.type = lookup(id.entry) E E 1 mod E 2 {E.type = if E 1.type == integer and E 2. type == integer then integer E E 1 [E 2 ] {E.type = if E 2. type == integer and E 1. type == array(s, t)thent 张昱 : 编译原理和技术语法制导的翻译 33 张昱 : 编译原理和技术语法制导的翻译 34 类型检查表达式类型转换 E E 1 { E.type =ife 1.type == pointer(t)thent E E 1 (E 2 ){E. type =ife 2. type == s and E 1. type == s t then t E E 1 op E 2 {E.type =ife 1.type == integer and E 2.type == integer then integer else if E 1.type == integer and E 2.type == real then real else if E 1.type == real and E 2.type == integer then real else if E 1.type == real and E 2.type == real then real 张昱 : 编译原理和技术语法制导的翻译 35 张昱 : 编译原理和技术语法制导的翻译 36 6

$类型检查语句 S id := E { if (id.type == E.type && E.type {boolean, integer) S.type = void; else S.type = type_error; S if E then S 1 {S. type = if E. type == boolean then S 1. type S while E do S 1 {S.$

7 类型检查语句 S id := E { if (id.type == E.type && E.type {boolean, integer) S.type = void; else S.type = type_error; S if E then S 1 {S. type = if E. type == boolean then S 1. type S while E do S 1 {S.type = if E.type == boolean then S 1. type S S 1 ; S 2 {S. type = if S 1. type == void and S 2.type== void then void 张昱 : 编译原理和技术语法制导的翻译 37 类型检查程序 P D; S {P. type = if S. type == void then void 类型检查器的实现一般是对语法树进行类型检查设计实现的关键 : 符号表的设计 : 如何表示不同的类型语法树的 Visitor 设计回顾 :ANTLR 会生成与标签对应的语法结构的 enter 和 exit 方法张昱 : 编译原理和技术语法制导的翻译 38 例题 1 编译时的控制流检查的例子 main() { printf( \n%ld\n,gcd(4,12)); continue; 编译时的报错如下 : continue.c: In function main : continue.c:3: continue statement not within a loop 张昱 : 编译原理和技术语法制导的翻译 39 例题 2 编译时的唯一性检查的例子 main() { int i; switch(i){ case 10: printf( %d\n, 10); break; case 20: printf( %d\n, 20); break; case 10: printf( %d\n, 10); break; 编译时的报错如下 : switch.c: In function main : switch.c:6: duplicate case value switch.c:4: this is the first entry for that value 张昱 : 编译原理和技术语法制导的翻译 40 例题 3 C 语言称 & 为地址运算符,&a 为变量 a 的地址数组名代表数组第一个元素的地址问题 : 如果 a 是一个数组名, 那么表达式 a 和 &a 的值都是数组 a 第一个元素的地址, 它们的使用是否有区别? 用四个 C 文件的编译报错或运行结果来提示例题 3 typedef int A[10][20]; Aa; A *fun() { return(a); 该函数在 Linux 上用 gcc 编译, 报告的错误如下 : 第 5 行 :warning: return from incompatible pointer type 张昱 : 编译原理和技术语法制导的翻译 41 张昱 : 编译原理和技术语法制导的翻译 42 7

8 例题 3 typedef int A[10][20]; Aa; A *fun() { return(&a); 该函数在 Linux 上用 gcc 编译时, 没有错误例题 3 typedef int A[10][20]; typedef int B[20]; Aa; B *fun() { return(a); 该函数在 Linux 上用 gcc 编译时, 没有错误张昱 : 编译原理和技术语法制导的翻译 43 张昱 : 编译原理和技术语法制导的翻译 44 例题 3 typedef int A[10][20]; Aa; fun() { printf( %d,%d,%d\n, a, a+1, &a+1); 例题 3 结论对一个 t 类型的数组 a[ i 1 ][ i 2 ] [ i n ] 来说, 表达式 a 的类型是 : pointer(array(0.. i 2 1, array(0.. i n 1, t) )) main() { fun(); 该程序的运行结果是 : , , 表达式 &a 的类型是 : pointer(array(0.. i 1 1, array(0.. i n 1, t) )) 张昱 : 编译原理和技术语法制导的翻译 45 张昱 : 编译原理和技术语法制导的翻译 46 类型表达式的等价 5.4 类型表达式的等价类型表达式的命名名字等价结构等价记录类型的定义对类型表达式命名 = 如何解释类型表达式相同? 结构等价名字等价是类型表达式的一个语法约定, 而不是引入新的类型 typedef cell *link; link next; link last; cell *p; cell *q, *r; 张昱 : 编译原理和技术语法制导的翻译 48 8

9 结构等价结构等价无类型名时, 两个类型表达式完全相同有类型名时, 用类型名所定义的类型表达式代换它们, 所得表达式完全相同 ( 类型定义无环时 ) typedef cell *link; link next; link last; cell *p; next, last, p, q 和 r 结构等价 cell *q, *r; 张昱 : 编译原理和技术语法制导的翻译 49 结构等价测试 sequiv(s, t) ( 无类型名时 ) if s 和 t 是相同的基本类型 then return true else if s == array(s 1, s 2 ) and t == array(t 1, t 2 ) then return sequiv(s 1, t 1 ) and sequiv(s 2, t 2 ) else if s == s 1 s 2 and t == t 1 t 2 then return sequiv(s 1, t 1 ) and sequiv(s 2, t 2 ) else if s == pointer (s 1 )andt == pointer(t 1 )then return sequiv(s 1, t 1 ) else if s == s 1 s 2 and t == t 1 t 2 then return squiv(s 1, t 1 ) and sequiv(s 2, t 2 ) else return false 张昱 : 编译原理和技术语法制导的翻译 50 名字等价名字等价把每个类型名看成是一个可区别的类型两个类型表达式不做名字代换就结构等价 typedef cell *link; link next; link last; next 和 last 名字等价 cell *p; p, q 和 r 名字等价 cell *q, *r; 类型表达式的等价 Pascal 语言的许多实现用隐含的类型名和每个声明的标识符联系起来 type link = cell; type link = cell; var next : link; np = cell; last : link; nqr = cell; p : cell; var next : link; q, r : cell; last : link; p : np; p 与 q 和 r 不是名字等价 q : nqr; r : nqr; 张昱 : 编译原理和技术语法制导的翻译 51 张昱 : 编译原理和技术语法制导的翻译 52 记录类型记录类型记录类型可看成其各个域类型的积类型记录和积之间的主要区别是记录的域被命名例如,C 语言的记录类型 typedef struct { int address; char lexeme [15 ]; row; 的类型表达式是 record(address : int, lexeme : array(15, char) ) 张昱 : 编译原理和技术语法制导的翻译 53 记录类型定型规则 (Type Record) (l i 是有区别的 ) T 1,, T n record(l 1 :T 1,, l n :T n ) (Val Record) (l i 是有区别的 ) M 1 :T 1,, M n : T n record (l 1 =M 1,, l n =M n ) : record (l 1 :T 1,, l n :T n ) (Val Record Select) M : record(l 1 :T 1,, l n :T n ) M.l j : T j (j 1..n) 张昱 : 编译原理和技术语法制导的翻译 54 9

10 类型表示中的环 type link = cell ; cell = record info : integer ; next : link end; 引入环的话, 递归定义的类型名可以替换掉 info cell = record, : : integer next pointer cell 张昱 : 编译原理和技术语法制导的翻译 55 类型表示中的环 typedef struct cell { int info; struct cell *next; cell; cell = record, : : info int next pointer 张昱 : 编译原理和技术语法制导的翻译 56 类型表示中的环 C 语言对除记录 ( 结构体 ) 共用体以外的所有类型使用结构等价, 而对记录类型用的是名字等价, 以避免类型图中的环 info cell = record, : : int next pointer cell 张昱 : 编译原理和技术语法制导的翻译 57 例题 4 在 X86/Linux 机器上, 编译器报告最后一行有错误 : incompatible types in return typedef int A1[10]; A2 *fun1( ) { typedef int A2[10]; return(&a); A1 a; typedef struct {int i;s1; S2 fun2( ) { typedef struct {int i;s2; return(s); S1 s; 在 C 语言中, 数组和结构体都是构造类型, 为什么上面第 2 个函数有类型错误, 而第 1 个函数却没有? 张昱 : 编译原理和技术语法制导的翻译 58 多态函数的引出 5.5 多态函数参数化多态类型系统的定义类型检查例如何编写求表长的通用程序? typedef struct { int info; link next; cell, *link; unknown type name link 张昱 : 编译原理和技术语法制导的翻译 60 10

11 多态函数的引出例如何编写求表长的通用程序? typedef struct cell{ int length(link lptr) { int info; int len = 0; link p = lptr; struct cell *next; while (list!= NULL) { cell, *link; len++; 计算过程与表元的数 p = p->next; 据类型无关, 但语言的类型系统使该函数不能通用 return len; 张昱 : 编译原理和技术语法制导的翻译 61 多态函数的引出例如何编写求表长的通用程序? 用 ML 语言很容易写出求表长的程序而不必管表元的类型 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1; tl- 返回表尾 null- 测试表是否为空 length ( [ sun, mon, tue ] ) length ( [10, 9, 8 ] ) 都等于 3 张昱 : 编译原理和技术语法制导的翻译 62 参数化多态多态函数 (polymorphic functions) 参数化多态允许函数参数的类型有多种不同的情况函数体中语句的执行能适应参数为不同类型的情况多态算符 (polymorphic operators) Ad-hoc 多态例如 : 数组索引函数应用通过指针间接访问相应操作的代码段接受不同类型的数组函数等 C 语言手册中关于取地址算符 & 的论述是 : 如果运算对象的类型是, 那么结果类型是指向的指针张昱 : 编译原理和技术语法制导的翻译 63 类型变量及其应用类型变量 length 的类型可以写成.list( ) integer 类型变量的引入便于讨论未知类型如, 在不要求标识符的声明先于使用的语言中, 可以通过使用类型变量来确定程序变量的类型 function deref (p); -- 对 p 的类型一无所知 : begin return p -- = pointer ( ) end; deref 的类型是. pointer( ) 张昱 : 编译原理和技术语法制导的翻译 64 多态函数的类型系统一个含多态函数的语言 P D; E 这是一个抽象语言, 忽略了函数定义的函数体 D D; D id : Q Q type-variable. Q 多态函数 T T T T T T 笛卡儿积类型 unary-constructor ( T ) basic-type type-variable 引入类型变量 ( T ) E E (E ) E, E id 张昱 : 编译原理和技术语法制导的翻译 65 多态函数的类型系统一个含多态函数的语言 P D; E D D; D id : Q Q type-variable. Q T T T T T T unary-constructor ( T ) basic-type type-variable ( T ) E E (E ) E, E id 一个程序 : deref :. pointer( ) ; q : pointer (pointer (integer)); deref (deref (q)) 张昱 : 编译原理和技术语法制导的翻译 66 11

12 多态函数的类型系统类型系统中增加的推理规则环境规则 (Env Var) 类型变量加到定型环境中, dom ( ), 多态函数的类型系统类型系统中增加的推理规则语法规则 (Type Parenthesis) T (T ) 语法规则 (Type Var) (Type Product) 1,, 2 1,, 2 T 1, T 2 T 1 T 2 张昱 : 编译原理和技术语法制导的翻译 67 (Type Forall), T.T (Type Fresh) 类型变量换名 ( i 不在中 ).T,, i, i [ i / ] T 张昱 : 编译原理和技术语法制导的翻译 68 多态函数的类型系统定型规则 (Exp Pair) E 1 : T 1, E 2 : T 2 E 1, E 2 : T 1 T 2 (Exp FunCall) E 1 : T 1 T 2, E 2 : T 3 E 1 (E 2 ) : S(T 2 ) ( 其中 S 是 T 1 和 T 3 的最一般的合一代换 ) 代换 : 类型表达式中的类型变量用其所代表的类型表达式去替换 subst(t:type_exp, Sv: type_var type_exp):type_exp 实例 : 把 subst 函数用于 t 后所得的类型表达式是 t 的一个实例, 用 S (t) 表示张昱 : 编译原理和技术语法制导的翻译 69 代换和实例 function subst (t : type_exp, Sv: type_var type_exp ) : type_exp; begin if t 是基本类型 then return t else if t 是类型变量 then return Sv(t) else if t 是 t 1 t 2 then return subst(t 1, Sv) subst(t 2, Sv) end 例子 (s < t 表示 s 是 t 的实例, 是类型变量 ) pointer( integer )<pointer( ) pointer( real )<pointer( ) integer integer < pointer( )< < 张昱 : 编译原理和技术语法制导的翻译 70 不合法的实例例下面左边的类型表达式不是右边的实例 integer real 代换不能用于基本类型 integer real 的代换不一致 integer 的所有出现都应该代换合一合一 (unify) 如果存在某个代换 Sv 使得 S(t 1 ) = S(t 2 ), 那么这两个表达式 t 1 和 t 2 能够合一最一般的合一代换 (the most general unifier) S S(t 1 ) = S(t 2 ); 对任何其它满足 S (t 1 ) = S (t 2 ) 的代换 Sv, 代换 S (t 1 ) 是 S(t 1 ) 的实例张昱 : 编译原理和技术语法制导的翻译 71 张昱 : 编译原理和技术语法制导的翻译 72 12

13 多态函数的类型检查多态函数和普通函数在类型检查上的区别 (1) 同一多态函数的不同出现不要求变元 / 参数有相同类型 (2) 必须把类型相同的概念推广到类型合一 (3) 要记录类型表达式合一的结果 apply: o deref o :pointer( o ) o apply : i deref i : pointer( i ) i q: pointer(pointer(integer)) deref(deref (q )) 的带标记的语法树张昱 : 编译原理和技术语法制导的翻译 73 检查多态函数的翻译方案 E E 1 (E 2 ) { p = mkleaf (newtypevar); // 返回类型 unify (E 1. type, mknode (, E 2.type, p) ); E. type = p E E 1, E 2 {E. type = mknode (, E 1.type, E 2.type) E id {E. type = fresh (lookup(id.entry)) // 类型变量张昱 : 编译原理和技术语法制导的翻译 74 例 : 多态函数的检查 apply: o deref o :pointer( o ) o deref i : pointer( i ) i 表达式 : 类型 q : pointer(pointer(integer)) deref i : pointer( i ) i deref i (q) : pointer(integer) deref o : pointer( o ) o deref o (deref i (q)) : integer apply : i q: pointer(pointer(integer)) 代换 i = pointer(integer) o = integer 张昱 : 编译原理和技术语法制导的翻译 75 求表长的函数的检查 length : ; lptr : ; fun length (lptr) = if null (lptr) then 0 if :. boolean ; else length (tl (lptr)) + 1; null :. list ( ) boolean ; tl :. list ( ) list ( ) ; 类型声明部分 0:integer ;1:integer ; +:integer integer integer ; match :. ; match ( -- 表达式, 匹配 length 函数的 length (lptr), -- 函数首部和函数体的类型 if (null (lptr), 0, length (tl(lptr)) +1) ) 张昱 : 编译原理和技术语法制导的翻译 76 求表长的函数的检查行定型断言代换规则 (1) lptr : (Exp Id) (2) length : (Exp Id) (3) length(lptr) : = (Exp FunCall) (4) lptr : 从 (1) 可得 (5) null : list( n ) boolean (Exp Id) 和 (Type Fresh) (6) null(lptr) : boolean = list ( n ) (Exp FunCall) (7) 0 : integer (Exp Num) (8) lptr : list( n ) 从 (1) 可得张昱 : 编译原理和技术语法制导的翻译 77 求表长的函数的检查行定型断言代换规则 (9) tl : list( t ) list( t ) (Exp Id) 和 (Type Fresh) (10) tl(lptr) : list( n ) t = n (Exp FunCall) (11) length : list( n ) 从 (2) 可得 (12) length(tl(lptr)) : (Exp FunCall) (13) 1 : integer (Exp Num) (14) + : integer integer integer (Exp Id) 张昱 : 编译原理和技术语法制导的翻译 78 13

14 求表长的函数的检查行定型断言代换规则 (15) length (tl(lptr)) +1 : integer = integer (Exp FunCall) (16) if : boolean i i i (Exp Id) 和 (Type Fresh) (17) if (... ) : integer i = integer (Exp FunCall) (18) match : m m (Exp Id) 和 (Type Fresh) m (19) match ( ) : integer m =integer (Exp FunCall) length 函数的类型是. list( ) integer 5.6 函数和算符重载 Ad-hoc 多态可能的类型集合及其缩小附加 : 子类型关系引起的协变和逆变张昱 : 编译原理和技术语法制导的翻译 79 重载重载符号有多个含义, 但在每个引用点的含义都是唯一的例如 : 加法算符 + 可用于不同类型, + 是多个函数的名字, 而不是一个多态函数的名字在 Ada 中,( ) 是重载的,A( I ) 有不同含义重载的消除在重载符号的引用点, 其含义能确定到唯一张昱 : 编译原理和技术语法制导的翻译 81 表达式的可能类型集合例 Ada 语言声明 : function (i, j : integer ) return complex; function (x, y : complex ) return complex; 使得算符重载, 可能的类型包括 : integer integer integer -- 这是预定义的类型 integer integer complex complex complex complex E:{i 3: {i (3 5) z(z:complex) E:{i, c E:{i : 5: {i {i i i, i i c, c c c 张昱 : 编译原理和技术语法制导的翻译 82 重载函数的应用缩小可能类型的集合 E E E. unique =ife. types == { t then t else type_error E id E. types = lookup(id. entry) E E 1 (E 2 ) E. types = {s E 2. types 中存在一个 s, 使得 s s 属于 E 1. types t = E. unique S = {s s E 2. types and s t E 1.types E 2. unique = if S == { s thens else type_error E 1. unique = if S == { s then s t else type_error 张昱 : 编译原理和技术语法制导的翻译 83 附加 : 子类型 - 协变和逆变子类型关系 < 类型上的偏序关系满足包含原理 : 如果 s 是 t 的子类型, 则需要类型为 t 的值时, 都可以将类型为 s 的值提供给它协变 (covariant)t<t', 则 c(t)<c(t') 函数类型在值域上是协变的假设 e:,e1:, 则 e(e1):. 如果 < ', 则 e(e1): '. 逆变 (contravariant)t<t', 则 c(t')<c(t) 函数类型在定义域上是逆变的假设 e:,e1: ', 如果 '<, 则 e(e1):. 张昱 : 编译原理和技术语法制导的翻译 84 14

15 例题 5 编译器和连接装配器未能发现下面的调用错误 long gcd (p, q) long p, q;{/* 这是参数声明的传统形式 */ /* 参数声明的现代形式是 long gcd ( long p, long q) { */ if (p%q == 0) return q; else return gcd (q, p%q); main() { printf( %ld,%ld\n, gcd(5), gcd(5,10,20)); 张昱 : 编译原理和技术语法制导的翻译 85 15

CC213

CC213 : (Ken-Yi Lee), E-mail: feis.tw@gmail.com 49 [P.51] C/C++ [P.52] [P.53] [P.55] (int) [P.57] (float/double) [P.58] printf scanf [P.59] [P.61] ( / ) [P.62] (char) [P.65] : +-*/% [P.67] : = [P.68] : ,