《编译原理》第6章-类型检查课件

语义分析类型检查验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。控制流检查控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。一致性检查在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。相关名字检查有时，同一名字必须出现两次或多次。例如，Ada语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。名字的作用域分析第六章类型检查本章内容静态检查中最典型的部分—类型检查： 类型系统、类型检查、多态函数、重载。忽略其它的静态检查：控制流检查、唯一性检查、相关名字检查。每个程序设计语言都有自己的类型机制，包括类型说明和使用。

类型分析是编译器语义分析的重要组成部分

。编译器首先根据类型说明，确定每一个变量和常量的类型

，计算其使用存储空间的大小，从而建立其到存储空间的映射。进而，编译器要确定每个语言结构的类型，以完成下面的主要任务：

（1）判定重载算符（函数）在程序中代表的是哪一个运算；（2）进行类型转换；（3）对语言结构进行类型检查。6类型分析

6.1.1类型表达式定义

语言结构的类型由类型表达式表示，类型表达式依赖于程序语言的类型体制。类型表达式或者是简单类型表达式，或者是构造符作用在类型表达式上得到的类型表达式。类型表达式的定义如下：

（1）类型名和基本类型是类型表达式。integer、char、real、boolean是基本类型，所以它们是类型表达式。另外，void表示“无类型”，type_error表示“出错类型”，它们也是类型表达式。6.1类型表达式

（2）类型构造符作用于类型表达式的结果仍然是类型表达式。类型构造符包括：

（a）数组构造符ARRAY：若T是类型表达式，则ARRAY（I,T）是类型表达式。

（b）笛卡儿乘积：若T1、T2是类型表达式，则T1T2是类型表达式，且是左结合的。

（c）记录类型构造符RECORD：若有标识符N1、N2……、Nn与类型表达式T1、T2、…、Tn，则RECORD（（N1

T1）（N2

T2）

…

（Nn

Tn））是一个类型表达式，它表示一个记录类型。6.1类型表达式

（d）指针类型构造符POINTER：若T是类型表达式，则POINTER（T）是类型表达式，它表示一个指针类型。

（e）函数类型构造符→：若D1、D2、…、Dn和R是类型表达式，则D1D2

……Dn→R是类型表达式，其中优先于→，它表示从定义域类型D1

D2

…

Dn到值域类型R的映射。

（3）类型表达式中可出现类型变量，变量是类型表达式。6.1类型表达式

设有Pascal程序片段：

TYPEstype=RECORD

name:ARRAY[1..8]OFchar;

score:integer

END;

VAR

table:ARRAY[1..50]OFstype;

p:↑stype;

则stype代表的类型表达式

RECORD((nameARRAY(1..8,char))

(scoreinteger))

和table绑定的类型表达式ARRAY(1..50,stype)

和p绑定的类型表达式

POINTER(stype)例

例1

设有下面的函数定义

FUNCTIONf(P1:T1;P2:T2;…，Pn:Tn):T;

BEGIN……END;

和f绑定的类型表达式T1T2

…

Tn→T

例2

在函数式语言中可如下定义恒等函数

funf(x)=x

x可以是任何类型的语言结构。因此x可以是任何类型。f的类型表达式为

为类型变量，其值是任何类型表达式。例

1.树:内部结点是类型构造符，叶结点是基本类型，类型名或类型变量。例如，

FUNCTIONf(a,b:char):integer:………charcharpointer(integer)pointerintegercharchar类型表达式的表达方法2.位串(对类型表达式作某些限制)

例如，考虑由POINTER、→和ARRAY作为构造符的类型表达式。pointer(t)表示指向类型为t的指针，freturns(t)表示若干变元的函数,其中t为函数返回对象的类型,而函数变元的类型则存放在其它地方。ARRAY(t)表示元素类型为t的数组，而数组元素的个数保存在其它地方。这样，构造符都成为一元算符，它们作用于基本类型形成的类型表达式有非常统一的结构。类型表达式的表达方法类型构造符编码

pointer01array10freturns11

基本类型编码

boolean0000char0001integer0010real0011

类型表达式编码

char0000000001freturns(char)0000110001pointer(freturns(char))0001110001array(pointer(freturns(char)))1001110001根据语言的类型体制和类型表达式的表示方法，分结构等价和名字等价。

结构等价

两个类型表达式结构等价，当且仅当它们完全相同。图6-6是测试两个类型表达式结构等价的算法，假设类型构造符仅有数组、笛卡儿积、指针和函数，这个算法递归地比较两个类型表达式的结构。

FUNCTIONeq(s,t):boolean;

BEGIN

IFs和t是相同的基本类型

THEN

return(true)

6.1.2类型表达式的等价ELSEIF(s=ARRAY(s1,s2))and(t=ARRAY(t1,t2))THEN

return(eq(s1,t1)andeq(s2,t2))

ELSEIF(s=s1s2)and(t=t1t2)THENreturn(eq(s1,t1)and(eq(s2,t2))

ELSEIF(s=POINTER(s1))and(t=POINTER(t1))THENreturn(eq(s1,t1))

ELSEIF(s=s1→s2)and(t=t1→t2)THEN

return(eq(s1,t1)andeq(s2,t2))

ELSEreturn(false)

END

类型可以命名。例如，

TYPELink=↑cell;

VARnext:Link;(6－2）

Last:Link;

P:↑cell;

q,r:↑cell;

所谓名字等价，是指两个等价类型有同一个名字，也就是说，两个不同的类型名表示不同的类型。在结构等价中，把类型表达式中的所有名字用它们所代表的类型表达式替换后，两个类型表达式等价即是结构等价。

类型表达式中的名字

例6.2下面给出和声明（6-2）中的5个变量相联系的类型表达式。

变量类型表达式

next

Link

last

Link

p

Pointer(cell)

q

Pointer(cell)

r

Pointer(cell)

在名字等价下，变量next和last有同样的类型;next和p的类型不相同。在结构等价下，所有五个变量都有同样的类型。不同的语言中，通过声明将变量标识符和类型相联系的规则是不同的，在解释这些规则时，结构等价和名字等价是两个有用的概念。

例6.3

在一些Pascal的实现中，用隐含的类型名和每个声明的变量标识符相联系，如果说明中出现没有名字的类型表达式，就建立一个隐含的类型名。

如（6－2）中的声明是如下处理的：

TYPEVAR

Link=↑cell;next:link;

np=↑cell;

last:link;

nqr=↑cell;

p:np;

q

:nqr;

r:nqr;

典型的实现是构造一张类型图，每当遇到类型构造符和基本类型，就建立一个新结点，但要记住类型名所命名的类型表达式。在这种方法中，如果两个类型表达式用类型图中同样的结点表示，那么，它们等价。link=pointerpointerpointercellnextlastpqr图6-7链表和树结构经常是递归定义的。它们的结点通常定义成一个记录，记录中含有指向同类型记录的指针。设链表中的结点含有一个整型信息和一个指向下一个结点的指针，实现链表的类型定义：

TYPElink=node;node=RECORDinfo:integer;next:linkEND;类型表示中的环用图表示类型表达式node=recordinfointegernextpointernodenode=recordnextinfointegerpointera.无环b.有环

C语言对除记录（结构）以外的所有类型使用结构等价，而记录类型用的是名字等价，以避免类型图中的环。cell=record::infopointernextintegercell6.2.1变量标识符和类型表达式的绑定程序说明部分建立计算环境,其中说明了每个变量标识符以及与之绑定的类型。语法(6－3)是一个简单的程序语言语法，该程序由一系列声明D和随后的一个表达式E组成，假设数组的下标从1开始。

文法G[P]，产生式如下：

(6－3)

P→D；E

D→D；D|id:T

T→char|integer|ARRAY[num]OFT|↑T

E→num|id|EMODE|E[E]|E↑6.2类型分析

语义分析程序首先处理类型说明，建立类型表达式，然后处理变量说明，建立变量和类型表达式的绑定。具体实现是把变量标识符的类型信息记录在其符号表的表项中，过程addtype（id.entry,T.type）完成这个任务，其翻译模式由图6－4给出

P→D；E

D→D；D

D→id:T

{addtype（id.enery，T.TYPE）}

T→char

{T.type:=char}

T→integer

{T.type:=integer}

T→↑T1

{T.type:=POINTER(T1.type)}

T→ARRAY[num]OFT1

{T.type:=ARRAY(num.val,T1.type)}

图6-4建立变量标识符和类型属性绑定的翻译模式

6.2.2类型检查类型检查可以分为动态和静态两种。动态检查在运行时刻完成。功效很低。但是如果语言允许动态确定类型，动态检查是必须的。静态检查在编译时刻完成。静态检查是高效的。如果一个语言能够保证经过静态检查之后，程序没有运行时刻的类型错误，则称为强类型的。类型检查的内容包括：表达式语句函数

检查运算对象之间的类型是否满足相容条件,函数lookup（e）取符号表中保存在条目e中的类型。

E→num

{E.type:=integer}

E→id

{E.type:=lookup(id.entry)}

E→E1MODE2

{E.type:=IF(E1.type=integer)AND(E2.type=integer)

THENintegerELSEtype_error}

E→E1[E2]

{E.type:=IF(E2.type=integer)AND(E1.type=ARRAY(s,t))

THENtELSEtype_error}

E→E1↑

{E.type:=IFE1.type=POINTER(t)

THENtELSEtype_error}

表达式的类型检查的翻译模式

表达式的类型检查

语句的类型检查主要包括：赋值语句类型的相容性，控制表达式的结果类型检查。指派给语句的类型是基本类型void，如果在语句中发现类型错误，指派给语句的类型是type_error。

语句的类型检查

S→id:=E{S.type:=IFid.type=E.type

THENvoidELSEtype_error}

S→IFETHENS1

{S.type:=IFE.type=boolean

THENS1.typeELSEtype_error}

S→WHILEEDOS1{S.type:=IFE.type=boolean

THENS1.typeELSEtype_error}

S→S1;S2{S.type:=IF(S1.type=void)AND(S2.type=void)

THENvoid

ELSEtype_error}

图6－5检查语句类型的翻译模式

对说明部分的分析，应该能知道被引用函数的类型。翻译模式为：

T→T1‘→’T2{T.type:=T1.type→T2.type}

函数引用可看成一个表达式作用于另一个表达式，它的类型检查是：

E→E1(E2){E.type:=IF(E2.type=s)AND(E1.type=s→t)

THENtELSEtype_error}

把单个参数推广到多个参数,类型为T1、T2、…、Tn的n个变元可以看成类型为T1T2

…Tn的一个变元。函数引用的类型检查

6.2.2类型转换

一般的程序设计语言中都规定了某些类型之间的转换关系：比如说整数量可以被当作实数量参与运算，并且不需要程序员显式说明。不同类型的常数在计算机中有不同的表示。当一个值需要转换成为其它类型使用的时候，需要使用某些代码进行转换。因此，编译程序要识别需要进行类型转换的地方，并相应地生成代码。程序设计语言的设计者需要考虑什么情况下需要和可以进行转换。

考虑表达式x+i，其中x是实型，i是整形,它的后缀式可能是

xiinttorealreal+

语言的定义会指出必须要做的类型转换。例如，当整数赋给实型变量时，应该把赋值号右边对象转换成左边对象的类型。

例6.6

考虑把算术运算符op作用于常数和标识符形成的表达式，假设运算对象有整型和实型两个类型

，函数lookup(e)返回符号表中保存在e条目中的类型。

6.2.2类型转换

E→num{E.type:=integer}

E→num.num{E.type:=real}

E→id{E.type:=lookup(id.entry)}

E→E1opE2{E.type:=IF(E1.type=integer)AND(E2.type=integer)

THENintegerELSE

IF(E1.type=integer)AND(E2.type=real)

THENrealELSE

IF(E1.type=real)AND(E2.type=integer)

THENreal

ELSE

IF(E1.type=real)AND(E2.type=real)

THENreal

ELSEtype_error}

图6－9需要强制类型转换的类型检查

运算符（函数）的重载多态函数重载运算符（overloadingoperator）根据上下文可以执行不同的运算。＋是重载符号，在A＋B中，当A和B为整数、实数、复数或者矩阵时，运算符执行不同类型的运算。当出现重载运算符时，要确定它所表示的唯一的意义，称为运算符识别。检查运算符的操作数。多态函数能实现对数据结构进行操作的算法，不管数据结构的元素类型是什么。多态函数的特点每次被调用时，传递过来的参数可以具有不同类型。

6.1假如有下面的Pascal说明

TYPE

atype=ARRAY[0..9,-10..10]OFinteger;

cell=RECORD

a,b:integer

END;

pcell=↑cell