编译原理 符号表1

《编译原理 符号表1》由会员分享，可在线阅读，更多相关《编译原理 符号表1（20页珍藏版）》请在金锄头文库上搜索。

1、第八章 符号表 8.1符号表的组织与作用编译过程符号表的作用一、符号表的作用遇到名字查表、登记、修改 目的：合理地组织符号表。构成：符号表的每一项包含名字栏和信息栏。表格形式如下所示： 名字栏（Name）信息栏（Information ） 第一项（入口1）第二项（入口2）第n项（入口n ）名字栏用来存放标识符或其内部码；信息栏包含许多子 栏和标志位，用来记录与该项名字相对应的种种不同属性。 （5）从表中删除一个或一组名字。操作：对于符号表的访问可概括为如下几类操作：（1）对给定名字，查询此名是否已在表中；（2）往表中填入一个新名字；（3）对给定名字，访问它的相关信息；（4）对给定名字，往表中填

2、写或更新它的某些信息;符号表组织方式：简单方式：固定二维表间接方式：使用主表指针独立的字符串数组（标识符名）二、符号表的组织方式 1、各项各栏所占存储单元的长度固定 2、间接方式安排名字栏poolelpmasNAMEINFORMATION , 6 , 4pool4elpmas6NAMEINFORMATION 符 号 表 的 结 构如果各种名字所需的信息（INFORMATION ）空间长短不一，那么，我们可把一些共同属性直接登记在符号表的信息栏中，而把某些特殊属性登记在别的地方，并在信息栏中附设一指示器，指向存放特殊属性的地方。特殊属性的登记：例如：对 于数组标识符专门开辟一个信息表区，即为 数

3、组信息表也称为内情向量表维数首地址界差d1 界差dn 上界I1 上界In下界U1 下界Un内情向量表在符号表的地址栏中存入符号 表与内情向量表连接入口地址 NAMEINFORMATIONCAT地址a符号表（1）把每一项置于连续的K个存储单元中，从而给出一 张K*N个存储单元的表。 （2） 把整个符号表分成M个子表，每个子表含N项。假 定子表Ti的每一项所需的字数为Ki，那么，K=K1+Km 。对于任何i,T1i,Tmi的并置就构成符号表第i项的全部 内容。一张可容纳N项的符号表在存储器中的两种表示方式：T1 T2 T3 T4N1N2N3K1K2K3K4K=K1+K2+K3+K4例8.1 FOR

4、TRAN符号表程序段：SUBROUTINE INCWAP(M,N) 10 K=M+1M=M+4N=KRETURNEND主要表格见p2258.2 整理与查找 一、线性表 2、提高查找效率的办法：给每一项附设一个指示器，这些指示器 把所有的项按“最新最近”访问原则连接成一条链，这条链的第一个 元素所指的项是最新最近被查询过的项，第二个元素所指的项是次 新近被查询过的项，诸如此类。每当填入新项时，总让链头指向最 新项，含有这种链条的线性表叫做自适应线性表。1、线性表介绍符号表的三种构造法和处理法： 线性查找、二叉树、杂凑技术。 BC I XYZ J1INFORMATIONNAME项数1 2 3 4A

5、VAILABLE线性符号表平均查找次数n/2二、对折查找与二叉树 （3）若要查找的项大于中项，则就到n/2+2n的各项中去查找。在造表的同时把表格中的项按名字的“大小”顺序整理排列。 所谓名字的“大小”通常是指名字的内码二进制。对于经顺序化的表格的查找可用对折法。对折法的查找方法如下： （1）首先把要查找的项和中项（即第n/2+1项）作比较，若相等，则宣布查找成功。（2）若要查找的项小于中项，则继续在1n/2的各项中去查找。顺序化的线性符号表 XYZ J1 I BCINFORMATIONNAME项数12 3 4AVAILABLE平均查找次数1+log2n二叉树的形成过程如下：令第一个碰到的名字

6、作为“根”结点，它 的左、右指示器均置为空， 当要加入新结点时，首先把它和根结点的值作比较，小者放在右枝 上，大者放在左枝上。如果根结点的左（右） 枝已成子树，则让新 结点和子树的根再作比较。重复上述步 骤，直至把新结点插入使它 成为二叉树 的一个端末结点（叶）为止。把符号表组织成一棵二叉树(二叉排序树） 令每项是一个结点，每个结点附设两个指示器栏，一栏为LEFT（左枝），令一栏为RIGHT（右枝）。每个结点的主栏内码值被看成是代表该结点的值。要求：任何结点P右枝的所有结点值均应小于结点P的值，而左枝的任何结点值均应大于结点P的值。 I BC XYZ J1INFORMATIONNAME项数1

7、2 3 4AVAILABLEJ1根LEFTRIGHT 00 0XYZ00BC00I0三、杂凑技术 1、假定有一个足够大的区域，这个区域用来填写一张含N项的符号 表。构造一个地址函数H，对任何名字，H函数的取值于0至N-1之间 。即不论对此项查表或填表，都能从H函数中获得它在表中的位置。 2、对地址函数H有两点要求：（1）函数的计算要简单、高效；（2）函数值能比较均匀的分布在0至N-1之间。3、构造函数H的办法： 直接地址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法4、解决地址冲突的办法： 开放地址法、再哈希法、链地址法(p228)、建立一个公共溢出区3、填入一个新的项的过程：（1）

8、先计算出H函数的值h（在0与N-1之间），将 HASHTABLEh的值赋给P（若未曾有杂凑值为h的项名填入过，则将P置空） 。（2）然后将指针指向HASHTABLEh，再把新名及其链接指示 器的值P填进指针所指向的符号表位置。 4、使用此方法的查表过程如下：首先计算出此项的函数H的值等于h，然后就指示器HASHTABLEh所指的项链逐一按序查找（线性查找）杂凑技术：使用一张杂凑链表通过间接方式查添符号表 。将具有相同杂凑值符号名连成一串，便于线性查找。杂凑表是一个可容纳N个指示器值的一维数组，它的每个元素的初值全为null。符号表除了通常包含的栏外，还增设了一链接栏，他把所有持有相同杂凑值的符

9、号名连接成一条链。availableSYM1H（SYM1）=hp=HASHTABLEh=nullHASHTABLEh=AVAVILABLE=n1SYM1null01hN-1杂凑表符号表LinkInformationNamen1n2n3n1nullavailableSYM2H（SYM2）=hp=HASHTABLEh= n1 HASHTABLEh=AVAVILABLE=n2n2SYM2n1SYM3H（SYM3）=hp=HASHTABLEh= n2HASHTABLEh=AVAVILABLE=n3n3SYM3n2availableavailable8.3名字的作用范围 对于过程嵌套结构型的程序设计语言

10、，每层过程中说明的名字只局限于该过程，离开了所在的过程就无意义了。也就是说， 同一个标识符，具有不同的性质，要求分配不同的存储空间。这样，如何组织符号表，使的同一个标识符在不同的作用域中能得到正确的引用，而不会产生混乱。通常实现最近嵌套作用域规则的办法是：对每个过程指定一个唯一的编号，即过程的顺序号，以便跟踪过程里的局部名字。在符号表中，表示局部名字用一个二元组：对一个名字查找符号表的原则:只有当表项中的名字的字符逐个匹配,并且该记录相关的编号 和当前所处理的过程的编号匹配时,才能确定查找成功.一、Pascal的符号表组织 1、在Pascal程序中标识符的作用域是包含说明该标识符的一个最 小分

11、程序。具体的概括为如下几点：（1）如果一个标识符在某一分程序首部已作说明，则不论此分程序是否含有内层分程序，也不论内分程序在嵌套多少层，只要在内层分程序未再次对该标识符加以说明，则此标识符在整个分程序中均有定义，且有相同的属性。（2）程序中的标号局限于定义该标号的最小分程序。 （3）由于Pascal程序中的过程可具有嵌套的结构，因此，可将每 一过程说明都假想为一个分程序。出现在过程体中的非形式 参数， 依其在相应的过程体中被说明与否，确定它们对过程而言是局部变 量还是非局部变量，而形式参数则总是局限于相应 的过程体的。 PASCAL程序中的标识符（或标号）的作用域，总是与说明（定义）这些标识符

12、的分程序的层次相联系的。（1） 针对符号表设计为栈符号表，新名字出现总是从栈顶填入。 为了保证从内层向外层查，查找操作从符号表的栈顶往底部查找。2、对于嵌套结构型程序设计语言（Pascal）的特点，可采用如下办法：（2）过程的嵌套层次表（display），是引入的一个显示层次关系 表。其作用是为了描述过程的嵌套层次，指出当前正在活动着的各 嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（ 相对地址）。 Display表也是一个栈，栈顶为level，用来指示层次 ，即指向当前的最内层过程的子符号表在栈符号表中的起始位置。（3）在符号表的信息栏中引入一个指针域（previous)，用来链

13、接 它在同一个过程内的下一名字在表中的下标（相对位置）。每一层 最后一个域名字，指针域之值为0。这样每当需要查找个新名字时 ，就能通过display表找出当前正在处理的最内层的过程及所有外层 的子符号表在栈符号表中的位置。然后通过指针域可以找到同一个 过程内的所有被说明的名字。例： procedure/B1var a,b:real;procedure/B2var c,d:real;procedure/B3var e,f:real;begin end;begin end;beginend; PreviousInformation Name1110987654321栈符号表DISPLAYabtop

14、sp 1levellevel20B2cdtopsp4level3050B3eftopsp7level60808.4 符号表的内容 （1）类型（整、实、双实、布尔、字符、复、标号或指针等） ；（2）种属（简单变量、数组或记录结构等）；（3）长度（所需的存储单元数）；（4）相应对数（存储单元相对地址）；（5）若为数组，则记录其内情向量；（6）若为记录结构，则把它与其分量按某种形式联系起来；（7）形式参数标志；（8）是否对这个变量进行过赋值（包括出现在输入名表中）的 标志位。对于变量名、数组名和过程名，它们的信息栏中一般要求有以下信息 ：1、变量：（1）是否为程序的外部过程；（2）若为函数，应指出它的类型；（3）其说明是否处理过；（4）是否递归定义；（5）形式参数是些什么？为了与实在参数进行比较， 必须把它们 的种属、类型信息同过程名联系在一起。例 8.2 p235例:图8.10 P232Exercise:p236 1,2,3,72、过程：