编译原理-类型检查.ppt

章类型检查2021/10/101内容m类型系统m类型表达式的等价m类型转换m函数和运算符的重载m多态函数m一致化算法2021/10/102静态检查（static checking）1.类型检查（type check）q操作对象必须与操作符匹配：函数名相加2.控制流检查（flow-of-control check）qbreak必须退出while、for、switch3.唯一性检查（uniqueness check）q对象（变量、标号）定义必须唯一4.名字关联检查（name-related check）q相同名字在不同位置2021/10/103类型检查m检查语法结构的类型与上下文匹配q简单的类型检查q两个类型的匹配m代码生成要利用类型信息m重载，多态2021/10/1046.1 类型系统m语法结构、类型、将类型赋予语法结构q+,-,*的两个运算数均为整数，结果为整数q&的结果为指向操作对象的指针，若操作对象类型为T，结果类型为“指向T的指针”m每个表达式都有一个相关联的类型m类型是有结构的！指针m基本类型：语言内部支持类型m结构类型：组合基本类型构成新类型2021/10/1056.1.1 类型表达式mtype expression用以表示语言结构的类型m基本类型或用类型构造符组合基本类型1.基本类型：boolean,char,integer,real,type_error,void2.类型名2021/10/106类型表达式（续）3.类型构造符a)数组：T是类型表达式，I为索引集合（整数范围），则array(I,T)是一个类型表达式，表示元素为类型T的数组类型int A10;array(0,9,integer)b)笛卡儿积：T1、T2为类型表达式，则T1T2为类型表达式2021/10/107类型表达式（续）c)记录：与笛卡儿积的不同之处仅在于记录的域有名字。元组typedef struct int address;char lexeme15;row;row table101;类型表达式为：record(addressinteger)(lexemearray(0,15,char)2021/10/108类型表达式（续）d)指针：T为类型表达式，则pointer(T)为类型表达式，表示“指向类型为T的对象的指针”类型row*p;pointer(row)e)函数：数学上，一个集合“定义域”到另一个集合“值域”的映射。程序语言，定义域类型D到值域类型R的映射：DR。%运算符(intint)intint*f(char a,char b);(charchar)pointer(integer)不考虑函数返回数组、函数类型的情况(integerinteger)(integerinteger)4.可使用类型表达式变量2021/10/109图表示类型表达式m(charchar)pointer(integer)2021/10/10106.1.2 类型系统mtype system：规则的集合规则将类型表达式赋予程序的不同部分m类型检查程序：实现一个类型系统m语法制导方式实现嵌入语义规则2021/10/10116.1.2静态/动态检查m静态编译器进行动态运行时进行m可靠类型系统，强类型语言编译器无type_error运行时无类型错误mint a10,i;b=ai;需动态检查m安全领域也涉及类型检查（缓冲溢出问题）2021/10/10126.1.4 错误恢复m最低要求：报告类型错误位置m错误处理应融入规则中m错误修正比描述正确程序更困难q根据错误的程序、处理缺失信息，来推测正确类型在变量使用之前无需定义它q类型变量可用来处理这种问题2021/10/10136.2 一个简单的类型检查器6.2.1 一种简单语言m用综合属性type保存类型表达式P D;ED D;D|id:TT char|integer|array num of T|TE literal|num|id|E mod E|E E|Em基本类型：char、integer、type_errorm例CODESome Types Expressionskey:integer;array256 of char array(1.256,char)key mod 1999 integer pointer(integer)2021/10/1014翻译模式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)mDid:T的规则在符号表保存标识符类型mT.type由后几个产生式语义规则计算mPD;E，D在E之前，保证在检查表达式类型之前类型已经保存入符号表2021/10/10156.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 m可添加其他类型和运算2021/10/10166.2.3 语句的类型检查m赋值、条件、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.type=void)then void else type_error 2021/10/10176.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):real2021/10/10186.3 类型表达式的等价m两个类型表达式等价的精确定义？m用类型表示方式可快速确定等价性m结构等价和名字等价m类型表达式的图表示不同叶结点为基本类型或类型名m递归定义类型会导致回路2021/10/10196.3.1 类型表达式的结构等价m结构等价（structural equivalence）1.相同的基本类型2.对子表达式施加的类型构造符相同q两个类型表达式结构等价dag中对应相同结点m有时要放松条件数组参数忽略界限q等价性检查算法稍做修改2021/10/1020等价性检查算法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;2021/10/1021例6.1：编码类型表达式m用二进制码表示类型和构造符m节省内存，加速检测二进制码不同的类型表达式肯定不等价mD.M.Ritchie，C编译器m忽略数组界限和函数参数charfreturns(char)pointer(freturns(char)array(pointer(freturns(char)2021/10/1022例6.1（续）m构造符的编码pointer01array10freturns11m基本类型编码boolean0000char0001integer0010real00112021/10/1023例6.1（续）m编码方法q最右端四位二进制位表示基本类型q它前面两位表示第一个构造符q再前面两位表示第二个构造符类型表达式编码char000000 0001freturns(char)000011 0001pointer(freturns(char)000111 0001array(pointer(freturns(char)100111 00012021/10/1024例6.1（续）m加速等价性检查q不同二进制串不可能表示相同类型q不同类型可能表示为相同二进制串数组界限、函数参数m记录的编码q在类型表达式中记录作为基本类型q用另一个二进制串编码它的域2021/10/10256.3.2 名字等价type link=cell;var next:link;last:link;p:cell;q,r:cell;m5个变量类型是否都相同？依赖实现m允许类型表达式命名，但不允许回路m名字等价：完全相同m结构等价：名字被替换后完全相同2021/10/1026例6.2变量类型表达式nextlinklastlinkppointer(cell)qpointer(cell)rpointer(cell)m名字等价：next,last类型相同，p,q,r类型相同，p,next类型不同m结构等价：5个变量类型都相同2021/10/1027例6.3m许多Pascal编译器会隐含地为每条标识符定义语句涉及到的类型关联一个类型名type link=cell;np=cell;nqr=cell;var next:link;last:link;p:np;q,r:nqr;m名字等价：next,last类型相同，q,r类型相同，p,next,q类型不同2021/10/1028例6.3（续）m实现方式构造类型图q对基本类型和类型构造符创建新结点q对新类型名创建叶结点，保存与类型表达式的链接m名字等价相同结点2021/10/10296.3.3 回路问题m链表、树：递归定义m实现：记录数据、指向同一记录类型的指针回路type link=cell;cell=recordinfo:integer;next:link;end;2021/10/1030回路问题（续）m将递归定义的类型名替换为类型表达式，类型图中会产生回路2021/10/1031例6.4 C语言避免回路m对除记录之外的类型使用结构等价struct cell int info;struct cell*next;mC语言要求类型名在使用前声明m例外：未定义记录类型的指针m回路：只可能是记录指针引起m结构等价判定遇到记录类型停止：只有名字相同的记录才认为类型相同2021/10/10326.4 类型转换mx+i，x为实型，i为整型q不同保存格式，不同加法指令q转换为相同类型进行运算m语言定义指定转换方法q赋值：转换为左部类型q表达式：intrealq类型检查器完成转换操作的生成qx i inttoreal real+m类型转换与重载紧密相连2021/10/1033强制类型转换（coercion）m编译器自动进行的隐含的类型转换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 ms2021/10/1034例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(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_error2021/10/1035lcc的类型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;类型构造符（基本类型）子类型表达式（用链表保存类型表达式）2021/10/1036类型构造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)for(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;函数类型和不完全数组类型无重复概念，总是创建新类型重复类型检查2021/10/1037类型构造NEW0(tn,PERM);tn-type.op=op;tn-type.type=ty;tn-type.size=size;tn-type.align=align;tn-type.u.sym=sym;tn-link=typetableh;typetableh=tn;return&tn-type;2021/10/1038指针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;脱掉指针2021/10/1039数组Type array(Type ty,int n,int a)assert(ty);if(isfunc(ty)error(illegal type array of%tn,ty);return array(inttype,n0);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(declaring type array of%t is undefinedn,ty);不允许函数数组数组的数组，低维必须大小已知2021/10/1040数组 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);2021/10/1041结构和联合Type newstruct(int op,char*tag)Symbol p;assert(tag);if(*tag=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);创建一个结构类型，但只是一个空架子2021/10/1042结构和联合p=install(tag,&types,level,PERM);p-type=type(op,NULL,0,0,p);if(p-scope maxlevel)maxlevel=p-scope;p-src=src;return p-type;2021/10/1043结构和联合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(duplicate field name%s in%tn,name,ty);NEW0(p,PERM);*q=p;p-name=name;p-type=fty;2021/10/1044结构和联合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.ftab0,PERM)-src=src;/*omit*/*omit*/return p;2021/10/1045结构和联合static Type structdcl(int op)ty=newstruct(op,tag);fields(ty);static void fields(Type ty)p=newfield(id,ty,fty);2021/10/1046类型等价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);2021/10/1047类型等价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;2021/10/1048类型等价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;2021/10/1049类型等价 else if(variadic(p1?ty1:ty2)return 0;ifp1=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;2021/10/1050TinyC的类型检查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);2021/10/1051TinyC的类型检查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;2021/10/1052TinyC的类型检查 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;2021/10/1053TinyC的类型检查 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;2021/10/10546.5 函数和操作符重载m重载（overloaded）符号：根据上下文，具有不同的意义q+：整型加法，浮点型加法qA(I)：数组A的第I个元素，以参数I调用A，将I转换为类型A的显式类型转换m重载的解析（resolved）：在某个特定上下文，确定符号的唯一意义q1+2：+为整型加法q运算符识别，operator identification2021/10/10556.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类型22021/10/1056可能类型集合情况的处理E id E.types=lookup(id.entry)E E1(E2)E.types=t|E2.types中 存在s使得st属于 E1.types m单一类型运算类型集合运算2021/10/1057例6.72021/10/10586.5.2 确定唯一类型m完整表达式须有唯一类型确定每个子表达式的唯一类型，或type_errorm自顶向下mE.types中每个类型t均为可行（feasible）类型确定E中重载标识符的类型，某种情况下，E的类型为tq对标识符成立，id.types中类型均可行q归纳法：E为E1(E2)，s为E2可行类型，st为E1可行类型，因此t为E可行类型2021/10/1059确定唯一类型的语义规则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)2021/10/10606.6 多态（polymorphic）函数m普通函数：参数类型固定m多态函数：不同调用参数可为不同类型m某些内置操作符多态操作符q数组索引符，函数调用符()，指针操作符&q&：“若操作对象类型为，则操作结果的类型为指向的指针2021/10/10616.6.1 为什么使用多态函数？m实现算法处理数据结构，而不必管其内部元素的类型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:=lenend2021/10/1062求任何类型列表长度的ML程序fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;m可应用于任何类型的列表qlength(“sun”,“mon”,“tue”);qlength(10,9,8);递归函数递归函数列表为空列表为空？列表剩余部分列表剩余部分2021/10/10636.6.2 类型变量ma,b,，表示未知类型m重要应用：不要求标识符先声明后使用的语言中，检查标识符使用的一致性m类型变量表示未声明标识符的类型q若类型变量发生变化，不一致！q若一直未变化，一致！同时得到标识符类型m类型推断，type inferenceq根据语言结构的使用方式判定其类型2021/10/1064例6.8type link=cell;procedure mlist(lptr:link;procedure p);beginwhile lptr nil do beginp(lptr);lptr:=lptr.nextendend;mp：参数情况未知，不完整的过程类型m由p(lptr)qp参数为link类型，p的类型为linkvoidq其他使用方式均会导致type_error2021/10/1065例6.9function deref(p);beginreturn p;end;m扫描第一行，p的类型未知，用b表示m第三行，应作用于指针，因此p为某未知基本类型a的指针类型，b=pointer(a)m因此函数deref类型为：pointer(a)a2021/10/10666.6.3 包含多态函数的语言m用 表示“对所有类型”mderef类型的精确描述：mlength：qlist(integer)integerqlist(list(char)integerm ：全称量词（universal quantifier）它所施用的类型变量称为由它约束（bound）2021/10/1067文法定义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)2021/10/1068多态函数类型检查m每个结点两个标签：子表达式和类型表达式m下标o：外层deref，i：内存deref2021/10/1069类型检查规则的特点1.不同位置出现的同一多态函数可具有不同类型的参数。mderefo参数为二重指针，而derefi的参数为一重指针。m关键在于 的解释，对不同deref，约束的类型变量a所代表的意义是不同的。m对多态函数的每次出现，都赋予不同的类型变量，而不再使用 上例中用ao、ai分别对应外层和内层deref2021/10/1070类型检查规则的特点（二）2.类型表达式中存在变量，因此要重新考虑类型等价的概念m类型为ss的函数E1施用于类型为t的E2，仅判定s和t是否等价是不够的，要对它们进行“一致化”（unify）m适当替换类型变量，检查是否有可能达到结构等价m上例：将ai替换为pointer(integer)，则pointer(ai)与pointer(pointer(integer)等价2021/10/1071类型检查规则的特点（三）3.需要某种机制记录一致化的影响m一个类型变量可出现在表达式的多个位置m若s和s的一致化使得变量a表示类型t，则在整个类型表达式中，它都应表示tm上例：ai作用域为derefi(q)，因此可用来一致化derefi和qm而ao为不同类型变量，因此表示不同类型不违反本规则2021/10/10726.6.4 代换，实例和合一m变量表示实际类型的形式化定义q类型变量类型表达式的映射，称为替换，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);mS(t)表示代换t的类型表达式，称为t的实例，instancem若无法代换，S(a)=a，恒等映射2021/10/1073例6.10mst表示s是t的一个实例qpointer(integer)pointer(a)qpointer(real)pointer(a)qinteger integer a aqpointer(a)bqa bm不是实例的情况qintegerrealqinteger reala aqinteger aa a2021/10/1074合一方法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)的一个实例2021/10/10756.6.5 多态函数类型检查m检查规则由下列对类型图的操作构成qfresh(t)将类型表达式t中约束变量代换为新变量，返回代换后类型表达式结点指针消除qunify(m,n)将结点m、n表示的类型表达式合一，会修改、保存对应的代换。若失败，则整个类型检查过程失败m图的创建仍可用mkleaf、mknode完成m每个类型变量创建不同结点2021/10/1076unify操作m合一、代换基于图论的方法mm、n为类型图结点，分别表示表达式e、f，若S(e)=S(f)，称m、n在代换S下等价m求最一般的合一代换q转化为在S下必须等价的结点的集合划分问题q类型表达式等价根必须等价qm、n等价表示相同操作且孩子结点等价2021/10/1077类型检查规则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);mE1.type=a，E2.type=b，都是类型变量m前者是函数，寻求两者等价，必有类型变量g，使得a=bg2021/10/1078例表达式类型代换qpointer(pointer(integer)derefipointer(ai)aiderefi(q)pointer(integer)ai=pointer(integer)derefopointer(ao)aoderefo(derefi(q)integer ao=integer2021/10/1079例6.112021/10/1080例6.11（续）mderefi的合一过程2021/10/1081例6.12 ML语言多态函数检查fun id0(id1,idk)=E;mid0：函数名，id1,idk：参数，E遵从前面定义的用于多态函数类型检查的文法，其中的标识符只可能是函数名、参数或内置函数m方法：例6.9方法的形式化q为函数名和参数创建新类型变量q多态函数的类型变量由 约束q检查id0(id1,idk)和E类型是否匹配q若成功，则推断出函数类型2021/10/1082例6.12（续）fun length(lptr)=if null(lptr)then 0else length(tl(lptr)+1;m类型变量：lengthb，lptrgm为匹配函数体：b=m按多态函数类型检查语言重写程序length:b;lptr:g;if:2021/10/1083例6.12（续）null:tl:0integer;1:integer;+:match:match(length(lptr),if(null(lptr),0,length(tl(lptr)+1)检查length(lptr)与函数体匹配2021/10/1084例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=anlength参数为参数为lptrg g返回类型