类型表达式 类型自身有结构 int, int[3] 具体语法:出现在编程语言中 抽象语法:出现在类型检查的实现中 如int[2]3对应的抽象语法aray(2,aray(3 integer) arry是类型构造算子,有两个参数:数字和类型 ·定义与具体语言相关
类型表达式 • 类型自身有结构 • int, int[3] • 具体语法：出现在编程语言中 • 抽象语法：出现在类型检查的实现中 • 如int[2][3]对应的抽象语法array(2,array(3,integer)) • array是类型构造算子，有两个参数：数字和类型 • 定义与具体语言相关
本书中类型表达式的抽象语法 基本类型是类型表达式,如 boolean,char, integer, float void 类型变量是类型表达式 arry(n,t得到一个类型表达式 record(a1:t1…,an:t)得到一个类型表达式,a为字段名 pointer(t)得到指针类型的类型表达式 s→t得到函数类型的类型表达式 S×t是类型表达式,描述类型的元组(如函数参数列表) ·可以为类型表达式命名,类型名也是类型表达式 tFl struct int a[5]; char c) st
本书中类型表达式的抽象语法 • 基本类型是类型表达式，如boolean, char, integer, float, void • 类型变量是类型表达式 • array(n, t)得到一个类型表达式 • record(a1 : t1 , …, an : tn )得到一个类型表达式，a为字段名 • pointer(t)得到指针类型的类型表达式 • s → t得到函数类型的类型表达式 • s t是类型表达式，描述类型的元组（如函数参数列表） • 可以为类型表达式命名，类型名也是类型表达式 • 例 struct {int a[5]; char c} st;
类型表达式的等价 当允许对类型表达式命名后, 类型表达式是否相同就有了不同的解释 出现了结构等价和名字等价两个不同的概念 type link = cell link next link last cell*p; cell* a, r
类型表达式的等价 当允许对类型表达式命名后， • 类型表达式是否相同就有了不同的解释 • 出现了结构等价和名字等价两个不同的概念 type link = cell* ; link next ; link last ; cell* p ; cell* q, r;
类型表达式的结构等价 ·当无类型名时,两个类型表达式完全相同 类型表达式的抽象语法树(或DAG)一样 相同的类型构造算子作用于相同的子表达式 ·有类型名时,用它们所定义的类型表达式代换它 ,所得表达式完全相同(类型定义无环时) type link = cell link next cell link last celle* cell*p; cell* a, r next,last,p,q和r的类型结构等价
类型表达式的结构等价 • 当无类型名时，两个类型表达式完全相同 • 类型表达式的抽象语法树（或DAG）一样 • 相同的类型构造算子作用于相同的子表达式 • 有类型名时，用它们所定义的类型表达式代换它 们，所得表达式完全相同(类型定义无环时) next, last, p, q和r的类型结构等价 cell* cell* type link = cell* ; link next ; link last ; cell* p ; cell* q, r;
类型表达式的名字等价 ·把每个类型名看成是一个可区别的类型 ·两个类型表达式名字等价当且仅当这两个类型表 达式不进行名字代换就能结构等价 type link = cell link next link last next和ast的类型名字等价 cell*p; p,q和r的类型名字等价 cell* a, r
类型表达式的名字等价 • 把每个类型名看成是一个可区别的类型 • 两个类型表达式名字等价当且仅当这两个类型表 达式不进行名字代换就能结构等价 next和last的类型名字等价 p, q和r的类型名字等价 type link = cell* ; link next ; link last ; cell* p ; cell* q, r;