Chapt8-符号表.ppt

编译原理教案,-2008,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,符号表的作用,一致性检查,和,作用域分析,；,辅助代码生成,。,编译原理教案-2008,8.1 符号表的组织与作用,符号表的每一项,(,入口,)包含两大栏：,名字,栏，也称主栏，关键字栏；,信息,栏，记录相应的,不同属性,，分为若干子栏。,对符号表的操作,：,填入名称,、,查找名字,、,访问信息,、,修改信息,、,删除,名字,编译原理教案-2008,符号表：分类、组织,对符号表进行操作的,时机,：,定义,性出现,；,使用,性出现,。,按名字的不同种属建立多张符号表，,如,：,常数表,、,变量名表,、,过程名表,符号的,组织,方式,：,1.安排各项各栏的存储单元为,固定长度,；,2.用,间接方式安排,各栏存储单元,。,编译原理教案-2008,编译原理教案-2008,编译原理教案-2008,8.2 整理和查找,1.,线性,查找,：,按,关键字出现的顺序,填写各项。,填表快,，,查找慢,。,结构简单，节省空间，,效率,低，,查找时间,复杂度,：,O,(n),。,改进：,自适应,线性表。,编译原理教案-2008,2.,二分,查找,：,表格中的项,按名字的,“大小”,顺序排列,。,填表慢,，,查找快,。查找时间,复杂度,：,O(Log,2,n),。,改进：组织成,二叉树,。,3.,杂凑,查找(,HASH,技术),：,杂凑函数,H(SYM)：0N-1N：,符号表的,项数,。,要求：1.,计算简单,高效；,2.,函数值分布均匀,。,填表快,，,查找快,。,编译原理教案-2008,8.4 符号表的内容,符号表的信息栏中登记了每个名字的有关性质：,类型,：,整,、,实,或,布尔,等；,种属,：简单,变量,、,数组,、,过程,等；,大小,：长度，即所需的,存储单元字数,；,相对数,：指分配给,该名字的存储单元,的,相对地址,。,编译原理教案-2008,PL语言编译程序的符号表,1.表格的定义：,名字,表(,nametab,),；,程序,体表(,btab,),；,层次显示,表(,display),；,数组,信息表(,atab,),；,中间代码,表(,code),。,编译原理教案-2008,(,1),名字表(,nametab),名字表,nametab：,登记程序中出现的各种,名字及其属性,：,编译原理教案-2008,(2)程序体表,btab,程序体表,btab,：,记录一个,程序体的总体信息,，用于对源程序中定义的,名字的作用域进行分析,；,对名字表进行管理,。,编译原理教案-2008,层次显示表display,层次显示表,display：,描述,正在处理,的,各个嵌套层次,，,对程序体表进行管理,。,编译原理教案-2008,(3),数组信息表,atab,编译原理教案-2008,例：,type a=array1.10,1.10 of integer;,nametab,atab,编译原理教案-2008,(4)中间代码表code,中间代码表,code：,用于,存放编译程序所产生的每条中间代码,。,编译原理教案-2008,8.3 名字的作用,范围,在许多程序语言中,，,名字都有一个确定的作用范围,。,两种程序体结构,：,并列结构,，如,：FORTRAN,；,嵌套结构,，如,：PASCAL，ADA,。,编译原理教案-2008,FORTRAN,程序举例,PROGRAM,MAIN,integer,X,，,Y,COMMON,/C/A,，,B,END,SUBROUTINE,SUB1,real,X,，,Z,COMMON,/C/A1,，,B1,END,编译原理教案-2008,PASCAL,程序举例,program,P,;,var,a,b,:integer;,procedure,P1,(,i1,j1,:integer);,var,c,d,:integer,end;,procedure,P2,(,i2,j2,:integer);,var,a,c,:integer;,procedure,P21,;,var,b1,b2,:boolean;,end;,end;,end.,编译原理教案-2008,符号表的组织方式,1,.,FORTRAN,语言,的符号表组织,：,一个,FORTRAN,程序由一个,主程序段,和若干个,辅程序段,组成,。,把,局部名,和,全局名,分别存在不同的地方,。,2.,嵌套结构,语言的符号表组织,：,如,：PASCAL、ALGOL、ADA,。名字的,作用域遵循“,最近嵌套原则,”,。,编译原理教案-2008,嵌套结构语言的符号表组织,两,个,方面的处理：,引入“,过程编号,”属性,。在,查找时，先查找,本过程编号的名字,，查不到则查找,外层过程编号的名字,，等等,。,按“,栈,”式思想,组织符号表,。在,查找时，,从后往前查找,，,找,到的第一个名字,就是所需查找的名字,。,编译原理教案-2008,PASCAL,程序的符号表：举例,program,P,;,var,a,b,:integer;,procedure,P1,(,i1,j1,:integer);,var,c,d,:integer,end;,procedure,P2,(,i2,j2,:integer);,var,a,c,:integer;,procedure,P21,;,var,b1,b2,:boolean;,end;,end;,end.,编译原理教案-2008,编译原理教案-2008,PASCAL,程序,PASCAL,程序本身可以看成是一个,操作系统所调用的过程,，,过程,可以,嵌套,和,递归,。,一个,PASCAL,过程,：,过程头,；,说明段,(,由一系列的,说明语句,组成,),；,begin,执行体,(,由一系列的,执行语句,组成,),；,end,编译原理教案-2008,作用域,：一个,名字,能,被使用的区域,范围称作这个名字的作用域。,允许,同一个标识符,在,不同的过程,中,代表不同的名字,。,名字作用域规则,-,最近嵌套原则,一个在,子程序,B,1,中,说明的名字,X,只在,B,1,中有效,(,局部于,B,1,),；,如果,B,2,是,B,1,的一个内层子程序,且,B,2,中对标识符,X,没有新的说明,，则,原来的名字,X,在,B,2,中仍然有效,。如果,B,2,对,X,重新作了说明,，那么，,B,2,对,X,的任何引用,都是指,重新说明过的这个,X,。,编译原理教案-2008,program main,var A,B:real;,procedure P1,var B:boolean;,begin,end,procedure P2,var A:integer;,begin,end,begin,end,A(real),B(real),B(bool),A(integr),编译原理教案-2008,