编译原理演示文稿5.ppt

第五章符号表在编译程序的工作过程中 经常需要收集和记录源程序中的一些信息 这些信息往往保存在称为符号表的表中 根据不同的需要可建立如常数表 标识符表各种用途的符号表等 由于每使用一个标识符就需要查表 在整个编译过程中编译程序对这些表格的操作是很频繁的 因此 如何提高填查表的效率直接影响到编译程序的工作效率 编译程序使用的数据结构从使用的目的来看 可分为查找型数据结构和分配型数据结构 查找型数据结构在编译程序中用于构造不同的信息表 保存源程序中不同实体的属性信息 这种结构的特点是每个实体的项只创建一次 但可以查询多次 因此 查询效率很重要 分配型数据结构主要用于处理嵌套结构的程序 其特点是分配给实体的内存地址对实体用户是可知的 因此 不会对其进行查询操作 但分配和回收的速度及内存的使用效率却是十分重要的 这里结合查找型数据结构重点讨论符号表 5 1分配型数据结构5 1 1栈栈是一种先进后出 后进先出的数据结构 访问栈一般访问的是栈顶元素 栈在编译程序中也起着重要的作用 如递归过程 或函数 中说明的动态的局部变量 非静态变量 每进入一次如递归过程 或函数 就需分配相应的一块存储单元 而这种存储单元的分配却符合栈这种先进后出 后进先出特性 例 设有PASCAL程序programcalc vara b sum integer procedureadd varx y integer beginsum x y end beginadd 3 5 write sum end 则编译语句sum x y时过程add的符号和主程序calc的符号都在符号表中 当过程add编译后其符号没有意义 可以从符号表中退去 如图显示 为了方便地入栈和退栈 把原来的栈顶元素的地址也放入符号表 如图 如果一个层次的符号结构看作一个记录的话 有分配符号表和回收符号表的动作 分配时动作 1 TOP TOP 1 分配存放原记录底的单元 2 TOP RB 将原记录底放入栈中 3 RB TOP RB指向新记录的底 4 TOP TOP n 将栈指针指向分配后的栈顶 回收时动作 1 TOP RB 1 恢复栈顶 2 RB RB 将保存的原记录底取出 分配和收回示意图如下 5 1 2堆堆是一种非线性结构 它允许随机分配和回收实体 分配请求返回的是指向所分配区域的指针 删除 回收 请求需提供指向回收区域的指针 堆不提供任何访问被分配实体的方式 它假设被分配实体的用户保留了指向分配区域的指针 例 执行以下C程序后堆的状态如图所示 int ptr1 ptr2 float ptr3 ptr1 int calloc 3 sizeof int ptr2 int calloc 2 sizeof int ptr3 float calloc 3 sizeof float free ptr2 3个内存区在调用calloc后被分配出去 指针ptr1 ptr2 ptr3分别指向这些区域 free释放了ptr2指向的区域 这就产生了一个 洞 每个要被分配的区域都假设在分配前包含length域 在使用堆这种数据结构中 反复在堆中分配 释放会造成不少空闲区 洞或碎片 如何回收这些空闲区 进行合理再分配 以提高内存的利用率是评判内存管理的标准 要回收这些空闲区域 首先必须标明空闲区域 目前常用的技术有引用计数和回收集两种 在引用计数技术中 系统为每个内存区都关联一个引用计数器来指出引用的次数 当新的用户访问该区域时 计数值增加 访问结束后减少 当计数值为0时表明该区域为空闲 这种技术易于执行 但开销会不断增大 回收集技术用两次扫描来辨别空闲区 第一次扫描所有已分配区的指针 标记那些已使用的内存区域 第二次扫描标出所有未标记区 确认它们为空闲区 该技术的开销不会逐渐增大 为了管理空闲区 系统将空闲区组成空闲链 并设立了一个链头指针 每个空闲区域的第一个字为本区域的长度 第二个字为一个指针指向下一个空闲区 如图所示 以满足分配请求 还可以通过内存重整理 使若干个由链相联系的空闲区合并成一个连续的空闲区以提高内存的使用率 使用空闲链结构时 完成分配请求可采用首次适配法和最佳适配法 5 2查找型数据结构由于在语法分析中采用的是上下文无关的方法 而实际算法语言往往是上下文有关的 如 标识符的前说明后使用问题函数的参数个数和类型匹配 如何解决这些问题一般采用通过填查符号表来决定的 因此如何组织和查找符号表对编译程序的效率有着重大的影响 下面介绍以查找型数据结构的符号表 5 2 1表的组织在编译程序中符号表用来存放语言程序中出现的有关标识符 或其它基本符号 如 常量 的属性信息 这些信息反映了标识符的语义特征属性 这些信息可以在词法分析中加入也可以在语法分析中不断积累和更新 而且这些信息可以用在从词法分析到代码生成的各个阶段 符号表功能可归结为 1 收集单词 符号 的属性 2 语义合法性检查 3 作为地址 内存空间 的分配依据 例 inta floatc 100 gotoloop loop 则在符号表中可能存在 例 loop 5 例 c 20 100 a c 10 5 1 查找型数据结构和符号表的项查找型数据结构是由一系列的登记项组成的 每个登记项又有若干信息 称为属性 组成的 一个登记项可以有一个关键字和若干次关键字 根据不同的符号表的组织登记项又可以有固定部分和非固定部分 这些符号表通常含有以下属性 符号名语言中的标识符可以是一个变量或常量的名字 一个函数或过程的名字以及标号的名字 它是识别字符常量 变量 函数 过程和标号的唯一标志 如将符号名作为关键字则不允许出现相同命名的标识符 也有的语言允许函数的重载 也有的语言每个标识符有相应的作用域 这样重载的标识符就可以通过参数个数或类型 标识符说明的位置来以示区别 2 符号的类型除过程外 函数 变量 常量标号都具有相应的类型属性 如基本数据类型字符型 整型 实型 布尔型和构造型类型数组 记录和枚举类型等 符号的类型直接影响到语义的正确性的检查和代码的生成 3 符号的存储类别符号的存储类别规定了符号的存储位置 如C语言中的动态变量 静态变量 寄存器变量和外部变量 对于存放在不同位置的数据所产生的代码显然是不同的 4 符号的作用域一个符号在程序中的作用范围 称为它的作用域 一般来说 一个符号的定义位置决定了该符号的作用域 C语言 语言的外部变量作用域是整个程序 因此一个外部变量符号只能出现说明一次 另外 C语言的静态变量虽然它的生成期与外部变量一样 但它的作用域只是说明它的函数 函数的形式参数和函数内说明的变量的作用域为该函数内 分程序结构的作用域只在该分程序内 例 inta chara floata a 5 5 符号变量的存储分配信息根据符号的存储类别定义和说明它们的位置 以及说明的次序确定每个变量应分配的存储区中的相对位置 由于动态变量每进入一次需分配同样大小的存储单元 一个编译程序有两类存储区 即静态数据据区和动态数据区 a 静态数据区该存储区单元经static定义后就成了静态变量 它在整个语言的运行过程中是不可改变 它的生成期从程序的开始至程序的结束 静态数据区根据它的作用域还可以分为公共静态数据区和局部静态数据区 b 动态存储区根据变量的局部定义和分程序结构 编译程序设置动态存储区来适应这些局部变量的生存和消亡 也就随着分程序的进入而分配 随着分程序的退出而释放 6 符号的其它属性符号表的其它属性主要有 a 数组的内情向量b 记录 结构 的成员信息c 函数及过程的形参下面常用符号的属性 符号表的组织 1 定长项格式定长项格式把所有符号都组织在一张符号表中 这样的组织方式的优点是不同种类的符号可以统一管理 它的缺点是所有属性必须具有相同的长度 这样就会产生存储空间浪费 2 分类项格式是按照相同类型的符号组织在一起 构造多个符号表 其优点是空间效率高 缺点是一个编译程序需要管理若干个符号表 增加了编译程序管理符表的复杂度 3 混合型项格式混合型项格式是定长格式和分类项格式的折中方式 既有定长项格式的访问高效性 又有分类项格式内存高利用率 它把项分成固定部分和非固定部分 固定部分除符号域和种属域外 还增加了一个指针域 用于存放指向非固定部分的指针 非固定部分增加了一个长度域 用于存放对应符号的属性个数 固定部分以高效的查找型数据结构组织 因为固定部分包含指向非固定部分的指针 如图所示 但这种方法的缺点对存取指针后的属性不太方便 另外 也可以将长度接近的符号放入一张表中这样相对于分类格式来说 既减少表的个数 降低了管理难度 其浪费的存储单元也不多 2 常用的符号表的结构一个编译程序从词法分析 语法分析 语义分析到代码生成的整个过程中 符号表是进行上下文检查 语义处理 代码生成和存储分配的重要依据 一个符号表的结构直接影响到编译程序的执行速成度 在编译程序的工作过程中 符号表被频繁地用来建立表项 查找表项 填充或修改表项的属性和删除表项 表的结构主要有 1 无序符号表这种符号表是按登记项出现的先后次序建立符号表 当获得一个符号时 并通过查整个符号表 确定不在表中就将它填入表中 这种方法填表速度较快 但查表速度较慢 2 有序符号表有序符号表是按照符号名的规律进行填表的 这样每次填表均要进行查找它的确定填入的位置 每当有符号填入 插入 时可能会引起表项的移动 增加了时间开销 对于有序符号表可以采用运行效率较高的二分 折半 查找方法 这种方法虽然查表速度相对无序符号表较快 但填表时间较长 3 散列表散列表中表项位置是由对表项中的符号名 即字符或代码 的值进行某种函数操作 通常称为 散列 或 杂凑 所得到的函数值来确定的 这种函数通常称为散列函数 但是不同的符号名经过散列函数计算后 有可能得到相同的函数值 这种不同符号的表项被散列到表中同一个位置的情况称为冲突 解决冲突方法之一是再散列 另一种方法称为拉链地址 这种方法把散列表的每个单元定义为链表的表头 散列在同一个位置上的所有项都存放到这个单元的链表中 对于散列表只需进行少量比较或无需比较就可以很快定位 由于散列表具有较高的运行效率 因而绝大多数编译程序中的符号表采用散列组织 4 树结构的符号表树结构的符号表如二叉树结构 实际上是有序表的一种变形 树的每个节点是一个含有指针的表项 在二叉树结构中 当树平衡时查找效果最好 此时效果与二分查找相同 最坏的情况是树退化成链表 则查找效果与顺序查找相同 5 栈符号表栈符号表适用与分程序嵌套结构型程序设计语言 符号表由栈来实现 表项的加入总是在栈顶位置 查找总是从符号表的栈顶向底部查找 保证了先查最近出现的标识符 由于程序是分层的 并且分程序结束时会释放对应分程序的有关表项 因此查找范围相对较小 5 2 2符号表的管理1 符号表的初始化一个符号表的状态反映了被编译的程序和位置和状态 也就是该程序的可视符号的状态 如何反映这些符号的状态 需要对这些符号表进行初始化 不同组织的符号表其初始化方法也不相同 a 表长变化的符号表对于有序符号表和无序符号表它的长度反映已登记的项的个数 因此它们的初始化只要将表长置为 0 b 表长不变的符号表对于如散列表 其表长确定的表 其中表已不能反映登记项的个数 这类表的是否有登记项取决于表项的值 因此这类符号表的初始化方法是将所有的表项清除 由于表项取决于符号栏 也可能是指向符号的指针 因此在初始化时 实际上只清除表符号栏的值 如图 2 符号表的查找和登录当编译程序获得一个标识符时 首先查表确定它是否在符号表中 如不在就需将它登录在符号表中 符号的登录形式与符号表的结构有关 当编译程序获得一个已在表中 或应该在表中 标识符时 就要查找符号确定该符号的类别 查找的目的是建立或确认该符号的语义属性 需要指出的是无论查找还是登录其算法都与其符号表的组织形式有关 查找和登录分为显式和隐式二种 在显式说明语言中 所有的标识符都要求在引用前进行说明 并且用专门的说明语句来声明 在显式说明语言程序中 同一层分程序内不能出现同名标识符被多次说明 因此 在说明部分每出现一个标识符 就要进行查表 以判断该标识符是否已登录过 若未登录过 则将该符号登录进符号表 在说明部分以外的地方 每出现一个符号也要进行查表 若在表中查不到该符号 则表示引用未说明过的符号 指出错误 并将该符号填入符号表中 若在表中查到该符号 则要检查该符号当前使用的属性与说明部分已登录过的属性是否一致 在隐式说明语言中 标识符并不一定都要求用专门的说明语句来声明 而是通过一些约定来表示标识符的某些属性 如FORTRAN语言中约定 标识符如没有专门的说明语句声明 则以字母I J K L M N之一打头的标识符所指的变量是整型 而其余字母开头的标识符所指的变量均为实型 在这类语言中编译程序每扫描到一个标识符也都需要查表 若在表中查到同名符号 则表示该符号已在符号表中登录过 于是获取相关的属性使用或进行语义的一致性检查 若查不到 则表示该标识符是一个新的标识符 需将其登录到符号表中去 3 符号表的删除在编译过程中 当某符号表的表项不再使用时 为了加快查找速度和提高空间的利用率 需要将登记项从符号表中删除 删除表项可采用两种方式 物理删除和逻辑删除 若在有序符号表中 若某表项被删除后 其设符号表的每介登记项均需依次 上移 对于无序表还可以将表中最后一项直接替代被删除的项 因而只需作一次移动 对于散列组织的符号表 当从中删除一个表项后 一般不影响后面的符号查找 若进行逻辑删除 则向表项中添加某些标记表明其已被删除 4 分程序结构的符号表管理对于具有分程序弄结构的语言的程序 不同层次分程序中定义的标识符号具有不同的作用域和不同的可视性规则 通常对于具有分程序结构的语言可用两种方式组织它们的符号表 一是对每个分程序建立