编译原理类型检查优质内容

资源描述

《编译原理类型检查优质内容》由会员分享，可在线阅读，更多相关《编译原理类型检查优质内容（100页珍藏版）》请在金锄头文库上搜索。

1、第六章类型检查1高级培训内容m类型系统m类型表达式的等价m类型转换m函数和运算符的重载m多态函数m一致化算法2高级培训静态检查（static checking）1.类型检查（type check）q操作对象必须与操作符匹配：函数名相加2.控制流检查（flow-of-control check）qbreak必须退出while、for、switch3.唯一性检查（uniqueness check）q对象（变量、标号）定义必须唯一4.名字关联检查（name-related check）q相同名字在不同位置3高级培训类型检查m检查语法结构的类型与上下文匹配q简单的类型检查q两个类型的匹配m代码生成要

2、利用类型信息m重载，多态4高级培训6.1 类型系统m语法结构、类型、将类型赋予语法结构q+, -, *的两个运算数均为整数，结果为整数q&的结果为指向操作对象的指针，若操作对象类型为T，结果类型为“指向T的指针”m每个表达式都有一个相关联的类型m类型是有结构的！指针m基本类型：语言内部支持类型m结构类型：组合基本类型构成新类型5高级培训6.1.1 类型表达式mtype expression用以表示语言结构的类型m基本类型或用类型构造符组合基本类型1.基本类型：boolean, char, integer, real, type_error, void2.类型名6高级培训类型表达式（续）3.类型

3、构造符a)数组：T是类型表达式，I为索引集合（整数范围），则array(I, T)是一个类型表达式，表示元素为类型T的数组类型int A10;array(0, , 9, integer)b)笛卡儿积：T1、T2为类型表达式，则T1T2为类型表达式7高级培训类型表达式（续）c)记录：与笛卡儿积的不同之处仅在于记录的域有名字。元组typedef struct int address;char lexeme15; row;row table101;类型表达式为：record(addressinteger)(lexemearray(0, , 15, char)8高级培训类型表达式（续）d)指针：T为类

4、型表达式，则pointer(T)为类型表达式，表示“指向类型为T的对象的指针”类型row *p;pointer(row)e)函数：数学上，一个集合“定义域”到另一个集合“值域”的映射。程序语言，定义域类型D到值域类型R的映射：DR。%运算符(intint)intint *f(char a, char b);(charchar)pointer(integer)不考虑函数返回数组、函数类型的情况(integerinteger)(integerinteger)4.可使用类型表达式变量9高级培训图表示类型表达式m(charchar)pointer(integer)10高级培训6.1.2 类型系统mty

5、pe system：规则的集合规则将类型表达式赋予程序的不同部分m类型检查程序：实现一个类型系统m语法制导方式实现嵌入语义规则11高级培训6.1.2静态/动态检查m静态编译器进行动态运行时进行m可靠类型系统，强类型语言编译器无type_error运行时无类型错误mint a10, i; b=ai;需动态检查m安全领域也涉及类型检查（缓冲溢出问题）12高级培训6.1.4 错误恢复m最低要求：报告类型错误位置m错误处理应融入规则中m错误修正比描述正确程序更困难q根据错误的程序、处理缺失信息，来推测正确类型在变量使用之前无需定义它q类型变量可用来处理这种问题13高级培训6.2 一个简单的类型检查器6

7、 : 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) mDid:T的规则在符号表保存标识符类型mT.type由后几个产生式语义规则计算mPD;E，D在E之前，保证在检查表达式类型之前类型已经保存入符号表15高级培训6.2.2 表达式类型检查E literal E.type = char E numE.type = integer E id E.t

8、ype = 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 m可添加其他类型和运算16高级培训6.2.3 语句的类型检查m赋值

9、、条件、whilem无错误，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.

10、type = void) then void else type_error 17高级培训6.2.4 函数的类型检查m函数定义T T1 T2 T.type = T1.typeT2.type m函数调用E E1(E2) E.type = if (E2.type=s)and (E1.type=st)then t else type_error m多参数：T1, , TnT1Tnm更复杂例子：root: (realreal)realrealfunction root(function f(real): real; x: real): real18高级培训6.3 类型表达式的等价m两个类型表达式等价的

11、精确定义？m用类型表示方式可快速确定等价性m结构等价和名字等价m类型表达式的图表示不同叶结点为基本类型或类型名m递归定义类型会导致回路19高级培训6.3.1 类型表达式的结构等价m结构等价（structural equivalence）1.相同的基本类型2.对子表达式施加的类型构造符相同q两个类型表达式结构等价dag中对应相同结点m有时要放松条件数组参数忽略界限q等价性检查算法稍做修改20高级培训等价性检查算法bool sequiv(s, t)if (s和t为相同基本类型)return true;else if (s = array(s1, s2) and t = array(t1, t2)r

12、eturn 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; 21高级培训例6.1：编码类型表达式m用二进制码表示类型和构造

13、符m节省内存，加速检测二进制码不同的类型表达式肯定不等价mD. M. Ritchie，C编译器m忽略数组界限和函数参数charfreturns(char)pointer(freturns(char)array(pointer(freturns(char)22高级培训例6.1（续）m构造符的编码pointer01array10freturns11m基本类型编码boolean0000char0001integer0010real001123高级培训例6.1（续）m编码方法q最右端四位二进制位表示基本类型q它前面两位表示第一个构造符q再前面两位表示第二个构造符类型表达式编码char000000 00

14、01freturns(char)000011 0001pointer(freturns(char)000111 0001array(pointer(freturns(char)100111 000124高级培训例6.1（续）m加速等价性检查q不同二进制串不可能表示相同类型q不同类型可能表示为相同二进制串数组界限、函数参数m记录的编码q在类型表达式中记录作为基本类型q用另一个二进制串编码它的域25高级培训6.3.2 名字等价type link = cell;var next : link; last : link; p : cell; q, r : cell; m5个变量类型是否都相同？依赖实现

15、m允许类型表达式命名，但不允许回路m名字等价：完全相同m结构等价：名字被替换后完全相同26高级培训例6.2变量类型表达式nextlinklastlinkppointer(cell)qpointer(cell)rpointer(cell)m名字等价：next, last类型相同，p, q, r类型相同，p, next类型不同m结构等价：5个变量类型都相同27高级培训例6.3m许多Pascal编译器会隐含地为每条标识符定义语句涉及到的类型关联一个类型名type link = cell; np = cell; nqr = cell;var next : link; last : link; p :

16、np; q, r : nqr;m名字等价：next, last类型相同，q, r类型相同，p, next, q类型不同28高级培训例6.3（续）m实现方式构造类型图q对基本类型和类型构造符创建新结点q对新类型名创建叶结点，保存与类型表达式的链接m名字等价相同结点29高级培训6.3.3 回路问题m链表、树：递归定义m实现：记录数据、指向同一记录类型的指针回路type link = cell; cell = recordinfo : integer;next : link; end;30高级培训回路问题（续）m将递归定义的类型名替换为类型表达式，类型图中会产生回路31高级培训例6.4 C语言避免回

17、路m对除记录之外的类型使用结构等价struct cell int info;struct cell *next;mC语言要求类型名在使用前声明m例外：未定义记录类型的指针m回路：只可能是记录指针引起m结构等价判定遇到记录类型停止：只有名字相同的记录才认为类型相同32高级培训6.4 类型转换mx+i，x为实型，i为整型q不同保存格式，不同加法指令q转换为相同类型进行运算m语言定义指定转换方法q赋值：转换为左部类型q表达式：intrealq类型检查器完成转换操作的生成qx i inttoreal real+m类型转换与重载紧密相连33高级培训强制类型转换（coercion）m编译器自动进行的隐含的

18、类型转换m一般要求：不能丢失信息m显式（explicit）类型转换：程序员qC：(float)10qPascal：ord(a)字符型整型 chr(65)整型字符型m常量类型转换编译时进行，提高性能qfor I := 1 to N do XI := 148.4N msqfor I := 1 to N do XI := 1.05.4N ms34高级培训例6.5E 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

19、 (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_error35高级培训lcc的类型typedef struct type *Type;struct type int op;Type type;int align;int

20、 size;union Symbol sym;struct unsigned oldstyle:1;Type *proto; f; u;Xtype x;类型构造符（基本类型）子类型表达式（用链表保存类型表达式）36高级培训类型构造static Type type(int op, Type ty, int size, int align, void *sym) unsigned h = (op(unsigned long)ty3)&(NELEMS(typetable)-1);struct entry *tn;if (op != FUNCTION & (op != ARRAY | size 0)f

21、or (tn = typetableh; tn; tn = tn-link)if (tn-type.op = op & tn-type.type = ty& tn-type.size = size & tn-type.align = align& tn-type.u.sym = sym)return &tn-type;函数类型和不完全数组类型无重复概念，总是创建新类型重复类型检查37高级培训类型构造NEW0(tn, PERM);tn-type.op = op;tn-type.type = ty;tn-type.size = size;tn-type.align = align;tn-type.

22、u.sym = sym;tn-link = typetableh;typetableh = tn;return &tn-type;38高级培训指针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;脱掉

23、指针39高级培训数组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) & ty-size = 0)error(missing array sizen);if (ty-size = 0) if (unqual(ty) = voidtype)error(illegal type array of %tn, ty);else if (Aflag = 2)warning(d

24、eclaring type array of %t is undefinedn, ty);不允许函数数组数组的数组，低维必须大小已知40高级培训数组 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);41高级培训结构和联合Type newstruct(int op, char *tag) Symbol p;assert(tag);if (*tag =

25、0)tag = stringd(genlabel(1);elseif (p = lookup(tag, types) != NULL & (p-scope = level| p-scope = PARAM & level = PARAM+1) if (p-type-op = op & !p-defined)return p-type;error(redefinition of %s previously defined at %wn,p-name, &p-src);创建一个结构类型，但只是一个空架子42高级培训结构和联合p = install(tag, &types, level, PERM)

26、;p-type = type(op, NULL, 0, 0, p);if (p-scope maxlevel)maxlevel = p-scope;p-src = src;return p-type;43高级培训结构和联合Field newfield(char *name, Type ty, Type fty) Field p, *q = &ty-u.sym-u.s.flist;if (name = NULL)name = stringd(genlabel(1);for (p = *q; p; q = &p-link, p = *q)if (p-name = name)error(duplic

27、ate field name %s in %tn,name, ty);NEW0(p, PERM);*q = p;p-name = name;p-type = fty; 44高级培训结构和联合if (xref) /* omit */if (ty-u.sym-u.s.ftab = NULL)/* omit */ ty-u.sym-u.s.ftab = table(NULL, level);/* omit */install(name, &ty-u.sym-u.s.ftab, 0, PERM)-src = src;/* omit */* omit */return p;45高级培训结构和联合stat

28、ic Type structdcl(int op) ty = newstruct(op, tag);fields(ty);static void fields(Type ty) p = newfield(id, ty, fty);46高级培训类型等价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 F

29、LOAT: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);47高级培训类型等价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;48高级培训

30、类型等价case FUNCTION: if (eqtype(ty1-type, ty2-type, 1) Type *p1 = ty1-u.f.proto, *p2 = ty2-u.f.proto; if (p1 = p2) return 1; if (p1 & p2) for ( ; *p1 & *p2; p1+, p2+)if (eqtype(unqual(*p1), unqual(*p2), 1) = 0)return 0;if (*p1 = NULL & *p2 = NULL)return 1;49高级培训类型等价 else if (variadic(p1 ? ty1 : ty2)re

31、turn 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;50高级培训TinyC的类型检查void typeCheck(TreeNode * syntaxTree) traverse(syntaxTree,nullProc,checkNode);static void traverse( TreeNode * t, void (*

32、 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); 51高级培训TinyC的类型检查static void checkNode(TreeNode * t) switch (t-nodekind) case ExpK: switch (t-kind.exp) case OpK: if (t-c

33、hild0-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;52高级培训TinyC的类型检查 default: break; break; case StmtK: switch (t-kind.stmt) c

34、ase 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;53高级培训TinyC的类型检查 case WriteK: if (t-child0-type != Integer) typeError(t-child0,write of non-integer value);

35、break; case RepeatK: if (t-child1-type = Integer) typeError(t-child1,repeat test is not Boolean); break; default: break; break; default: break; 54高级培训6.5 函数和操作符重载m重载（overloaded）符号：根据上下文，具有不同的意义q+：整型加法，浮点型加法qA(I)：数组A的第I个元素，以参数I调用A，将I转换为类型A的显式类型转换m重载的解析（resolved）：在某个特定上下文，确定符号的唯一意义q1+2：+为整型加法q运算符识别，op

36、erator identification55高级培训6.5.1 子表达式可能类型集合m例6.6mAda允许对乘法运算符“*”进行重载qfunction “*” (i, j : integer) return complex;qfunction “*” (x, y : complex) return complex;m*具有三种可能类型qinteger integer integerqinteger integer complexqcomplex complex complexq2*(3*5)3*5类型1qz*(3*5)，z为复数类型3*5类型256高级培训可能类型集合情况的处理E id E.

37、types = lookup(id.entry)E E1(E2) E.types = t | E2.types中存在s使得st属于 E1.types m单一类型运算类型集合运算57高级培训例6.758高级培训6.5.2 确定唯一类型m完整表达式须有唯一类型确定每个子表达式的唯一类型，或type_errorm自顶向下mE.types中每个类型t均为可行（feasible）类型确定E中重载标识符的类型，某种情况下，E的类型为tq对标识符成立，id.types中类型均可行q归纳法：E为E1(E2)，s为E2可行类型，st为E1可行类型，因此t为E可行类型59高级培训确定唯一类型的语义规则E EE.

38、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

39、then s t else type_errorE.code = E1.code | E2.code | gen(apply : E.unique)60高级培训6.6 多态（polymorphic）函数m普通函数：参数类型固定m多态函数：不同调用参数可为不同类型m某些内置操作符多态操作符q数组索引符，函数调用符()，指针操作符&q&：“若操作对象类型为，则操作结果的类型为指向的指针61高级培训6.6.1 为什么使用多态函数？m实现算法处理数据结构，而不必管其内部元素的类型type link = cell; cell = recordinfo : integer;next : link end;

40、function length(lptr : link) : integer;var len : integer;beginlen := 0;while lptr nil do beginlen := len + 1;lptr := lptr.next;end;length := lenend;62高级培训求任何类型列表长度的ML程序fun length(lptr) =if null(lptr) then 0else length(tl(lptr) + 1;m可应用于任何类型的列表qlength(“sun”, “mon”, “tue”);qlength(10, 9, 8);递归函数递归函数列表

41、为空列表为空？列表剩余部分列表剩余部分63高级培训6.6.2 类型变量ma, b, ，表示未知类型m重要应用：不要求标识符先声明后使用的语言中，检查标识符使用的一致性m类型变量表示未声明标识符的类型q若类型变量发生变化，不一致！q若一直未变化，一致！同时得到标识符类型m类型推断，type inferenceq根据语言结构的使用方式判定其类型64高级培训例6.8type link = cell;procedure mlist(lptr : link; procedure p);beginwhile lptr nil do beginp(lptr);lptr := lptr.nextendend;

42、mp：参数情况未知，不完整的过程类型m由p(lptr)qp参数为link类型，p的类型为linkvoidq其他使用方式均会导致type_error65高级培训例6.9function deref(p);beginreturn p;end;m扫描第一行，p的类型未知，用b表示m第三行，应作用于指针，因此p为某未知基本类型a的指针类型，b=pointer(a)m因此函数deref类型为：pointer(a)a66高级培训6.6.3 包含多态函数的语言m用表示“对所有类型”mderef类型的精确描述：mlength：qlist(integer)integerqlist(list(char)inte

44、ref，i：内存deref69高级培训类型检查规则的特点1.不同位置出现的同一多态函数可具有不同类型的参数。mderefo参数为二重指针，而derefi的参数为一重指针。m关键在于的解释，对不同deref，约束的类型变量a所代表的意义是不同的。m对多态函数的每次出现，都赋予不同的类型变量，而不再使用上例中用ao、ai分别对应外层和内层deref70高级培训类型检查规则的特点（二）2.类型表达式中存在变量，因此要重新考虑类型等价的概念m类型为ss的函数E1施用于类型为t的E2，仅判定s和t是否等价是不够的，要对它们进行“一致化”（unify）m适当替换类型变量，检查是否有可能达到结构等价m上

45、例：将ai替换为pointer(integer)，则pointer(ai)与pointer(pointer( integer)等价71高级培训类型检查规则的特点（三）3.需要某种机制记录一致化的影响m一个类型变量可出现在表达式的多个位置m若s和s的一致化使得变量a表示类型t，则在整个类型表达式中，它都应表示tm上例： ai作用域为derefi(q)，因此可用来一致化derefi和qm而ao为不同类型变量，因此表示不同类型不违反本规则72高级培训6.6.4 代换，实例和合一m变量表示实际类型的形式化定义q类型变量类型表达式的映射，称为替换，substitutionsubst(t : type_e

46、xpression) : type_expression/利用代换（映射）S将类型表达式t中变量代换if (t为基本类型) return t;else if (t为类型变量) return S(t);else if (t为t1t2) return subst(t1)subst(t2);mS(t)表示代换t的类型表达式，称为t的实例，instancem若无法代换，S(a)=a，恒等映射73高级培训例6.10mst表示s是t的一个实例qpointer(integer) pointer(a)qpointer(real) pointer(a)qinteger integer a aqpointer(a

47、) bqa bm不是实例的情况qintegerrealqinteger reala aqinteger aa a74高级培训合一方法m类型表达式t1和t2能合一的条件存在代换S，S(t1) = S(t2)m最一般的合一代换，most general unifier最少变量约束的代换q类型表达式t1和t2的最一般的合一代换是一个代换S，它满足以下条件1.S(t1) = S(t2)2.对任何其他代换S，S(t1) = S(t2)，S是S的一个实例，即，对任意t，S(t)是S(t)的一个实例75高级培训6.6.5 多态函数类型检查m检查规则由下列对类型图的操作构成qfresh(t)将类型表达式t中约

48、束变量代换为新变量，返回代换后类型表达式结点指针消除qunify(m, n)将结点m、n表示的类型表达式合一，会修改、保存对应的代换。若失败，则整个类型检查过程失败m图的创建仍可用mkleaf、mknode完成m每个类型变量创建不同结点76高级培训unify操作m合一、代换基于图论的方法mm、n为类型图结点，分别表示表达式e、f，若S(e)=S(f)，称m、n在代换S下等价m求最一般的合一代换q转化为在S下必须等价的结点的集合划分问题q类型表达式等价根必须等价qm、n等价表示相同操作且孩子结点等价77高级培训类型检查规则E E1(E2) p = mkleaf(newtypevar);unify

49、(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); mE1.type=a，E2.type=b，都是类型变量m前者是函数，寻求两者等价，必有类型变量g，使得a=bg78高级培训例表达式类型代换qpointer(pointer(integer)derefipointer(ai) aiderefi(q)pointer(integer) ai=pointer(integer)derefopointer(ao) aod

50、erefo(derefi(q)integer ao=integer79高级培训例6.1180高级培训例6.11（续）mderefi的合一过程81高级培训例6.12 ML语言多态函数检查fun id0 ( id1, , idk ) = E;mid0：函数名， id1, , idk：参数，E遵从前面定义的用于多态函数类型检查的文法，其中的标识符只可能是函数名、参数或内置函数m方法：例6.9方法的形式化q为函数名和参数创建新类型变量q多态函数的类型变量由约束q检查id0 ( id1, , idk )和E类型是否匹配q若成功，则推断出函数类型82高级培训例6.12（续）fun length(lptr

51、) =if null(lptr) then 0else length(tl(lptr) + 1;m类型变量：lengthb，lptrgm为匹配函数体：b=m按多态函数类型检查语言重写程序length : b;lptr : g;if : 83高级培训例6.12（续）null : tl : 0 : integer;1 : integer;+ :match :match (length(lptr),if ( null(lptr), 0, length(tl(lptr) + 1) 检查length(lptr)与函数体匹配84高级培训例6.12（续）表达式：lptr :length :length(lp

52、tr) :lptr :null :null(lptr) :0 :lptr :tl :tl(lptr) :类型gbdglist(an)booleanbooleanintegerlist(an)list(at)list(at)list(an)替换b=gdg=list(an)at=anlength参数为参数为lptrg g返回类型为返回类型为d dnull参数类型为参数类型为list(a an)lptr类型类型g g=list(a an) length类类型为型为list(a an)d d85高级培训例6.12（续）表达式：length :length(tl(lptr) :1 :+ :length(

53、tl(lptr) + 1:if :if () :match :match() :类型list(an)ddintegerintegerinteger integerintegerbooleanaiaiaiintegeramam aminteger替换d=integerai=integeram=integerlength的返的返回类型，因回类型，因此此d d=integera an最终未被替代，最终未被替代，length类型为类型为86高级培训6.7 合一算法m合一：类型表达式e、f通过变量代换，是否可达到类型等价q特殊情况：等价性检查，无变量q本节算法适用类型图有回路情况q算法寻找最一般的合一代

54、换S87高级培训例6.13me、f：m两个合一代换S, S：xS(x)S(x)a1 a3 a1a2 a2 a1a3 a3 a1a4 a2 a1a5list(a2) list(a1)m代换结果：最一般的合一代换最一般的合一代换S(e)是是S(e)的实例，的实例，反之不成立反之不成立88高级培训算法思想m用树表示表达式S(e)的结点数目可能与e、f的结点数目呈指数关系图表示m图论方法：在最一般的合一代换下必须等价的结点，进行集合划分89高级培训算法6.1 合一算法输入：一个类型图和要进行合一的结点m、n输出：若一致，返回true；否则，返回false。本算法的函数可修改为前面给出的多态函数类型检查

55、规则所需的unify函数方法：结点用上图所示记录实现set域维护等价结点集合每个等价类选出一个代表结点set域为空指针等价类内其他结点指向代表结点初始，每个结点形成一个等价类90高级培训算法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

56、, t2); else if (s或t表示类型变量) union(s, t);return true; else return false;91高级培训find和union操作1.find(n)q返回结点n等价类的代表结点2.union(m, n)q将结点m、n所在等价类合并q若两个等价类代表结点中某个不是变量结点，则将其作为合并等价类的代表结点。q否则，其中任一个作为新代表结点。q原因：若等价类包含类型构造符或基本类型，变量结点不能做为代表结点q否则，（纯变量）表达式可通过变量达到合一92高级培训算法（续）munion的实现：将一个等价类代表结点的set指针指向另一个的代表结点mfind：沿

57、set链遍历，直到空指针m算法6.1，使用s=find(m)和t=find(n)qs、t相等m、n已在相同等价类中qs、t为相同基本类型返回真qs、t为相同类型操作符合并两个等价类，继续递归检查他们孩子结点等价性qs、t其中一个为变量合并，类型操作符或基本类型成为代表结点变量不会与两个不同的表达式合一93高级培训例6.14m考虑例6.13的表达式，初始dag为m合一过程unify(1, 9)：相同操作符，合并，unify(2, 10), unify(8, 14)unify(2, 10)：相同操作符，合并，unify(3, 11), unify(6, 13)94高级培训例6.14（续）unify

58、(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作为代表结点95高级培训例6.14（续）unify(6, 13)：相同操作符，合并，unify(4, 4)真unify(6,13)为真，6作为代表结点unify(2,

59、10)为真，2作为代表结点unify(8, 14)：一个变量，合并，8作为代表结点，返回真unify(1, 9)为真，1作为代表结点96高级培训例6.14（续）最终结果97高级培训构造合一代换m算法6.1最终得到的类型图中，每个结点n表示与find(n)相关联的类型表达式m对每个变量a，find(a)表示a的等价类的代表结点nm因此，n表示的表达式实际上就是S(a)m如上例qa3的代表结点为4，表示a1qa5的代表结点为8，表示list(a2)98高级培训例6.15e : real ef : real (real f)unify(1, 3)：相同操作符，合并，unify(2, 4), unify(1, 5)unify(2, 4)：相同基本类型，合并，返回真99高级培训例6.15（续）unify(1, 5)：相同操作符，合并，unify(2, 6), unify(1, 1)unify(2, 6)：相同基本类型，合并，返回真unify(1, 5)为真unify(1, 3)为真100高级培训

展开阅读全文

编译原理类型检查优质内容

最新文档