Chapt8符号表

国防科技大学计算机系,602,教研室,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第八章,符号表,符号表的作用:,一致性检查和作用域分析;,辅助代码生成.,国防科技大学计算机系,602,教研室,8.1 符号表的组织与作用,符号表的每一项(入口)包含两大栏:,名字栏，也称主栏，关键字栏,信息栏，记录相应的不同属性，分为若干子栏.,对符号表的操作:,填入名称,查找名字,访问信息,填写修改信息,删除,国防科技大学计算机系,602,教研室,对符号表进行操作的时机：,定义性出现,使用性出现,按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表、,符号的组织方式:,1. 安排各项各栏的存储单元为固定长度,2. 用间接方式安排各栏存储单元,国防科技大学计算机系,602,教研室,符号表的存放次序:,1.,把每一项置于连续,K,存储单元中，构成一张,K*N,的表,2. 把整个符号表分成,m,个子表，如,T,1,T,2,T,m,，每个子表含有,N,项.,国防科技大学计算机系,602,教研室,例:,PASCAL,程序段：,PROCEDURE INCWAP(M，N:INTEGER);,LABEL START;,VAR,K:INTEGER;,BEGIN,START:,K:=M+1;,M:=N+4;,N:=K;,END.,国防科技大学计算机系,602,教研室,PROCEDURE INCWAP(M,，,N:INTEGER);,LABEL START;,VAR,K:INTEGER;,BEGIN,START:,K:=M+1;,M:=N+4;,N:=K;,END.,国防科技大学计算机系,602,教研室,PROCEDURE INCWAP(M,，,N:INTEGER);,LABEL START;,VAR,K:INTEGER;,BEGIN,START:,K:=M+1;,M:=N+4;,N:=K;,END.,国防科技大学计算机系,602,教研室,PROCEDURE INCWAP(M,，,N:INTEGER);,LABEL START;,VAR,K:INTEGER;,BEGIN,START:,K:=M+1;,M:=N+4;,N:=K;,END.,国防科技大学计算机系,602,教研室,PROCEDURE INCWAP(M,，,N:INTEGER);,LABEL START;,VAR,K:INTEGER;,BEGIN,START:,K:=M+1;,M:=N+4;,N:=K;,END.,国防科技大学计算机系,602,教研室,国防科技大学计算机系,602,教研室,PROCEDURE INCWAP(M,，,N:INTEGER);,LABEL START;,VAR,K:INTEGER;,BEGIN,START:,K:=M+1;,M:=N+4;,N:=K;,END.,国防科技大学计算机系,602,教研室,8,.,2,整理和查找,1.,线性查找,按关键字出现的顺序填写各项。,填表快，查找慢。,结构简单，节省空间，效率低，查找时间,复杂度,：,O,(n)。,改进：,自适应线性表,国防科技大学计算机系,602,教研室,2.,二分查找,表格中的项按名字的“大小”顺序整理排列。,填表慢,查找快。查找时间,复杂度,:,O(Log,2,n),改进：组织成二叉树。,3. 杂凑查找(,HASH,技术),杂凑函数,H(SYM)：0N-1,N：,符号表的项数。,要求：1. 计算简单高效,2. 函数值分布均匀,填表快，查找快,国防科技大学计算机系,602,教研室,8,.,4,符号表的内容,符号表的信息栏中登记了每个名字的有关性质,类型：整、实或布尔等,种属：简单变量、数组、过程等,大小：长度，即所需的存储单元字数,相对数：指分配给该名字的存储单元的相对地址,国防科技大学计算机系,602,教研室,PL,语言编译程序的符号表,1. 表格的定义,名字表(,nametab,),程序体表(,btab,),层次显示表(,display),数组信息表(,atab,),中间代码表(,code),国防科技大学计算机系,602,教研室,1),名字表(,nametab,),名字表,nametab,：,登记程序中出现的各种名字及其属性,名字标识符,名字种类，可以是常量,(constant),、变量,(variable),、类型,(type),、过程,(procedure),名字所在的程序体的静态层次。规定主程序的层次为,1,，主程序中定义的层次为,2,，依次类推,名字的类型，类型有整型,(ints),、字符型,(chars),、布尔型,(bool),、数组,(arrays),，对于无类型的名字填入,notype,一个布尔量，用于标明名字是否为变量形参名，当名字是否为变量形参名时填入,false,，其他情况填入,true,或不填,当名字为数组类型或数组变量名时，,ref,指向该数组在数组信息表中的位置；当名字为过程名时，,ref,指向该过程在程序体表,(btab),中的位置；其他情况,ref,为,0,adr,当名字为变量名时,(,包括形参，存入该变量,(,或形参,),在相应活动记录中分类的存贮单元的相对地址；对于过程名，填入他们相应代码的入口地址,val,当名字为变量名时，填入他们的相应值,size,当名字为类型名时，填入该类型数据所需存贮单元的数目,指向同一程序体中定义的上一个名字在,nametab,中的位置，每个程序体在,nametab,中登记的第一个名字的,link,为,0,国防科技大学计算机系,602,教研室,(2) 程序体表,btab,和层次显示表,display,程序体表,btab,：,记录个程序体的总信息，用于对源程序中定义的名字的作用域进行分析；对名字表进行管理,指向本程序体中最后一个形式参在,nametab,中的位置,指向本程序体中最后一个名字在,nametab,中的位置,本程序体所有形参所需体积、包括连接数据所占空间,本程序体所有局部数据所需空间大小,国防科技大学计算机系,602,教研室,层次显示表,display：,描述正在处理的各嵌套层，对程序体表进行管理,btab,国防科技大学计算机系,602,教研室,(3),数组信息表,atab,数组的下标类型,数组元素类型,当元素为数组时，它指向该元素数组信息在,atab,表中的位置，其他情况为,0,数组下限,数组上限,数组元素的体积,数组本身的体积,国防科技大学计算机系,602,教研室,type a=array1.10, 1.10 of integer;,nametab,atab,国防科技大学计算机系,602,教研室,(4) 中间代码表,code,code：,用于存放编译程序所产生的每条中间代码。,国防科技大学计算机系,602,教研室,8,.,3,名字的作用,范围,在许多程序语言中,名字都有一个确定的作用范围.,两种程序体结构:,并列结构，如,FORTRAN,嵌套结构，如,PASCAL，ADA,国防科技大学计算机系,602,教研室,PROGRAM MAIN,integer X，Y,COMMON /C/A，B,END,SUBROUTINE SUB1,real X，Z,COMMON /C/A1，B1,END,国防科技大学计算机系,602,教研室,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.,国防科技大学计算机系,602,教研室,1,.,FORTRAN,的符号表组织,一个,FORTRAN,程序由一个主程序段和若干个辅程序段组成,.,把局部名和全局名分别存在不同的地方,.,2.,嵌套结构语言的符号表组织,如,PASCAL、ALGOL、ADA,作用域遵循最近嵌套原则,.,国防科技大学计算机系,602,教研室,PASCAL,PASCAL,程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。,一个,PASCAL,过程：,过程头；,说明段（由一系列的说明语句组成）；,begin,执行体（由一系列的执行语句组成）；,end,国防科技大学计算机系,602,教研室,作用域,：一个名字能被使用的区域范围称作这个名字的作用域。,允许同一个标识符在不同的过程中代表不同的名字。,名字作用域规则,-,最近嵌套原则,一个在子程序,B1,中说明的名字,X,只在,B1,中有效（局部于,B1,）；,如果,B2,是,B1,的一个内层子程序且,B2,中对标识符,X,没有新的说明，则原来的名字,X,在,B2,中仍然有效。如果,B2,对,X,重新作了说明，那么，,B2,对,X,的任何引用都是指重新说明过的这个,X,。,国防科技大学计算机系,602,教研室,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,),国防科技大学计算机系,602,教研室,两种做法:,引入,过程编号,属性,。,查找时，先查找本过程编号的名字，查不到则查找外层过程编号的名字，等等.,按栈式思想组织符号表。查找时，从后往前查找，碰到的第一个名字就是所需查找的名字.,国防科技大学计算机系,602,教研室,PL,语言的中间代码,指令格式：,opcod,l a,opcod,：操作码,l,：第一操作数，程序体层数,a,：第一操作数，相对地址,编译是如何确定变量的层数,(,地址,),？,运行是如何根据指令中变量的层数和相对地址确定变量的存储单元？,国防科技大学计算机系,602,教研室,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.,国防科技大学计算机系,602,教研室,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.,国防科技大学计算机系,602,教研室,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.,function,position(id:alfa):integer,;,var,i,j:integer,;,begin,nametab0.name:=id; j:=level;,repeat,i:=,btab,displayj,.last;,while,nametabi.name,id do,i:=,nametabi.link,;,j:=j-1,until (j0);,if (i=0) then error(10);,position:=i,end; position ,b1,:=,a,+ b,国防科技大学计算机系,602,教研室,PL,语言的中间代码,指令格式：,opcod,l a,Opcod,：操作码,l,：第一操作数，程序体层数,a,：第一操作数，相对地址,编译是如何确定变量的层数,(,地址,),？,运行时如何根据指令中变量的层数和相对地址确定变量的存储单元？,国防科技大学计算机系,602,教研室,