资源描述
5类型检查,学时：4知识点：类型体制各语法成分的类型检查符号表,2,5类型检查,5.1语义分析的概念5.2类型体制5.3简单类型检查器的说明5.4类型表达式的等价5.5类型检查有关的其他主题5.6符号表小结作业,3,5.1语义分析的概念,程序设计语言的结构由上下文无关文法来描述程序结构正确与否与该结构的上下文有关，如：变量的作用域问题同一作用域内同名变量的重复声明问题表达式、赋值语句中的操作数的类型一致性问题思考：设计上下文有关文法来描述语言中上下文有关的结构？理论上可行，构造有困难，构造相应的分析器更困难解决办法：设计专门的语义动作补充上下文无关文法的分析器利用语法制导翻译技术实现语义分析,4,上下文有关信息的记录与使用,符号表记录编译过程中识别出的上下文有关的信息，如：变量的类型相对地址信息的引用根据词法分析器识别出的标识符的属性值（标识符在符号表中的入口），查找符号表中对应该标识符的记录，从而可以取得该标识符有关的信息。如果编译的程序块处于该变量的作用域内，则这个变量将一直保留在符号表中,5,动态检查：目标程序运行时进行的检查静态检查：读入源程序、但不执行源程序的情况下进行的检查，包括：类型检查对访问数据的操作和被访问数据的类型进行检查，检查操作的合法性和数据类型的相容性。控制流检查检查控制流语句是否使控制转移到一个合法的位置。一致性检查有些场合要求所定义的对象恰好被定义一次一个标识符在同一程序块中必须而且只能被说明一次CASE语句中用于匹配选择表达式的常量必须各不相同枚举类型定义中的各元素不允许重复有些场合要求标识某结构的名字必须出现两次或两次以上,静态检查,6,类型检查,由类型检查器完成检验结构的类型是否和它的上下文所期望的一致算术运算符mod用户定义的函数，实参与形参一致类型检查器的位置,生成目标代码时可能用到类型检查器产生的信息重载运算符：一个运算符在不同的上下文中表示不同的运算类型强制：编译器把运算对象变换为上下文所期望的类型,7,5.2类型体制,设计类型检查器时要考虑的因素：语法结构类型概念把类型指派给语言结构的规则Pascal、C语言报告中关于类型的描述：如果算术运算符加、减和乘的两个运算对象都是整型，那么结果是整型。一元运算符与A相关的类型表达式为：array(1.10,integer)笛卡儿乘积：如果T1和T2是类型表达式，那么它们的笛卡儿乘积T1T2也是类型表达式，假定是左结合的。,9,如Pascal的程序片段：,typerow=recordaddress:integer;lexeme:array1.15ofcharend;vartable:array1.10ofrow;,类型名row代表类型表达式:record(addressinteger)(lexemearray(1.15,char)和变量table相关的类型表达式为：array(1.10,row)指针：如果T是类型表达式，那么pointer(T)是表示“指向T类型对象的指针”的类型表达式。Pascal的例子：varp:row;与P相关的类型表达式为：pointer(row),记录：记录类型是它的各域类型的笛卡儿乘积，记录的域有名，每个域是一个二元组（域名类型）,10,函数：从定义域类型D到值域类型R的映射类型由类型表达式DR表示。,Pascal的内部函数mod：intintint用户定义的Pascal函数：functionf(a,b:char):integer;f的类型表达式：charcharpointer(integer)函数g：参数是把整数映射成整数的函数返回结果是和参数类型相同的另一函数g的类型表达式为：(integerinteger)(integerinteger)类型表达式可以包含变量（称为类型变量），变量的值是类型表达式。,11,类型表达式的有向图,利用语法制导翻译技术为类型表达式构造树或dag内部结点：类型构造器叶结点：基本类型、类型名、或类型变量如：charcharpointer(integer),12,二、类型体制,把类型表达式指派到程序各部分的一组规则由类型检查器实现同一语言的不同编译器使用的类型体制可能不同数组作为变元传递时，数组的下标集合可以指明，也可以不指明原因：不同的Pascal语言编译器实现的类型体制不同UNIX系统中，lint命令实现的类型体制比C语言编译器本身所实现的更详细。,13,三、静态和动态类型检查,静态类型检查：由编译器完成的检查动态类型检查：目标程序运行时完成的检查如果目标代码把每个对象的类型和该对象的值一起保存，那么任何检查都可以动态完成。一个健全的类型体制不需要动态检查类型错误如果一种语言的编译器能够保证它所接受的程序不会有运行时的类型错误，则称这种语言是强类型语言。有些检查只能动态完成table:array0.255ofchar;i:integer;计算tablei,14,四、错误恢复,类型错误不直观，必须报告错误的性质和位置，希望能从错误中恢复，检查剩余的输入出错处理会影响类型检查的规则，必须将其正确地设计进类型体制中包含出错处理的类型体制可能比说明正确程序所需要的类型体制大得多类型检查器必须应付缺少信息的局面，我们可能不知道错误程序片段的类型使用的技术类似于支持变量隐式声明的语言所需要的技术,15,5.3简单类型检查器的说明,利用语法制导方法说明类型体制一、语言说明二、确定标识符的类型三、表达式的类型检查四、语句的类型检查,16,一、语言说明,源语言文法：PD;SDD;D|id:TTchar|integer|boolean|arraynumofT|T|T1T2Sid:=E|ifEthenS1|whileEdoS1|S1;S2Eliteral|num|id|id1id2EE1andE2EE1modE2EE1E2EE1EE1(E2),综合属性E.type，类型体制指派给E产生的表达式的类型表达式,E.type:=char,E.type:=integer,E.type:=lookup(id.entry),E.type:=iflookup(id1.entry)=integerandlookup(id2.entry)=integerorlookup(id1.entry)=charandlookup(id2.entry)=charthenbooleanelsetype_error,20,EE1andE2,EE1modE2EE1E2EE1EE1(E2),E.type:=ifE1.type=booleanandE2.type=booleanthenbooleanelsetype_error,E.type:=ifE1.type=integerandE2.type=integerthenintegerelsetype_error,E.type:=ifE2.type=integerandE1.type=array(s,t)thentelsetype_error,21,EE1,EE1(E2),E.type:=ifE1.type=pointer(t)thentelsetype_error,E.type:=ifE1.type=standE2.type=sthentelsetype_error,22,四、语句的类型检查,Sid:=ESifEthenS1SwhileEdoS1SS1;S2,S.type:=iflookup(id.entry)=E.typethenvoidelsetype_error,S.type:=ifE.type=booleanthenS1.typeelsetype_error,S.type:=ifE.type=booleanthenS1.typeelsetype_error,S.type:=ifS1.type=voidandS2.type=voidthenvoidelsetype_error,23,5.4类型表达式的等价,语义规则的形式：if两个类型表达式相同then返回某一个类型else返回type_error关键：精确地定义什么情况下两个类型表达式等价问题：类型表达式可以命名，且这个名字可用于随后的类型表达式中名字代表它自己？代表另一个类型表达式？新的名称是一个类型表达式，这个表达式与名称所代表的类型表达式是否总是等价的？,24,一、结构等价,如果类型表达式仅由类型构造器作用于基本类型组成，则两个类型表达式等价的自然概念是结构等价两个类型表达式要么是同样的基本类型要么是同样的构造器作用于结构上等价的类型表达式。两个类型表达式结构等价当且仅当它们完全相同例如：integer仅等价于integerpointer(integer)仅等价于pointer(integer),25,测试两个类型表达式结构等价的算法,输入：两个类型表达式s和t输出：如果s和t结构等价，则返回true，否则返回false方法：functionsequiv(s,t):booleanbeginifs和t是同样的基本类型thenreturntrueelseifs=array(s1,s2)且t=array(t1,t2)thenreturnsequiv(s1,t1)andsequiv(s2,t2)elseifs=s1s2且t=t1t2thenreturnsequiv(s1,t1)andsequiv(s2,t2)elseifs=pointer(s1)且t=pointer(t1)thenreturnsequiv(s1,t1)elseifs=s1s2且t=t1t2thenreturnsequiv(s1,t1)andsequiv(s2,t2)elsereturnfalseend.,26,实际应用中结构等价概念的修改,当数组作为参数传递时，数组的界不作为类型的一部分算法调整elseifs=array(s1,s2)且t=array(t1,t2)thenreturnsequiv(s2,t2),27,编码测试方法,对基本类型规定确定位数、确定位置的二进制编码；对类型构造器规定确定位数的二进制编码类型表达式可用一组二进制编码表示例：D.M.Ritchie的C编译器中类型表达式的编码方式类型构造器：pointer(t)指向类型t的指针freturn(t)含有参数的函数，返回类型t的对象array(t)元素类型为t的数组（不定长度）一元运算符，类型表达式具有统一的结构charfreturn(char)pointer(freturn(char)array(pointer(freturn(char),28,编码方式,类型构造器的编码,基本类型的编码,类型表达式及其二进制编码示例,29,有些语言(如Pascal)允许用户定义类型名Pascal类型定义和变量声明：typelink=cell;varnext:link;last:link;p:cell;q,r:cell;问题：next、last、p、q和r是否具有相同的类型关键：类型表达式link和类型表达式cell是否等价回答：依赖于具体的实现系统原因：在Pascal报告中没有定义“类型等价”这个术语,二、名字等价,30,名字等价把每个类型名看成是一个可区别的类型,两个类型表达式名字等价，当且仅当它们完全相同所有的名字被替换后，两个类型表达式成为结构等价的类型表达式，那么这两个表达式结构等价。声明中的变量及其类型表达式：,考虑名字等价的情形,考虑结构等价的情形,31,标识符与类型通过声明相联系的规则举例,Pascal的许多编译器用隐含的类型名与每个声明的标识符相联系如果声明中出现了没有名字的类型表达式，则建立一个隐含的类型名。每当声明中出现类型表达式时，就建立一个新的类型名。typelink=cell;np=cell;nqr=cell;varnext:link;last:link;p:np;q,r:nqr;next,last等价；q,r等价；next,last和p和q,r互不等价结构等价和名字等价这两个概念，可以用来揭示各种语言中通过说明使类型和标识符相关的规则C语言采用结构等价，Pascal采用名字等价,32,类型图,类型图表示类型构造方法：每当出现一个类型构造器或基本类型，就建立一个新的结点；每当出现一个新的类型名时，就建立一个叶结点；要跟踪该名字所代表的类型表达式。在类型图中，如果两个类型表达式用相同的结点表示，则它们是名字等价的。,typelink=cell;np=cell;nqr=cell;varnext:link;last:link;p:np;q,r:nqr;,link,pointer,cell,=,pointer,pointer,33,三、类型表示中的环,指针和结点的类型定义用Pascal语言描述如下：typelink=cell;cell=recordinfo:integer;next:linkend;cell的类型表达式：,34,C语言的处理,C语言对除结构（记录)以外的所有类型采用结构等价的概念，避免在类型图中出现环路C语言中对于cell的类型定义如下：structcellintinfo;structcell*next;,35,5.5类型检查有关的其他主题,一、类型转换二、重载三、多态性类型,36,一、类型转换,表达式：x+i，x为real，i为integer整型数和实型数在计算机中的表示不同，运算的机器指令也不同编译程序必须首先转换一个操作数，以保证类型相同语言定义指出什么转换是必需的赋值语句：把赋值号右边的对象转换成左边对象的类型表达式：把整数转换成实数，然后在这一对实型对象上进行实数运算类型检查器在源程序的中间表示里插入这些转换操作X+I的后缀式可能是：xiinttorealreal+如果从一种数据类型转换成另一种数据类型可以由编译器自动完成，则这种类型转换是隐式的，隐式转换也叫做强制转换。一般要求隐式转换原则上不丢失信息如果转换必须由程序员显式地写在源程序中，则这种转换叫做显式转换。显式的类型转换对类型检查器来说好象函数调用,37,常数的隐式转换,forI:=1toNdoXI:=1执行时间：48.4NsforI:=1toNdoXI:=1.0执行时间：5.4Ns编译器为第一个语句产生的目标代码含运行时的例程调用，该例程把1的整型表示转换为实型表示大多数编译器都在编译时把1转换为1.0,38,从整型到实型的类型检查规则,39,二、重载,操作符的重载：如果同一操作符名用于了两个不同的操作在数学中，加法运算符+是重载的当A和B是整数、实数、复数或矩阵时，表达式A+B中的+具有不同的含义。重载符号的含义依赖于上下文在重载符号的引用点，其含义能够确定到唯一，叫做重载的消除。重载的消除有时也称为算符的辨别，因为它确定了运算符号表示哪种运算。大多数语言中，算术运算符是重载的，并且它们的重载可以通过查看其操作对象来消除。,40,函数或过程的重载,重载可以扩展到用户说明的函数或过程，相关的操作使用相同的名字，但说明不同的参数或不同的类型例，对两个整数和实数值，定义取最大值的函数functionmax(x,y:integer):integer;functionmax(x,y:real):real;在Pascal和C中是非法的，在Ada和C+中是合法的，类型检查器可以根据参数的类型确定要使用哪一个max函数实现：符号表保持名字所有可能类型的集合，并把这个集合返回给类型检查器，由类型检查器根据上下文确定类型,41,三、多态性类型,如果允许语言的构造有多种类型，则语言是多态性的如果所有的名字和表达式都要求有唯一的类型，则语言是单态性的重载是单态性要求的一种放松，只能用于相同名字多种独立说明的情形，当单个说明需要用于任意的类型时就出现了另一种不同情形,42,多态性例子,交换两个变量值的过程在原理上可以用于任何类型的变量，只要它们类型相同Procedureswap(varx,y:anytype);这里anytype被看作是类型变量，能假设成任意实际的类型可以这样表达这个过程的类型functionswap(var:anytype,var:anytype):void这样的类型实际上是类型模式或类型方案，而不是实际类型类型检查器对每次使用swap的情形都需要确定实际的类型，匹配这个类型模式，或说明一个类型错误,43,给定代码Varx,y:integer;a,b:char;swap(x,y);swap(a,b);swap(a,x);在调用swap(x,y)时，根据其给定的多态性类型模式“指定”到单态类型：functionswap(var:integer,var:integer):void在调用swap(a,b)时，它被指定类型：functionswap(var:char,var:char):void在调用swap(a,x)时，它的类型为：functionswap(var:char,var:integer):void这个类型不能从swap的类型模式通过替代类型变量anytype来产生在类型检查算法进行这种一般的多态性类型检查，其中包括复杂的模式匹配技术，在现代函数式语言中有应用,44,5.6符号表,符号表在翻译过程中起两方面的重要作用：检查语义（即上下文有关）的正确性辅助正确地生成代码通过在符号表中插入和检索变量的属性来实现的符号表是一张动态表在编译期间符号表的入口不断地增加在某些情况下又在不断地删除编译器需要频繁地与符号表进行交互，符号表的效率直接影响编译器的效率。,45,本节内容安排,一、建立和访问符号表的时机二、符号表的内容三、在符号表上的操作四、符号表的组织,46,一、建立和访问符号表的时机,1.多遍编译器,符号表在词法分析遍内创建，变量在符号表中的位置作为词法分析器所产生的记号的属性,47,2.合并遍的编译器,两方面的优点：对语法分析器来讲降低了文法的复杂性允许用更系统的方法对上下文有关的错误进行检测和校正。,48,二、符号表的内容,符号表中记录的是和标识符相关的属性出现在符号表中的属性种类，在一定程度上取决于程序设计语言的性质。符号表的典型形式：,49,变量名,变量名必须常驻内存问题：标识符长度是可变的解决办法：标识符长度有限制：设置一个长度固定的域，它的长度为该语言允许的标识符最大长度。标识符长度没有限制：设置一个长度固定的域，域内存放一个串描述符，包含位置指针和长度两个子域，指针域指示该标识符在总的串区内的开始位置，长度域记录该标识符中的字符数。,存取速度较高，存储空间利用率较低,存取速度较慢，节省存储空间。,50,使用串描述符表示变量,51,目标地址,指示运行时变量值存放的相对位置对于静态存储分配的语言（如Fortran），目标地址按连续的顺序分配，从1开始到m（m是分配给一个程序的数据区的最大值）。对于块结构的语言(如Pascal)，通常采用二元地址BL：块的嵌套深度，用于确定分配给声明变量的块的数据区的基址。NO：变量的目标地址偏移量，指示该变量的存储单元在数据区中相对于基址的位置。,52,数据类型,当所编译的语言有数据类型（隐式或显式的）时，必须把类型属性存放到符号表中。对于无类型的语言，可删除该域。变量的类型属性用于：类型检查生成代码空间分配变量的类型以一种编码形式存放在符号表中。,53,数组的维数/参数的个数,数组引用时，其维数应当与数组声明时定义的维数一致。类型检查阶段必须对这种一致性（维数、每维的长度）进行检查维数用于数组元素地址的计算。过程调用时，实参必须与形参一致。实参的个数与形参的个数一致实参的类型与相应形参的类型一致在符号表组织中：把参数的个数看作它的维数是很方便的，因此，可将这两个属性合并成一个。这种方法也是协调的，因为对这两种属性所做的类型检查是类似的。,54,交叉引用表,编译程序可以提供的一个十分重要的程序设计辅助工具：交叉引用表编译器一般设一个选项，用户可以选择是否生成交叉引用表,55,链域,为了于便产生按字母顺序排列的交叉引用表如果编译程序不产生交叉引用表，则链域以及语句的行号属性都可以从符号表中删除。,56,三、在符号表上的操作,基本操作：插入和检索要求变量显式声明的强类型语言：编译器在处理声明语句时调用两种操作检索：查重、确定新表目的位置插入：建立新的表目在程序中引用变量名时，调用检索操作查找信息，进行语义分析、代码生成可以发现未定义的名字允许变量隐式声明的语言：标识符的每次出现都按首次出现处理检索：已经声明，进行类型检查，.首次出现，插入操作，从其作用推测出该变量的全部属性,57,定位和重定位操作,对于块结构的语言，在建立和删除符号表时还要使用两种附加的操作，即定位和重定位。当编译器识别出块的开始时，执行定位操作。当编译器遇到块的结束时，执行重定位操作。定位操作：建立一个新的子表（包含于符号表中），在该块中声明的所有变量的属性都存放在此子表中。重定位操作：删除存放该块中局部变量的子表这些变量的作用域局部于该块，出了该块后这些变量不能再被引用。不同分程序中的相同变量名问题的解决方法：分程序是按层次嵌套的，如果多层嵌套（如n层），那么这些子符号表也是多层嵌套，并按序生成（即先产生子符号表1，最后产生子符号表n）。在第n层分程序需要查找某一标识符时，先从子符号表n开始查找，如果未查到，再依次查子符号表n-1,n-2,1，如果在符号表i首先出现该标识符名，这便正是所要查找的结果,58,符号表的逻辑结构,59,四、符号表的组织,1.非块结构语言的符号表组织2.块结构语言的符号表组织,60,1.非块结构语言的符号表组织,非块结构语言：编写的每一个可独立编译的程序单元是一个不含子模块的单一模块模块中声明的所有变量属于整个模块符号表组织无序线性表属性记录按变量声明/出现的先后顺序填入表中插入前都要进行检索，若发现同名变量对显式声明的语言：错误对隐式声明的语言：引用适用于程序中出现的变量很少的情况,61,散列表查找时间与表中记录数无关的一种符号表组织方式,有序线性表按字母顺序对变量名排序的表避免了对整个表的查找线性查找：当遇到第一个比查找变量名值大的项目时，就可以判定该变量名不在表中了。当执行插入操作时，要增加额外的比较和移动操作。若使用单链结构表的话，可省去表记录的移动，但需要在每个表记录中增加一个链接字段。折半查找：首先把变量名与中间项进行比较，结果或是找到该变量名，或是指出下一次要在哪半张表中进行。重复此过程，直到找到该变量名或确定该变量名不在表中为止。,62,散列函数H,除法：最常用的散列函数，H(x)=(xmodm)+1，通常m为一个大的素数，这样可使标识符尽可能均匀地分散在表中中平方散列法：先将标识符进行平方运算，然后将结果的两头几个值或数字去掉，直到剩下的位数或数字等于所期望的地址，必须对所有的标识符的平方值进行同样的处理。折叠法：标识符被分成若干段，可能除最后一段外，每一段与所需地址具有同样长度，然后各段加起来，忽略最后的进位，以构成一个地址。长度相关法：变量名的长度和名字的某个部分一起用来直接产生一个表地址，或更普遍的方法是产生一个有用的中间字，然后用除法产生一个最终的表地址。,63,解决冲突的方法,变量名被映射到一个存储单元d中，而这个单元已被占用开放地址法分离链表法,按照顺序d,d+1,m,1,2,d-1进行扫描，直到找到一个空闲的存储单元为止，或者在扫描完m个单元之后搜索停止在查找一个记录时，按同样的顺序扫描，或找到要找的记录、或找到一个空闲单元（从未使用过）为止,将发生冲突的记录链到一个专门的溢出区，该溢出区与主区相分离为每一组冲突的记录设置一个链表，主区和溢出区的每一个记录都必须有一个链接字段。为节省存储空间，建立一个中间表（散列表），所有记录都存入溢出区，而主区（散列表）只有链域,64,示意图,65,2.块结构语言的符号表组织,块结构语言：模块中可嵌套子块子块中可以定义局部变量。每个块应有一个子表符号表组织栈式符号表当遇到变量声明时，将包含变量属性的记录入栈当到达块结尾时，将该块中声明的所有变量的记录出栈因为这些变量是局部于该块的，在块外已不可用的。,66,栈式符号表,readarrayxa,exchange,quicksort,67,操作,插入检查子表中是否有重名变量无，将新记录推入栈顶单元有，报告错误检索从栈顶到栈底线性检索在当前子表中找到，局部变量在其他子表中找到，非局部名字根据最近嵌套作用域原则，选择变量的记录第一次检索到的名字就是按照最近嵌套作用域原则要求的名字得申明,68,定位,将下一个可用的栈顶单元的地址压入块索引表的顶端块索引表的元素是指针，指向相应块的子表中第一个记录在栈中的位置重定位有效地清除刚刚被编译完的块在栈式符号表中的所有记录用块索引表顶端元素的值恢复栈顶指针top，完成重定位操作top指示符号表栈顶第一个空闲的记录存储单元。,69,栈式散列符号表,假设散列表的大小为11，散列函数执行如下变换：,70,栈式散列符号表示意图,1,2,3,a,x,readarray,nil,nil,nil,1,4,i,4,nil,nil,exchange,nil,4,71,栈式散列符号表示意图,6,quicksort,5,1,k,3,6,v,2,7,parttition,nil,8,9,i,nil,9,j,7,10,72,操作,插入散列函数将变量名映射到散列表单元是否存在冲突？该表单元是否为空？无冲突：将栈指针的值记入该散列表单元将新记录推入栈顶有冲突检查冲突链中是否有同名变量没有：将新记录插入冲突链的链头有：检查同名变量是否属于当前子表同名变量在栈中的位置=块索引表顶端元素的值？=：在当前子表中，报告错误=块索引表顶端元素的值=：局部名字：非局部名字,74,定位与重定位,定位当识别到一个新块时，要为之创建子表将下一个可用的栈顶单元的地址压入块索引表的顶端标识新块符号子表的开始位置重定位当一个块编译完成时，它的有关记录必须逻辑上或物理上从符号表中除去。用块索引表顶端单元的值确定要删除的栈单元依次取出栈单元中的名字通过散列函数将该名字映射到散列表单元从链中把链头记录删除重复，直到新链头在栈中的位置块索引表顶端单元的值用块索引表顶端单元的值设置栈顶指针TOP,75,小结,语义分析的概念编译的一个重要任务、检查语义的合法性类型检查控制流合法性检查同名变量检查关联名字检查利用语法制导的翻译技术实现类型体制语法结构、类型概念、把类型指派给语言结构的规则类型表达式的定义类型推导,76,小结（续）,简单类型检查器的说明声明语句的类型检查表达式的类型检查语句的类型检查类型表达式的等价结构等价名字等价类型表达式结构等价的测试算法类型检查有关的其他主题函数和运算符的重载类型转换多态函数,77,小结（续）,符号表何时创建内容操作检索、插入定位、重定位组织形式非块结构语言块结构语言,78,作业,1236811,
展开阅读全文