编译原理符号表1.pptVIP

第八章 符号表 * * 8.1符号表的组织与作用－－编译过程符号表的作用 一、符号表的作用－遇到名字查表、登记、修改 目的：合理地组织符号表。 构成：符号表的每一项包含名字栏和信息栏。表格形式如下所示： …… …… 信息栏（Information） 名字栏（Name） 第一项 （入口1） 第二项 （入口2） 第n项 （入口n） 名字栏用来存放标识符或其内部码；信息栏包含许多子栏和标志位，用来记录与该项名字相对应的种种不同属性。 （5）从表中删除一个或一组名字。 操作：对于符号表的访问可概括为如下几类操作： （1）对给定名字，查询此名是否已在表中； （2）往表中填入一个新名字； （3）对给定名字，访问它的相关信息； （4）对给定名字，往表中填写或更新它的某些信息; 符号表组织方式： 简单方式：固定二维表 间接方式：使用主表指针＋独立的字符串数组（标识符名） 二、符号表的组织方式 1、各项各栏所占存储单元的长度固定 2、间接方式安排名字栏 p o o l e l p m a s NAME INFORMATION ? , 6 ? , 4 p o o l 4 e l p m a s 6 NAME INFORMATION ? ? 符号表的结构 如果各种名字所需的信息（INFORMATION ）空间长短不一， 那么，我们可把一些共同属性直接登记在符号表的信息栏中， 而把某些特殊属性登记在别的地方，并在信息栏中附设一指示 器，指向存放特殊属性的地方。 特殊属性的登记：例如：对于数组标识符 专门开辟一个信息表区，即为数组信息表也称为内情向量表 维数 首地址 界差d1 ? ? ? 界差dn 上界I1 ? ? ? 上界In 下界U1 ? ? ? 下界Un 内情向量表 在符号表的地址栏中存入符号表与内情向量表连接入口地址 ? ? ? NAME INFORMATION CAT 地址 ? ? a ? 符号表 （1）把每一项置于连续的K个存储单元中，从而给出一 张K*N个存储单元的表。? （2） 把整个符号表分成M个子表，每个子表含N项。假定子表Ti的每一项所需的字数为Ki，那么，K=K1+…+Km。对于任何i,T1[i],…Tm[i]的并置就构成符号表第i项的全部内容。 一张可容纳N项的符号表在存储器中的两种表示方式： T1 T2 T3 T4 N1 N2 N3 K1 K2 K3 K4 K=K1+K2+K3+K4 例8.1 FORTRAN符号表 程序段： SUBROUTINE INCWAP(M,N) 10 K=M+1 M=M+4 N=K RETURN END 主要表格见p225 8.2 整理与查找 一、线性表 2、提高查找效率的办法：给每一项附设一个指示器，这些指示器把所有的项按“必威体育精装版最近”访问原则连接成一条链，这条链的第一个元素所指的项是必威体育精装版最近被查询过的项，第二个元素所指的项是次新近被查询过的项，诸如此类。每当填入新项时，总让链头指向必威体育精装版项，含有这种链条的线性表叫做自适应线性表。 1、线性表介绍 符号表的三种构造法和处理法： 线性查找、 二叉树、 杂凑技术。 ? ? ? BC ? ? ? I ? ? ? XYZ ? ? ? J1 INFORMATION NAME 项数 1 2 3 4 AVAILABLE 线性符号表 平均查找次数 n/2 二、对折查找与二叉树 （3）若要查找的项大于中项，则 就到[n/2]+2~n的各项中去查找。 在造表的同时把表格中的项按名字的“大小”顺序整理排列。 所谓名字的“大小”通常是指名字的内码二进制。 对于经顺序化的表格的查找可用对折法。 对折法的查找方法如下： （1）首先把要查找的项和中项 （即第[n/2]+1项）作比较，若 相等，则宣布查找成功。 （2）若要查找的项小于中项， 则继续在1~[n/2]的各项中去查找。 顺序化的线性符号表 ? ? ? XYZ ? ? ? J1 ? ? ? I ? ? ? BC INFORMATION NAME 项数 1 2 3 4 AVAILABLE 平均查找次数 1+log2n 二叉树的形成过程如下： 令第一个碰到的名字作为“根”结点，它 的左、右指示器均置为空，当要加入新结点时，首先把它和根结点的值作比较，小者放在右枝上，大者放在左枝上。如果根结点的左（右） 枝已成子树，则让新结点和子树的根再作比较。重复上述步 骤，直至把新结点插入