编译原理chapter8-符号表(2016)

编译原理chapter8符号表Chapter8符号表编译原理chapter8符号表8.1符号表的组织与作用8.2整理与查找8.3名字的作用范围8.4符号表的内容编译原理chapter8符号表符号表的作用一张符号表的每一项（或称入口）包含两大栏（或称区段、字域）,即名字栏和信息栏。表格形式如下所示：…………信息栏（Information）名字栏（Name）第一项（入口1）第二项（入口2）第n项（入口n）编译原理chapter8符号表名字栏用来存放标识符或其内部码；信息栏包含许多子栏和标志位，用来记录与该项名字相对应的种种不同属性。（5）从表中删除一个或一组名字。在整个编译期间，对于符号表的访问可概括为如下几类操作：（1）对给定名字，查询此名是否已在表中；（2）往表中填入一个新名字；（3）对给定名字，访问它的相关信息；（4）对给定名字，往表中填写或更新它的某些信息;编译原理chapter8符号表符号表的组织方式1、各项各栏所占存储单元的长度固定2、间接方式安排名字栏poolelpmasNAMEINFORMATION•,6•,4pool4elpmas6NAMEINFORMATION••编译原理chapter8符号表如果各种名字所需的信息（INFORMATION）空间长短不一，那么，我们可把一些共同属性直接登记在符号表的信息栏中，而把某些特殊属性登记在别的地方，并在信息栏中附设一指示器，指向存放特殊属性的地方。例如：对于数组标识符专门开辟一个信息表区，即为数组信息表也称为内情向量表维数首地址界差d1•••界差dn上界I1•••上界In下界U1•••下界Un内情向量表在符号表的地址栏中存入符号表与内情向量表连接入口地址•••NAMEINFORMATIONCAT地址••a•符号表编译原理chapter8符号表8.2整理与查找一、线性表2、一种提高线性表查找效率的办法：给每一项附设一个指示器，这些指示器把所有的项按“最新最近”访问原则连接成一条链，这条链的第一个元素所指的项是最新最近被查询过的项，第二个元素所指的项是次新近被查询过的项，诸如此类。每当填入新项时，总让链头指向最新项，含有这种链条的线性表叫做自适应线性表。1、线性表介绍符号表的三种构造法和处理法：线性查找、二叉树、杂凑技术。•••BC•••I•••XYZ•••J1INFORMATIONNAME项数1234AVAILABLE线性符号表平均查找次数n/2编译原理chapter8符号表二、对折查找与二叉树（3）若要查找的项大于中项，则就到[n/2]+2〜n的各项中去查找。在造表时把表格中的项按名字的“大小”顺序整理排列。所谓名字的“大小”通常是指名字的内码二进制。对于经顺序化的表格的查找可用对折法。对折法的查找方法如下：（1）首先把要查找的项和中项（即第[n/2]+1项）作比较，若相等，则宣布查找成功。平均查找次数1+log2n（2）若要查找的项小于中项，则继续在1〜[n/2]的各项中去查找。编译原理chapter8符号表二叉树的形成过程如下：令第一个碰到的名字作为“根”结点，它的左、右指示器均置为空，当要加入新结点时，首先把它和根结点的值作比较，小者放在右枝上，大者放在左枝上。如果根结点的左（右）枝已成子树，则让新结点和子树的根再作比较。重复上述步骤，直至把新结点插入使它成为二叉树的一个端末结点（叶）为止。编译原理chapter8符号表三、杂凑技术1、假定有一个足够大的区域，这个区域用来填写一张含N项的符号表。构造一个地址函数H，对任何名字，H函数的取值在0至N-1之间。即不论对此项查表或填表，都能从H函数中获得它在表中的位置。2、对地址函数H有两点要求：（1）函数的计算要简单、高效；（2）函数值能比较均匀的分布在0至N-1之间。3、构造函数H的办法：直接地址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法4、解决地址冲突的办法：开放地址法、再哈希法、链地址法、建立一个公共溢出区编译原理chapter8符号表填入一个新项的过程：（1）先计算出H(SYM)的函数值h（在0与N-1之间），将Hashtable[h]的值赋给P（若未曾有杂凑值为h的项名填入过，则将P置NULL）。（2）然后将指针指向Hashtable[h]，再把新名及其链接指示器的值P填进指针所指向的符号表位置。杂凑技术：使用一张杂凑链表通过间接方式查填符号表。将具有相同杂凑值符号名连成一串，便于线性查找。杂凑表是一个可容纳N个指示器值的一维数组，它的每个元素的初值全为null。符号表除了通常包含的栏外，还增设了一链接栏，他把所有持有相同杂凑值的符号名连接成一条链。编译原理chapter8符号表LinkInformationName符号表............n1n2n3........................Hashtable01...h...N-1NULLNULLNULLNULL......availableSYM1H(SYM1)=hHashtable[h]=available=n1n1NULLSYM2H(SYM2)=havailablen1Hashtable[h]=available=n2n2SYM1SYM2P=Hashtable[h]=NULLP=Hashtable[h]=n1SYM3H(SYM3)=hP=Hashtable[h]=n2availableHashtable[h]=available=n3n3n2SYM3编译原理chapter8符号表8.3名字的作用范围最近嵌套作用域规则：即对每个过程指定一个唯一的编号，以便跟踪过程里的局部名字。在符号表中，表示局部名字用一个二元组：名字,过程编号对一个名字查找符号表是：只有当表项中的名字其字符逐个匹配，并且该记录相关的编号和当前所处理的过程的编号匹配时，才能确定查找成功.编译原理chapter8符号表嵌套结构型程序设计语言的符号表：1）针对符号表设计为栈符号表，新名字出现总是从栈顶填入。为了保证从内层向外层查，查找操作从符号表的栈顶往底部查找。TOP指向栈顶第一个可用单元，P总是指向最新子符号表首地址。2）过程的嵌套层次表（display），是引入的一个显示层次关系表。其作用是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（相对地址）。display表本身也是一个栈，每进入一个新的过程（或函数），栈顶指针增1；每退出一个新的过程（或函数），栈顶指针减1。栈顶指针总是指向当前正在处理的最内层的过程在栈符号表中的起始位置。编译原理chapter8符号表3）在信息栏中引入一个指针域（previous)，用来链接它在同一个过程内的下一名字在表中的下标（相对位置）。每一层最后一个域名字，指针域之值为0。这样每当需要查找个新名字时，就能通过display表找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置。然后通过指针域可以找到同一个过程内的所有被说明的名字。编译原理chapter8符号表fun3(){inte,f;}fun2(){intc,d;fun3();}fun1(){inta,b;fun2();}InformationName12345678910栈符号表Display表abfun2230topsp1levelcdfun3topsp4506levelleveleftopsp7level08编译原理chapter8符号表8.4符号表的内容（1）类型（整、实、双实、字符、指针等）；（2）种属（简单变量、数组或结构体等）；（3）长度（所需的存储单元数）；（4）相对数（存储单元相对地址）；（5）若为数组，则记录其内情向量；（6）若为记录结构，则把它与其分量按某种形式联系起来；（7）形式参数标志；（8）是否对这个变量进行过赋值的标志位。对于变量名、数组名和函数名，信息栏中一般要求有以下信息：编译原理chapter8符号表（1）是否为程序的外部函数；（2）应指出它的类型；（3）其说明是否处理过；（4）是否递归定义；（5）形式参数？为了与实在参数进行比较，必须把它们的种属、类型信息同过程名联系在一起。2、函数：