编译原理chapter8 符号表(2016)

1、编编 译译 原原 理理 chapter8 符号符号表表Chapter8 符号表符号表编编 译译 原原 理理 chapter8 符号符号表表8.1 符号表的组织与作用符号表的组织与作用8.2 整理与查找整理与查找 8.3 名字的作用范围名字的作用范围 8.4 符号表的内容符号表的内容 编编 译译 原原 理理 chapter8 符号符号表表符号表的作用符号表的作用 一张符号表的每一项（或称入口）包含两大栏（或称一张符号表的每一项（或称入口）包含两大栏（或称区段、字域）区段、字域）,即即名字栏和信息栏名字栏和信息栏。表格形式如下所示：。表格形式如下所示： 信息栏（信息栏（Information）名字

2、栏（名字栏（Name）第一项第一项（入口（入口1）第二项第二项（入口（入口2）第第n项项（入口（入口n）编编 译译 原原 理理 chapter8 符号符号表表 名字栏用来存放标识符或其内部码；信息栏包含名字栏用来存放标识符或其内部码；信息栏包含许多子栏和标志位，用来记录与该项名字相对应的种种许多子栏和标志位，用来记录与该项名字相对应的种种不同属性。不同属性。 （5）从表中删除一个或一组名字。）从表中删除一个或一组名字。 在整个编译期间，对于符号表的访问可概括为如在整个编译期间，对于符号表的访问可概括为如下几类操作：下几类操作：（1）对给定名字，查询此名是否已在表中；）对给定名字，查询此名是否已

3、在表中；（2）往表中填入一个新名字；）往表中填入一个新名字；（3）对给定名字，访问它的相关信息；）对给定名字，访问它的相关信息；（4）对给定名字，往表中填写或更新它的某些信息）对给定名字，往表中填写或更新它的某些信息;编编 译译 原原 理理 chapter8 符号符号表表符号表的组织方式符号表的组织方式 1、各项各栏所占存储单元的长度固定、各项各栏所占存储单元的长度固定 2、间接方式安排名字栏、间接方式安排名字栏poolelpmasNAMEINFORMATION , 6 , 4pool4elpmas6NAMEINFORMATION编编 译译 原原 理理 chapter8 符号符号表表 如果各种

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

5、1I1 上界上界InIn下界下界U1U1 下界下界UnUn内情向量表内情向量表在符号表的地址栏中存入符号在符号表的地址栏中存入符号表与内情向量表连接入口地址表与内情向量表连接入口地址 NAMENAMEINFORMATIONINFORMATIONCATCAT地址地址a a符号表符号表编编 译译 原原 理理 chapter8 符号符号表表 （1）把每一项置于连续的）把每一项置于连续的K个存储单元中，从而给出一张个存储单元中，从而给出一张K*N个个 存储单元的表。存储单元的表。 （2）把整个符号表分成）把整个符号表分成M个子表，每个子表含个子表，每个子表含N项。假定子表项。假定子表 Ti的每一项所需

6、的字数为的每一项所需的字数为Ki，那么，那么，K=K1+Km。对于任。对于任 何何i,T1i,Tmi的并置就构成符号表第的并置就构成符号表第i项的全部内容。项的全部内容。一张可容纳一张可容纳N项（每项需用项（每项需用K个字）的符号表在存储个字）的符号表在存储器中可用两种表示方式器中可用两种表示方式： T1 T2 T3 T4N1N2N3K1K2K3K4K=K1+K2+K3+K4编编 译译 原原 理理 chapter8 符号符号表表8.2 整理与查找整理与查找 一、线性表一、线性表 2、一种提高线性表查找效率的办法：给每一项附设一个指示器，、一种提高线性表查找效率的办法：给每一项附设一个指示器，这

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

8、 I XYZ J1INFORMATIONNAME项数项数1234AVAILABLE线性符号表线性符号表平均查找次数平均查找次数n/2编编 译译 原原 理理 chapter8 符号符号表表二、对折查找与二叉树二、对折查找与二叉树 （3）若要查找的项大于中项，则就到）若要查找的项大于中项，则就到n/2+2n的各项的各项 中去查找。中去查找。在造表时把表格中的项按名字的在造表时把表格中的项按名字的“大小大小”顺序整理排列。顺序整理排列。所谓名字的所谓名字的“大小大小”通常是通常是指名字的内码二进制指名字的内码二进制。对于经顺序化的表格的查找可用对折法。对于经顺序化的表格的查找可用对折法。对折法的查找

9、方法如下：对折法的查找方法如下：（1）首先把要查找的项和）首先把要查找的项和中中项（即第项（即第n/2+1项）作比项）作比 较，若相等，则宣布查找成功。较，若相等，则宣布查找成功。平均查找次数平均查找次数 1+log2n（2）若要查找的项小于中项，则继续在）若要查找的项小于中项，则继续在1n/2的各项的各项 中去查找。中去查找。编编 译译 原原 理理 chapter8 符号符号表表 二叉树的形成过程如下：二叉树的形成过程如下： 令第一个碰到的名字作为令第一个碰到的名字作为“根根”结点，它的左、结点，它的左、右指示器均置为空，当要加入新结点时，首先把它和右指示器均置为空，当要加入新结点时，首先把

10、它和根结点的值作比较，根结点的值作比较，小者放在右枝上小者放在右枝上，大者放在左枝大者放在左枝上上。如果根结点的左（右）。如果根结点的左（右） 枝已成子树，则让新结点枝已成子树，则让新结点和子树的根再作比较。重复上述步和子树的根再作比较。重复上述步 骤，直至把新结点骤，直至把新结点插入使它成为二叉树的一个端末结点（叶）为止。插入使它成为二叉树的一个端末结点（叶）为止。编编 译译 原原 理理 chapter8 符号符号表表三、三、杂凑杂凑技术技术 1、假定有一个足够大的区域，这个区域用来填写一、假定有一个足够大的区域，这个区域用来填写一张含张含N项的符号表。构造一个地址函数项的符号表。构造一个地

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

12、办法： 开放地址法、再哈希法、开放地址法、再哈希法、链地址法链地址法、建立一个公共溢出区、建立一个公共溢出区编编 译译 原原 理理 chapter8 符号符号表表 填入一个新项的过程：填入一个新项的过程：（1）先计算出）先计算出H(SYM) 的函数值的函数值h（在（在0与与N-1之间），之间）， 将将Hashtableh的值赋给的值赋给P（若未曾有杂凑值为（若未曾有杂凑值为 h的项名填入过，则将的项名填入过，则将P置置NULL）。）。（2）然后将指针指向）然后将指针指向Hashtableh，再把新名及其，再把新名及其 链接指示器的值链接指示器的值P填进指针所指向的符号表位置。填进指针所指向的符

13、号表位置。 杂凑技术：使用一张杂凑链表通过间接方式查填符号表。杂凑技术：使用一张杂凑链表通过间接方式查填符号表。 将具有相同杂凑值符号名连成一串，便于线性查找。将具有相同杂凑值符号名连成一串，便于线性查找。杂凑表是一个可容纳杂凑表是一个可容纳N个指示器值的一维数组个指示器值的一维数组，它的，它的每个元素的初值全为每个元素的初值全为null。符号表除了通常包含的栏。符号表除了通常包含的栏外，还增设了外，还增设了一链接栏，他把所有持有相同杂凑值的一链接栏，他把所有持有相同杂凑值的符号名连接成一条链符号名连接成一条链。编编 译译 原原 理理 chapter8 符号符号表表LinkInformatio

14、nName符符 号号 表表.n1n2n3.Hashtable01.h.N-1NULLNULLNULLNULL.availableSYM1H(SYM1)=hHashtableh=available=n1n1NULLSYM2H(SYM2)=havailablen1Hashtableh=available=n2n2SYM1SYM2P=Hashtableh=NULLP=Hashtableh=n1SYM3H(SYM3)=hP=Hashtableh=n2availableHashtableh=available=n3n3n2SYM3编编 译译 原原 理理 chapter8 符号符号表表8.3 名字的作用范

15、围名字的作用范围 最近嵌套作用域规则最近嵌套作用域规则：即对每个过程指定一个唯一的：即对每个过程指定一个唯一的编号，以便跟踪过程里的局部名字。编号，以便跟踪过程里的局部名字。在符号表中，表示局部名字用一个二元组：在符号表中，表示局部名字用一个二元组： 对一个名字查找符号表是：只有当表项中的名字其字对一个名字查找符号表是：只有当表项中的名字其字符逐个匹配，并且该记录相关的编号和当前所处理符逐个匹配，并且该记录相关的编号和当前所处理的过程的编号匹配时，才能确定查找成功的过程的编号匹配时，才能确定查找成功.编编 译译 原原 理理 chapter8 符号符号表表嵌套结构型程序设计语言嵌套结构型程序设计

16、语言的符号表：的符号表：1） 针对符号表设计为针对符号表设计为栈符号表栈符号表，新名字出现总是从栈，新名字出现总是从栈顶填入。为了保证从内层向外层查，查找顶填入。为了保证从内层向外层查，查找 操作从符号表操作从符号表的栈顶往底部查找。的栈顶往底部查找。TOP指向栈顶第一个可用单元，指向栈顶第一个可用单元，P总是指向最新子符号表首地址。总是指向最新子符号表首地址。2）过程的过程的嵌套层次表（嵌套层次表（display），是引入的一个显，是引入的一个显示层次关系表示层次关系表。其作用是为了。其作用是为了描述过程的嵌套层次，描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或指出当前正在活动着的

17、各嵌套的过程（或 函数）相应函数）相应的子符号表在栈符号表中的起始位置的子符号表在栈符号表中的起始位置（相对地址）。（相对地址）。 display表本身也是一个栈，每进入一个新的过程表本身也是一个栈，每进入一个新的过程（或函数），栈顶指针增（或函数），栈顶指针增1；每退出一个新的过程（或；每退出一个新的过程（或函数），栈顶指针减函数），栈顶指针减1。栈顶指针总是指向当前正在处栈顶指针总是指向当前正在处理的最内层的过程在栈符号表中理的最内层的过程在栈符号表中 的起始位置。的起始位置。编编 译译 原原 理理 chapter8 符号符号表表3）在信息栏中引入一个指针域（在信息栏中引入一个指针域（pr

18、evious)，用来链，用来链 接它在同一个过程内的下一名字在表中的下标（相接它在同一个过程内的下一名字在表中的下标（相 对位置）。每一层最后一个域名字，指针域之值为对位置）。每一层最后一个域名字，指针域之值为0。 这样每当需要查找个新名字时，就能通过这样每当需要查找个新名字时，就能通过display表表 找出当前正在处理的最内层的过程及所有外层的子找出当前正在处理的最内层的过程及所有外层的子 符号表在栈符号表中的位置。然后通过指针域可以符号表在栈符号表中的位置。然后通过指针域可以 找到同一个过程内的所有被说明的名字。找到同一个过程内的所有被说明的名字。编编 译译 原原 理理 chapter8 符号符号表表fun3() int e,f;fun2() int c,d; fun3();fun1() int a,b; fun2();InformationName12345678910栈符号表栈符号表Display表表abfun2230topsp1levelcdfun3topsp4506levelleveleftopsp7le