1、第7章 符号表,1,第6章 符号表,2,6.1.1 符号表项的域理论上，符号表只是一个具有名字域和信息域这2个域的表,大致结构如下:,第一项（入口1）,第二项（入口2）,第n项（入口n）,第7章 符号表,3,我们要求它具备以下几种功能：1，确定一个给定的名字是否在表中；2，填入新的名字；3，访问所给名字的有关信息；4，对给定的名字，填写和更新它的有关息；5，删除一个或者一组名字,第7章 符号表,4,7.1.2 分表语言中，名字表示各种类型的对象：变量名，过程名，常数，域名（结构），标号等，由于各种类型的名字因用法不同，栏目及所需的空间相差很大，因此往往独立建表，由此带来的负面影响是：导致零头太
2、多。如果登记项格式可以变化，则另外一个表也可以；如果禁止把关键字作为标识符，则应把关键字先进表，标函也进表.,第7章 符号表,5,7.1.3 符号表内容的细目 1，表示名字的字符串+编号，如果多个程序块或过程中可以使用同一标识符，则必须指出这个名字属于哪一个程序块或过程；2，名字的属性（包括类型和种类）以及识别名字用途的信息（标号， 形参，数组）3，参数（维数，下标的上下界）4，描述分配给名字存储单元的位置的偏移量,第7章 符号表,6,7.1.4 符号表登记项的建立 a, 符号表名字何时建立：1，词法分析。当识别了一个标识符时，它可以建 立，不能填充种类，类型等； install 子程序返回（
3、$ID, 符号表指针）；2，但是当一个名字在同一个程序块或过程中，可用作标号、实型变量、域名时，词法只能返回（$ID, TOKEN），由语法分析程序为标识符建表,第7章 符号表,7,b, 这些信息在不同的时刻插入符号表：1，遇到显式说明时，把属性插入；2，语法可以隐含的说明变量的某种用途，如标号后的 ： ，所以和产生式 语句- id:语句 相关的语义动作是把 id 为标号的事实插入符号表，标号链，定义否填入；3，地址分配；类似，过程说明的语法告诉我们某些名字是形参。,第7章 符号表,8,7.1.5 名字和符号表记录 实现表的最简单方式是看成记录的线性数组，每一栏目所占存储单元长度不变，每个名字
4、对应一个记录，记录通常由已知个连续的存储字组成。,标识符信息标识符信息,图6.1(a) 存储标识符在记录中,第7章 符号表,9,图7.1(b) 名字存储在分开的数组中,第7章 符号表,10,1，当一个名字的最大长度不太长时，如FORTRAN为8字符， 用2个字存储，其余补空；2，ALGOL 名字不限， PL/1 31个（8个字）， 则采用间接方式，专门字符数组，这样使表的名字域大小不变；对于其他的域也可以这样办理，(技术性工作).,第7章 符号表,11,把整个符号表分成若干子表,NAME:0:,2(i-1):,4(i-1):,INFORMATION:0:,例子：分两个子表的符号表安排,第7章
5、符号表,12,7.1.6 符号表空间的重新使用符号表占用空间很大，且信息更新，故有重新使用空间的问题，那些空间不可用呢？程序员用来表示名字的标识符，必须一直保存在符号表中，直到不再引用为止，以便该标识符只能代表同一个名字，这是必要的，它使标识符的所有使用与符号表登记项相结合（表中有的内容在以后不再使用了），从而是同一个名字。但是，如果用来存放标识符的空间在下一次能重新使用，那么用少量空间就能解决问题。,第7章 符号表,13,例如，在以后几遍中，放名字的数组可以释放，所以设法回收用来存储标识符的空间，（事实上，图7.1b 第一字也能回收）方法：用两个而不是一个数组来存放记录,如不查表，可释放,2
6、i-12i,IDENTIFIERS:,INFORMATION:,两个数组的符号表方案(7.1a 一分为二),4i-34i,注意：DIMPLE的外部表示不再是符号表的指针，而是整数下标i,此时，用i来存取另一数组,第7章 符号表,14,有效地加入新项和找出有关项，本节主要讨论三种机制：,1,线性表2，树3，散列表,7.2.1 线性表,记录的线性表,Available,第7章 符号表,15,线形表的效率估计 插入名字的工作量与表长 n 成正比查找的工作量平均 n/2访问的工作量与表长 n 成正比.,第7章 符号表,16,以少量额外空间为代价，在每一个记录中增加一个Link域，并按Link域指示的顺
7、序检索表设定First指出第一个记录的位置，Link指出下一个记录：,链式结构的自适应表,第7章 符号表,17,1，自适应表Link 的原则,指示器把所有的项按“最新最近”访问原则连结成一条链使得在任何的时候，这条链的第一元素所指的项是最近被查询过的项，第二个元素是次新查询过的项依据是 ： 刚刚被访问过的项以最大概率被继续访问,第7章 符号表,18,2，做法,当引用一个名字或者当第一次建立该名字的纪录时，我们通过移动指针把名字纪录移到表的前部，下图说明把NAME4纪录移到头上（NAME4刚刚被引用），原来的链是3142，现在改为4312,(a)3,1,4,2,(b)4,3,1,2,第7章 符号
8、表,19,3，算法：可以写出把NAME i 移到头上来的算法,原来的情况如此，现在开始改变让FIRST i,r,q,i,q,第7章 符号表,20,算法：1，若Link p = i， 则记下 p ; 若Link i = q， 则q Link p ; /这样，i 就脱离了2，若原FIRST r， 则记 r Link i ;3, 让FIRST i;,第7章 符号表,21,二，折半查找,1，方法：为了提高查表速度，在造表的同时把表中的项按名字的“大小”顺序整理，所说名字的“大小”，通常是指名字的内码二进制值。若规定由小 大，那么对任何要找的名字来说，无论相对哪一个参考点，我们总可以知道要找的名字在参考
9、点的前面还是后面。因此一个简单的算法是每次都把参考点定在中间。我们已经知道，对 N 项名表，查找的平均长度为log2N (2为底数)这较其线性查找，已经提高了许多，若1024项，是10：512,第7章 符号表,22,进一步的改进,不在表的中间进行试查，而是对每步的试查位置作较准确的推断，若要在下表中查名字CAT，查2/26 处似更合理一些，猜测的好坏和对名表的了解程度有关，若能知符号表中的每个字母开头的词有多少，就能有一个校准的初始推测。在编译中，带有实际的名字项是取自整个名字集中的一个非随机子集，并知道它们的某种总的信息。Peterson 证明： 平均查找长度大约等于(1/2)*log2N，
10、如1000项是 5 次。,第7章 符号表,23,评价,尽管如此，编译器不愿意采用它，它的致命弱点是，添加一项就要重新整理，使它按序。因此对于名字表不合适。但是对于固定的表，如定义符表等就很有用。（插入固定表）,第7章 符号表,24,再改进,把符号表组织成一个二叉树，每一项是一个节点节点组成：,第7章 符号表,25,构造过程：,这样构造的树，保持任何结点 P 右枝的所有结点值小于结点 P 的值，而 P 左枝的所有结点值大于结点 P 的值： P 值 P 右枝的所有结点值.,再加入名字 LMN: ABCD LMN ABCD 置于左； 因为 ABAA ABCD 置于右,根结点：第一个遇到的名字，此时，
11、左右指示器为 null.,root,root,第7章 符号表,26,评价,优点,二叉树与对折查找的效率比较：附设左右指示器，耗费空间，每查找一项所要的比较次数仍然和log2N 成比例,顺序化整理工作十分简单,第7章 符号表,27,思考：,表格处理包括填 查表，要两者快才好，但线性表和折半法只能占一边，能否找到更好的办法？,先在一个限制比较多的情况下讨论,第7章 符号表,28,三，直接取表法,K 表位置若名字的第一个字母都不一样，那么我们用一个 26 元的向量作符号表。设映像函数 I( K ) 对每一个名字 K， I( K ) 就是 K 的第一个字母在字母表中的位置K +表头 100 : I(
12、K ) = 100+( K )*l,第7章 符号表,29,优点：,这个方法查填都很快，一次就行，函数唯一的时候，名字不需要存,缺点：,1，如果名字 26 字母也无效,然而，它给我们一个启示：利用函数关系， 查填表，构造,第7章 符号表,30,四，混列表 （hash table, computed entry table, scatter table）,特点：去掉表长度 26 的限制，去掉名字字母构成的限制.映像函数定义为： I ( k ) 产生的唯一的一组整数，即对任何关键字 k1 != k2, 有 I ( K1) != I ( K2 );一般说来 I ( K ) 可能值的范围较大，导致无法存
13、取表;于是放弃 I ( K ) 唯一的条件，直接取表保留，把I (K)限制在一个范围之内,以便取表.,第7章 符号表,31,混列表-定义,映像函数 I ( K )，1= I ( K ) = N 时， HASH 表本身有空白可用，做法是一旦表中不再插入新项了，就把溢出表移入表中。图示从略。,第7章 符号表,38,映像函数的构造：,例：M = 128 = 2 7 , 设计 I，该表为 FORTRAN 的符号表，以字母开头，后跟 1 5 个字母或者数字，这样一共有26 * 365 个标识符，他们映像到 0 127 表项中 (用 8 进制表示)： A Z 41 72 0 9 20 31 空白 01如
14、标识符 CAT2 能用 100011 100001 110100 43 41 64 22 01 01 C A T 2 |_| |_|表示。由于表项 128 项，要产生 7 位二进制数字作为结果的映像函数，目标均匀。,总时间 = 计算 I + 查找长度取舍策略： 宁可要差的函数；不要大的查找长度,第7章 符号表,39,方法：1,1，最简单法，截取 头 7 位二进制位作为 I 的结果 得到 1000111,所有字母都是以1开头,取开头7 位二进制位,这样得到的都是大于1000000,所以都是大于64,只使用64127的登记项.这样063的登记项就浪费了,第7章 符号表,40,方法：2,取 2 8
15、位,结果是: 这样的符号表很有规则, 与字母 顺序相同,A B C .O 在表前半部. P Q R.Z 在表后半部,第7章 符号表,41,方法：3,取 6 12 位,A B C D E F G H . 100010 100100 100110 101 000100001 100011 100101 100111,结果: A C E在表后半部 B D F在表前半部,第7章 符号表,42,4, 选和5，除法6，平方取中,结果较好,其他方法：,第7章 符号表,43,7.3 名字的作用范围,一，名字的作用域1，允许在同一程序中，把同一标识符多次说明为不同的名字，这些名字可以具有不同的属性，且通常应该存
16、贮在不同的位置；2，符号表的职责就是要区别同一标识符的不同说明；3，有限的作用域给了编译程序允许符号表登记项共享空间的机会： 词法分析 优化 标识符 符号表指针 真实地址 源 中间代码 目标代码 下面讨论如何在符号表中表示作用域,第7章 符号表,44,二，FORTRAN 的符号表组织：,特点： 模块结构分块编译，局部量在本块编译完后，就可以消失，全局量不能消失1， 一遍扫描：一段编译完成后，局部名表可以重用，不存在重名问题；注意： A，一段完了，重置 AVAIL 到头； B，新填项时候注意，当 AVAIL1 = AVAIL2 的时候，全部局部名信息切除（表区已满）,局部名表,全局名表,第7章
17、符号表,45,2， 多遍扫描：处理完一段之后，应该把它的局部名表保存到外存中，因为后续遍要用注意：1， 由于符号表的现行局部名表是可覆盖的，当词法分析后，名字的字符串已经由符号表的指针代替，不同目标段中，同一指针代表不同的登记项，此时，名字栏也无用，如果保存到外存，可去掉它。,各段局部名表开始位置,局部名表在主存,第7章 符号表,46,ALGOL 的符号表组织：,特点：分程序结构，标识符说明有最近嵌套原则，当遇到某一个标识符 NAME 的时候，必须弄清哪一个最内层分程序有 NAME 的说明。1，需要一种数据结构，它使当前活动的名字能够从其中找到它所属的分程序或者未定义的结论；另一方面，对以后几
18、遍还要用的但现在不再活动的名字信息，不能让他们没有留下什么踪迹就消失。2，一般的想法：把符号表分 2 区间，当分程序结束时，它的登记项从活动区移到不活动区。即：活名区和死名区,第7章 符号表,47,程序例子：B1: begin B2: beginB3: beginend;end; B4: begincurrentend;end,第7章 符号表,48,处理到 B1中的 current 的时候的符号表情形 （杂凑链法）：,AVAIL,END,BP1,BP2,BLOCK TABLE,SYMBOL TABLE,HASH TABLE,CHAR STRING,CSP,INFORMATION,第7章 符号表
19、,49,填表：把名字 XYZ 加入表,H ( XYZ) = h,没找到！,由串XYZ形成的新表项,HASH TABLE,第7章 符号表,50,查找,首先找到的那个项就是我们要找的项,为什么？,第7章 符号表,51,进入分程序要做的工作,需要在分程序表 BLOCKTABLE 中的活动区指示点 BP1 处增设一个新项。这个新项包括 2 个指示器，一个指向符号表活端空白区的现行位置（即 AVAIL 的现行值），另一个指向字符串数组空白区的现行位置（即取 CSP的现行值 ）；并附设一个计数器，准备累计新分程序层内的局部各个数。由于分程序的嵌套性，所以，符号表，分程序表和字符串数组本质上都是作为栈使用的
20、。,退出分程序要做的工作,B1: beginB2: beginB3: begin end; end;B4: begincurrentend;end,以右边程序段的 B4 为例说明：,第7章 符号表,52,1，把分程序表中的 B4 移到 BP2 所指的一端。把它指向符号表的指示器改为指向符号表 END 所指的位置。2，把符号表中现行分程序 B4 所属的项全部移到死端 END 所指的位置。当把符号表的项从活端移到死端时必须把他们和杂凑表的联系断开。因而需要搜索每条杂凑链，从每条链中去掉所有属于 B4 的项（他们全在链的首部），然后让链头指向链的剩余部分。,注意：去掉一个项名并不意味着除掉它在信息区
21、的相应内容。我们已经说过，在中间代码中，代表项名的指示器实际上是指向信息区的。,3，把 AVAIL 和 CSP 分别调回道进入 B4 前的原值，即释放 B4 所占的符号表活端区和字符串数组空间。,第7章 符号表,53,7.4 符号表的内容,符号表的信息栏中登记了每个名字的有关性质，如类型（整，实或 布尔等），种属（简单变量，数组，过程等），大小（长度，即所需的存储单元字数）以及相对数（指分配给该名字的存储单元的相对地址）。不同的程序设计语言对于名字性质的定义各有不同，符号名的性质可能在编译时候确定下来（说明语句或隐含约定），或者在目标程序运行时才能确定（没有说明语句也没有隐含约定的语言）。,符号表中的信息栏的具体组织和安排取决于所翻译的具体语言与目标机器,第7章 符号表,54,参考文献,1，Kenneth C.Louden,冯博琴译，编译原理与实践，机械工业出版社，P227-P264;2,严尉敏，数据结构与算法，清华大学出版社，Hash表部分与Binary Tree 部分。,
