资源描述：
《上次课程小结.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、上次课程小结类型系统：赋给程序各部分的一组规则类型表达式：由类型构造符作用与基本类型表达式。基本的类型表达式：基本类型、类型名、类型变量的值类型构造符：×、＋、array(I,T)、pointer(T)、record（F1×F2×...)、D→R简单的类型检查：语法制导翻译声明时构造类型表达式引用时计算类型表达式（类型检查）4.4类型表达式的等价在简单的类型检查中，通过判定所给的两个类型表达式是否相等来进行类型检查。对于单态的类型，我们引入一个更专业的术语，类型等价来描述类型检查。类型的等价与类型的表示有关，表示不
2、同，等价的概念也不同。本节讨论三个重要问题：有哪些类型等价程序设计语言规定什么样的等价以及等价的判别4.4.1结构等价与等价的判别若两个仅由类型构造符作用于基本类型组成的类型表达式完全相同，则称两个类型表达式结构等价。换句话说，类型表达式结构等价当且仅当二者完全相等。若类型表达式中没有名字，则结构等价就是类型等价。例如int与int结构等价，array(1..10,real)与array(1..10,real)结构等价。反映在类型表达式的语法树上，就是两棵语法树完全相同。<1>结构等价的判别算法4.1判别类型是否结
3、构等价输入两个类型表达式输出若两个类型表达式结构等价则返回true否则false方法用下述递归函数进行判别：functionsequiv(s,t)returnbooleanisbeginendsequiv;ifsandtarethesametypethenreturntrue;elsifs=array(s1,s2)andt=array(t1,t2)thenreturnsequiv(s1,t1)andsequiv(s2,t2);elsifs=s1×s2andt=t1×t2thenreturnsequiv(s1,t1)
4、andsequiv(s2,t2);elsifs=pointer(s1)andt=pointer(t1)thenreturnsequiv(s1,t1);elsifs=s1→s2andt=t1→t2thenreturnsequiv(s1,t1)andsequiv(s2,t2);elsereturnfalse;endif;<1>结构等价的判别（续）例4.13再考虑函数声明functionmax(x,y:integer):integer和调用max(5,8)：在对调用语句max(5,8)的类型检查中，因为函数形参的类型和实
5、参的类型等价（sequiv(s,E2.type)=true），所以最终的函数值的类型为int。声明时：调用时：E→E1,E2{E.type:=E1.type×E2.type;}
6、E1(E2){E.type:=ifE2.type=sandE1.type=s→tthentelsetype_error;}<2>类型表达式的优化表示sequiv(s,t)算法的弱点：需要对两棵语法树完全遍历后才能确定它们是否等价。当类型构造符层次很多并且仅在最底层不等价时，算法的效率较低。改进的思路：在调用sequiv之前，先用一种简单的方
7、法将明确可以确定不等价的情况排除。即为了提高效率，牺牲一些次要信息，只有当两个类型表达式的主要信息相等时才判定次要信息是否也相等。具体方法：对类型表达式的主要信息进行编码。将类型构造符表示的每个内部节点的多于一个的孩子分支剪去，仅保留一个重要的分支，类型表达式的语法树就退化为一个链，即一条从根到叶子的路径。对链上每个节点编码，形成一个类型编码的字符串或者整型数。由于类型编码仅反映了类型表达式的主要成份，因此两个编码不同，则类型表达式一定不等价（从而起到过滤的作用），反之不一定。<2>类型表达式的优化表示（续1）数组
8、的类型表达式array(s,t)简化为array(t)，即忽略下标类型保留数组元素类型。函数的类型表达式s→t简化为freturns(t)，即忽略参数类型保留返回值的类型。指针的类型表达式pointer(t)本身就是一个一元的构造符，因此无需简化。问题：×与record的简化如何处理？简化类型表达式的编码：基本类型类型构造符类型编码构造符编码boolean0000pointer01char0001array10int0010freturns11real0011non00类型表达式的化简：<2>类型表达式的优化表示（
9、续2）基本类型类型构造符类型编码构造符编码boolean0000pointer01char0001array10int0010freturns11real0011non00例4.14考虑类型表达式array(1..10,pointer(int→char))：简化后的类型表达式为array(pointer(freturns(char)))。将其从左到右转换为编
