58类型分析

58类型分析内容摘要：

q,r: ↑cell。 所谓名字等价，是指两个等价类型有同一个名字，也就是说，两个类型名表示不同的类型。 在结构等价中，在类型表达式中的所有名字被它们代表的类型表达式替换后，两个类型表达式等价即是结构等价。 13 例 下面给出和声明（ ）中的 5个变量相 联系的类型表达式。 变 量 类 型表 达 式 next Link last Link p Pointer(cell) q Pointer(cell) r Pointer(cell) 在名字等价下，变量 next和 last有同样的类 型。 next和 p的类型不相同。 在结构等价下， 所有五个变量都有同样的类型。 14 不同的语言中，通过声明变量标识符和类型 联系的规则是不同的，在解释这些规则时，结构等价和名字等价是两个有用的概念。 例 在一些 Pascal的实现中，用隐含的类 型名和每个声明的变量标识符相联系，如果说明中出现没有名字的类型表达式，就建立一个 隐含的类型名。 TYPE VAR Link=↑cell。 next : link。 np=↑cell。 last : link。 nqr=↑cell。 p : np。 q,r : nqr。 15 典型的实现是构造一张类型图，每当遇到类 型构造符和基本类型，就建立一个新结点，但 要记住类型名所命名的类型表达式。 在这种方 法中，如果两个类型表达式用类型图中同样的 结点表示，那么，它们等价。 link = pointer pointer pointer cell next last p q r 图 16 类型表示中的环 链表和树结构经常是递归定义的。 它们的结点通常定义成一个记录，记录中含有指向同类型记录的指针。 设链表中的结点含有一个整型信息和一个指向下一个结点的指针，实现链表的类型定义： TYPE link=node。 node=RECORD info:integer。 next: link END。 17 类型表达式用图表示如下： Node=record    Info integer next pointer node Node=record    next Info integer pointer a. 无环 b. 有环 18 类型分析 变量标识符和类型表达式的绑定 程序说明部分建立计算环境 ,其中说明了每个变量标识符以及与之绑定的类型。 语法()是一个简单的程序语言语法，假设数组的下标从 1开始。 文法 G[P]，产生式如下： (5 . 10) P→D； E D→D； D|id:T T→char| integer| ARRAY[num] OF T|↑T E→。