编译原理类型检查.ppt

第六章 类型检查,内容,类型系统类型表达式的等价类型转换函数和运算符的重载多态函数一致化算法,静态检查（static checking）,类型检查（type check）操作对象必须与操作符匹配：函数名相加控制流检查（flow-of-control check）break必须退出while、for、switch唯一性检查（uniqueness check）对象（变量、标号）定义必须唯一名字关联检查（name-related check）相同名字在不同位置,类型检查,检查语法结构的类型与上下文匹配简单的类型检查两个类型的匹配代码生成要利用类型信息重载，多态,6.1 类型系统,语法结构、类型、将类型赋予语法结构+,-,*的两个运算数均为整数，结果为整数&的结果为指向操作对象的指针，若操作对象类型为T，结果类型为“指向T的指针”每个表达式都有一个相关联的类型类型是有结构的！指针基本类型：语言内部支持类型结构类型：组合基本类型构成新类型,6.1.1 类型表达式,type expression用以表示语言结构的类型基本类型或用类型构造符组合基本类型基本类型：boolean,char,integer,real,type_error,void类型名,类型表达式（续）,类型构造符数组：T是类型表达式，I为索引集合（整数范围），则array(I,T)是一个类型表达式，表示元素为类型T的数组类型int A10;array(0,9,integer)笛卡儿积：T1、T2为类型表达式，则T1T2为类型表达式,类型表达式（续）,记录：与笛卡儿积的不同之处仅在于记录的域有名字。元组typedef struct int address;char lexeme15;row;row table101;类型表达式为：record(addressinteger)(lexemearray(0,15,char),类型表达式（续）,指针：T为类型表达式，则pointer(T)为类型表达式，表示“指向类型为T的对象的指针”类型row*p;pointer(row)函数：数学上，一个集合“定义域”到另一个集合“值域”的映射。程序语言，定义域类型D到值域类型R的映射：DR。%运算符(intint)intint*f(char a,char b);(charchar)pointer(integer)不考虑函数返回数组、函数类型的情况(integerinteger)(integerinteger)可使用类型表达式变量,图表示类型表达式,(charchar)pointer(integer),6.1.2 类型系统,type system：规则的集合规则将类型表达式赋予程序的不同部分类型检查程序：实现一个类型系统语法制导方式实现嵌入语义规则,静态/动态检查,静态编译器进行动态运行时进行可靠类型系统，强类型语言编译器无type_error运行时无类型错误int a10,i;b=ai;需动态检查安全领域也涉及类型检查（缓冲溢出问题）,6.1.4 错误恢复,最低要求：报告类型错误位置错误处理应融入规则中错误修正比描述正确程序更困难根据错误的程序、处理缺失信息，来推测正确类型在变量使用之前无需定义它类型变量可用来处理这种问题,6.2 一个简单的类型检查器,6.2.1 一种简单语言用综合属性type保存类型表达式P D;ED D;D|id:TT char|integer|array num of T|TE literal|num|id|E mod E|E E|E基本类型：char、integer、type_error例CODESome Types Expressionskey:integer;array256 of char array(1.256,char)key mod 1999 integer pointer(integer),翻译模式,P D;E D D;D D id:T addtype(id.entry,T.type)T charT.type=char T integer T.type=integer T array num of TT.type=array(1.num.val,T.type)T T T.type=pointer(T.type)Did:T的规则在符号表保存标识符类型T.type由后几个产生式语义规则计算PD;E，D在E之前，保证在检查表达式类型之前类型已经保存入符号表,6.2.2 表达式类型检查,E literal E.type=char E numE.type=integer E id E.type=lookup(id.entry)E E1 mod E2E.type=if(E1.type=integer)and(E2.type=integer)then integer else type_error E E1 E2 E.type=if(E2.type=integer)and(E1.type=array(s,t)then t else type_error E E1E.type=if(E1.type=pointer(t)then t else type_error 可添加其他类型和运算,6.2.3 语句的类型检查,赋值、条件、while无错误，void；错误，type_errorS id:=ES.type=if(lookup(id.entry)=E.type)then void else type_error S if E then S1S.type=if(E.type=boolean)then S1.type else type_error S while E do S1S.type=if(E.type=boolean)then S1.type else type_error S S1;S2S.type=if(S1.type=void)and(S2.type=void)then void else type_error,6.2.4 函数的类型检查,函数定义T T1 T2 T.type=T1.typeT2.type 函数调用E E1(E2)E.type=if(E2.type=s)and(E1.type=st)then t else type_error 多参数：T1,TnT1Tn更复杂例子：root:(realreal)realrealfunction root(function f(real):real;x:real):real,6.3 类型表达式的等价,两个类型表达式等价的精确定义？用类型表示方式可快速确定等价性结构等价和名字等价类型表达式的图表示不同叶结点为基本类型或类型名递归定义类型会导致回路,6.3.1 类型表达式的结构等价,结构等价（structural equivalence）相同的基本类型对子表达式施加的类型构造符相同两个类型表达式结构等价dag中对应相同结点有时要放松条件数组参数忽略界限等价性检查算法稍做修改,等价性检查算法,bool sequiv(s,t)if(s和t为相同基本类型)return true;else if(s=array(s1,s2)and t=array(t1,t2)return sequiv(s1,t1)and sequiv(s2,t2);else if(s=s1s2 and t=t1t2)return sequiv(s1,t1)and sequiv(s2,t2);else if(s=pointer(s1)and t=pointer(t1)return sequiv(s1,t1);else if(s=s1s2 and t=t1t2)return sequiv(s1,t1)and sequiv(s2,t2);else return false;,例6.1：编码类型表达式,用二进制码表示类型和构造符节省内存，加速检测二进制码不同的类型表达式肯定不等价D.M.Ritchie，C编译器忽略数组界限和函数参数charfreturns(char)pointer(freturns(char)array(pointer(freturns(char),例6.1（续）,构造符的编码pointer01array10freturns11基本类型编码boolean0000char0001integer0010real0011,例6.1（续）,编码方法最右端四位二进制位表示基本类型它前面两位表示第一个构造符再前面两位表示第二个构造符类型表达式编码char000000 0001freturns(char)000011 0001pointer(freturns(char)000111 0001array(pointer(freturns(char)100111 0001,例6.1（续）,加速等价性检查不同二进制串不可能表示相同类型不同类型可能表示为相同二进制串数组界限、函数参数记录的编码在类型表达式中记录作为基本类型用另一个二进制串编码它的域,6.3.2 名字等价,type link=cell;var next:link;last:link;p:cell;q,r:cell;5个变量类型是否都相同？依赖实现允许类型表达式命名，但不允许回路名字等价：完全相同结构等价：名字被替换后完全相同,例6.2,变量类型表达式nextlinklastlinkppointer(cell)qpointer(cell)rpointer(cell)名字等价：next,last类型相同，p,q,r类型相同，p,next类型不同结构等价：5个变量类型都相同,例6.3,许多Pascal编译器会隐含地为每条标识符定义语句涉及到的类型关联一个类型名type link=cell;np=cell;nqr=cell;var next:link;last:link;p:np;q,r:nqr;名字等价：next,last类型相同，q,r类型相同，p,next,q类型不同,例6.3（续）,实现方式构造类型图对基本类型和类型构造符创建新结点对新类型名创建叶结点，保存与类型表达式的链接名字等价相同结点,6.3.3 回路问题,链表、树：递归定义实现：记录数据、指向同一记录类型的指针回路type link=cell;cell=recordinfo:integer;next:link;end;,回路问题（续）,将递归定义的类型名替换为类型表达式，类型图中会产生回路,例6.4 C语言避免回路,对除记录之外的类型使用结构等价struct cell int info;struct cell*next;C语言要求类型名在使用前声明例外：未定义记录类型的指针回路：只可能是记录指针引起结构等价判定遇到记录类型停止：只有名字相同的记录才认为类型相同,6.4 类型转换,x+i，x为实型，i为整型不同保存格式，不同加法指令转换为相同类型进行运算语言定义指定转换方法赋值：转换为左部类型表达式：intreal类型检查器完成转换操作的生成x i inttoreal real+类型转换与重载紧密相连,强制类型转换（coercion）,编译器自动进行的隐含的类型转换一般要求：不能丢失信息显式（explicit）类型转换：程序员C：(float)10Pascal：ord(a)字符型整型 chr(65)整型字符型常量类型转换编译时进行，提高性能for I:=1 to N do XI:=148.4N msfor I:=1 to N do XI:=1.05.4N ms,例6.5,E num E.type=integer E num.numE.type=real E id E.type=lookup(id.entry)E E1 op E2E.type=if(E1.type=integer)and(E2.type=integer)then integer else if(E1.type=integer)and(E2.type=real)then realelse if(E1.type=real)and(E2.type=integer)then realelse if(E1.type=real)and(E2.type=real)then realelse type_error,lcc的类型,typedef struct type*Type;struct type int op;Type type;int align;int size;union Symbol sym;struct unsigned oldstyle:1;Type*proto;f;u;Xtype x;,类型构造符（基本类型）,子类型表达式（用链表保存类型表达式）,类型构造,static Type type(int op,Type ty,int size,int align,void*sym)unsigned h=(op(unsigned long)ty3),函数类型和不完全数组类型无重复概念，总是创建新类型,重复类型检查,类型构造,NEW0(tn,PERM);tn-type.op=op;tn-type.type=ty;tn-type.size=size;tn-type.align=align;tn-=sym;tn-link=typetableh;typetableh=tn;return,指针,Type ptr(Type ty)return type(POINTER,ty,IR-ptrmetric.size,IR-ptrmetric.align,pointersym);Type deref(Type ty)if(isptr(ty)ty=ty-type;elseerror(type error:%sn,pointer expected);return isenum(ty)?unqual(ty)-type:ty;,脱掉指针,数组,Type array(Type ty,int n,int a)assert(ty);if(isfunc(ty)error(illegal type array of%tn,ty);return array(inttype,n,0);if(isarray(ty),不允许函数数组,数组的数组，低维必须大小已知,数组,else if(n INT_MAX/ty-size)error(size of array of%t exceeds%d bytesn,ty,INT_MAX);n=1;return type(ARRAY,ty,n*ty-size,a?a:ty-align,NULL);,结构和联合,Type newstruct(int op,char*tag)Symbol p;assert(tag);if(*tag=0)tag=stringd(genlabel(1);elseif(p=lookup(tag,types)!=NULL,创建一个结构类型，但只是一个空架子,结构和联合,p=install(tag,结构和联合,Field newfield(char*name,Type ty,Type fty)Field p,*q=,结构和联合,if(xref)/*omit*/if(ty-u.sym-=NULL)/*omit*/ty-u.sym-=table(NULL,level);/*omit*/install(name,结构和联合,static Type structdcl(int op)ty=newstruct(op,tag);fields(ty);static void fields(Type ty)p=newfield(id,ty,fty);,类型等价,int eqtype(Type ty1,Type ty2,int ret)if(ty1=ty2)return 1;if(ty1-op!=ty2-op)return 0;switch(ty1-op)case ENUM:case UNION:case STRUCT:case UNSIGNED:case INT:case FLOAT:return 0;case POINTER:return eqtype(ty1-type,ty2-type,1);case VOLATILE:case CONST+VOLATILE:case CONST:return eqtype(ty1-type,ty2-type,1);,类型等价,case ARRAY:if(eqtype(ty1-type,ty2-type,1)if(ty1-size=ty2-size)return 1;if(ty1-size=0|ty2-size=0)return ret;return 0;,类型等价,case FUNCTION:if(eqtype(ty1-type,ty2-type,1)Type*p1=ty1-,*p2=ty2-;if(p1=p2)return 1;if(p1,类型等价,else if(variadic(p1?ty1:ty2)return 0;if(p1=NULL)p1=p2;for(;*p1;p1+)Type ty=unqual(*p1);if(promote(ty)!=(isenum(ty)?ty-type:ty)return 0;return 1;return 0;assert(0);return 0;,TinyC的类型检查,void typeCheck(TreeNode*syntaxTree)traverse(syntaxTree,nullProc,checkNode);static void traverse(TreeNode*t,void(*preProc)(TreeNode*),void(*postProc)(TreeNode*)if(t!=NULL)preProc(t);int i;for(i=0;i childi,preProc,postProc);postProc(t);traverse(t-sibling,preProc,postProc);,TinyC的类型检查,static void checkNode(TreeNode*t)switch(t-nodekind)case ExpK:switch(t-kind.exp)case OpK:if(t-child0-type!=Integer)|(t-child1-type!=Integer)typeError(t,Op applied to non-integer);if(t-attr.op=EQ)|(t-attr.op=LT)t-type=Boolean;else t-type=Integer;break;case ConstK:case IdK:t-type=Integer;break;,TinyC的类型检查,default:break;break;case StmtK:switch(t-kind.stmt)case IfK:if(t-child0-type=Integer)typeError(t-child0,if test is not Boolean);break;case AssignK:if(t-child0-type!=Integer)typeError(t-child0,assignment of non-integer value);break;,TinyC的类型检查,case WriteK:if(t-child0-type!=Integer)typeError(t-child0,write of non-integer value);break;case RepeatK:if(t-child1-type=Integer)typeError(t-child1,repeat test is not Boolean);break;default:break;break;default:break;,6.5 函数和操作符重载,重载（overloaded）符号：根据上下文，具有不同的意义+：整型加法，浮点型加法A(I)：数组A的第I个元素，以参数I调用A，将I转换为类型A的显式类型转换重载的解析（resolved）：在某个特定上下文，确定符号的唯一意义1+2：+为整型加法运算符识别，operator identification,6.5.1 子表达式可能类型集合,例6.6Ada允许对乘法运算符“*”进行重载function“*”(i,j:integer)return complex;function“*”(x,y:complex)return complex;*具有三种可能类型integer integer integerinteger integer complexcomplex complex complex2*(3*5)3*5类型1z*(3*5)，z为复数类型3*5类型2,可能类型集合情况的处理,E id E.types=lookup(id.entry)E E1(E2)E.types=t|E2.types中 存在s使得st属于 E1.types 单一类型运算类型集合运算,例6.7,6.5.2 确定唯一类型,完整表达式须有唯一类型确定每个子表达式的唯一类型，或type_error自顶向下E.types中每个类型t均为可行（feasible）类型确定E中重载标识符的类型，某种情况下，E的类型为t对标识符成立，id.types中类型均可行归纳法：E为E1(E2)，s为E2可行类型，st为E1可行类型，因此t为E可行类型,确定唯一类型的语义规则,E EE.types=E.typesE.unique=if E.types=t then t else type_errorE.code=E.codeE id E.types=lookup(id.entry)E.code=gen(id.lexeme:E.unique)E E1(E2)E.types=s|E2.types中存在s使得ss属于E1.types t=E.uniqueS=s|sE2.types and stE1.types E2.unique=if S=s then s else type_errorE1.unique=if S=s then s t else type_errorE.code=E1.code|E2.code|gen(apply:E.unique),6.6 多态（polymorphic）函数,普通函数：参数类型固定多态函数：不同调用参数可为不同类型某些内置操作符多态操作符数组索引符，函数调用符()，指针操作符&：“若操作对象类型为，则操作结果的类型为指向的指针,6.6.1 为什么使用多态函数？,实现算法处理数据结构，而不必管其内部元素的类型type link=cell;cell=recordinfo:integer;next:link end;function length(lptr:link):integer;var len:integer;beginlen:=0;while lptr nil do beginlen:=len+1;lptr:=lptr.next;end;length:=lenend;,求任何类型列表长度的ML程序,fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;可应用于任何类型的列表length(“sun”,“mon”,“tue”);length(10,9,8);,递归函数,列表为空？,列表剩余部分,6.6.2 类型变量,a,b,，表示未知类型重要应用：不要求标识符先声明后使用的语言中，检查标识符使用的一致性类型变量表示未声明标识符的类型若类型变量发生变化，不一致！若一直未变化，一致！同时得到标识符类型类型推断，type inference根据语言结构的使用方式判定其类型,例6.8,type link=cell;procedure mlist(lptr:link;procedure p);beginwhile lptr nil do beginp(lptr);lptr:=lptr.nextendend;p：参数情况未知，不完整的过程类型由p(lptr)p参数为link类型，p的类型为linkvoid其他使用方式均会导致type_error,例6.9,function deref(p);beginreturn p;end;扫描第一行，p的类型未知，用b表示第三行，应作用于指针，因此p为某未知基本类型a的指针类型，b=pointer(a)因此函数deref类型为：pointer(a)a,6.6.3 包含多态函数的语言,用 表示“对所有类型”deref类型的精确描述：length：list(integer)integerlist(list(char)integer：全称量词（universal quantifier）它所施用的类型变量称为由它约束（bound）,文法定义,P D;ED D;D|id:QQ type_varible.Q|TT T T|T T|unary_constructor(T)|basic_type|type_varible|(T)E E(E)|E,E|id程序例：deref:q:pointer(pointer(integer);deref(deref(q),多态函数类型检查,每个结点两个标签：子表达式和类型表达式下标o：外层deref，i：内存deref,类型检查规则的特点,不同位置出现的同一多态函数可具有不同类型的参数。derefo参数为二重指针，而derefi的参数为一重指针。关键在于 的解释，对不同deref，约束的类型变量a所代表的意义是不同的。对多态函数的每次出现，都赋予不同的类型变量，而不再使用 上例中用ao、ai分别对应外层和内层deref,类型检查规则的特点（二）,类型表达式中存在变量，因此要重新考虑类型等价的概念类型为ss的函数E1施用于类型为t的E2，仅判定s和t是否等价是不够的，要对它们进行“一致化”（unify）适当替换类型变量，检查是否有可能达到结构等价上例：将ai替换为pointer(integer)，则pointer(ai)与pointer(pointer(integer)等价,类型检查规则的特点（三）,需要某种机制记录一致化的影响一个类型变量可出现在表达式的多个位置若s和s的一致化使得变量a表示类型t，则在整个类型表达式中，它都应表示t上例：ai作用域为derefi(q)，因此可用来一致化derefi和q而ao为不同类型变量，因此表示不同类型不违反本规则,6.6.4 代换，实例和合一,变量表示实际类型的形式化定义类型变量类型表达式的映射，称为替换，substitutionsubst(t:type_expression):type_expression/利用代换（映射）S将类型表达式t中变量代换if(t为基本类型)return t;else if(t为类型变量)return S(t);else if(t为t1t2)return subst(t1)subst(t2);S(t)表示代换t的类型表达式，称为t的实例，instance若无法代换，S(a)=a，恒等映射,例6.10,st表示s是t的一个实例pointer(integer)pointer(a)pointer(real)pointer(a)integer integer a apointer(a)ba b不是实例的情况integerrealinteger reala ainteger aa a,合一方法,类型表达式t1和t2能合一的条件存在代换S，S(t1)=S(t2)最一般的合一代换，most general unifier最少变量约束的代换类型表达式t1和t2的最一般的合一代换是一个代换S，它满足以下条件S(t1)=S(t2)对任何其他代换S，S(t1)=S(t2)，S是S的一个实例，即，对任意t，S(t)是S(t)的一个实例,6.6.5 多态函数类型检查,检查规则由下列对类型图的操作构成fresh(t)将类型表达式t中约束变量代换为新变量，返回代换后类型表达式结点指针消除unify(m,n)将结点m、n表示的类型表达式合一，会修改、保存对应的代换。若失败，则整个类型检查过程失败图的创建仍可用mkleaf、mknode完成每个类型变量创建不同结点,unify操作,合一、代换基于图论的方法m、n为类型图结点，分别表示表达式e、f，若S(e)=S(f)，称m、n在代换S下等价求最一般的合一代换转化为在S下必须等价的结点的集合划分问题类型表达式等价根必须等价m、n等价表示相同操作且孩子结点等价,类型检查规则,E E1(E2)p=mkleaf(newtypevar);unify(E1.type,mknode(,E2.type,p);E.type=p;E E1,E2 E.type=mknode(,E1.type,E2.type);E id E.type=fresh(id.type);E1.type=a，E2.type=b，都是类型变量前者是函数，寻求两者等价，必有类型变量g，使得a=bg,例,表达式类型代换qpointer(pointer(integer)derefipointer(ai)aiderefi(q)pointer(integer)ai=pointer(integer)derefopointer(ao)aoderefo(derefi(q)integer ao=integer,例6.11,例6.11（续）,derefi的合一过程,例6.12 ML语言多态函数检查,fun id0(id1,idk)=E;id0：函数名，id1,idk：参数，E遵从前面定义的用于多态函数类型检查的文法，其中的标识符只可能是函数名、参数或内置函数方法：例6.9方法的形式化为函数名和参数创建新类型变量多态函数的类型变量由 约束检查id0(id1,idk)和E类型是否匹配若成功，则推断出函数类型,例6.12（续）,fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;类型变量：lengthb，lptrg为匹配函数体：b=按多态函数类型检查语言重写程序length:b;lptr:g;if:,例6.12（续）,null:tl:0:integer;1:integer;+:match:match(length(lptr),if(null(lptr),0,length(tl(lptr)+1),检查length(lptr)与函数体匹配,例6.12（续）,表达式：lptr:length:length(lptr):lptr:null:null(lptr):0:lptr:tl:tl(lptr):,类型gbdglist(an)booleanbooleanintegerlist(an)list(at)list(at)list(an),替换b=gdg=list(an)at=an,length参数为lptrg返回类型为d,null参数类型为list(an)lptr类型g=list(an)length类型为list(an)d,例6.12（续）,表达式：length:length(tl(lptr):1:+:length(tl(lptr)+1:if:if():match:match():,类型list(an)ddintegerintegerinteger integerintegerbooleanaiaiaiintegeramam aminteger,替换d=integerai=integeram=integer,length的返回类型，因此d=integer,an最终未被替代，length类型为,6.7 合一算法,合一：类型表达式e、f通过变量代换，是否可达到类型等价特殊情况：等价性检查，无变量本节算法适用类型图有回路情况算法寻找最一般的合一代换S,例6.13,e、f：两个合一代换S,S：xS(x)S(x)a1 a3 a1a2 a2 a1a3 a3 a1a4 a2 a1a5list(a2)list(a1)代换结果：,最一般的合一代换S(e)是S(e)的实例，反之不成立,算法思想,用树表示表达式S(e)的结点数目可能与e、f的结点数目呈指数关系图表示图论方法：在最一般的合一代换下必须等价的结点，进行集合划分,算法6.1 合一算法,输入：一个类型图和要进行合一的结点m、n输出：若一致，返回true；否则，返回false。本算法的函数可修改为前面给出的多态函数类型检查规则所需的unify函数方法：结点用上图所示记录实现set域维护等价结点集合每个等价类选出一个代表结点set域为空指针等价类内其他结点指向代表结点初始，每个结点形成一个等价类,算法6.1（续）,bool unify(node m,n)s=find(m);t=find(n);if(s=t)return true;else if(s和t为相同基本类型结点)return true;else if(s为操作符结点，孩子结点为s1,s2 且t为操作符结点，孩子结点为t1,t2)union(s,t);return unify(s1,t1)and unify(s2,t2);else if(s或t表示类型变量)union(s,t);return true;else return false;,find和union操作,find(n)返回结点n等价类的代表结点union(m,n)将结点m、n所在等价类合并若两个等价类代表结点中某个不是变量结点，则将其作为合并等价类的代表结点。否则，其中任一个作为新代表结点。原因：若等价类包含类型构造符或基本类型，变量结点不能做为代表结点否则，（纯变量）表达式可通过变量达到合一,算法（续）,union的实现：将一个等价类代表结点的set指针指向另一个的代表结点find：沿set链遍历，直到空指针算法6.1，使用s=find(m)和t=find(n)s、t相等m、n已在相同等价类中s、t为相同基本类型返回真s、t为相同类型操作符合并两个等价类，继续递归检查他们孩子结点等价性s、t其中一个为变量合并，类型操作符或基本类型成为代表结点变量不会与两个不同的表达式合一,例6.14,考虑例6.13的表达式，初始dag为合一过程unify(1,9)：相同操作符，合并，unify(2,10),unify(8,14)unify(2,10)：相同操作符，合并，unify(3,11),unify(6,13),例6.14（续）,unify(1,9)：相同操作符，合并，unify(2,10),unify(8,14)unify(2,10)：相同操作符，合并，unify(3,11),unify(6,13)unify(3,11)：相同操作符，合并，unify(4,7),unify(5,12)unify(4,7)：两个变量，合并，4作为代表结点，返回真unify(5,12)：两个变量，合并，5作为代表结点，返回真unify(3,11)为真，3作为代表结点,例6.14（续）,unify(6,13)：相同操作符，合并，unify(4,4)真unify(6,13)为真，6作为代表结点unify(2,10)为真，2作为代表结点unify(8,14)：一个变量，合并，8作为代表结点，返回真unify(1,9)为真，1作为代表结点,例6.14（续）,最终结果,构造合一代换,算法6.1最终得到的类型图中，每个结点n表示与find(n)相关联的类型表达式对每个变量a，find(a)表示a的等价类的代表结点n因此，n表示的表达式实际上就是S(a)如上例a3的代表结点为4，表示a1a5的代表结点为8，表示list(a2),例6.15,e:real ef:real(real f)unify(1,3)：相同操作符，合并，unify(2,4),unify(1,5)unify(2,4)：相同基本类型，合并，返回真,例6.15（续）,unify(1,5)：相同操作符，合并，unify(2,6),unify(1,1)unify(2,6)：相同基本类型，合并，返回真unify(1,5)为真unify(1,3)为真,