第章符号表管理技术PPT课件.ppt

1 编译原理基础 2 3 第七章符号表管理技术 教学目标 明确符号表的作用 组织 内容了解符号表上的操作了解符号表结构 非块程序结构语言块程序结构语言 4 7 1何时建立和访问符号表7 2符号表的组织和内容7 3符号表上的操作7 4非块程序结构语言的符号表结构7 5块程序结构语言的符号表组织 教学内容 5 第7章符号表管理技术 在编译的各个阶段经常要收集 使用出现在源程序中的各种信息 为了方便 通常把这些信息用一些表格进行记录 存储和管理 如常量表 数组信息表等等 这些表统称为符号表 符号表主要保存各类标识符的属性 1 生存期最长2 使用最为频繁 6 7 1何时建立和访问符号表 7 7 1何时建立和访问符号表 符号表可在词法分析时创建 也可在语义分析时创建 1 符号表在词法分析遍内创建 符号表此时只含有标识符的名字 其它属性要在语义分析阶段填入 2 符号表只在语义分析时才创建符号表 词法分析只输出标识符符号 在语义分析阶段根据标识符的属性创建符号表记录 并同时填入其它的属性信息 8 7 2符号表的组织和内容 符号表的管理程序应该具有快速查找 快速删除 易于使用 易于维护的特点 符号表 二维表格每个表项可分为两部分 第一部分是名字域 用来存放符号的名字 第二部分是属性域 用来记录与该名字相对应的各种属性和特征 9 符号表示例 变量名 目标地址 类型 维数或过程的参数数目 变量声明的源程序行号 变量引用的源程序行号 以字母顺序列表的链域 10 变量名 变量名 通常采用的存储方法有两种 定长存贮方法优点 简单且存取速度快缺点 空间利用率低 标识符长度不能超过名字域的宽度 集中存贮方法 优点 存贮效率高 标识符无长度限制 缺点 存取效率低 如图7 1所示 变量名 目标地址 类型 维数或过程的参数数目 变量声明的源程序行号 变量引用的源程序行号 以字母顺序列表的链域 11 目标地址 目标地址 程序中每个变量都必须有一个相应的目标地址 该地址是为该变量分配的内存地址 可能是相对的 采用静态存储分配的语言 如FORTRAN 地址连续的顺序分配采用动态存储分配的语言 相对地址 运行时还要根据该程序块分配的数据区的起始地址和变量的相对地址计算出变量的绝对内存地址 标识符表示的是函数名或子程序名 则目标地址是该函数或子程序代码的开始地址 如果是数组名 则应为数组模板的起始地址 变量名 目标地址 类型 维数或过程的参数数目 变量声明的源程序行号 变量引用的源程序行号 以字母顺序列表的链域 12 类型 维数或过程的参数数目 类型 符号表中要保存每个标识符的数据类型 以便分配内存和进行类型检查 维数及参数个数 1 数组引用时 其维数应当与数组声明中所定义的维数一致 也用于数组元素地址的计算 2 过程调用时 实参个数必须与形参个数一致 变量名 目标地址 类型 维数或过程的参数数目 变量声明的源程序行号 变量引用的源程序行号 以字母顺序列表的链域 13 交叉引用表和链域 交叉引用表 变量或首次引用该变量的语句行号以及所有引用该变量的语句行号 链域 为了便于产生按字母顺序排序的变量交叉引用表 如果编译程序不产生交叉引用表 则符号表中的链域以及语句的行号属性都可从表中删去 变量名 目标地址 类型 维数或过程的参数数目 变量声明的源程序行号 变量引用的源程序行号 以字母顺序列表的链域 14 7 2符号表的组织和内容 从编译系统建造符号表的过程来划分 符号表可分为静态表和动态表两大类 一是静态表即在编译前就已经构造好了的符号表 如保留字表 标准函数名表等 二是动态表即在编译过程中根据需要构造的符号表 如变量表 数组信息表 过程信息表等等 15 7 3符号表上的操作 操作 1 向表中填入一个新标识符 2 对于给定一个标识符 查找是否在表中 访问它在表中的相关信息 在表中填写或更新它的某些信息 3 更新或删除一个或一组无用的项 16 7 4非块程序结构语言的符号表结构 17 7 4非块程序结构语言的符号表结构 1 无序表无序表插入和查找操作比较简单 但查找效率低 如果符号表较小 采用无序表则非常合适 无序表的优点是结构简单 节省空间 添加及查找操作简单 易于实现 2 有序表变量名按字母顺序存放 最常用的查找技术是折半查找法 18 7 4非块程序结构语言的符号表结构 3 散列符号表将程序中出现的符号通过哈希函数进行映射 得到的函数值作为该符号在表中的位置 Hash表的基本思想 1 为符号表设置一个足够大的空间M2 为符号构造一个散列函数Hash Ki 使得0 Hash Ki M 1 i 1 2 n3 这样查找Ki时 Hash Ki 就决定了Ki在符号表中的位置 19 7 4非块程序结构语言的符号表结构 散列函数 哈希函数 具有如下性质 1 函数值只依赖于对应的符号 2 函数的计算简单且高效 3 函数值能比较均匀地分布在一定范围内 构造散列函数的方法有 除法散列函数 乘法散列函数 多项式除法散列函数 平方取中散列函数等 哈希常用处理冲突的办法有 顺序法 倍数法和链表法 20 用 质数除余法 来构造散列符号表 1 根据各符号名中的字符确定正整数h 2 将上一步确定的整数除以符号表的长度N 然后取其余数 这个余数就作为符号的散列位置 3 处理冲突可采用链接法 即将出现冲突的符号用指针连接起来 假设现有5个符号C1 C2 C3 C4 C5 分别转换成正整数为87 55 319 273和214 符号表的长度是5 那么 利用质数除余法得到的散列地址为 2 0 4 3 4 如下图所示 21 7 5块程序结构语言的符号表组织 块程序结构语言的概念所谓块程序结构语言是指程序模块可包含嵌套的子模块 每一子模块可以有一组自己的局部变量 按块程序结构语言的规定 变量的作用域是定义它的块程序 同一块内的变量不能重名 但不同块以及嵌套块之间的变量可以重名 因而某变量的声明可与嵌套块的内层变量同名 使用时局部变量优先 22 7 5 1块程序结构语言的概念 一段C程序 右边给出当编译程序编译到此处时的有效变量 realx y charname name y xintfun1 intind ind fun1 name y x intx x ind fun1 name y xx fun2 ind 1 fun1 name y xintfun2 intj j fun2 fun1 name y x intf 10 booltest1 test1 f j fun2 fun1 name y x j fun2 fun1 name y x fun2 fun1 name y xmain main fun2 fun1 name y x charname name main fun2 fun1 name y xx 2 y 5 printf d n fun1 x y 23 一段C程序 右边给出当编译程序编译到此处时的有效变量 realx y charname name y xintfun1 intind ind fun1 name y x intx x ind fun1 name y xx m2 ind 1 fun1 name y xintfun2 intj j fun2 fun1 name y x intf 10 booltest1 test1 f j fun2 fun1 name y x j fun2 fun1 name y x fun2 fun1 name y xmain main fun2 fun1 name y x charname name main fun2 fun1 name y xx 2 y 5 printf d n fun1 x y 24 7 5 2栈式符号表 包括一个符号表栈及一个块索引栈 符号表栈 记录变量的属性块索引栈 指出每个块的符号表的开始位置由于栈式符号表中记录是无序的 因而查询效率比较差 25 例7 1 有一段C程序如下 画出编译到a b c d处的栈式符号表 realx y charname aintfun1 intind intx bx fun2 ind 1 intfun2 intj intf 10 booltest1 c main charname dx 2 y 5 printf d n fun1 x y 26 补充 错误处理 词法错误语法错误语义错误违反了语言的环境限制数组维数太大循环嵌套层数太多 27 词法错误 语法错误和语义错误 28 超越系统限制 计算机系统和编译系统 1 数据溢出错误 常数太大 计算结果溢出 2 符号表 静态存储分配数据区溢出 3 动态存储分配数据区溢出 语义规则 标识符先说明后引用标识符引用要符合作用域规定过程调用时实参与形参类型一致参与运