第9章符号表案例.ppt

1 第九章符号表 广东工业大学计算机学院 广东工业大学计算机学院 LOGO 2 引言 符号表作为编译系统的重要设施 贯穿于文法分析 检查和语义处理的编译全过程 在编译程序中符号表用来存放源程序中出现的有关名字的属性信息 这些信息集中反映了名字的语义特征属性 符号表总体结构的设计和实现下列因素有关 源语言的复杂性 包括词法结构 语法结构的复杂性 对于编译系统在时间效率和空间效率方面的要求 广东工业大学计算机学院 LOGO 3 Contents 知识结构 广东工业大学计算机学院 LOGO 4 本课内容 9 1符号表的作用和地位9 2符号的主要属性及作用9 3符号表的组织9 4符号表的管理 广东工业大学计算机学院 LOGO 5 符号表的功能 符号表中所登记的信息在编译的不同阶段都要用到 例如 在词法分析及语法分析过程中不断更新表中的信息 另外 在词法分析到代码生成的各阶段则会从表中获取不同的属性信息 符号表的功能主要归结为以下几个方面 收集符号属性 作为上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据 广东工业大学计算机学院 LOGO 6 1 收集符号属性 编译程序扫描说明部分收集有关标识符的属性 并在符号表中建立符号的相应属性信息 例如 编译程序分析到下述两个说明语句 intA floatB 5 则在符号表中收集到关于符号A的属性是一个整型变量 关于符号B的属性是具有5个浮点型元素的一维数组 广东工业大学计算机学院 LOGO 7 2 作为上下文语义的合法性检查的依据 通过符号表中属性记录可进行相应上下文的语义检查 例如 在一个C语言程序中出现inti 3 5 定义整型数组i floati 4 2 定义实型数组i 重定义冲突 inti 3 5 定义整型数组i 重定义冲突从本例还可以看出 无论在后面两句中i的其它属性与前一句是否完全相同 只要标识符名重定义 就将产生重定义冲突的语义错误 广东工业大学计算机学院 LOGO 8 3 作为目标代码生成阶段地址分配的依据 每个符号变量在目标代码生成时需要确定其在存储分配中的位置 主要是相对位置 要确定一个变量在目标代码生成时的地址 需要 首先要确定其被分配的区域 例如 在C语言中有公共区 文件静态区 函数静态区 函数运行时的动态区等 其次是根据变量出现的次序 通常使用在该区域中相对于区头的相对位置来决定该变量在某个区中所处的具体位置 广东工业大学计算机学院 LOGO 9 本课内容 9 1符号表的作用和地位9 2符号的主要属性及作用9 3符号表的组织9 4符号表的管理 广东工业大学计算机学院 LOGO 10 符号表的组成 信息栏包含许多子栏和标志位 用来记录相应名字和各种属性 名字栏也称主栏 主栏的内容称为关键字 keyword 符号表包括名字栏和信息栏 可有多列 广东工业大学计算机学院 LOGO 11 符号表的操作分类 在整个编译期间 对于符号表的操作大致可归纳为五类 对给定名字 查询名字是否已在表中 往表中填入一个新的名字 对给定名字 访问它的某些信息 对给定名字 填写或更新它的某些信息 删除一个或一组无用的项 广东工业大学计算机学院 LOGO 12 符号表的属性概述 虽然不同的语言定义的标识符属性不尽相同 下列几种属性通常都是需要的 符号名 符号的存储类别 符号变量的存储分配信息 符号的其它属性 数组内情向量 记录结构型的成员信息 函数及过程的形参 符号的类型 符号的作用域及可视性 广东工业大学计算机学院 LOGO 13 符号的存储类别 大多数语言对变量的存储类别定义采用两种方式 1 用关键字指定 例如在C语言中用static定义是属于文件的静态存储变量或属于函数内部的静态存储变量 2 根据变量声明在程序中的位置来决定 例如在C语言中 在函数体外定义的变量是缺省是程序的公共存储变量 而在函数体内定义的变量是该函数所独有的私有存储变量 广东工业大学计算机学院 LOGO 14 符号的作用域及可视性 一个变量的作用域即该变量可以出现的场合 也就是说在某个变量作用域范围内该变量是可引用的 这就是变量可视性的作用域规则 但是变量可视性不仅仅取决于它的作用域 还有两种情况影响到一个变量的可视性 函数的形式参数 影响变量可视性的举例inta 外部定义的整型变量aintfunc a b floata 函数内部定义的局部整型变量a intb b b a 引用的是哪一个a 在函数func中可看到的是floata 看不到inta 广东工业大学计算机学院 LOGO 15 函数的形式参数 续 在C语言的最新文本中增加了一个语法记号 使得可以在函数内部显式地引用外部的同名变量 上例可改写如下 inta 2 intfunc a b floata 1 intb 1 b b a b b a 则b 2 引用floata 引用inta 广东工业大学计算机学院 LOGO 16 影响变量可视性的规则举例2 分程序 或复合语句 结构 影响变量可视性的举例 inta 第一层开头 定义局部整型变量a chara 第二层开头 定义局部字符型变量a 第三层开头 floata 第四层头 定义局部实型变量a 第四层尾 a 引用的是哪个a 第三层尾 第二层尾 第一层尾 第二层的chara 所以 在符号表属性中需要记录表示该符号在程序结构上被定义的层次 广东工业大学计算机学院 LOGO 17 符号变量的存储分配信息 可以根据以下因素来确定每一个变量应分配到哪一个存储区 以及在该区中的具体位置 符号变量的存储类别定义这些变量出现的位置和次序在符号表中用相对区头的位移量表示 例如有以下程序段 C语言 inta floatb structcc intd floate c 广东工业大学计算机学院 LOGO 18 符号的其它属性 符号表中的其它重要属性 数组内情向量数组类型维数和各维的上 下界数组首地址 记录结构型的成员信息 函数及过程的形参 广东工业大学计算机学院 LOGO 19 本课内容 9 1符号表的作用和地位9 2符号的主要属性及作用9 3符号表的组织9 4符号表的管理 广东工业大学计算机学院 LOGO 20 1 符号表构造举例 假设一个语言程序发现有下列3类符号及其所需之属性 第一种造表方式 构造等长表项的多个表 注意 各属性不一定等长 广东工业大学计算机学院 LOGO 21 符号表构造举例 续1 假设一个语言程序发现有下列3类符号及其所需之属性 第二种造表方式 构造一张包括所有属性的表 缺点 可能会造成存储空间的浪费 广东工业大学计算机学院 LOGO 22 符号表构造举例 续2 假设一个语言程序发现有下列3类符号及其所需之属性 第三种造表方式 据符号属性相似程度分类造若干个表 缺点 仍然存在可能的存储空间浪费 广东工业大学计算机学院 LOGO 23 符号表构造举例 续3 下面单独考察 第一 二类符号之符号表 对第1类符号来说 属性值4栏是冗余的 而对于第2类符号 则属性值3栏是冗余的 把属性值3和属性值4合并成属性值34 在当该表项符号是属第1类时 属性值34中收集的是属性值3的值 若是第2类符号时 属性值34中收集的是属性值4的值 C语言中可用UNION来实现 这样的组织结构会增加符号表管理和运行的复杂性 但减少了空间开销 广东工业大学计算机学院 LOGO 24 各种造表方式的优缺点比较 对于单个表 管理方便一致 空间效率高 编译程序将同时管理若干个表 而且对各类符号的共同属性的管理必须设置重复的运行机制 管理集中单一 不同种类符号的共同属性可一致地管理和处理 由于属性各有不同 为完整表达各类符号的全部属性必将出现不等长的表项 以及表项中属性位置的交错重叠 这就极大地增加了管理复杂度 在管理复杂性及时空效率方面都取得折衷的效果 无法制定形式化的构造规则 依赖于符号表构造者的经验 未必能适应编译过程中出现的所有情况 广东工业大学计算机学院 LOGO 25 2 符号表项的排列 线性组织 在编译程序中 符号表项的组织传统上采用三种构造方法 线性法 二分法和散列法 1 线性组织这种方法规定符号表中表项按它的符号被扫描到的先后顺序登录 例如有一程序中出现符号的情况如下 a 第1次出现a b 第1次出现b a 第2次出现a d 第1次出现d c 第1次出现c b 第2次出现b h 表头 是表的开始位置 p 符号表当前的结束位置 优点 缺点 无空白项 存储空间效率高 查找效率低下 广东工业大学计算机学院 LOGO 26 符号表项的排列 排序组织及二分法 2 排序组织及二分法符号表中的表项按其符号的字符代码串 可以看成一个整数值 的值的大小从大到小 或从小到大 排列 优点 缺点 查找效率高 造表过程需要耗费较大的代价 表项的比较和移动 广东工业大学计算机学院 LOGO 27 符号表项的排列 散列组织 散列组织 哈希表 具有较高的运行效率 因而绝大多数编译程序中的符号表采用散列组织 关键在于采用适当的哈希函数以及冲突解决办法 广东工业大学计算机学院 LOGO 28 3 关键字域的组织 符号表的关键字域就是符号本身 它可以是语言的保留字 操作符号或标识符 包括变量名 函数名 记录结构标志等 关键字域的组织有两种方式 1 等长关键字域 段 符号表 2 不等长关键字段符号表 采用关键字池的索引结构 广东工业大学计算机学院 LOGO 29 1 等长关键字域 段 符号表 为使得符号表中存放标识符的关键字段等长 需要将关键字段设置为标识符的最大长度 例如C语言的关键字段长度是32个字节 其中前31个是存放名字 第32个是存放字符串结束标志 由于程序中的标识符长短不一 用等长结构会产生溢出或冗余 广东工业大学计算机学院 LOGO 30 关键字池的索引结构 如果希望既保证关键字段的等长 又要减少甚至消除冗余 可采用关键字池的索引结构 假设有一组标识符anexemplerofkey wrdsfield关键字段的组织结构如右图 广东工业大学计算机学院 LOGO 31 4 其它域的组织 符号表属性域的组织 根据属性性质大致分成两类 一类是符号的属性值的类型相同 并且是等长的 则该属性域的类型结构就可用其长度及类型来定义 例如boolean int float等基本数据类型另一类符号的属性值的类型相同 但不等长 则该属性域的定义不能用简单的数据类型来定义 例如 数组内情向量 广东工业大学计算机学院 LOGO 32 1 等长属性值域的组织 下面我们讨论一些典型的等长属性值域的组织 1 表示某个符号的布尔性质的属性域 可用1个bit位来表示 也可用1个布尔量来表示 如defined1 definedtrue 表示已定义defined0 definedfalse 表示尚未定义 2 表示符号的数据类型可以用若干个bit位来表示 也可用1个整型量来表示 以C语言为例 广东工业大学计算机学院 LOGO 33 等长属性值域的组织 续 对于表示符号之间关系的属性 可用指针或指针链来构造 如函数符号与它的形参符号之间的关系属性 函数 形参 指针域 例 func1 para1 para2 para3 func2 广东工业大学计算机学院 LOGO 34 指针型参数域的应用 设有一个C语言的结构体变量结构 structtag1 memb1 memb2 structtag2 memb3 memb4 memb5 memb6 memb7 stv 空 空 广东工业大学计算机学院 LOGO 35 2 2 不等长属性值域的组织 符号的某些属性值是不等长的 例如数组内情向量 设有下列两个数组array1 subscrip1 subscrip2 array2 subscrip3 subscrip4 subscrip5 subscrip6 0 值用来表示下标到此为止 广东工业大学计算机学院 LOGO 36 3 下推链域的组织 在某些程序语言的结构中 分程序的分层结构允许同名标识符具有的生存期发生重叠 即存在同名标识符 为实现这种同名标识符的语义功能 符号表中需要设立下推链域的组织 下推链域要求 在进入内层结构并发生重名标识符定义时 1 把当前符号中外层的该符号下推到下推链中 2 在符号表被下推的表项处 建立内层的同名标识符表项 广东工业大学计算机学院 LOGO 37 下推链举例 例 inti 1 func 2 floati 3 4 inti 5 5 6 inti 7 i 8 i 9 广东工业大学计算机学院 LOGO 38 本课内容 9 1符号表的作用和地位9 2符号的主要属性及作用9 3符号表的组织9 4符号表的管理 广东工业大学计算机学院 LOGO 39 符号表的行为 符号表的行为主要包括 1 符号表的初始化2 符号的登录3 符号的查找4 有关分程序结构的符号表层次管理对符号表的这些管理除初始化之外 其它都是动态进行的 广东工业大学计算机学院 LOGO 40 1 符号表的管理 初始化 不同组织方法的符号表有不同的初始化方法 符号表的表长是渐增变化的情况只需将表尾推向表头 表示该符号表中还没有任何表项 符号表的表长是确定的情况对这类符号表的初始化方法 需要将表中全部表项值清除 广东工业大学计算机学院 LOGO 41 2 符号表的管理 登录 一个符号表项的登录最基本的是该符号的名字登录 此外还有关于该名字的属性的登录 1 对于线性方法组织的符号表 通常把该表的尾指针p指向的表项是作为新创建的表项 之后将p推向下一个备用表项 广东工业大学计算机学院 LOGO 42 二分法组织的符号表的登录 2 对于二分法组织的符号表 在创建了新的表项后 根据登录符号在符号表中按用二分法选定一个位置 把该位置以后的所有原表项下移一个表项的位置 然后在选定位置登录新符号 symbolk 对于散列表 新符号的登录是通过杂凑算法决定登录表项的位置 如果产生冲突 则应用冲突解决算法 广东工业大学计算机学院 LOGO 43 名字属性的获取 名字属性大都取决于编译程序获得某个符号时 编译程序所处的程序扫描点的状态 例如在下面的程序段中获取到的符号a的属性 是取决于编译程序扫描到 a n m 时的有关状态 func x y structtag inta n m t a int Auto 动态存储区 LEVEL 1 相对于tag的位移量 n m的二维数组 广东工业大学计算机学院 LOGO 44 3 符号表的管理 查找 查找的一般步骤为 1 在保留字表和运算符表中查找该符号是否保留字或运算符 若是 转向 2 否则转向 3 2 把该符号转换为保留字或运算符的内部代码 表示 3 在标识符表中进行查找 若在查找到则表示该符号已在符号表中登录 检查是否需要登录新属性 否则表示该符号是一个新的需要登录的符号 符号表的查找算法 顺序查找 折半查找和杂凑查找 广东工业大学计算机学院 LOGO 45 4 符号表中分程序结构层次的管理 通常对于具有分程序结构的语言可用两种方式组织它们的符号表 方法一 对每个分程序建立一个独立的分表结构的符号表 方法二 把各分程序符号组织在一张单表结构的符号表中 广东工业大学计算机学院 LOGO 46 分程序结构层次的管理举例1 源程序的形式 第1层分程序inta floatb d 第2层