第章符号表的组织与管理PPT课件.ppt

第6章符号表的组织与管理 符号表是编译程序中主要的数据结构之一 它主要用来存放程序语言中出现的有关标识符的信息 编译程序处理标识符时主要涉及两部分内容 其一是标识符自身 其二是与标识符相关的信息 这些信息又包括 标识符的类型 如实型 整型 布尔型等 标识符的种属 如数组名 变量名 过程名 函数名等 标识符的作用域 如全局变量或局部变量等 在对程序语言进行编译的过程中 常常需要处理出现在程序语言中的标识符及相关信息 如在词法分析中每识别到一个标识符 编译程序就要查阅符号表 若符号表中没有该标识符的定义 就将标识符及其相关信息登录在符号表中 在语义分析时 符号表中的内容可以用于语义检查 代码优化时 编译程序将利用符号表提供的信息选出恰当的代码进行优化 目标代码生成时 编译程序将依据符号表中的符号名分配目标地址 由此可见 编译过程的各个阶段都要访问符号表 因此合理地组织和管理这些符号表显得尤为重要 符号表的作用 连接声明与引用的桥梁 记住每个符号的相关信息 如作用域和绑定等 帮助编译的各个阶段正确有效地工作 符号表设计的基本要求 目标是合理存放信息和快速准确查找 正确存储各类信息 适应不同阶段的需求 便于有效地进行查找 插入 删除和修改等操作 空间可以动态扩充 本章教学内容 符号表的作用 内容 组织和管理 一 符号表的作用 符号表的作用 收集符号属性 上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据 二 符号表的内容 语言符号可分为关键字 保留字 符号 操作符符号及标识符符号 它们之间的主要属性有较大差别 因此通常为它们建立不同的符号表 但有些编译程序也将关键字符号与标识符符号建立在同一符号表中 符号表条目 逻辑上讲 每个声明的名字在符号表中占据一栏 称为一个条目 用于存放名字的相关信息 符号表中的内容 保留字 标识符 特殊符号 包括算符 分隔符等 等等 不同类别的符号存放在不同的子表中 如变量名表 过程名表 保留字表等 存放方式 关键字 属性 关于组合关键字 intx doublex structx floaty z 为C 构造的符号表中 组合关键字至少应该包括三项 名字 作用域 类型 当一个名字x在同一作用域中允许有多于一个的声明 则对x的引用时需要根据上下文确定x到底属于哪个对象 因此程序设计语言在语法上规定了不允许这样的声明 以简化编译时的处理 符号表的每一项 入口 包含两大栏 名字栏 也称主栏 关键字栏信息栏 记录相应的不同属性 分为若干子栏符号的组织方式 1 安排各项各栏的存储单元为固定长度2 用间接方式安排各栏存储单元 构成名字的字符串的存储 定长数据变长数据直接存放间接存放 名字 直接存储 属性sortproc aint readarrayproc draw a red line for object aboolean 名字 间接存储 属性101 或101 4 proc 106 或105 1 int 108 或106 9 proc 118 或105 28 boolean sort a readarray draw a red line for object a 101 sortareadarraydraw a red line for object a 101 间接存储的方法实际上解决了复杂信息的存储问题 将其推广到属性 则任何一个复杂的属性 均可以为其另辟空间 空间本身可以是复杂结构 如数组的内情向量等 而仅需要将指向此空间的指针放在此属性在符号表中的对应位置即可 符号表中的标识符一般设置的属性项目有 符号名 符号的类型 符号的存储类别 符号的作用域及可视性 符号变量的存储分配信息 符号的其它属性 下面三个方面亦是符号表中表达标识符属性的重要信息 数组内情向量 数组是一种重要的数据类型 编译程序处理数组说明的主要工作是 把描述数组属性信息的内情向量登录到符号表中 内情向量包括数组类型 维数 各维的上 下界及数组首地址 这些属性信息是确定存储分配时数组所占空间的大小和数组元素位置的依据 记载数组内情向量的符号表 记录结构型的成员信息 一个记录结构型的变量 在存储分配时所占空间大小要由它的全体组成成员来确定 另外对于记录结构型变量还需要有它所属成员排列次序的属性信息 这二种信息用来确定结构型变量存储分配时所占空间的尺寸及确定该结构成员的位置 函数及过程的形参 函数和过程的形参作为该函数或过程的局部变量 但它又是该函数或过程对外的接口 每个函数或过程的形参个数 形参的排列次序及每个形参的类型 都体现了调用该函数或过程时的属性 它们都应该反映在符号表的函数或过程标识符的项中 有关函数及过程的形参属性信息用来作调用过程的匹配处理和语义检查 按名字的不同种属建立多张符号表 如常数表 变量名表 过程名表 符号表的存放次序 1 把每一项置于连续K存储单元中 构成一张K N的表2 把整个符号表分成m个子表 如T1 T2 Tm 每个子表含有N项 例 PASCAL程序段 PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END 三 符号表的组织 线性组织这种方法规定符号表中表项按它的符号被扫描到的先后顺序登录 排序组织及二分法语言中的每一个符号 都是由一个或几个ASCII或EBCDIC代码字符拼写而成的 每一个符号在机器内都是由这种字符代码串来表示 排序组织的符号表 就是在符号表中的表项按其符号的字符代码串 可以看成一个整数值 的值的大小从大到小 或从小到大 排列的 散列组织一个符号在散列表中的位置 是由对该符号 即字符代码串 进行某种函数操作 通常称为 杂凑函数 所得到的函数值来确定的 所得到的函数值与该表项在表中位置的对应关系 是通过对函数值的 求整 以及相对于表长的 求余 得到的 符号表的散列组织相对来说具有较高的运行效率 因而绝大多数编译程序中的符号表采用散列组织 为了提高效率降低算法复杂度 通常杂凑函数采用整数操作 目前编译程序中 一般采用对符号代码的位操作作为杂凑函数 见得最多的是符号代码的字符段叠加或加权叠加以及符号代码的对折或多折等位操作 四 符号表的操作 在一个符号表上可以进行下列操作 1 往表中填入一个新标识符 2 对给定标识符 查找它是否已在表中 访问它的某些信息 往表中填入或更新某些信息 3 更新或删除一个或一组无用的项 对符号表进行操作的时机 定义性出现使用性出现 整理和查找 1 线性查找按关键字出现的顺序填写各项 填表快 查找慢 结构简单 节省空间 效率低 查找时间复杂度 O n 改进 自适应线性表 2 二分查找表格中的项按名字的 大小 顺序整理排列 填表慢 查找快 查找时间复杂度 O Log2n 改进 组织成二叉树 3 杂凑查找 HASH技术 杂凑函数H SYM 0 N 1N 符号表的项数 要求 1 计算简单高效2 函数值分布均匀填表快 查找快 示例 PL语言编译程序的符号表 1 表格的定义名字表 nametab 程序体表 btab 层次显示表 display 数组信息表 atab 中间代码表 code 1 名字表 nametab 名字表nametab 登记程序中出现的各种名字及其属性 名字标识符 名字种类 可以是常量 constant 变量 variable 类型 type 过程 procedure 名字所在的程序体的静态层次 规定主程序的层次为1 主程序中定义的层次为2 依次类推 名字的类型 类型有整型 ints 字符型 chars 布尔型 bool 数组 arrays 对于无类型的名字填入notype 一个布尔量 用于标明名字是否为变量形参名 当名字是否为变量形参名时填入false 其他情况填入true或不填 当名字为数组类型或数组变量名时 ref指向该数组在数组信息表中的位置 当名字为过程名时 ref指向该过程在程序体表 btab 中的位置 其他情况ref为0 adr 当名字为变量名时 包括形参 存入该变量 或形参 在相应活动记录中分类的存贮单元的相对地址 对于过程名 填入他们相应代码的入口地址val 当名字为变量名时 填入他们的相应值size 当名字为类型名时 填入该类型数据所需存贮单元的数目 指向同一程序体中定义的上一个名字在nametab中的位置 每个程序体在nametab中登记的第一个名字的link为0 2 程序体表btab和层次显示表display 程序体表btab 记录个程序体的总信息 用于对源程序中定义的名字的作用域进行分析 对名字表进行管理 指向本程序体中最后一个形式参在nametab中的位置 指向本程序体中最后一个名字在nametab中的位置 本程序体所有形参所需体积 包括连接数据所占空间 本程序体所有局部数据所需空间大小 层次显示表display 描述正在处理的各嵌套层 对程序体表进行管理 btab 3 数组信息表atab 数组的下标类型 数组元素类型 当元素为数组时 它指向该元素数组信息在atab表中的位置 其他情况为0 数组下限 数组上限 数组元素的体积 数组本身的体积 typea array 1 10 1 10 ofinteger nametab atab 4 中间代码表codecode 用于存放编译程序所产生的每条中间代码 再见 8 3名字的作用范围 在许多程序语言中 名字都有一个确定的作用范围 两种程序体结构 并列结构 如FORTRAN嵌套结构 如PASCAL ADA PROGRAMMAIN integerX YCOMMON C A B ENDSUBROUTINESUB1 realX ZCOMMON C A1 B1 END programP vara b integer procedureP1 i1 j1 integer varc d integer end procedureP2 i2 j2 integer vara c integer procedureP21 varb1 b2 boolean end end end 1 FORTRAN的符号表组织一个FORTRAN程序由一个主程序段和若干个辅程序段组成 把局部名和全局名分别存在不同的地方 2 嵌套结构语言的符号表组织如PASCAL ALGOL ADA作用域遵循 最近嵌套原则 PASCALPASCAL程序本身可以看成是一个操作系统所调用的过程 过程可以嵌套和递归 一个PASCAL过程 过程头 说明段 由一系列的说明语句组成 begin执行体 由一系列的执行语句组成 end 作用域 一个名字能被使用的区域范围称作这个名字的作用域 允许同一个标识符在不同的过程中代表不同的名字 名字作用域规则 最近嵌套原则 一个在子程序B1中说明的名字X只在B1中有效 局部于B1 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明 则原来的名字X在B2中仍然有效 如果B2对X重新作了说明 那么 B2对X的任何引用都是指重新说明过的这个X programmainvarA B real procedureP1varB boolean begin endprocedureP2varA integer begin endbegin end A real B real B bool A integr 两种做法 引入 过程编号 属性 查找时 先查找本过程编号的名字 查不到则查找外层过程编号的名字 等等 按 栈 式思想组织符号表 查找时 从后往前查找 碰到的第一个名字就是所需查找的名字 PL语言的中间代码 指令格式 opcodlaopcod 操作码l 第一操作数 程序体层数a 第一操作数 相对地址编译是如何确定变量的层数 地址 运行是如何根据指令中变量的层数和相对地址确定变量的存储单元 programP vara b integer procedureP1 i1 j1 integer varc d integer end procedureP2 i2 j2 integer vara c integer procedureP21 varb1 b2 boolean end end end programP vara b integer procedureP1 i1 j1 integer varc d integer end procedureP2 i2 j2 integer vara c integer procedureP21 varb1 b2 boolean end end end programP vara b integer procedureP1 i1 j1 integer varc d integer end procedureP2 i2 j2 integer vara c integer procedureP21 varb1 b2 boolean end end end functionposition id alfa integer vari j integer beginnametab 0 name id j level repeati btab display j last whilenametab i nameiddoi nametab i link j j 1until j0 if i 0 thenerror 10 position iend position b1 a b PL语言的中间代码 指令格式 opcodlaOpcod 操作码l 第一操作数 程序体层数a 第一操作数 相对地址编译是如何确定变量的层数 地址 运行时如何根据指令中变量的层数和相对地址确定变量的存储单元 名字的作用域 程序设计语言的名字可以出现在不同的范围内 并且可以具有不同的意义 两种划分范围的方式 并列的和嵌套的 不同的语言采用不同的方式 如Pascal的过程定义可以是嵌套的 而C的过程定义是并列的 但是C允许程序块是嵌套的 名字的作用域 名字在哪个范围内起作用 并列的两个范围内的名字作用域互不相干 但是分别在嵌套的两个范围内的名字 其作用域的问题就需要制定规则来限定 以使得任何一个名字在任何范围内涵义都是无二义的 名字的作用域规则 规定一个名字在什么样的范围内应该表示什么意义 名字的作用域 续1 静态作用域原则 static scoperule 编译时就可以确定名字的作用域 也可以说 仅从静态读程序就可确定名字的作用域 最近嵌套原则 mostcloselynested 以程序块为例 也适用于过程 程序块B中声明的作用域包括B 如果名字x不在B中声明 那么B中x的出现是在外围程序块B 的x声明的作用域中 使得 a B 有x的声明 并且 b B 比其它任何含x声明的程序块更接近被嵌套的B 通俗地讲 名字的声明在离其最近的内层起作用 即在名字引用处从内向外看 它处在所遇到的第一个该名字声明的作用域 例子 找人张三 软件学院的张三 计算机学院的张三 西电软件学院的张三 名字的作用域 续2 例4 10说明符合作用域规则的C 程序 voidmain inta 0 b 0 B0层 intb 1 B1层 被B0嵌套 inta 2 c 4 d 5 B2层 被B1嵌套 printf d d n a b 结果为 2 1 intb 3 B3层 与B2并列 printf d d n a b 结果为 0 3 printf d d n a b 结果为 0 1 printf d d n a b 结果为 0 0 声明与作用域 声明作用域inta 0B0 B2intb 0B0 B1intb 1B1 B3inta 2B2intb 3B3 线性表 线性表应是一个栈 以正确反映名字的作用域 即符号的加入和删除 均在线性表的一端进行 线性表上的操作 关键字 名字 作用域 查找 从表头 栈顶 开始 遇到的第一个名字 插入 先查找 再插入在表头 1voidmain 2 inta 0 b 0 B03 intb 1 B14 inta 2 c 4 d 5 B27 intb 3 B311 线性表 续1 1voidmain 2 inta 0 b 0 B03 intb 1 B14 inta 2 c 4 d 5 B27 intb 3 B311 线性表上操作的效率 n个条目 一个名字的查找 成功查找 平均 n 1 2 不成功查找 n 1建立n个条目的符号表 最坏 n 1 n 2 2 删除 a 暂时 将在同一作用域的名字同时摘走 适当保存 b 永久 将在同一作用域的名字同时摘走 不再保存 修改 与查找类似 修改第一个遇到的名字的信息 修改可以用插入 删除代替 散列表 散列表的构成将线性表分成m个小表 构造hash函数 使名字均匀地散布在m个子表中 如果散列均匀 则时间复杂度会降到原线性表的1 m 每个名字挂在两个链上 便于删除操作 哈希链 hashlink 链接所有具有相同hash值的元素 表头在表头数组中 作用域链 scopelink 链接所有在同一作用域中的