编译原理与技术 类型检查 2018/11/21 《编译原理与技术》－类型检查.

Presentation on theme: "编译原理与技术 类型检查 2018/11/21 《编译原理与技术》－类型检查."— Presentation transcript:

1 编译原理与技术 类型检查 2018/11/21 《编译原理与技术》－类型检查

2 类型检查 类型体制 类型检查 － 类型等价 类型转换 － 隐式转换 － 显式转换 类型推导 － 算符重载 2018/11/21
《编译原理与技术》－类型检查

3 类型体制 程序设计语言中的类型 － 类型代表着某类值（域）的集合，如整型（数）、实型（数）、字符串等。
－ 类型本身具有结构；多数语言提供称为基本类型或预定义类型的“内建”类型，如C的int，char和double。同时可以应用类型构造器作用于基本类型得到“复合类型”，常见的类型构造器有record/struct、array、set、pointer、function等。 － 用“类型表达式”来表示具有类型的语言结构 －“类型体制”也就是将类型表达式指派到语言结构上的规则（集合），而类型检查则是来实现这个类型体制。 2018/11/21 《编译原理与技术》－类型检查

4 类型窄化(Narrowing)必须做type-cast
基本类型 C Java long double double double float float long long long int long short int char short byte char boolean 类型加宽(Widening) unsigned 类型窄化(Narrowing)必须做type-cast 2018/11/21 《编译原理与技术》－类型检查

5 － 联合/变体（union/variant) － 位域（bit fields）
复合类型 － 结构/记录（不同类型的对象聚集） C Pascal struct foo { RECORD int a; var a : integer; float b; var b : real; } ; END ; struct foo X; X.a = … － 联合/变体（union/variant) － 位域（bit fields） 2018/11/21 《编译原理与技术》－类型检查

6 a[0] = … a = new int[11]; a[0] := …
复合类型 － 数组（相同类型的对象聚集） C Java Pascal int a[11]; int [ ] a; var a : array [0..10] of integer; a[0] = … a = new int[11]; a[0] := … 2018/11/21 《编译原理与技术》－类型检查

7 int *a; Integer Ref; var p : ^ integer; int x = 11; new(p);
复合类型 － 指针 C Java Pascal int *a; Integer Ref; var p : ^ integer; int x = 11; new(p); Ref = new Integer(15); a = &x; Ref . intValue() ; *a = … p := … p^ := … 2018/11/21 《编译原理与技术》－类型检查

8 如： int foo(…)  (void) foo(…) － 通用指针 如C中，int *ptr ; …  (void *) ptr
－ 返回类型、空参数列表 如C中：void foo( void ) － cast 如： int foo(…)  (void) foo(…) － 通用指针 如C中，int *ptr ; …  (void *) ptr 2018/11/21 《编译原理与技术》－类型检查

9 － 采用类型构造器作用于类型表达式上，可以得到新的类型表达式。
语言结构的类型可表示为类型表达式。 － 基本类型可作为类型表达式； － 类型名也可以是类型表达式； － 采用类型构造器作用于类型表达式上，可以得到新的类型表达式。 （1）数组：array( I, T ) ; I 、T分别为下标与数组元素的类型； （2）积：x ； 如 T1 x T2 ； （3）记录：record ( (域名x域类型) 的积 ) （4）指针: pointer( T ) ; T 为所指对象类型 （5）函数：参数类型的积  结果类型 － 类型表达式可以含（类型）变量。 2018/11/21 《编译原理与技术》－类型检查

10 student stu1, stu2; //stu1的类型表达式如下：
e.g. 给出以下声明的类型表达式： typedef struct { char name[32]; int age; float score; } student; student stu1, stu2; //stu1的类型表达式如下： record( (name x array(0..31, char) ) x (age x int ) x (score x float ) ) 2018/11/21 《编译原理与技术》－类型检查

11 student * enter( char * name,
e.g. 给出以下函数的类型表达式： student * enter( char * name, int age, float score ) 函数enter的类型表达式为： ( pointer(char) x int x float )  pointer( student) 2018/11/21 《编译原理与技术》－类型检查

12 类型检查 类型检查就是语言类型体制的“实现”
如： 运算符mod（或C中的％）一般要求参与运算的左、右表达式类型均为整型（或兼容类型），那么可以将此类型检查“形式化”为： EE1 mod E2 { if (E1.type == INT) and (E2.type == INT) then E.type :=INT else E.type := type_error } 2018/11/21 《编译原理与技术》－类型检查

13 EE1 [ E2 ] { if (E1.type == array(s,t) ) and (E2.type == s)
而数组元素的类型检查可描述如下： EE1 [ E2 ] { if (E1.type == array(s,t) ) and (E2.type == s) then E.type := t else E.type := type_error } 2018/11/21 《编译原理与技术》－类型检查

14 － 确定两个名字或值是否具有“相同”的类型 结构等价：structure equivalence
类型等价 － 确定两个名字或值是否具有“相同”的类型 结构等价：structure equivalence 两个类型结构等价，如果它们的组成成分相同且组织方式相同；是一种面向实现“较低级”的“类型检查”； 存在问题：不能区分那些虽然内部结构完全相同，但其实确为不同的类型。如C的2个结构定义： struct person { struct school { char * name; char * name; char * address; char * address; int age; int age; } a; } b; a = b; //??? C中除了结构类型外（struct），其他类型均采用结构等价。 2018/11/21 《编译原理与技术》－类型检查

15 int y; /* x 和 y 是否类型（名）等价？ */
名等价：name equivalence －每一个类型定义可视为引入新的类型； － 类型别名，如C中： typedef int INT; INT x; int y; /* x 和 y 是否类型（名）等价？ */ － 严格（strict）名等价：将类型的别名也看成不同的类型；即，将别名看成一个新的类型“定义”； － 松散（loose）名等价：类型的别名看成相同的类型；即，将别名看成一个“声明”，而与原来的类型共享有关“定义”。 C中结构类型采用名等价。 2018/11/21 《编译原理与技术》－类型检查

16 TYPE Alink = POINTER TO Cell; TYPE Blink = Alink;
e.g. 指出以下变量声明中的类型等价关系 TYPE Cell = … TYPE Alink = POINTER TO Cell; TYPE Blink = Alink; VAR p,q : POINTER TO Cell; VAR r : Alink; VAR s : Blink; VAR t,u : POINTER TO Cell; VAR v : Alink; 2018/11/21 《编译原理与技术》－类型检查

17 严格名等价： p和q具有相同类型； t和u具有相同类型； r和v具有相同类型； 松散名等价： r、v和u具有相同类型； 结构等价：
所有7个变量具有相同类型！ p（或q）与t（或u）是否名等价呢？ 一般情况下，p或t的类型，即“无名”类型： POINTER TO Cell 被看成不同的类型定义! 2018/11/21 《编译原理与技术》－类型检查

18 类型转换 在某些程序上下文环境中，所使用的对象的类型为A，而实际所需的类型确为B。此时需要对有关“类型”进行转换。例如：
(1) int i ; float f ; f = i; //赋值语句 (2) //表达式 (3) char * p ; p = (char*) malloc(…); // 函数返回值（参数） 隐式转换－ 类型强制（type coercion） 显式转换－type cast 2018/11/21 《编译原理与技术》－类型检查

19 － 类型兼容性（type compatibility）
隐式转换（类型强制） － 类型兼容性（type compatibility） 在实际需要类型B的上下文中，也允许使用类型A；此时，多由编译器完成相关类型检查和（产生代码）进行相关类型的转换。 C/C++中有许多类型隐式转换，如： short = unsigned long //取低端2字节 unsigned long = short //符号扩展 short = char // 0 或符号扩展 float = unsigned long // 无符号长整数->浮点数，可能丢失精度 double = float; // 单精度浮点数->双精度浮点数 float = double // 双精度浮点数->单精度浮点数，可能丢失精度 2018/11/21 《编译原理与技术》－类型检查

20 long double + any  long double 否则 double + any  double 否则
隐式转换 更多算术运算中的转换：如果 long double + any  long double 否则 double + any  double 否则 float + any  float 否则 unsigned long + any  unsigned long 否则 long + unsigned int  unsigned long 否则 long + any  long 否则 unsigned int + any  unsigned int 否则 int( any ) + any  int 2018/11/21 《编译原理与技术》－类型检查

21 显式转换 － 可以看成是“函数”调用 如下C的声明： struct person { struct school {
char * name; char * name; char * address; char * address; int age; int age; } a; } b; 虽然a 和 b 结构上“是”等价的，但C语言要求对结构进行名等价，因此语句 a = ( person ) b ; 不能实行转换！ 考虑语句 a = * ( person *) &b; // OK? ! 2018/11/21 《编译原理与技术》－类型检查

22 类型推导 语言结构的类型（含义）可能随上下文而变化。如表达式 a + b ，当a和b均为整型时，表达式亦为整型，而a或b为complex（复数型），则为complex型。 算符或函数重载（overloading） － 算符或函数在不同的上下文中有不同的含义 － 多数时候可以根据上下文消除重载； 2018/11/21 《编译原理与技术》－类型检查

23 重载 多数语言中对算符“×”重载，如： int × int  int int × int  complex
complex × complex  complex 设 3，4 ，5仅为整型；z为complex型，那么 3 ×（4 × 5） 和 （ 3 × 5 ） × z 的类型是什么？ 2018/11/21 《编译原理与技术》－类型检查