编译原理第八章符号表.doc

第八章 符号表编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息这些信息通常记录在一张或几张符号表中符号表的每一项包含两部分，一部分是名字（标识符） ，另一部分是此名字的有关信息每个名字的有关信息一般指种属（如简单变量、数组、过程等） 、类型（如整、实、布尔等）等等这些信息将使用于语义检查、产生中间代码以及最终生成目标代码等不同阶段编译过程中，每当扫描器识别出一个单词后，编译程序就查阅符号表，看它是否已在其中如果它是一个新名就将它填进表里它的有关信息将在词法分析和语法-语义分析过程中陆续填入符号表中所登记的信息在编译的不同阶段都要用到在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否相一致）和产生中间代码在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据对于一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同因为每遍所关心的信息各有差异本章重点：符号表的一般组织和使用方法第一节 符号表的组织和使用概括地说，一张符号表的每一项（或称入口）包含两大栏（或称区段，字域） ，即名字栏和信息栏表格的形式是：信息栏通常包含许多子栏和标志位，用来记录相应名字的种种不同属性。

由于查填符号表一般都是通过匹配名字来实现的，因此，名字栏也称主栏主栏的内容称为关键字（key word） 虽然原则上说，使用一张统一的符号表也就够了，但是，许多编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等这是因为，不同种属名字的相应信息往往不同，并且信息栏的长度也各有差异的缘故因而，按不同种属建立不同的符号表在处理上常常是比较方便的对于编译程序的符号表来说，它所涉及的基本操作大致可归纳为五类：1、对给定名字，确定此名是否在有中；2、填入新名；3、对给定名字，访问它的有关信息；4、对给字名字，填写或更新它的某些信息；5、删除一个或一组无用的项不同种类的表格所涉及的操作往往也是不同的上述五方面只是一些基本的共同操作 符号表最简单的组织方式是让各项各栏所占的存储单元的长度都是固定的这种项栏长度固定的表格易于组织、填写和查找对于这种表格，每一栏的内容可直接填写在有关的区段里例如，有些语言规定标识符的长度不得超过 8 个字符，于是，我们就可以用两个机器字作为主栏（假定每个机器字可容四个字符）每个名字直接填写在主栏中。

若标识长度不到 8 个字符，则用空白符补足这种直接填写式的表格形式如下：符 号 表NAME INFORMATIONSAMPLE …WEIGHT …但是，有许多语言对标识符的长度几乎不加限制，或者说，标识符的长度范围甚宽譬如说，名字栏（ NAME）信息栏（INFORMATION ）第 1 项（入口1）第 2 项（入口2）第 n 项（入口n）线性表符号 属性h→ abdcP→图 8-2-1 线性组织的符号表最长可容许由 100 个字符组成的名字在这种情况下，如果每项都用 25 个字作主栏，则势必会大量浪费存储空间因此，最好用一个独立的字符串数组，把所有标识符都存放在其中在符号表的主栏放一个指示器和一个整数指示器指出标识符在字符串数组中的位置；整数代表此标识符的长度这样，符号表的结构就如下图所示：这是一种用间接方式安排名字栏的办法类似地，如果各种名字所需的信息（INF-ORMATION）空间长短不一，那么，我们可把一些共同属性直接登记在符号表的信息栏中，而把某些特殊属性登记在别的地方，并在信息栏中附设一指示器指向存放特殊属性的地方编译开始时，符号表或者是空的，或者预先存放了一些保留字和标准函数名的有关项。

在整个编译过程中，符号表的查填频率是非常高的编译工作的相当一大部分时间是花费在查填符号表上所以，研究表格结构和查填方法是一件非常重要的事情下面，我们简略地介绍几种一般的表格构造法和查填法第二节 符号表项的排列与查找符号表作为一个多元组，表中元组之间的排列组织是构造符号表的重要成分在编译程序的整个工作过程中，符号表被频繁也用来建立表项，找查表项，填充和引用表项的属性因此表项的排列组织对该系统运行的效率起着十分重要的作用在“数据结构”技巧的讨论中提供了很多有关多元组表格的组织方法和它们有关的操作算法而在编译程序中，符号表项的组织传统上采用三种构造方法即线性法，二分法及散列法1、线性组织 这种方法规定符号表项中按它的符号被扫描到的先后顺序建立例如有一程序中出现符号的情况如下：…………………a…………………b………a…………………d………c…………………b…………则符号表中表项排列将如图 8-2-1其中 h 表示该符号表之表头，是表的开始位置，p 表示该符号表的表项是符号表当前的结束位置，在编译程序工作过程中，扫描得到之新符号总是登入到 p 的位置，而 p 又取下一新位置，编译程序开始工作时 p 处于 h 表头位置。

这种组织方式在“数据结构”的讨论中可知它的管理简单但运行效率低，特别当表项数目较大后效率就非常低因为它没有空白项，因此存储空间效率高，但对于符号个数不确定的情况下，无法事先确定该符号表的总长度对于事先能确定符号个数且符号个数不大（公认为小 20）时采用线性表组织是非常合适的符 号 表NAME INFORMATION• . 6L O O P S A M P L E W E I G H T字符串数组排序表符号 属性h→ abcdP→图 8-2-2 排序组织的符号表2、排序组织及二分法 语言中任何符号都是由一个或几个字符拼写而成的，在机器中是用字符代码（通常是 ASCII 或 EBCDIC 代码）表达因每一个符号在机器内都是由这种字符代码串来表示排序组织的符号表，就是在符号表中的表项按其符号的字符代码串（可以看成一个整数值）的值的大小从大到小（或从小到大）排列的对上述例 2 中的符号出现情况按排序组织得到的符号表将如图 8-2-2编译扫描的次序是 a,b,d,c由于 c 代码小于 d 代码，因此 c 应在 d 表项之前关于排序表的表项建立及符号查找，通常采用“二分法”详细的组织和算法在有关“数据结构”的书中可找到。

排序表的空间组织和存储开销与线性表基本相同，但排序表的运行效率要比线性表高，算法复杂性也高于线性表排序表有很多变形结构方式，如二叉树结构等，也在编译程序中可根据空间开销和运行效率等要求作适当的选取，这儿不去详细讨论，因为它不属编译范畴3、散列组织 对于表格处理来说，根本问题在于如何保证查表与填表两方面的工作都能高效地进行对于线性表来说，填表快，查表慢而对于二分法而言，则填表慢，查表快杂凑法是一种争取查表、填表两方面都能高速进行的统一技术这种办法是：假定有一个足够大的区域，这个区域是以填写一张含 N 项的符号表我们希望构造一个地址函数 H，对任何名字SYM， H（SYM）取值于 0 至 N—1 之间这就是说，不论对 SYM 查表或填表，我们都希望能从H（SYM ）获得它的表中的位置例如，我们用无符号整数作为项名，令 N=17，把 H（SYM）定义为 SYM÷N 的余数那么，名字 ˋ09ˊ将被置于表中的第 9 项，ˋ34ˊ 将被置于表中的第 0 项，ˋ171ˊ将被置于表中的第 1 项，如此等等对于地址函数 H 有两点要求：第一，函数的计算要简单、高效；第二，函数值能比较均匀地分布在 0 至 N—1 之间。

例如，若取 N 为质数，把 H（SYM）定义为 SYM÷N 的余数就是一个相当理想的函数构造函数 H 的办法很多，通常是将符号名的编码杂凑成 0~N~1 间的某一个值因此，地址函数 H 也常常称为杂凑函数注意，杂凑函数的选择往往和具体计算机系统的字符编码有关如果是对数目确定的已知符号名，我们可以通过试验，精挑细选，构造出一个一一对应函数如果杂凑函数是用来产生用户的标识符表的，由于用户使用标识是随机的，而且标识符的个数也是无限的（虽然在一个源程序中所有的标识符的全体是有限的） ，因此，企图构造一一对应的函数当然是徒劳的在这种情况下，除了希望函数值的分布比较均匀之外，我们还应没法解决“地址冲突”的问题以 N=17，H（ SYM）为 SYM÷N 的余数为例，由于 H（ˋ 05ˊ）= H（ˋ22ˊ）=5，若表格的第 5 项已为ˋ05ˊ所占，那么，后来的ˋ22ˊ应放在哪里呢？解决地址冲突的办法很多我们这里只介绍一种最简单的线性查填解决法这种办法的填表过程是：对任何名字 SYM，令 H（SYM）=h，若第 h 项为空，则直接把 SYM 填入若 h 项不空，则看第 h+1（mod N）项，为空则填入，否则继续考察第 h+2（mod N）项，如此反复，直至或者把SYM 填为第 h+i（mod N）项；或者到达 h+N=h（mod N） （说明表区已满） ，无法再填入。

查表过程与此相仿：令 H（SYM）=h ，若第 h 项为空，则说明 SYM 不在表中，若 SYM 等于第 h 项的名字，则宣布查找成功，且 SYM 的项数为 h否则，继续考察第 h+1（mod N）项如此反复，直至或者在第 h+i（ mod N）项中找到 SYM；或者 h+i（mod N）项为空，说明 SYM 不在表中；或者到达 h+N= h（mod N） ，同样说明 SYM 不在表中详细的组织和算法在有关“数据结构”的书中可找到第三节 习题一、单项选择题1、编译程序使用 区别标识符的作用域a. 说明标识符的过程或函数名 b. 说明标识符的过程或函数的静态层次c. 说明标识符的过程或函数的动态层次 d. 标识符的行号2、在目标代码生成阶段，符号表用于 a. 目标代码生成 b. 语义检查 c. 语法检查 d. 地址分配3、过程信息表不包含 a. 过程入口地址 b. 过程的静态层次 c. 过程名 d. 过程参数信息4、下列关于标识符和名字叙述中，正确的是 a. 标识符有一定的含义 b. 名字是一个没有意义的字符序列c. 名字有确切的属性 d. a~c 都不正确解答：1、b 2、d 3、b 4、c二、多项选择题1、符号表的每一项均包含 。

a. 名字栏 b. 类型栏 c. 信息栏 d. 值栏 e. a~d 均包含2、对编译程序所用到的符号表，涉及的操作有 a. 填写或更新信息栏内容 b. 填入新名 c.给定名字，访问它的有关信息d. 杂凑技术 e.线性表和排序二叉树3、源程序中的错误一般有 a. 词法错误 b. 语法错误 c. 语义错误d. 编译错误 e. 违反环境限制的错误解答：1、a 、c 2、a 、b、 c 3、a、b、c、e三、填空题1、符号表中名字栏内容有两种填写方式，它们是 填写和 填写2、词法分析阶段的错误主要是 ，可通过 的办法纠正错误3、符号表中名字的有关信息在 和 过程中陆续填入4、在目标代码生成阶段，符号表是 的依据解答：1、标识符 标识符地址及长度 2、拼写错误 最小距离匹配 3、词法分析 语法语义分析4、地址分配四、问答题：1、在编译过程中为什么要建立符号表？解答：在编译过程中始终要涉及到对一些语法符号的处理，这就需要用到语法符号的相关属性为了在需要时能找到这些语法成分及其相关属性，就必须使用一些表格来保存这些语法成分及其属性，这些表格就是符号表。