符号表的作用ppt课件Chapt8符合表.ppt

国防科技大学计算机系602教研室第八章 符号表符号表•符号表的作用符号表的作用: :–一致性一致性检查和作用域分析和作用域分析; ;–辅助代助代码生成生成. .国防科技大学计算机系602教研室8.1 8.1 符号表的组织与作用•符号表的每一符号表的每一项( (入口入口) )包含两大包含两大栏: :–名字名字栏，也称主，也称主栏，关，关键字字栏–信息信息栏，，记录相相应的不同属性，分的不同属性，分为若干子若干子栏. .•对对符号表的操作符号表的操作: :–填入名称填入名称–查查找名字找名字–访问访问信息信息–填写修改信息填写修改信息–删删除除国防科技大学计算机系602教研室•对对符号表符号表进进行操作的行操作的时时机：机：–定定义义性出性出现现–使用性出使用性出现现•按名字的不同种属建立多按名字的不同种属建立多张张符号表，如常数表、符号表，如常数表、变变量名表、量名表、过过程名表、程名表、…•符号的符号的组织组织方式方式: :1. 1. 安排各安排各项项各各栏栏的存的存储单储单元元为为固定固定长长度度2. 2. 用用间间接方式安排各接方式安排各栏栏存存储单储单元元国防科技大学计算机系602教研室•符号表的存放次序符号表的存放次序: :1. 1. 把每一把每一项项置于置于连续连续K存存储单储单元中，构成一元中，构成一张张K*N的表的表2. 把整个符号表分成把整个符号表分成m个子表，如个子表，如T1,T2,…Tm，每个子表含有，每个子表含有N项项.国防科技大学计算机系602教研室例: : PASCALPASCAL程序段：PROCEDURE INCWAP(MPROCEDURE INCWAP(M，，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.国防科技大学计算机系602教研室PROCEDURE INCWAP(MPROCEDURE INCWAP(M，，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.国防科技大学计算机系602教研室PROCEDURE INCWAP(MPROCEDURE INCWAP(M，，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.国防科技大学计算机系602教研室PROCEDURE INCWAP(MPROCEDURE INCWAP(M，，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.国防科技大学计算机系602教研室PROCEDURE INCWAP(MPROCEDURE INCWAP(M，，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.国防科技大学计算机系602教研室国防科技大学计算机系602教研室PROCEDURE INCWAP(MPROCEDURE INCWAP(M，，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.国防科技大学计算机系602教研室8.2 8.2 整理和查找1. 线线性性查查找找•按关按关键键字出字出现现的的顺顺序填写各序填写各项项。

•填表快，填表快，查查找慢•结结构构简单简单，，节节省空省空间间，效率低，，效率低，查查找找时间时间复复杂度度：：O(n)(n)•改改进进：：自适自适应线性表性表国防科技大学计算机系602教研室2. 二分二分查查找找•表格中的表格中的项项按名字的按名字的“大小大小”顺顺序整理排列序整理排列•填表慢填表慢, ,查查找快查查找找时间时间复复杂度度: :O(Log2n)•改改进进：：组织组织成二叉成二叉树树3. 3. 杂杂凑凑查查找找( (HASHHASH技技术术) )•杂杂凑函数凑函数H(SYM)：：0~N-1 N：：符号表的符号表的项数•要求：要求：1. 计算算简单高效高效 2. 函数函数值分布均匀分布均匀•填表快，填表快，查查找快找快国防科技大学计算机系602教研室8.4 8.4 符号表的内容n符号表的信息栏中登记了每个名字的有关符号表的信息栏中登记了每个名字的有关性质性质 Ø类型：整、实或布尔等类型：整、实或布尔等Ø种属：简单变量、数组、过程等种属：简单变量、数组、过程等Ø大小：长度，即所需的存储单元字数大小：长度，即所需的存储单元字数Ø相对数：指分配给该名字的存储单元的相对数：指分配给该名字的存储单元的相对地址相对地址国防科技大学计算机系602教研室PL￿语言编译程序的符号表1. 表格的定义表格的定义n名字表名字表(nametab)n程序体表程序体表(btab)n层次显示表层次显示表(display)n数组信息表数组信息表(atab)n中间代码表中间代码表(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=array[1..10, 1..10] of integer;nametabatab国防科技大学计算机系602教研室(4) 中间代码表中间代码表codecode：：用于存放编译程序所产生的每条中间用于存放编译程序所产生的每条中间代码。

代码国防科技大学计算机系602教研室8.3 8.3 名字的作用范围•在在许许多程序多程序语语言中言中, ,名字都有一个确定的作用范名字都有一个确定的作用范围围. .•两种程序体两种程序体结结构构: :–并列并列结结构，如构，如FORTRANFORTRAN–嵌套嵌套结结构，如构，如PASCALPASCAL，，ADAADA国防科技大学计算机系602教研室PROGRAM MAIN …integer X，，YCOMMON /C/A，，B …ENDSUBROUTINE SUB1 …real X，，ZCOMMON /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. FORTRANFORTRAN的符号表的符号表组织组织•一个一个FORTRANFORTRAN程序由一个主程序段和若干程序由一个主程序段和若干个个辅辅程序段程序段组组成成.•把局部名和全局名分把局部名和全局名分别别存在不同的地方存在不同的地方.2. 嵌套嵌套结结构构语语言的符号表言的符号表组织组织•如如PASCALPASCAL、、ALGOLALGOL、、ADAADA作用域遵循作用域遵循" "最近最近嵌套原嵌套原则则" ".国防科技大学计算机系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 … endbegin …endA(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 nametab[0].name:=id; j:=level; repeat i:=btab[ display[j] ].last; while nametab[i].name<>id do i:=nametab[i].link; j:=j-1 until (j<0) or (i<>0); if (i=0) then error(10); position:=i end; { position }b1 := a + b国防科技大学计算机系602教研室PL语言的中间代码•指令格式：指令格式： opcod l a–Opcod：操作：操作码–l：第一操作数，程序体：第一操作数，程序体层数数–a：第一操作数，相：第一操作数，相对地址地址•编译是如何确定是如何确定变量的量的层数数(地址地址)？？•运行运行时如何根据指令中如何根据指令中变量的量的层数和相数和相对地址确定地址确定变量的存量的存储单元？元？。