北大编译原理讲义chapter5_2.ppt

《北大编译原理讲义chapter5_2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、5.8类型分析每个程序设计语言都有自己的类型机制，包括类型说明和使用。类型分析是编译器语义分析的重要组成部分 。编译器首先根据类型说明，确定每一个变量和常量的类型 ，计算其使用存储空间的大小，从而建立其到存储空间的映射。进而，编译器要确定每个语言结构的类型，以完成下面的主要任务：（1）判定重载算符（函数）在程序中代表是那一个运算；（2）进行类型转换；（3）对语言结构进行类型检查。15.8.1类型表达式5.8.1.1类型表达式定义语言结构的类型由类型表达式指称，类型表达式依赖于程序语言的类型体制。类型表达式或者是简单类型表达式，或者是构造符作用在类型表达式上得到

2、的类型表达式。类型表达式的定义如下：   （1）类型名和基本类型是类型表达式。integer、char、real、boolean是基本类型，所以它们是类型表达式。另外，void表示“无类型”，type_error表示“出错类型”，它们也是类型表达式。2（2）类型构造符作用于类型表达式的结果仍然是类型表达式。类型构造符包括：  （a）数组构造符ARRAY：若T是类型表达式，则ARRAY（I,T）是类型表达式。（b）笛卡儿乘积：若T1、T2是类型表达式，则T1T2是类型表达式，且是左结合。 （c）记录类型构造符RECORD：若有标识符N1、N2……、N

3、n与类型表达式T1、T2、…、Tn，则RECORD（（N1T1）（N2T2）…（NnTn））是一个类型表达式，它指称一个记录类型。3（d）指针类型构造符POINTER：若T是类型表达式，则POINTER（T）是类型表达式，它指称一个指针类型。   （e）函数类型构造符→：若D1、D2、…、Dn和R是类型表达式，则D1D2……Dn→R是类型表达式，其中优先于→，它指称从定义域类型D1D2…Dn到值域类型R的映射。  （3）类型表达式中可出现类型变量，变量值是类型表达式。4例5.23设有Pascal程序片段：TYPEstype=REC

4、ORDname:ARRAY[1..8]OFchar;score:integerEND;VARtable:ARRAY[1..50]OFstype;p:↑stype;则stype代表的类型表达式RECORD((nameARRAY(1..8,char))(scoreinteger))和table绑定的类型表达式ARRAY(1..50,stype)和P绑定的类型表达式POINTER(stype)5例5.24设有下面的函数定义FUNCTIONf(P1:T1;P2:T2;…，Pn:Tn):T;   BEGIN……END;和f绑定的类型表达式T1T2…Tn→T

5、例5.25在函数式语言中可如下定义恒等函数funf(x)=xx可以是任何类型的语言结构。因此x可以是任何类型。f的类型表达式为为类型变量，其值是任何类型表达式。6类型表达式的表达方法1.树:内部结点是类型构造符，叶结点是基本类型，类型名或类型变量。例如，FUNCTIONf(a,b:char):integer:………charcharpointer(integer)pointerintegercharchar72.位串(对类型表达式作某些限制)例如，考虑由POINTER、→和ARRAY作为构造符的类型表达式。Pointer(t)表示指向类型为t的

6、指针，freturns(t)表示若干变元的函数,其中t为函数返回对象的类型,而函数变元的类型则存放在其它地方。ARRAY(t)表示元素类型为t的数组，而数组元素的个数保存在其它地方。这样，构造符都成为一元算符，它们作用于基本类型形成的类型表达式有非常统一的结构。8类型构造符编码pointer01array10freturns11基本类型编码boolean0000char0001integer0010real0011类型表达式编码char0000000001freturns(char)0000110001pointer(freturns(char))000111

7、0001array(pointer(freturns(char)))100111000195.8.1.2类型表达式的等价根据语言的类型体制和类型表达式的表示方法，分结构等价和名字等价。结构等价两个类型表达式结构等价，当且仅当它们完全相同。图5.30是测试两个类型表达式结构等价的算法，假设类型构造符仅有数组、笛卡儿积、指针和函数，这个算法递归地比较两个类型表达式的结构。FUNCTIONeq(s,t):boolean;BEGINIFs和t是相同的基本类型THENreturn(true)10ELSEIF(s=ARRAY(s1,s2))and(t=ARRAY(t1,t

8、2))THENreturn(eq(s1