符号表的组织与管理.ppt

1 第六章符号表 6 1符号表的作用6 2符号表的组织6 3符号表的建立和查找 2 学习目标 符号表作为编译系统的重要设施 贯穿于文法分析 检查和语义处理的编译全过程 本章目的使学生深刻全面地了解符号表的地位和作用 掌握符号表的组织和管理方法 以及编译过程中符号表的操作活动过程 3 学习指南 在编译程序中符号表用来存放源程序中出现的有关名字的属性信息 这些信息集中反映了名字的语义特征属性 符号表在编译全过程的地位和作用非常重要 是进行上下文合法性检查和语义处理及代码生成的依据 符号表总体结构的设计和实现是与源语言的复杂性 包括词法结构 语法结构的复杂性 有关 还与对于编译系统在时间效率和空间效率方面的要求有关 4 难重点 符号表总体组织的选择原则 变量的类型和存储类别等属性的重要性 采用单表结构时 如何解决分程序构造中同名名字声明的可视性规则 采用分表结构适合哪种语言的编译系统 5 6 1符号表的作用 在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息 这些信息集中反映了标识符的语义特征属性 在词法分析及语法在分析过程中不断积累和更新表中的信息 在词法分析到代码生成的各阶段 按各自的需要从表中获取不同的属性信息 不论编译策略是否分趟 符号表的作用和地位是完全一致的 6 根据编译程序工作阶段的不同划分 名字表中的各种信息将在编译程序工作过程中的适当时候填入 对于在词法分析阶段就建立符号表的编译程序 当扫描源程序识别出一个单词 名字 时 就以此名字查找符号表 若表中无此名的登记项 就将此名字填入符号表中 至于与此名相关的其它信息 可视工作方便分别在语法分析 语义分析及中间代码生成等阶段陆续填入 在语义分析时 符号表中的信息可以用于语义检查 在代码优化时 编译程序则利用符号表提供的信息选出恰当的代码进行优化 而目标代码生成时 编译程序将依据符号表中的符号名来分配目标地址 7 几乎在编译程序工作的全过程中 都需要对符号表进行频繁地访问 查表或填表 其耗费的时间在整个编译过程中占有很大的比例 因此 合理地组织符号表并相应选择好的查 填表方法是提高编译程序工作效率的有效办法 8 符号表的作用 收集符号属性上下文语义的合法性检查的依据作为目标代码生成阶段地址分配的依据 9 作用一 收集符号属性 编译程序扫描说明部分收集有关标识符的属性 并在符号表中建立符号的相应属性信息 例如 编译程序分析到下述两个说明语句intx y 5 floatw 则在符号表中收集到关于符号x的属性是一个整型变量 y是一个具有10个元素的整型数组 关于符号w的属性是浮点型简单变量 10 作用二 上下文语义的合法性检查的依据 同一个标识符可能在程序的不同地方出现 而有关该符号的属性是在这些不同情况下收集的 特别是在多趟编译及程序分段编译 在PASCAL及C中以文件为单位 的情况下 更需检查标识符属性在上下文中的一致性和合法性 通过符号表中属性记录可进行相应上下文的语义检查 11 例如 在一个C语言程序中出现intA 2 3 定义整型数组AfloatA 4 5 定义实型数组A 重定义冲突intA 2 3 定义整型数组A 重定义冲突 编译过程首先在符号表中记录了标识符A的属性是2 3个整型元素的数组 而后在分析第二 第三这两个定义说明时编译系统可通过符号表检查出标识符A的二次重定义冲突错误 本例还可以看到不论在后二句中A的其它属性与前一句是否完全相同 只要标识符名重定义 就将产生重定义冲突的语义错误 12 作用三 目标代码生成阶段地址分配的依据 每个符号变量在目标代码生成时需要确定其在存储分配的位置 主要是相对位置 语言程序中的符号变量由它被定义的存储类别 如在C FORTRAN语言中 或被定义的位置 如分程序结构的位置 来确定 首先要确定其被分配的区域 例如 在C语言中首先要确定该符号变量是分配在公共区 extern 文件静态区 externstatic 函数静态区 函数中static 还是函数运行时的动态区 auto 等 其次是根据变量出现的次序 决定该变量在某个区中所处的具体位置 这通常使用在该区域中相对区头的相对位置确定 而有关区域的标志及相对位置都是作为该变量的语义信息被收集在该变量的符号表属性中 13 符号的主要属性及作用 符号名变量名 函数名 过程名等 重载信息符号类型int float等 函数的类型看返回值符号的存储类型Common Static Auto Regist符号的作用域及可视性Public Private等符号变量的存储分配信息静态存储区 动态存储区符号的其他属性数组内情向量 结构成员信息 函数及过程的形参 14 1 符号名 语言中的一个标识符可以是一个变量的名字 一个函数的名字或一个过程的名字 每个标识符通常由若干个字符 非空格字符 组成的字符串来表达 符号表中设置一个符号名域 存放该标识符 该域通常就是符号表的关键字域 15 通常在语言程序中标识符字符串是一个变量 函数或过程的唯一标志 因此在符号表中符号名作为表项之间的唯一区别一般不允许重名 从而该符号名与它在符号表中的位置建立起一一对应之关系 使得我们可以用一个符号在表中的位置 通常是一个整数 来替换该符号名 通常把一个标识符在符号表中的位置的整数值称之谓该标识符的内部代码 在经过分析处理的语言程序中标识符不再是一个字符串而是一个整数值 这不但便于识别比较而且缩短了表达的长度 16 根据语言的定义 程序中出现的重名标识符定义将按照该标识符在程序中的作用域和可视性规则进行相应的处理 而在符号表运行过程中 表中的标识符名始终是唯一的标志 在一些允许操作重载 operatoroverload 的语言中 函数名 过程名是可以重名的 对于这类重载的标识符要通过它们的参数个数和类型以及函数返回值类型来区别 以达到它们在符号表中的唯一性 17 2 符号的类型 标识符中除过程标识符之外函数和变量标识符都具有数据类型 datatype 属性 对于函数的数据类型指的是该函数值的数据类型 基本数据类型有整型 实型 字符型 逻辑型 布尔型 及位组型等 符号的类型属性是在语言程序中该符号的定义中得到 变量符号的类型属性决定了该变量的数据在存储空间的存储格式 还决定了在该变量上可以施加的运算操作 18 随着程序设计语言的发展 语言中变量的类型也得到了扩充 目前大多数语言已定义了在基本数据类型基础上扩充的复合数据类型 复合数据类型有数组类型 记录结构类型等 它们都是由基本数据类型组合而成的 数组或记录结构中的每个基本元素可以是基本数据类型 也可以是其它任何一种组合式数据类型 构成嵌套式数据类型定义 作为存储变量地址的指针类型所指向的变量同样可以是基本数据类型 也可以是其它任何一种组合式数据类型 定义一个变量的基本数据类型或它的组合类型都是符号表中表示标识符属性的重要信息 符号表中设置一个符号类型域 存放该符号的类型 对复合数据类型 通常还需要设置该类型的扩展成分 以存放复合类型的完整的类型属性 19 3 符号的存储类别 大多数语言对变量的存储类别定义采用二种方式 一种是用关键字指定 例如在C语言中用static定义是属于文件的静态存储变量或属于函数内部的静态存储变量 用register定义使用寄存器存储的变量 一种方式是根据定义变量说明在程序中的位置来决定 例如在C语言中 在函数体外缺省存储类关键字所定义的变量是外部变量 即程序的公共存储变量 而在函数体内缺省存储类关键字所定义的变量是内部变量 即属于该函数所独有的私有存储变量 通常是动态分配的存储变量 20 符号表中设置一个符号存储类别域 存放该符号的存储类别 区别符号存储类型的属性是编译过程语义处理 检查和存储分配的重要依据 符号的存储类别还决定了符号变量的作用域 可视性和它的生命周期等问题 21 4 符号的作用域及可视性 一个符号变量在程序中起作用的范围 称谓它的作用域 一般来说 定义该符号的位置及存储类关键字决定了该符号的作用域 C语言中一个外部变量的作用域是整个程序 因此一个外部变量符号的定义在整个程序中只能出现一次 同名变量的说明可以出现多次那是为了使用和编译的方便 在函数外说明的定义的静态变量的作用域是定义该静态变量的文件 而在函数内部定义的静态变量其作用域仅仅是该变量定义所在的函数或过程中 与局部量不同的是 这些内部静态量在其作用域之外 仍然保持存在 一般来说一个变量的作用域就是该变量可以出现的场合 也就是说在某个变量作用域范围内该变量是可引用的 这就是变量可视性的作用域规则 22 其它两种情况影响到一个变量的可视性 函数的形式参数 inta 外部定义的整型变量aintfunc floata intb 函数内部定义的局部整型变量a 屏蔽了外部定义的整型变量a a 引用的是函数内部定义 此处是形参 的局部整型变量a a 引用inta 23 分程序 或复合语句 结构 inta 第一层头 定义的局部整型变量a chara 第二层头 定义的局部字符型变量a 第三层头 floata 第四层头 定义的局部实型变量a 第四层尾 a 引用第二层定义的局部字符型变量a 第三层尾 第二层尾 第一层尾 第三层所引用的a 不是第四层的floata 不是第一层inta 而是第二层chara 也就可以说从第三层向外 看到的第一个定义a的变量定义即chara 24 怎么确立符号的作用域和可视性 为确立符号的作用域和可视性 符号表属性中除了需要符号的存储类别之外还需要表示该符号在程序结构上被定义的层次 符号表中设置一个表达符号所在层次的属性域 存放该符号的定义层次 无论是作为函数形参的定义也好或作为分程序中的局部定义也好 都可统一地用定义层次来区分 一般来说 若把外部变量视为0层的话 则函数内部作为第1层 依次向内嵌套定义的分程序分别为2 3 层 在C语言程序中函数之间是并列定义的 因此每个函数内部都定义为第一层 而函数内的分程序也可以是并列定义的 对于并列定义的分程序当然具有相同的层次号 25 5 符号变量的存储分配信息 根据符号变量的存储类别定义及它们出现的位置和次序来确定每一个变量应分配的存储区及在该区中的具体位置 用相对区头的位移量表示 通常有两类存储区 即静态存储区和动态存储区 静态存储区该存储区单元经定义分配后成为静态单元 即在整个语言程序运行过程中是不可改变的 动态存储区根据变量的局部定义和分程序结构 编译程序设置动态存储区来适应这些局部变量的生存和消亡 局部即在该定义范围之外此变量已经没存在的必要 动态变量的生存期是定义该变量的局部范围 26 6 符号的其它属性 数组内情向量编译程序处理数组说明的主要工作是 把描述数组属性信息的内情向量登录到符号表中 内情向量包括数组类型 维数 各维的上 下界及数组首地址 这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据 记录结构型的成员信息一个记录结构型的变量 在存储分配时所占空间大小要由它的全体组成成员来确定 另外对于记录结构型变量还需要有它所属成员排列次序的属性信息 这二种信息用来确定结构型变量存储分配时所占空间的尺寸及确定该结构成员的位置 函数及过程的形参函数和过程的形参作为该函数或过程的局部变量 但它又是该函数或过程对外的接口 每个函数或过程的形参个数 形参的排列次序及每个形参的类型 都体现了调用该函数或过程时的属性 它们都应该反映在符号表的函数或过程标识符的项中 有关函数及过程的形参属性信息用来作调用过程的匹配处理和语义检查 27 对于编译程序所用的符号表来说 它所涉及的基本操作大致可以归纳为 往表中填入一个新标识符 对给定的标识符 查找它是否已在表中 访问它的有关信息 往表中填入或更新它在表中的某些信息 从表中删去一个或一组无用的项 28 6 2符号表的组织 语言中不同种类的符号 它们的属性信息种类不完全相同 而不同的程度也是不一样的 如语言关键字 保留词 的属性与变量符号属性信息相差太大 而变量符号的属性信息与函数或过程的属性也有相当大的差别 但对于像不同变量之间 如简单变量与数组或记录结构之间 的属性信息差别相对就小一些 按照处理对象的特点 符号表的组织方式一般可分为 直接方式和间接方式按照标识符的种属 符号表信息栏的组织方式 29 1 1直接方式 直接方式是指在符号表中直接填入源程序中定义的标识符及相关信息 Name 名字 栏的长度是固定的 这种栏目长度固定的表格易于组织 填写或查找 是最简单的一种符号表组织方式 30 1 2间接方式 间接方式是指单独设置一个字符串数组来存放所有的标识符 并在符号表的名字栏中设置两项内容 一 是指针 用来指向标识符在数组中的起始位置 二 是一整数值 用来表示该标识符的长度 31 间接组织方式的符号表 32 2 按照标识符的种属 把属性种类完全相同的那些符号组织在一起 构造出表项是分别为等长的多个符号表 如简单变量 数组 过程等分别建立不同的符号表 如简单变量名表 数组名表 过程名表等 33 intf inta intb intc if a b c 1 elsec 0 returnc 按标识符种属组织的各种符号表 a 简单变量名表 b 常数表 c 函数入口名表 34 根据符号表名字栏的组织特点 符号表信息栏的组织方式也可以分为两类 固定信息内容和仅记录信息存放地址 3 符号表信息栏的组织方式 固定信息内容如果名字栏中的标识符按种属分类 仅记录信息存放地址如果符号表的名字不分种属 35 3 1固定信息内容 如果名字栏中的标识符按种属分类 则因同类标识符其基本特征一致 故可将这些信息一一记录在信息栏中 类型 整 实 布尔 字符 指针等 长度 所需的存储单元数 相对地址 存储单元的相对地址 36 3 2仅记录信息存放地址 如果符号表的名字不分种属 则由于不同种属的标识符其特征不一致 也即它们所需存储的信息不一致 因而不容易确定一个固定长度的空间来统一安排 这时 可在符号表外另设一组存储空间 并在符号表信息栏中放一指针来指向这个存储空间始址 37 对数组标识符需要存储有关数组维数 每维上 下界值 数组类型及数组存放的起始地址等信息 如果将信息与名字一起全部放在符号表中 则因维数不同而使记录该信息的空间大小不易确定 因此 通常给它们另外安排一个内情向量表来记录数组的全部信息 同时在符号表的信息栏设置一指针指向内情向量的入口地址 此外 对像函数名 过程名等含有较多信息且不容易规范信息长度的名字都可以采取这种办法 38 记录数组内情向量的符号表 39 这样组织的最大优点是每个符号表的属性个数和结构完全相同 则表项是等长的 并且表项中的每个属性栏都是有效的 对于单个符号表示来说 这样使得管理方便一致 空间效率高 但这样组织的主要缺点是一个编译程序将同时管理若干个符号表 增加了总体管理的工作量和复杂度 而且对各类符号共同属性的管理必须设置重复的运行机制 使得符号表的管理显得臃肿 40 分程序结构语言的符号表建立 所谓分程序结构的语言 是指用这种语言编写的分程序中可以再包含嵌套的分程序 并且可以定义属于它自己的一组局部变量 由于分程序的嵌套导致名字作用域的嵌套 故有时也将允许名字作用域嵌套的语言称为具有分程序结构的语言 典型的分程序结构语言是PASCAL 虽然通常不把C语言视为嵌套分程序结构的语言 但在它的函数定义中 函数体可以是一个嵌套的分程序 因而其中所涉及的各个局部变量的作用域也具有嵌套特征 41 源程序的形式 第一层分程序inta floatb d 第二层分程序intc floata 第三层分程序intd floatc 第四层分程序floatd a b c d 42 通常对于具有分程序结构的语言可用两种方式组织它们的符号表 分程序结构语言符号表的两种组织方式 一是对每个分程序建立一个独立的分表结构的符号表 一是把各分程序符号组织在一张单表结构的符号表中 43 1 分表结构 分表结构的组织管理 其基本思想是 每当编译程序扫描到一个分程序结构开始时 为该分程序建立一张符号表 在该分程序中定义的标识符 都被登录在该符号表中 而当编译程序扫描到一个分程序的结束时 编译程序释放为该分程序所建立的符号表 这种符号表的分表结构与源程序的分程序层次结构是完全一致的 这种层次结构是编译过程中动态建立和动态消亡的 44 根据分程序作用域和可视规则 编译程序扫描到某个分程序时 符号的登录是在为该分程序所建立的符号表中进行 而符号的查找是首先在该分程序符号表中进行 若没有查到 再根据分程序的层次结构 逐层向外地依次查找各层符号表 一直到查到为止 若所有符号表都已查完仍未找到 则表示有词法错误 45 在图第四层分程序的表达式a b c d中a是第二层定义的floata b是第一层定义的floatb c是第三层定义的floatc d是第四层定义的floatd 46 2 单表结构 单表结构的组织管理其基本思想是 所有分程序中定义的标识符都集中在单张符号表中 为了实现分程序构造中标识符的作用域和可视性规则的要求 在这种单表组织的符号表中 由于分层的分程序结构 因此需要强调三个主要的特定要求 首先 标志分程序层次其次 在编译程序扫描进入一个分程序时 和在退出一个分程序时 对符号表的管理 最后 重名标识符的处理 47 首先 为了标志一个符号所属的分程序层次 在符号表中可设立一个属性域用来登录符号所在分程序的层次 通常编译系统在扫描分程序结构的源程序时 设立一个记录当前扫描位置的分程序层次的状态量 每当一个标识符被定义并被登录符号表时 当时的表达分程序层次的状态量作为该标识符的分程序层次被登录到该符号的层次属性域中 其次 在编译程序扫描进入一个分程序时 表示分程序层次的状态量要增加一层 使进入分程序后定义的标识符登录符号表时 有相应的层次量作为层次属性登录 退出一个分程序时 不但要把表示分程序层次的状态量降低一层 而且需要把符号表中 所有在退出的分程序中登录的符号项清除 最后 对于具有分程序结构的源程序 在不同的分程序中 指嵌套的分程序中 允许定义重名的标识符 重名标识符可用下推链来组织 48 进入分程序第一层时的符号表层次属性表达 49 进入第二层分程序后单表结构的符号表情况 下推链中存放的是嵌套分程序中同名标识符的外层定义属性 这种结构不但符合作用域规则 也实现了可视性规则 50 进入第三层分程序后单表结构的符号表情况 51 进入第四层分程序后单表结构的符号表情况 52 6 3符号表的建立和查找 53 1 线性符号表 符号表中最简单且最容易实现的数据结构是线性表 它是按程序中标识符出现的先后次序建立的符号表 编译程序不做任何整理次序的工作 在扫描源程序时 根据各标识符在程序说明部分出现的先后顺序将标识符及其有关信息填入符号表中 当编译过程中需要查找符号表中的某个标识符时 只能采用线性查找方法 即从符号表的第一项开始直到表尾一项一项地顺序查找 若线形表种含有n项名字和信息 查找其中一次的平均比较次数为1 2 效率较低 54 例如有一程序中出现符号的情况如下 a 第一次出现a的地方 b 第一次出现b的地方 a 第二次出现a的地方 d 第一次出现d的地方 c 第一次出现c的地方 b 第二次出现b的地方 其中h表示该符号表之表头 是表的开始位置 p表示该符号表的表项是符号表当前的结束位置 在编译程序工作过程中 扫描得到之新符号总是登录到p的位置 而p又取下一新位置 编译程序开始工作时p处于h表头位置 55 这种组织方式的管理简单但运行效率低 特别当表项数目较大后效率就非常低 因为它没有空白项 因此存储空间效率高 但对于符号个数不确定的情况下 无法事先确定该符号表的总长度 对于事先能确定符号个数且符号个数不大 公认为小于20 时采用线性表组织是非常合适的 56 自适应线形表 在原有线形表结构的基础上 给每项附设一个指示器 这些指示器把所有的项按 最新最近 访问原则连接成一条链 使得在任何时候 这条链上的第一个元素所指的项就是最新最近被查询过的项 第二个元素所指的项是次新次近被查询过的项 依此类推 每次查表时都按这条链所给的顺序执行 一旦查到就立即修改这条链 使得链头总是指向刚刚查到的项 每当填入新项时 也总是让链头指向这个最新项 这种方法改善了查找效率 但是编译程序却多要管理一条链 57 2 二分查找和二叉树 为了提高查表速度 可以在造表的同时把各标识符按照一定的顺序进行排列 符号表中的表项按符号的代码串的值从小到大排列 显然 这样的符号表是有序的 对于有序符号表 一般采用折半查找法进行查表 即首先从表的中项开始比较 如果未找到则将查找范围缩小一半 然后继续查找 直到找到或查找失败为止 使用这种折半查找法对一个含有N项的符号表来说 查找其中的一项最多只需做1 2N次比较 虽然这种查找法的效率有所提高 但是对于一个边填写边引用的动态查找符号表来说 每填进一项就引起