1、第八章第八章 符号表符号表n符号表的组织与作用符号表的组织与作用n整理和查找整理和查找n符号表的内容符号表的内容n名字的作用范围名字的作用范围第八章第八章 符号表符号表n符号表的作用符号表的作用: :一致性检查和作用域分析一致性检查和作用域分析; ;辅助代码生成辅助代码生成. .名字栏（名字栏（Name）信息栏（信息栏（Information） 第一项第一项（入口（入口1）第二项第二项（入口（入口2）第第n项项（入口（入口n）8.1 8.1 符号表的组织与作用符号表的组织与作用n符号表符号表的每一项的每一项( (入口入口) )包含包含两大栏两大栏: :名字栏名字栏，也称主栏，关键字栏，也称主栏
2、，关键字栏信息栏信息栏，记录相应的不同属性，分为，记录相应的不同属性，分为若干子栏若干子栏. .8.1 8.1 符号表的组织与作用符号表的组织与作用n对符号表的操作对符号表的操作: :填入名称填入名称查找名字查找名字访问信息访问信息填写修改信息填写修改信息删除删除n对符号表进行操作的时机：对符号表进行操作的时机：定义性出现定义性出现 int xint x；使用性出现使用性出现 if x100if x100n按按名字的不同种属名字的不同种属建立建立多张符号表多张符号表，如常，如常数表、变量名表、过程名表、数表、变量名表、过程名表、n符号表的组织方式符号表的组织方式: :1. 1. 安排各项各栏的
3、存储单元为固定长度安排各项各栏的存储单元为固定长度2. 2. 用间接方式安排各栏存储单元用间接方式安排各栏存储单元8.1 8.1 符号表的组织与作用符号表的组织与作用poolelpmasNAMEINFORMATION , 6 , 4pool4elpmas6NAMEINFORMATION符符号号表表的的结结构构 用间接方式安排各栏存储单元用间接方式安排各栏存储单元维数维数首地址首地址界差界差d1 界差界差dn上界上界I1 上界上界In下界下界U1 下界下界Un内情向量表内情向量表 NAMEINFORMATIONCAT地址地址a符号表符号表用用间间接接方方式式安安排排各各栏栏存存储储单单元元n符号
4、表的存放次序符号表的存放次序: :一一张可容纳张可容纳N N项的符号表在存储器中可用下述两项的符号表在存储器中可用下述两种不同的方式之一表示（假定每项需用种不同的方式之一表示（假定每项需用K K个字）个字）1. 把每一项置于连续把每一项置于连续K存储单元中，构成一张存储单元中，构成一张K*N的表的表2. 把整个符号表分成把整个符号表分成m个子表，如个子表，如T1,T2,Tm，每个子表含有每个子表含有N项项.8.1 8.1 符号表的组织与作用符号表的组织与作用 T1 T2 T3 T4N1N2N3K1K2K3K4K=K1+K2+K3+K4例例: : PASCALPASCAL程序段：程序段：PROC
5、EDURE 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.PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEG
6、INSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.表 0.1 符号名表 SNTNAME INFORMATIONM形式参数，整型，值参数N形式参数，整型，值参数K整型，变量表 0.2 常数表 CT值(VALUE)(1)1(2)4PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M
7、+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END. 表 0.5 四元式表 QTOPROPN1OPN2RESULT(1)link(2)parINCWAP1M(3)parINCWAP2N(4)+M1K(5)+N4M(6):=KN(7) returnPROCEDURE 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
8、; N:=K; N:=K;END.END.表 0.3 入口名表 ENT NAME INFORMATION (1) INCWAP 二目子程序,入口四元式:1 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. 表 0.5 四元式表 QTOPROPN1OPN2RESULT(1)lin
9、k(2)parINCWAP1M(3)parINCWAP2N(4)+M1K(5)+N4M(6):=KN(7) return 表 0.4 标号表 LTNAME INFORMATION(1)START 四元式:(4)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. 表 0.5 四元式
10、表 QTOPROPN1OPN2RESULT(1)link(2)parINCWAP1M(3)parINCWAP2N(4)+M1K(5)+N4M(6):=KN(7) return第八章第八章 符号表符号表n符号表的组织与作用符号表的组织与作用n整理和查找整理和查找n符号表的内容符号表的内容n名字的作用范围名字的作用范围8 8. .2 2 整理和查找整理和查找1. 线性查找线性查找2. 二分查找二分查找3.杂凑查找杂凑查找( (HASHHASH技术技术) )8 8. .2 2 整理和查找整理和查找1. 线性查找线性查找n按按关键字出现的顺序关键字出现的顺序填写各项。填写各项。p填表快，查找慢。填表快
11、，查找慢。p结构简单，节省空间，效率低，查找时间结构简单，节省空间，效率低，查找时间复杂复杂度度：O(n)(n)。n改进：改进：自适应线性表：自适应线性表：给每一项附设一个指示器，这给每一项附设一个指示器，这些指示器把所有的项按些指示器把所有的项按“最新最近最新最近”访问原则连接成一条访问原则连接成一条链，这条链的链，这条链的第一个第一个元素所指的项是元素所指的项是最新最近最新最近被查询过的被查询过的项，项，第二个第二个元素所指的项是元素所指的项是次新近次新近被查询过的项，诸如此被查询过的项，诸如此类。每当填入新项时，总让链头指向最新类。每当填入新项时，总让链头指向最新项。项。2. 二分查找二
12、分查找n表格中的项按名字的表格中的项按名字的“大小大小”顺序整理排列。顺序整理排列。p填表慢填表慢, ,查找快。查找快。p查找时间查找时间复杂度复杂度: :O(Log2n)n改进：组织成二叉树。改进：组织成二叉树。3. 3. 杂凑查找杂凑查找( (HASHHASH技术技术) )n杂凑函数杂凑函数H(SYM)：0N-1 N：符号表的项数。符号表的项数。n要求：要求：1. 函数计算简单高效函数计算简单高效 2. 函数值分布均匀函数值分布均匀n填表快，查找快填表快，查找快杂凑技术杂凑技术( (HASHHASH技术技术) )n杂凑技术使用杂凑技术使用一张杂凑链表一张杂凑链表通过通过间接方式查填间接方式
13、查填符符号表，常常把所有相同杂凑值得符号名连成一串号表，常常把所有相同杂凑值得符号名连成一串，便于线性查找。，便于线性查找。n杂凑表是一个可容纳杂凑表是一个可容纳N个指针的一维数组，它的个指针的一维数组，它的每个元素的初值全为每个元素的初值全为null。n符号表除了通常包含的栏外还增设一符号表除了通常包含的栏外还增设一链接栏链接栏，它，它把所有持相同杂凑值的符号名连接成一条链把所有持相同杂凑值的符号名连接成一条链n 填入一个新的填入一个新的SYM的过程：的过程： （1）先计算出）先计算出H(SYM)的值的值h（在（在0与与N-1之间），将之间），将HASHTABLEh的值赋给的值赋给P（若未曾
14、有杂凑值为（若未曾有杂凑值为h的项名填的项名填入过，则将入过，则将P置空）。置空）。（2）然后置）然后置HASHTABLEh=available，再把新名，再把新名SYM及及其链接指示其链接指示 器器LINK的值的值P填进指针填进指针available所指向的符号表所指向的符号表位置。位置。 n 使用此方法的查表过程如下：使用此方法的查表过程如下： 首先计算出此项的函数首先计算出此项的函数H的值等于的值等于h，然后就指示器，然后就指示器 HASHTABLEh所指的项链逐一按序查找（线性查找）所指的项链逐一按序查找（线性查找）杂凑技术杂凑技术( (HASHHASH技术技术) )available
15、SYM1H（SYM1）=hp=HASHTABLEh=nullHASHTABLEh=AVAVILABLE=n1SYM1null 01hN-1杂凑表杂凑表符号表符号表 LinkInformationName n1n2n3n1nullavailableSYM2H（SYM2）=hp=HASHTABLEh= n1HASHTABLEh=AVAVILABLE=n2n2SYM2n1SYM3H（SYM3）=hp=HASHTABLEh= n2HASHTABLEh=AVAVILABLE=n3n3SYM3n2availableavailable第八章第八章 符号表符号表n符号表的组织与作用符号表的组织与作用n整理和查
16、找整理和查找n符号表的内容符号表的内容n名字的作用范围名字的作用范围8 8. .4 4 符号表的内容符号表的内容n对于变量名、数组名和过程名，它们的信对于变量名、数组名和过程名，它们的信息栏中一般要求有下列信息：息栏中一般要求有下列信息：n1.变量变量类型：类型：整、实或布尔等；整、实或布尔等；种属：种属：简单变量、数组、过程等；简单变量、数组、过程等；大小：大小：长度，即所需的存储单元字数长度，即所需的存储单元字数；相对数：相对数：指分配给该名字的存储单元指分配给该名字的存储单元的相对地址；的相对地址；若为若为数组数组，则记录其内情向量；，则记录其内情向量；形式参数形式参数标志；标志；是否对
17、这个变量进行过赋值是否对这个变量进行过赋值的标志位的标志位。8 8. .4 4 符号表的内容符号表的内容n2.过程过程是否为程序的外部过程？是否为程序的外部过程？若为函数，类型是什么？若为函数，类型是什么？其说明是否处理过？其说明是否处理过？是否递归？是否递归？形式参数是些什么？形式参数是些什么？为了与实在参数为了与实在参数进行比较，进行比较， 必须把它们的种属、类型必须把它们的种属、类型信息同过程名联系在一起。信息同过程名联系在一起。第八章第八章 符号表符号表n符号表的组织与作用符号表的组织与作用n整理和查找整理和查找n符号表的内容符号表的内容n名字的作用范围名字的作用范围8 8. .3 3
18、 名字的作用名字的作用范围范围n在许多程序语言中在许多程序语言中, ,名字都有一个确定的作名字都有一个确定的作用范围用范围. .n作用域作用域：一个名字能被使用的区域范围称：一个名字能被使用的区域范围称作这个名字的作用域。作这个名字的作用域。n两种程序体结构两种程序体结构: :并列结构，如并列结构，如FORTRANFORTRAN嵌套结构，如嵌套结构，如PASCALPASCAL，ADAADAPROGRAM MAIN integer X，YCOMMON /C/A，B ENDSUBROUTINE SUB1 real X，ZCOMMON /C/A1，B1 ENDprogram P; var a,b :
19、 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.n一个一个FORTRANFORTRAN程序由一个主程序段和若干个辅程程序由一个主程序段和若干个辅程序段组成序段组成.n变量、数组和语句函数名的作用范围就是它们变量、数组和语句函数名的作用范围就是它们所处的那个程序段。所处的那个程序段。n对于一遍扫描的编译程序，可以逐段产生其目
20、对于一遍扫描的编译程序，可以逐段产生其目标代码。当一程序段处理完后，它的所有的局标代码。当一程序段处理完后，它的所有的局部名均无需保存在符号表中，需要继续留在符部名均无需保存在符号表中，需要继续留在符号表总的只是全局名。号表总的只是全局名。n把把局部名局部名和和全局名全局名分别存在不同的地方分别存在不同的地方.nPASCALPASCAL程序本身可以看成是一个操作系程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。统所调用的过程，过程可以嵌套和递归。一个一个PASCAL过程：过程：过程头；过程头；说明段（由一系列的说明语句组成）；说明段（由一系列的说明语句组成）；begin执行体（
21、由一系列的执行语句组成）；执行体（由一系列的执行语句组成）；endn如如PASCALPASCAL、ALGOLALGOL、ADAADA作用域遵循作用域遵循 最近最近嵌套原则嵌套原则 .允许同一个标识符在不同的过程中代表允许同一个标识符在不同的过程中代表不同的名字。不同的名字。名字作用域规则名字作用域规则- 最近嵌套原则最近嵌套原则 n一个在子程序一个在子程序B1中说明的名字中说明的名字X只在只在B1中中有效（局部于有效（局部于B1）；）；n如果如果B2是是B1的一个内层子程序且的一个内层子程序且B2中对中对标识符标识符X没有新的说明，则原来的名字没有新的说明，则原来的名字X在在B2中仍然有效。如
22、果中仍然有效。如果B2对对X重新作了说明，重新作了说明，那么，那么，B2对对X的任何引用都是指重新说明的任何引用都是指重新说明过的这个过的这个X。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)两种做法两种做法: :引入引入 过程编号过程编号 属性属性。查找时，先查找本查找时，先查找本过程编号的名字，查不到则查找外层过程过程编号的名字，查不到则查找外层过程编
23、号的名字，编号的名字，等等，等等. .按按 栈栈 式思想组织符号表式思想组织符号表。查找时，从后。查找时，从后往前查找，碰到的第一个名字就是所需查往前查找，碰到的第一个名字就是所需查找的名字找的名字. .名字作用域分析（名字作用域分析（嵌套结构语言嵌套结构语言） 对每个过程指定一个唯一的对每个过程指定一个唯一的编号（层次）编号（层次），即，即过过程的顺序号程的顺序号，以便跟踪过程里的局部名字。，以便跟踪过程里的局部名字。 在符号表中，表示在符号表中，表示局部名字用一个二元组：局部名字用一个二元组： 对一个名字查找符号表的原则对一个名字查找符号表的原则: 只有当表项中的只有当表项中的名字的名字的
24、字符逐个匹配字符逐个匹配,并且该记录相关的编号和并且该记录相关的编号和当前所处理的过程的当前所处理的过程的编号匹配编号匹配时时,才能确定查找才能确定查找成功成功.引入引入 过程编号过程编号 属性属性（1） 将符号表设计为将符号表设计为栈符号表栈符号表，新名字出现总是从栈顶填入。为，新名字出现总是从栈顶填入。为了保证从内层向外层查，查找操作从符号表的了保证从内层向外层查，查找操作从符号表的栈顶栈顶往底部查找。往底部查找。（2）过程的嵌套层次表过程的嵌套层次表（display），是引入的一个显示层次关系），是引入的一个显示层次关系表表。其作用是为了描述过程的嵌套层次，指出当前正在活动着的各。其作用
25、是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（相对地址）。相对地址）。 Display表也是一个栈，栈顶为表也是一个栈，栈顶为level，用来指示层次，用来指示层次，即指向当前的最内层过程的，即指向当前的最内层过程的子符号表子符号表在在栈符号表栈符号表中的起始位置。中的起始位置。（3）在在符号表的信息栏符号表的信息栏中引入一个中引入一个指针域指针域（previous)，用来链接，用来链接它在同一个过程内的下一名字在表中的下标（相对位置）。每一层它在同一个过程内的下一名字在表中的
26、下标（相对位置）。每一层最后一个域名字，指针域之值为最后一个域名字，指针域之值为0。这样每当需要查找个新名字时。这样每当需要查找个新名字时，就能通过，就能通过display表表找出当前正在处理的最内层的过程及所有外找出当前正在处理的最内层的过程及所有外层的子符号表在层的子符号表在栈符号表栈符号表中的位置。然后通过指针域可以找到同一中的位置。然后通过指针域可以找到同一个过程内的所有被说明的名字。个过程内的所有被说明的名字。按按 栈栈 式思想组织符号表式思想组织符号表 例：例： procedure/B1 var a,b:real; procedure/B2 var c,d:real; proced
27、ure/B3 var e,f:real; begin end; begin end; begin end; PreviousInformation Name1110987654321栈符号表栈符号表DISPLAYabtopsp1levellevel20B2cdtopsp4level3050B3eftopsp7level6080procedure/B1 var a,b:real; procedure/B2 var c,d:real; procedure/B3 var e,f:real; 练习：练习： procedure B1(input ,output) const a=10; var b,c:integer; e:real; procedure B2(x,real); var f,g:real; procedure B3(y,real); const b=5; var h:boolean; begin end; begin end; begin end;
