编译原理第8章.ppt

第八章符号表 编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息 这些信息通常记录在一张或几张符号表中 符号表的每一项包含两部分 一部分是名字 标识符 另一部分是此名字的有关信息 每个名字的有关信息一般指种属 如简单变量 数组 过程等 类型 如整 实 布尔等 等等 编译过程中 每当扫描器识别出一个单词后 编译程序就查阅符号表 看它是否已在其中 如果它是一个新名就将它填进表里 它的有关信息将在词法分析和语法 语义分析过程中陆续填入 本章内容概要 符号表的组织和作用符号表的作用符号表的组织方式整理与查找线性表对折查找与二叉树杂凑技术名字的作用范围符号表的内容 符号表的组织和作用 符号表的信息栏中登记了每个名字的有关性质 如类型 整 实或布尔等 种属 简单变量 数组 过程等 大小 长度 即所需的存储单元字数 以及相对数 指分配给该名字的存储单元的相对地址 不同的程序语言对于名字性质的定义各有不同 符号表的性质须到目标程序运行时才能确定下来 每当编译程序碰到一个新名时就按其语义将它登记在符号表的某一端中 符号表的作用 概括地说 一张符号表的每一项 或称入口 包含两大栏 或称区段 字域 即名字栏和信息栏 表格的形式是 对于编译程序的符号表来说 它所涉及的基本操作大致可归纳为五类 1 对给定名字 确定此名是否在表中 2 填入新名 3 对给定名字 访问它的有关信息 4 对给定名字 填写或更新它的某些信息 5 删除一个或一组无用的项 不同种类的表格所涉及的操作往往也是不同的 上述五方面只是一些基本的共同操作 符号表的组织方式 符号表最简单的组织方式是让各项各栏所占的存储单元的长度都是固定的 这种项栏长度固定的表格易于组织 填写和查找 对于这种表格 每一栏的内容可直接填写在有关的区段里 例如 有些语言规定标识符的长度不得超过8个字符 于是 我们就可以用两个机器字作为主栏 假定每个机器字可容四个字符 每个名字直接填写在主栏中 若标识长度不到8个字符 则用空白符补足 这种直接填写式的表格形式如下 但是 有许多语言对标识符的长度几乎不加限制 或者说 标识符的长度范围甚宽 譬如说 最长可容许由100个字符组成的名字 在这种情况下 如果每项都用25个字作主栏 则势必会大量浪费存储空间 因此 最好用一个独立的字符串数组 把所有标识符都存放在其中 在符号表的主栏放一个指示器和一个整数 指示器指出标识符在字符串数组中的位置 整数代表此标识符的长度 这样 符号表的结构就如下图所示 编译开始时 符号表或者是空的 或者预先存放了一些保留字和标准函数名的有关项 在整个编译过程中 符号表的查填频率是非常高的 编译工作的相当一大部分时间是花费在查填符号表上 所以 研究表格结构和查填方法是一件非常重要的事情 下面 我们简略地介绍几种一般的表格构造法和查填法 整理和查找 编译开始时 符号表或者是空的 或者预先存放了一些保留字和标准函数名的有关项 在整个编译过程中 符号表的查填频率是非常高的 编译工作的相当一大部分时间是花费在查填符号表上 符号表作为一个多元组 表中元组之间的排列组织是构造符号表的重要成分 在编译程序的整个工作过程中 符号表被频繁也用来建立表项 查找表项 填充和引用表项的属性 因此表项的排列组织对该系统运行的效率起着十分重要的作用 在整个编译过程中 符号表的查填频率是非常高的 编译工作的相当一大部分时间是花费在查填符号表上 所以 研究表格结构和查填方法是一件非常重要的事情 符号表的三种构造法和处理法 即线性查找 二叉树和杂凑技术 第一种办法最简单 但效率低 二叉树的查找效率高一些 然而实现上略困难一点 杂凑表的效率最高 线性表 这种方法规定符号表项中按它的符号被扫描到的先后顺序建立 例如有一程序中出现符号的情况如下 则符号表中表项排列如下 其中h表示该符号表之表头 是表的开始位置 p表示该符号表的表项是符号表当前的结束位置 在编译程序工作过程中 扫描得到之新符号总是登入到p的位置 而p又取下一新位置 编译程序开始工作时p处于h表头位置 线性组织方式在 数据结构 的讨论中可知它的管理简单但运行效率低 特别当表项数目较大后效率就非常低 因为它没有空白项 因此存储空间效率高 但对于符号个数不确定的情况下 无法事先确定该符号表的总长度 对于事先能确定符号个数且符号个数不大 公认为小20 时采用线性表组织是非常合适的 对折查找与二叉树 二叉树的查找效率高一些 然而实现上略困难一点 语言中任何符号都是由一个或几个字符拼写而成的 在机器中是用字符代码 通常是ASCII或EBCDIC代码 表达 因每一个符号在机器内都是由这种字符代码串来表示 排序组织的符号表 就是在符号表中的表项按其符号的字符代码串 可以看成一个整数值 的值的大小从大到小 或从小到大 排列的 如下是一个按排序组织得到的符号表 对排序表的表项建立及符号查找 通常采用 二分法 排序表的空间组织和存储开销与线性表基本相同 但排序表的运行效率要比线性表高 算法复杂性也高于线性表 排序表有很多变形结构方式 如二叉树结构等 也在编译程序中可根据空间开销和运行效率等要求作适当的选取 杂凑技术 杂凑法是一种争取查表 填表两方面都能高速进行的统一技术 这种办法是 假定有一个足够大的区域 这个区域是以填写一张含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的余数就是一个相当理想的函数 注意 杂凑函数的选择往往和具体计算机系统的字符编码有关 如果是对数目确定的已知符号名 我们可以通过试验 精挑细选 构造出一个一一对应函数 如果杂凑函数是用来产生用户的标识符表的 由于用户使用标识是随机的 而且标识符的个数也是无限的 虽然在一个源程序中所有的标识符的全体是有限的 因此 企图构造一一对应的函数当然是徒劳的 在这种情况下 除了希望函数值的分布比较均匀之外 我们还应没法解决 地址冲突 的问题 解决地址冲突的办法很多 我们这里只介绍一种最简单的线性查填解决法 这种办法的填表过程是 对任何名字SYM 令H SYM h 若第h项为空 则直接把SYM填入 若h项不空 则看第h 1 modN 项 为空则填入 否则继续考察第h 2 modN 项 如此反复 直至或者把SYM填为第h i modN 项 或者到达h N h modN 说明表区已满 无法再填入 查表过程与此相仿 令H SYM h 若第h项为空 则说明SYM不在表中 若SYM等于第h项的名字 则宣布查找成功 且SYM的项数为h 否则 继续考察第h 1 modN 项 如此反复 直至或者在第h i modN 项中找到SYM 或者h i modN 项为空 说明SYM不在表中 或者到达h N h modN 同样说明SYM不在表中 详细的组织和算法在有关 数据结构 的书中可找到 名字的作用范围 在许多程序设计语言中 名字往往有一个确定的作用范围 例如 FORTRAN中 变量 数组和语句函数的名字的作用范围是它们所处的程序段 主程序段 子程序段或函数段 而外部名 公用区名和过程名的作用范围则是整个程序 对于过程嵌套结构型的程序设计语言 每层过程中说明的名字只局限于该过程 离开了所在过程就无意义了 因此 名字的作用范围是和所处的那个过程相联系的 符号表的内容 符号表的信息栏中登记了每个名字的有关性质 如类型 种属 大小以及相对数 不同的语言对于名字