编译原理陈火旺版8章8

1、第八章 符号表 8.1符号表的组织与作用符号表的组织与作用一、符号表的作用一、符号表的作用 一张符号表的每一项包含两大栏一张符号表的每一项包含两大栏,即即名字栏名字栏和和信息栏信息栏。表格形式如下所示：表格形式如下所示： 名字栏（Name）信息栏（Information） 第一项（入口1）第二项（入口2）第n项（入口n） 名字栏名字栏用来存放标识符或其内部码；用来存放标识符或其内部码；信息栏信息栏包含许多子包含许多子栏和标志位，用来记录与该项名字相对应的种种不同属性。栏和标志位，用来记录与该项名字相对应的种种不同属性。 （5）从表中删除一个或一组名字。）从表中删除一个或一组名字。在整个编译期间

2、，对于符号表的访问可概括为如下几类操作：在整个编译期间，对于符号表的访问可概括为如下几类操作：（1）对给定名字，查询此名是否已在表中；）对给定名字，查询此名是否已在表中；（2）往表中填入一个新名字；）往表中填入一个新名字；（3）对给定名字，访问它的相关信息；）对给定名字，访问它的相关信息；（4）对给定名字，往表中填写或更新它的某些信息）对给定名字，往表中填写或更新它的某些信息;二、符号表的组织方式二、符号表的组织方式 1、各项各栏所占存储单元的长度固定、各项各栏所占存储单元的长度固定 2、间接方式安排名字栏、间接方式安排名字栏poolelpmasNAMEINFORMATION , 6 , 4p

3、ool4elpmas6NAMEINFORMATION如果各种名字所需的信息（如果各种名字所需的信息（INFORMATION ）空间长短不一，）空间长短不一，那么，我们可把一些那么，我们可把一些共同属性共同属性直接登记在直接登记在符号表的信息栏符号表的信息栏中，中，而把某些而把某些特殊属性特殊属性登记在登记在别的地方别的地方，并在信息栏中附设一指示并在信息栏中附设一指示器，指向存放特殊属性的地方。器，指向存放特殊属性的地方。例如：对于数组标识符例如：对于数组标识符专门开辟一个信息表区，即为专门开辟一个信息表区，即为数组信息表数组信息表也称为也称为内情向量表内情向量表维数维数首地址首地址界差界差d

4、1 界差界差dn上界上界I1 上界上界In下界下界U1 下界下界Un内情向量表内情向量表在符号表的地址栏中存入符号在符号表的地址栏中存入符号表与内情向量表连接入口地址表与内情向量表连接入口地址 NAMEINFORMATIONCAT地址地址a符号表符号表 （1）把每一项置于连续的把每一项置于连续的K个存储单元中，从而给出一个存储单元中，从而给出一 张张K*N个存储单元的表。个存储单元的表。 （2） 把整个符号表分成把整个符号表分成M个子表，每个子表含个子表，每个子表含N项。假项。假定子表定子表Ti的每一项所需的字数为的每一项所需的字数为Ki，那么，那么，K=K1+Km。对于任何对于任何i,T1i

5、,Tmi的并置就构成符号表第的并置就构成符号表第i项的全部项的全部内容。内容。一张可容纳一张可容纳N项项的符号表在存储器中的的符号表在存储器中的两种两种表示方式：表示方式： T1 T2 T3 T4N1N2N3K1K2K3K4K=K1+K2+K3+K4例8.1 FORTRAN符号表程序段： SUBROUTINE INCWAP(M,N)10 K=M+1 M=M+4 N=K RETURN END主要表格见p2258.2 整理与查找整理与查找 一、线性表一、线性表 2、提高查找效率的办法：给每一项附设一个指示器，这些指示器、提高查找效率的办法：给每一项附设一个指示器，这些指示器把所有的项按把所有的项按

6、“最新最近最新最近”访问原则连接成一条链，这条链的访问原则连接成一条链，这条链的第一第一个个元素所指的项是元素所指的项是最新最近最新最近被查询过的项，被查询过的项，第二个第二个元素所指的项是元素所指的项是次新近次新近被查询过的项，诸如此类。每当填入新项时，总让链头指向被查询过的项，诸如此类。每当填入新项时，总让链头指向最新项，含有这种链条的线性表叫做最新项，含有这种链条的线性表叫做自适应线性表自适应线性表。1、线性表介绍、线性表介绍符号表的三种构造法和处理法：符号表的三种构造法和处理法： 线性查找、线性查找、二叉树、二叉树、杂凑技术。杂凑技术。 BC I XYZ J1INFORMATIONNA

7、ME项数项数1234AVAILABLE线性符号表线性符号表平均查找次数平均查找次数n/2二、对折查找与二叉树二、对折查找与二叉树 （3）若要查找的项大于中项，则）若要查找的项大于中项，则 就到就到n/2+2n的各项中去查找。的各项中去查找。在造表的同时把表格中的项按名字的在造表的同时把表格中的项按名字的“大小大小”顺序整理排列。顺序整理排列。所谓所谓名字的名字的“大小大小”通常是通常是指名字的内码二进制。指名字的内码二进制。对于经对于经顺序化顺序化的表格的查找可用的表格的查找可用对折法。对折法。对折法的对折法的查找方法查找方法如下：如下：（1）首先把要查找的项和中项）首先把要查找的项和中项（即

8、第（即第n/2+1项）作比较，若项）作比较，若 相等，则宣布查找成功。相等，则宣布查找成功。（2）若要查找的项小于中项，）若要查找的项小于中项，则继续在则继续在1n/2的各项中去查找。的各项中去查找。顺序化的线性符号表顺序化的线性符号表 XYZ J1 I BCINFORMATIONNAME项数项数1234AVAILABLE查找次数不超过查找次数不超过1+log2n 二叉树的形成过程如下二叉树的形成过程如下：令第一个碰到的名字作为令第一个碰到的名字作为“根根”结点，它结点，它 的左、右指示器均置为空，的左、右指示器均置为空，当要加入新结点时，首先把它和根结点的值作比较，小者放在右枝当要加入新结点

9、时，首先把它和根结点的值作比较，小者放在右枝上，大者放在左枝上。如果根结点的左（右）上，大者放在左枝上。如果根结点的左（右） 枝已成子树，则让新枝已成子树，则让新结点和子树的根再作比较。重复上述步结点和子树的根再作比较。重复上述步 骤，直至把新结点插入使它骤，直至把新结点插入使它成为二叉树成为二叉树 的一个端末结点（叶）为止。的一个端末结点（叶）为止。把符号表组织成一棵把符号表组织成一棵二叉树二叉树(二叉排序树二叉排序树）令每项是一个结点，每个结点附设令每项是一个结点，每个结点附设两个指示器栏两个指示器栏，一栏为，一栏为LEFT（左枝），令一栏为（左枝），令一栏为RIGHT（右枝）。每个结点的

10、主栏内码值被（右枝）。每个结点的主栏内码值被看成是代表该结点的值。看成是代表该结点的值。要求：要求：任何结点任何结点P右枝右枝的所有结点值均应的所有结点值均应小于小于结点结点P的值的值，而，而左枝左枝的任何结点值均应的任何结点值均应大于大于结点结点P的值的值。 I BC XYZ J1INFORMATIONNAME项数项数1234AVAILABLEJ1根LEFTRIGHT00 0XYZ00BC00I0三、杂凑技术三、杂凑技术 1、假定有一个足够大的区域，这个区域用来填写一张含、假定有一个足够大的区域，这个区域用来填写一张含N项的符号项的符号表。构造一个表。构造一个地址函数地址函数H，对任何名字，

11、对任何名字，H函数的取值于函数的取值于0至至N-1之间之间。即不论对此项查表或填表，都能从即不论对此项查表或填表，都能从H函数中获得它在表中的位置。函数中获得它在表中的位置。 2、对地址函数、对地址函数H有有两点要求两点要求：（1）函数的计算要简单、高效；）函数的计算要简单、高效；（2）函数值能比较均匀的分布在）函数值能比较均匀的分布在0至至N-1之间。之间。3、构造函数、构造函数H的办法：的办法：直接地址法、数字分析法、平方取中法、直接地址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法折叠法、除留余数法、随机数法4、解决地址冲突的办法：、解决地址冲突的办法： 开放地址法、再哈希法、

12、链地址法、开放地址法、再哈希法、链地址法、建立一个公共溢出区建立一个公共溢出区 3、填入一个新的项的过程：、填入一个新的项的过程： （1）先计算出）先计算出H函数的值函数的值h（在（在0与与N-1之间），将之间），将HASHTABLEh 的值赋给的值赋给P（若未曾有杂凑值为（若未曾有杂凑值为h的项名填入过，则将的项名填入过，则将P置空）。置空）。（2）然后将）然后将HASHTABLEh置为置为AVAILABLE，再把新名及其链，再把新名及其链接指示接指示 器的值器的值P填进指针所指向的符号表位置。填进指针所指向的符号表位置。 4、使用此方法的查表过程如下：、使用此方法的查表过程如下： 首先计算

13、出此项的函数首先计算出此项的函数H的值等于的值等于h，然后就指示器，然后就指示器 HASHTABLEh所指的项链逐一按序查找（线性查找）所指的项链逐一按序查找（线性查找）杂凑技术：使用一张杂凑链表通过间接方式查添符号表。杂凑技术：使用一张杂凑链表通过间接方式查添符号表。将具有相同杂凑值符号名连成一串，便于线性查找。杂凑表是一将具有相同杂凑值符号名连成一串，便于线性查找。杂凑表是一个可容纳个可容纳N个指示器值的一维数组，它的每个元素的初值全为个指示器值的一维数组，它的每个元素的初值全为null。符号表除了通常包含的栏外，还增设了一链接栏，他符号表除了通常包含的栏外，还增设了一链接栏，他把所有持有

14、相把所有持有相同杂凑值的符号名连接成一条链同杂凑值的符号名连接成一条链。（见下页）。（见下页）availableSYM1H（SYM1）=hp=HASHTABLEh=nullHASHTABLEh=AVAVILABLE=n1SYM1null 01hN-1杂凑表杂凑表符号表符号表 LinkInformationName n1n2n3n1nullavailableSYM2H（SYM2）=hp=HASHTABLEh= n1HASHTABLEh=AVAVILABLE=n2n2SYM2n1SYM3H（SYM3）=hp=HASHTABLEh= n2HASHTABLEh=AVAVILABLE=n3n3SYM3n

15、2availableavailable8.3名字的作用范围名字的作用范围 对于对于过程嵌套结构型过程嵌套结构型的程序设计语言，的程序设计语言，每层过程中说明的名字每层过程中说明的名字只局限于该过程只局限于该过程，离开了所在的过程就无意义了。也就是说，离开了所在的过程就无意义了。也就是说， 同一个标识符，具有不同的性质，要求分配不同的存储空间。同一个标识符，具有不同的性质，要求分配不同的存储空间。这样，如何组织符号表，使得同一个标识符在不同的作用域中这样，如何组织符号表，使得同一个标识符在不同的作用域中能得到正确的引用，而不会产生混乱。能得到正确的引用，而不会产生混乱。通常实现通常实现最近嵌套作

16、用域规则最近嵌套作用域规则的办法是：对每个过程指定一个的办法是：对每个过程指定一个唯一的编号，即过程的顺序号，以便跟踪过程里的局部名字。唯一的编号，即过程的顺序号，以便跟踪过程里的局部名字。在符号表中，表示在符号表中，表示局部名字用一个二元组：局部名字用一个二元组：对一个名字查找符号表是对一个名字查找符号表是:只有当表项中的名字其字符逐个匹配只有当表项中的名字其字符逐个匹配,并且该记录相关的编号和当前所处理的过程的编号匹配时并且该记录相关的编号和当前所处理的过程的编号匹配时,才能才能确定查找成功确定查找成功.Pascal的符号表组织的符号表组织 1、在在Pascal程序中标识符的作用域是包含说

17、明该标识符的一个最程序中标识符的作用域是包含说明该标识符的一个最小分程序。具体的概括为如下几点：小分程序。具体的概括为如下几点：（1）如果一个标识符在某一分程序首部已作说明如果一个标识符在某一分程序首部已作说明，则不论此分程序，则不论此分程序是否含有内层分程序，也不论内分程序在嵌套多少层，只要在内是否含有内层分程序，也不论内分程序在嵌套多少层，只要在内层分程序未再次对该标识符加以说明，层分程序未再次对该标识符加以说明，则此标识符在整个分程序中则此标识符在整个分程序中均有定义，且有相同的属性均有定义，且有相同的属性。（2）程序中的）程序中的标号局限于定义该标号的最小分程序标号局限于定义该标号的最

18、小分程序。（3）由于）由于Pascal程序中的过程可具有嵌套的结构，因此，可将每程序中的过程可具有嵌套的结构，因此，可将每 一过程说明都假想为一个分程序。出现在过程体中的非形式一过程说明都假想为一个分程序。出现在过程体中的非形式 参数，参数，依其在相应的过程体中被说明与否，确定它们对过程而言是局部变依其在相应的过程体中被说明与否，确定它们对过程而言是局部变量还是非局部变量，量还是非局部变量，而形式参数则总是局限于相应而形式参数则总是局限于相应 的过程体的的过程体的。PASCAL程序中的标识符（或标号）的作用域，总是与说明（定义）程序中的标识符（或标号）的作用域，总是与说明（定义）这些标识符的分

19、程序的层次相联系的这些标识符的分程序的层次相联系的。参见P232（1） 针对符号表设计为针对符号表设计为栈符号表栈符号表，新名字出现总是从栈顶填入。，新名字出现总是从栈顶填入。为了保证从内层向外层查，查找操作从符号表的栈顶往底部查找。为了保证从内层向外层查，查找操作从符号表的栈顶往底部查找。2、对于嵌套结构型程序设计语言（、对于嵌套结构型程序设计语言（Pascal）的特点，可采用如下）的特点，可采用如下 办法办法：（2）过程的嵌套层次表（过程的嵌套层次表（display），是引入的一个显示层次关系），是引入的一个显示层次关系表表。其作用是为了描述过程的嵌套层次，指出当前正处理的各嵌套。其作用是

20、为了描述过程的嵌套层次，指出当前正处理的各嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（相对的过程（或函数）相应的子符号表在栈符号表中的起始位置（相对地址）。地址）。（3）在信息栏中引入一个指针域（在信息栏中引入一个指针域（previous)，用来链接它在同一，用来链接它在同一个过程内的下一名字在表中的下标（相对位置）。每一层最后一个个过程内的下一名字在表中的下标（相对位置）。每一层最后一个域名字，指针域之值为域名字，指针域之值为0。这样每当需要查找个新名字时，就能通。这样每当需要查找个新名字时，就能通过过display表找出当前正在处理的最内层的过程及所有外层的子符号表找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置。然后通过指针域可以找到同一个过程内的表在栈符号表中的位置。然后通过指针域可以找到同一个过程内的所有被说明的名字。所有被说明的名字。 例：例： procedure/B1 var a,b:real; procedure/B2 var c,d:real; procedure/B3 var e,f:real; begin end; begin end; begin end; PreviousInformation Name1110987654321栈符号表栈符号表DISPLAYab