编译原理-西安交通大学7_符号表2.0

《编译原理-西安交通大学7_符号表2.0》由会员分享，可在线阅读，更多相关《编译原理-西安交通大学7_符号表2.0（57页珍藏版）》请在金锄头文库上搜索。

1、第第6 6章章 符号表符号表1 1，联系，联系编译程序必须收集，利用出现在源程序中的名字的信息，编译程序必须收集，利用出现在源程序中的名字的信息，这种信息被列进成为符号表的数据结构中，给一个名字收这种信息被列进成为符号表的数据结构中，给一个名字收集的信息包括集的信息包括 : :表示名字的字符串，表示名字的字符串，名字的类型（例如，整形，实型，串等），名字的类型（例如，整形，实型，串等），种属（种属（JBJB，结果），结果），存储单元存储单元 其它依赖于语言的特性。其它依赖于语言的特性。1第6章 符号表2 2，填项，填项 3 3，使用表中的信息用于编译的各个阶段，使用表中的信息用于编译的各个阶段

2、扫描源程序，遇到一个名字就检索表，若它是一个新的扫描源程序，遇到一个名字就检索表，若它是一个新的名字，就填表，在调用词法语法分析程序时，还要把有名字，就填表，在调用词法语法分析程序时，还要把有关的信息填入（如标号的链，定义否）关的信息填入（如标号的链，定义否）语义分析语义分析时，用它来检查名字的使用是否与它们原先的说明一致，时，用它来检查名字的使用是否与它们原先的说明一致，如如GOTO L , L GOTO L , L 为标号；为标号；代码生成代码生成时，需要了解必须给名字分配多少，以及哪一种存储时，需要了解必须给名字分配多少，以及哪一种存储；2第6章 符号表为了便于查错和改错，可以记录前面是

3、否已经打印过象为了便于查错和改错，可以记录前面是否已经打印过象“变量变量A A未未定义定义”这样的出错信息，以免重复。这样的出错信息，以免重复。对于多遍扫描的编译器，不同遍的表也往往不同。对于多遍扫描的编译器，不同遍的表也往往不同。本章主要讨论本章主要讨论 : :设计表的主要问题是登记项的格式，设计表的主要问题是登记项的格式，表的组织和访问的方法，表的组织和访问的方法，访问的格式，访问的格式，存放的位置（主存或者辅存）。存放的位置（主存或者辅存）。3第6章 符号表6.1 6.1 符号表的内容符号表的内容6.1.16.1.1 符号表项的域符号表项的域理论上，符号表只是一个具有名字域和信息域这理论

4、上，符号表只是一个具有名字域和信息域这2 2个域个域的表的表, ,大致结构如下大致结构如下: :名字栏名字栏信息栏信息栏第一项（入口1）第二项（入口2）第n项（入口n）4第6章 符号表我们要求它具备以下几种功能我们要求它具备以下几种功能：1 1，确定一个给定的名字是否在表中；，确定一个给定的名字是否在表中；2 2，填入新的名字；，填入新的名字；3 3，访问所给名字的有关信息；，访问所给名字的有关信息；4 4，对给定的名字，填写和更新它的有关息；，对给定的名字，填写和更新它的有关息；5 5，删除一个或者一组名字，删除一个或者一组名字5第6章 符号表6.1.2 6.1.2 分表分表语言中，名字表示

5、各种类型的对象：变量名，过程名，常语言中，名字表示各种类型的对象：变量名，过程名，常数，域名（结构），标号等，由于各种类型的名字因用法数，域名（结构），标号等，由于各种类型的名字因用法不同，栏目及所需的空间相差很大，因此往往独立建表，不同，栏目及所需的空间相差很大，因此往往独立建表，由此带来的负面影响是：导致零头太多。如果登记项格式由此带来的负面影响是：导致零头太多。如果登记项格式可以变化，则另外一个表也可以；可以变化，则另外一个表也可以；如果禁止把关键字作为标识符，则应把关键字先进表，标如果禁止把关键字作为标识符，则应把关键字先进表，标函也进表函也进表. .6第6章 符号表6.1.3 6.1

6、.3 符号表内容的细目符号表内容的细目 1 1，表示名字的字符串，表示名字的字符串+ +编号，如果多个程序块或编号，如果多个程序块或过程中可以使用同一标识符，则必须指出这个名字属于哪过程中可以使用同一标识符，则必须指出这个名字属于哪一个程序块或过程；一个程序块或过程；2 2，名字的属性（包括类型和种类）以及识别名字，名字的属性（包括类型和种类）以及识别名字用途的信息（标号，用途的信息（标号， 形参，数组）形参，数组）3 3，参数（维数，下标的上下界），参数（维数，下标的上下界）4 4，描述分配给名字存储单元的位置的偏移量，描述分配给名字存储单元的位置的偏移量7第6章 符号表6.1.4 6.1.

7、4 符号表登记项的建立符号表登记项的建立 a, a, 符号表名字何时建立：符号表名字何时建立：1 1，词法分析。当识别了一个标识符时，它可以建，词法分析。当识别了一个标识符时，它可以建 立，不能填充种类，类型等；立，不能填充种类，类型等； install install 子程序返回子程序返回（$ID, $ID, 符号表指针）；符号表指针）；2 2，但是当一个名字在同一个程序块或过程中，可用，但是当一个名字在同一个程序块或过程中，可用作标号、实型变量、域名时，词法只能返回（作标号、实型变量、域名时，词法只能返回（$ID, $ID, TOKENTOKEN），由语法分析程序为标识符建表），由语法分析

8、程序为标识符建表8第6章 符号表b, b, 这些信息在不同的时刻插入符号表：这些信息在不同的时刻插入符号表：1 1，遇到显式说明时，把属性插入；，遇到显式说明时，把属性插入；2 2，语法可以隐含的说明变量的某种用途，如标号，语法可以隐含的说明变量的某种用途，如标号后后的的 ： ，所以和产生式，所以和产生式 语句语句- id:- id:语句语句 相关的相关的语义动作语义动作是把是把 id id 为标号的事实插入符号表，为标号的事实插入符号表，标号链，定义否填入；标号链，定义否填入；3 3，地址分配；，地址分配；类似，过程说明的语法告诉我们某些名字是形参。类似，过程说明的语法告诉我们某些名字是形参

9、。9第6章 符号表6.1.5 6.1.5 名字和符号表记录名字和符号表记录 实现表的最简单方式是看成记录的线性数组，每一栏目所占存储单实现表的最简单方式是看成记录的线性数组，每一栏目所占存储单元长度不变，每个名字对应一个记录，记录通常由已知个连续的存元长度不变，每个名字对应一个记录，记录通常由已知个连续的存储字组成。储字组成。DIMP DIMP 二个字二个字LELE属性属性 5 5个字个字标识符标识符信息信息标识符标识符信息信息记录记录1 1记录记录2 2图图6.1(a) 6.1(a) 存储标识符在记录中存储标识符在记录中10第6章 符号表6 6 属性属性 R FD IM P LE Q U图图

10、6.1(b) 6.1(b) 名字存储在分开的数组中名字存储在分开的数组中记录记录1 1记录记录2 211第6章 符号表1 1，当一个名字的最大长度不太长时，如，当一个名字的最大长度不太长时，如FORTRANFORTRAN为为8 8字字符，符， 用用2 2个字存储，其余补空；个字存储，其余补空；2 2，ALGOL ALGOL 名字不限，名字不限， PL/1 31PL/1 31个（个（8 8个字），个字）， 则采用则采用间接方式，专门字符数组，这样使表的名字域大小不间接方式，专门字符数组，这样使表的名字域大小不变；变；对于其他的域也可以这样办理，对于其他的域也可以这样办理，( (技术性工作技术性工

11、作).).? ?如果向量表维数可变怎么办如果向量表维数可变怎么办? ?12第6章 符号表把整个符号表分成若干子表把整个符号表分成若干子表SAMPLE的属性LESAMPLE4N 字2N 字NAME:0:2(i-1):4(i-1):INFORMATION:0:例子：分两个子表的符号表安排13第6章 符号表6.1.6 6.1.6 符号表空间的重新使用符号表空间的重新使用符号表占用空间很大，且信息更新，故有重新使用符号表占用空间很大，且信息更新，故有重新使用空间的问题，那些空间不可用呢？空间的问题，那些空间不可用呢？程序员用来表示名字的标识符，必须一直保存在符程序员用来表示名字的标识符，必须一直保存在

12、符号表中，直到不再引用为止，以便该标识符只能代号表中，直到不再引用为止，以便该标识符只能代表同一个名字，这是必要的，它使标识符的所有使表同一个名字，这是必要的，它使标识符的所有使用与符号表登记项相结合（表中有的内容在以后不用与符号表登记项相结合（表中有的内容在以后不再使用了），从而是同一个名字。再使用了），从而是同一个名字。但是，如果用来存放标识符的空间在下一次能重新但是，如果用来存放标识符的空间在下一次能重新使用，那么用少量空间就能解决问题。使用，那么用少量空间就能解决问题。14第6章 符号表例如，在以后几遍中，放名字的数组可以释放，所以设法回收用来存例如，在以后几遍中，放名字的数组可以释放

13、，所以设法回收用来存储标识符的空间，（事实上，图储标识符的空间，（事实上，图9.1b 9.1b 第一字也能回收）第一字也能回收）方法：方法：用两个而不是一个数组来存放记录用两个而不是一个数组来存放记录DIMP DIMP LELEDIMP LEDIMP LE属性属性如不查表，可释放如不查表，可释放2i-12i-12i2iIDENTIFIERS:IDENTIFIERS:INFORMATION:INFORMATION:两个数组的符号表方案两个数组的符号表方案(9.1a (9.1a 一分为二一分为二) )5i-45i-45i5i注意：注意：DIMPLEDIMPLE的外部表示不再是符号表的指针，而是整数

14、下标的外部表示不再是符号表的指针，而是整数下标i,i,此时，用此时，用i i来存取另一数组来存取另一数组15第6章 符号表有效地加入新项和找出有关项，本节主要讨论三种机制：有效地加入新项和找出有关项，本节主要讨论三种机制：6.2 6.2 整理与查找整理与查找1,线性表2，树3，散列表6.2.1 6.2.1 线性表线性表Name1Info1Name2Info2Name3Info3NameNinfoN记录的线性表记录的线性表AvailableAvailable16第6章 符号表线形表的效率估计线形表的效率估计 插入名字的工作量与表长插入名字的工作量与表长 n n 成正比成正比查找的工作量平均查找的

15、工作量平均 n/2n/2访问的工作量与表长访问的工作量与表长 n n 成正比成正比. .17第6章 符号表 一，自适应表一，自适应表 (Self-organizing List)(Self-organizing List)以少量额外空间为代价，在每一个记录中增加一个以少量额外空间为代价，在每一个记录中增加一个LinkLink域，域，并按并按LinkLink域指示的顺序检索表域指示的顺序检索表设定设定FirstFirst指出第一个记录的位置，指出第一个记录的位置，LinkLink指出下一个记录：指出下一个记录：NAME1NAME1DATA1DATA1LINK1LINK12 23 3 . .4 4

16、 . . . .链式结构的自适应表FIRSTAVAILABLE18第6章 符号表1，自适应表Link 的原则不适合随机访问不适合随机访问指示器把所有的项按指示器把所有的项按“最新最近最新最近”访问原则连结成一条链访问原则连结成一条链使得在任何的时候，这条链的第一元素所指的项是最近被使得在任何的时候，这条链的第一元素所指的项是最近被查询过的项，第二个元素是次新查询过的项查询过的项，第二个元素是次新查询过的项依据是依据是 刚刚被访问过的项以最大概率被继续访问刚刚被访问过的项以最大概率被继续访问19第6章 符号表2 2，做法，做法当引用一个名字或者当第一次建立该名字的纪录时，我们通过当引用一个名字或

17、者当第一次建立该名字的纪录时，我们通过移动指针把名字纪录移到表的前部，下图说明把移动指针把名字纪录移到表的前部，下图说明把NAME4NAME4纪录移纪录移到头上（到头上（NAME4NAME4刚刚被引用），原来的链是刚刚被引用），原来的链是31423142，现在改为，现在改为43124312NAME1NAME1DATA1DATA1LINK1LINK12 23 3 . .4 4 . . . . 1 1 2 2 3 3 . . 移到表头移到表头 4.4.(a)(a)3,1,4,23,1,4,2(b)(b)4,3,1,24,3,1,2FIRSTAVAILABLEFIRST20第6章 符号表3 3，算法

18、：可以写出把，算法：可以写出把NAME i NAME i 移到头上来的算法移到头上来的算法namelinkp i q.r.FIRST原原FIRST如果不改变，则如果不改变，则 FIRST r - p q.原原来来的的情情况况如如此此，现现在在开开始始改改变变让让FIRST ir rq qi iq q21第6章 符号表算法：算法：1，若，若Link p = i， 则记下则记下 p ; 若若Link i = q， 则则q Link p ; /这样，这样，i 就脱离了就脱离了2，若原，若原FIRST r， 则记则记 r Link i ;3, 让让FIRST i;22第6章 符号表二，折半查找二，折半

19、查找1 1，方法：，方法：为了提高查表速度，在造表的同时把表中的项按名字的为了提高查表速度，在造表的同时把表中的项按名字的“大小大小”顺序整理，所说名字的顺序整理，所说名字的“大小大小”，通常是指名字的内码二进制值。，通常是指名字的内码二进制值。若规定由小若规定由小 大，那么对任何要找的名字来说，无论相对哪大，那么对任何要找的名字来说，无论相对哪一个参考点，我们总可以知道要找的名字在参一个参考点，我们总可以知道要找的名字在参考考点的前面还是点的前面还是后面。因此一个简单的算法是每次都把参后面。因此一个简单的算法是每次都把参考考点定在中间。点定在中间。我们已经知道，对我们已经知道，对 N N 项

20、名表，查找的平均长度为项名表，查找的平均长度为loglog2 2N N (2为底数为底数)这较其线性查找，已经提高了许多，若这较其线性查找，已经提高了许多，若10241024项，是项，是1010：51251223第6章 符号表进一步的改进进一步的改进不在表的中间进行试查，而是不在表的中间进行试查，而是对每步的试查位置对每步的试查位置作作较准确的较准确的推断推断，若要在下表中查名字，若要在下表中查名字CATCAT，查，查2/26 2/26 处似更合理一些，猜测的好坏和对名表的了解程度处似更合理一些，猜测的好坏和对名表的了解程度有关，若能知符号表中的每个字母开头的词有多少，有关，若能知符号表中的每

21、个字母开头的词有多少，就能有一个校准的初始推测。在编译中，带有实际就能有一个校准的初始推测。在编译中，带有实际的名字项是取自整个名字集中的一个非随机子集，的名字项是取自整个名字集中的一个非随机子集，并知道它们的某种总的信息。并知道它们的某种总的信息。PetersonPeterson 证明：证明： 平均查找长度大约等于平均查找长度大约等于(1/2)*log2N(1/2)*log2N，如，如10001000项是项是 5 5 次。次。24第6章 符号表评价评价尽管如此，编译器不愿意采用它，它的致命弱点是，添加一项就要重新整理，使它按序。因此对于名字表不合适。但是对于固定的表，如定义符表等就很有用。（

22、插入固定表）25第6章 符号表 left left 结点值结点值 内码内码 right right再改进把符号表组织成一个二叉树，每一项是一个节点，把符号表组织成一个二叉树，每一项是一个节点，节点组成：节点组成：26第6章 符号表构造过程：构造过程：这样构造的树，保持任何结点这样构造的树，保持任何结点 P P 右枝的所有结点值小于结点右枝的所有结点值小于结点 P P 的值，而的值，而 P P 左枝的所有结点值大于结点左枝的所有结点值大于结点 P P 的值：的值： P P 值值 P P P 右枝的所有结点值右枝的所有结点值. .再加入名字再加入名字 LMN:LMN: ABCD LMN XYZA

23、ABCD LMN ABCD XYAZ ABCD 置于左；置于左； 因为因为 ABAA ABCD ABAA ABCD 置于右置于右根结点：第一个遇到的名字，此时，左右指示器为根结点：第一个遇到的名字，此时，左右指示器为 null.null. NULLXYZARIGHTNULLABAANULLNULLLMNNULLrootNULLABCDNULLLEFTABCDRIGHTrootNULLXYZANULL27第6章 符号表评价优点二叉树与对折查找的效率比较：二叉树与对折查找的效率比较：附设左右指示器，耗费空间，每查找一项所的比较次数仍然和附设左右指示器，耗费空间，每查找一项所的比较次数仍然和logl

24、og2 2N N 成比例成比例顺序化整理工作十分简单顺序化整理工作十分简单28第6章 符号表思考：思考：表格处理包括填查表，要两者快才好，但线性表和折半法只能表格处理包括填查表，要两者快才好，但线性表和折半法只能占一边，能否找到更好的办法？占一边，能否找到更好的办法？先在一个限制比较多的情况下讨论先在一个限制比较多的情况下讨论29第6章 符号表三，直接取表法三，直接取表法K K 表位置表位置若名字的第一个字母都不一样，若名字的第一个字母都不一样，那么我们用一个那么我们用一个 26 26 元的向量作元的向量作符号表。符号表。设映像函数设映像函数 I( K ) I( K ) 对每一个名对每一个名字

25、字 K K， I( K ) I( K ) 就是就是 K K 的第一的第一个字母在字母表中的位置，表头个字母在字母表中的位置，表头 100100， I( K ) = 100+( K )*lI( K ) = 100+( K )*l Z . K . B .A .26 元向量元向量-符号表符号表I (A)I (B)I (K)100l30第6章 符号表优点：优点：这个方法查填都很快，一次就行，函数唯一的时候，名字不需要存这个方法查填都很快，一次就行，函数唯一的时候，名字不需要存缺点：缺点：1，如果名字，如果名字 26 字母也无效字母也无效然而，它给我们一个启示：利用函数关系，然而，它给我们一个启示：利用

26、函数关系， 查填表，构造查填表，构造31第6章 符号表四，混列表四，混列表 （hash table, computed entry table, scatter table）特点：特点：去掉表长度去掉表长度 26 的限制，去掉名字字母构成的限制，映像函数定义的限制，去掉名字字母构成的限制，映像函数定义为：为： I ( k ) 产生的唯一的一组整数，即对任何关键字产生的唯一的一组整数，即对任何关键字 k1 != k2, 有有 I ( K1) != I ( K2 )，一般说来，一般说来 I ( K ) 可能值的范围较大，导致无法可能值的范围较大，导致无法查找存取表，于是放弃查找存取表，于是放弃 I

27、 ( K ) 唯一的条件，直接取表保留，把唯一的条件，直接取表保留，把I (K)限制在一个范围之内以便取表限制在一个范围之内以便取表32第6章 符号表混列表混列表-定义定义映像函数映像函数 I ( K )，1= I ( K ) = N 时，时， HASH 表本身有空白可用，做法是一旦表中不表本身有空白可用，做法是一旦表中不再插入新项了，就把溢出表移入表中。再插入新项了，就把溢出表移入表中。图示从略。图示从略。39第6章 符号表映像函数的构造：映像函数的构造：例：例：M = 128 = 2 7 , 设计设计 I，该表为，该表为 FORTRAN 的符号表，以字的符号表，以字母开头，后跟母开头，后跟

28、 1 5 个字母或者数字，这样一共有个字母或者数字，这样一共有26 * 365 个标个标识符，他们映像到识符，他们映像到 0 127 表项中表项中 (用用 8 进制表示进制表示)： A Z 41 72 0 9 20 31 空白空白 01如如 标识符标识符 CAT2 能用能用 100011 100001 110100 43 41 64 22 01 01 C A T 2 |_| |_|表示。由于表项表示。由于表项 128 项，要产生项，要产生 7 位二进制数字作为结果的映像位二进制数字作为结果的映像函数，目标均匀。函数，目标均匀。总时间总时间 = 计算计算 I + 查找长度查找长度取舍策略：取舍策

29、略： 宁可要差的函数；不要大的查找长度宁可要差的函数；不要大的查找长度40第6章 符号表方法：方法：11，最简单法，截取，最简单法，截取 头头 7 位二进制位作为位二进制位作为 I 的结果的结果 得到得到 1000111所有字母都是以1开头,取开头7 位二进制位,这样得到的都是大于1000000,所以都是大于64,只使用64127的登记项.这样063的登记项就浪费了41第6章 符号表方法：方法：2取取 2 8 位位结果是结果是: : 这样的符号表很有规则这样的符号表很有规则, , 与字与字母母 顺序相同顺序相同,A B C .O ,A B C .O 在表前半部在表前半部. . P Q R.Z

30、P Q R.Z 在表后半部在表后半部方法：方法：2取取 6 12 位位A B C D E F G H . 100010 100100 100110 101 000100001 100011 100101 100111 结果: A C E在表后半部 B D F在表前半部4, 4, 选和选和5 5，除法，除法6 6，平方取中，平方取中, ,结果较好结果较好其他方法：其他方法：6.3 名字的作用范围名字的作用范围 一，名字的作用域一，名字的作用域1，允许在同一程序中，把同一标识符多次说明为不同的名字，允许在同一程序中，把同一标识符多次说明为不同的名字，这些名字可以具有不同的属性，且通常应该存贮在不同

31、的位置；这些名字可以具有不同的属性，且通常应该存贮在不同的位置；2，符号表的职责就是要区别同一标识符的不同说明；，符号表的职责就是要区别同一标识符的不同说明；3，有限的作用域给了编译程序允许符号表登记项共享空间的，有限的作用域给了编译程序允许符号表登记项共享空间的机会：机会： 词法分析词法分析 优化优化 标识符标识符 符号表指针符号表指针 真实地址真实地址 源源 中间代码中间代码 目标代码目标代码 下面讨论如何在符号表中表示作用域下面讨论如何在符号表中表示作用域45第6章 符号表二，二，FORTRAN 的符号表组织：的符号表组织：特点：特点： 模块结构模块结构分块编译，局部量在本块编译完后，就

32、可以消失，全局量不能消失分块编译，局部量在本块编译完后，就可以消失，全局量不能消失1， 一遍扫描：一遍扫描：一段编译完成后，局部名表可以重用，不存在重名问题；一段编译完成后，局部名表可以重用，不存在重名问题；注意：注意： A，一段完了，重置，一段完了，重置 AVAIL 到头；到头； B，新填项时候注意，当，新填项时候注意，当 AVAIL1 = AVAIL2 的时候，全部的时候，全部局部名信息切除（表区已满）局部名信息切除（表区已满）NAMEINFORMATIONNAMEINFORMATIONAVAIL1AVAIL2局部名表全局名表46第6章 符号表2， 多遍扫描：多遍扫描：处理完一段之后，应该

33、把它的局部名表保存到外存中，因为后续遍要处理完一段之后，应该把它的局部名表保存到外存中，因为后续遍要用用注意：注意：1， 由于符号表的现行局部名表是可覆盖的，当词法分析后，名字的由于符号表的现行局部名表是可覆盖的，当词法分析后，名字的字符串已经由符号表的指针代替，不同目标段中，同一指针代表不同字符串已经由符号表的指针代替，不同目标段中，同一指针代表不同的登记项，此时，名字栏也无用，如果保存到外存，可去掉它。的登记项，此时，名字栏也无用，如果保存到外存，可去掉它。NAMEINFORMATION各段局部名表开始位置局部名表在主存47第6章 符号表ALGOL 的符号表组织：的符号表组织：特点：分程序

34、结构，标识符说明有最近嵌套原则，当遇到某一个标识特点：分程序结构，标识符说明有最近嵌套原则，当遇到某一个标识符符 NAME 的时候，必须弄清哪一个最内层分程序有的时候，必须弄清哪一个最内层分程序有 NAME 的说明。的说明。1，需要一种数据结构，它使当前活动的名字能够从其中找到它所属的，需要一种数据结构，它使当前活动的名字能够从其中找到它所属的分程序或者未定义的结论；另一方面，对以后几遍还要用的但现在不分程序或者未定义的结论；另一方面，对以后几遍还要用的但现在不再活动的名字信息，不能让他们没有留下什么踪迹就消失。再活动的名字信息，不能让他们没有留下什么踪迹就消失。2，一般的想法：把符号表分，一

35、般的想法：把符号表分 2 区间，当分程序结束时，它的登记项从区间，当分程序结束时，它的登记项从活动区移到不活动区。即：活动区移到不活动区。即：活名区活名区和和死名区死名区48第6章 符号表程序例子：程序例子：B1: begin B2: beginB3: beginend;end; B4: begincurrentend;end49第6章 符号表处理到 B1中的 current 的时候的符号表情形 （杂凑链法）：SYMSYM的信息的信息分程序分程序 B1B1的名的名字字分程序分程序 B4B4的名的名字字SYMSYM的入口的入口分程序分程序 B2B2的名的名字字分程序分程序 B3B3的名的名字字S

36、YMB1 ( n1 )B1 ( n1 )B4 ( n4 )B4 ( n4 )B2 ( n2 )B2 ( n2 )B3 ( n3 )B3 ( n3 )AVAILENDBP1BP2BLOCK TABLESYMBOL TABLEHASH TABLECHAR STRINGCSPINFORMATION50第6章 符号表 填表：把填表：把名字 XYZ 加入表 p H ( XYZ) = h现行分程序层外层查找方向（沿着有相同杂凑值构成的链查找没找到！没找到！AVAILAVAIL由串由串XYZ形成的新表项形成的新表项HASH TABLE现行分程序层51第6章 符号表 查找查找首先找到的那个项就是我们要找的项首

37、先找到的那个项就是我们要找的项为什么？为什么？52第6章 符号表 进入分程序要做的工作进入分程序要做的工作需要在分程序表 BLOCKTABLE 中的活动区指示点 BP1 处增设一个新项。这个新项包括 2 个指示器，一个指向符号表活端空白区的现行位置（即 AVAIL 的现行值），另一个指向字符串数组空白区的现行位置（即取 CSP的现行值 ）；并附设一个计数器，准备累计新分程序层内的局部各个数。由于分程序的嵌套性，所以，符号表，分程序表和字符串数组本质上都是作为栈使用的。 退出分程序要做的工作退出分程序要做的工作B1: beginB2: beginB3: begin end; end;B4: be

38、gincurrentend;end以右边程序段的 B4 为例说明：53第6章 符号表1，把分程序表中的 B4 移到 BP2 所指的一端。把它指向符号表的指示器改为指向符号表 END 所指的位置。2，把符号表中现行分程序 B4 所属的项全部移到死端 END 所指的位置。当把符号表的项从活端移到死端时必须把他们和杂凑表的联系断开。因而需要搜索每条杂凑链，从每条链中去掉所有属于 B4 的项（他们全在链的首部），然后让链头指向链的剩余部分。注意：去掉一个项名并不意味着除掉它在信息区的相应内容。我们已经说过，在中间代码中，代表项名的指示器实际上是指向信息区的。3，把 AVAIL 和 CSP 分别调回道进

39、入 B4 前的原值，即释放 B4 所占的符号表活端区和字符串数组空间。54第6章 符号表6.4 符号表的内容符号表的内容符号表的信息栏中登记了每个名字的有关性质，如类型（整，实或 布尔等），种属（简单变量，数组，过程等），大小（长度，即所需的存储单元字数）以及相对数（指分配给该名字的存储单元的相对地址）。不同的程序设计语言对于名字性质的定义各有不同，符号名的性质可能在编译时候确定下来（说明语句或隐含约定），或者在目标程序运行时才能确定（没有说明语句也没有隐含约定的语言）。符号表中的信息栏的具体组织和安排取决于所翻译的具体语言与目标机器55第6章 符号表参考文献参考文献参考文献参考文献1 1，Kenneth Kenneth C.LoudenC.Louden, ,冯博琴译，冯博琴译，编译原理与实践编译原理与实践，机械工业，机械工业出版社，出版社，P227-P264;P227-P264;2,2,严尉敏，严尉敏，数据结构与算法数据结构与算法，清华大学出版社，清华大学出版社，HashHash表部分与表部分与Binary Tree Binary Tree 部分。部分。57第6章 符号表