编译原理课件06符号表的组织与管理.ppt

1 1 第6章 符号表的组织与管理 6.1 符号表的作用 6.2 符号表的组织 6.3 符号表的建立和查找 本章小结 6.1 符号表的作用 一.符号表作用 　　存放语言程序中出现的有关标识符的属性信息。 编译程序护理标识符时主要涉及两部分信息： 标识符本身 与标识符相关的信息，如标识符的类型、种属、作用域等等 二.符号表的功能 收集有关标识符的属性，并在符号表中建立符号的相应属性信息 例如：int A; float B[5]; 上下文语义的合法性检查的依据： 检查标识符属性在上下文中的一致性和合法性 例如，在C语言中同一个标识符可作引用说明和定义说明 ┇ int i[3,5]; //定义说明i ┇ extern float i; // 引用说明i ┇ 符号的主要属性及作用 语言符号可分为：关键字符号、操作符符号、标识符符号 1.符号名： 标识符：变量的名字、函数的名字、过程的名字 通常把一个标识符在符号表中的位置的整数值称之为该标识符的内部代码 在经过分析处理的语言程序中标识符不再是一个字符串而是一个整数值 6.2 符号表的组织 一.符号表的总体组织 第1种：按照属性种类完全相同的那些符号组织在一起 优点：每个符号表中存放符号的属性个数和结构完全相同 缺点：一个编译程序将同时管理若干个符号表，增加了总体管理的工作量和复杂度 6.3 符号表的建立和查找 一.符号表的初始化 在编译过程中某个时刻，符号表的状态反映了该时刻被编译的语言程序正被编译的位置的状态。具体来说主要是反映了在该时刻语言程序中可视标识符的状态 符号表的初始化，就是在对语言程序开始编译的时刻，定义建立符号表的初始状态 五.下推链域的组织 为实现这种同名标识符的语义功能，符号表中需要设立下 　推链域的组织 下推链域的组织要求在进入一个内层结构并发生重名标识 　符定义时，需把当前符号表中外层的该符号表项下推到 　下推链中而在符号表被下推的表项处建立内层的同名识 　符的表项 例如，设有一个程序（C语言程序）如图9.17所示： 当逐个退出分程序时，下推链被逐次回推到符号表项中， 　其具体结构如图9.18所示： 例如，有一程序中出现符号的情况如下： ……………… …a………… ………b…… …a………… ………d…… …c………… ………b…… …… 则符号表中表项排列将如图9.6所示： h表示该符号表之表头，是表的开始位置 p表示该符号表的表项是符号表当前的结束位置 2.排序组织及二分法： 排序组织的符号表，就是在符号表中的表项按其符号的字 　符代码串（可以看成一个整数值）的值的大小从大到小 　（或从小到大）排列的 关于排序表的表项建立及符号查找，通常采用“二分法” 对上述例子中的符号出现情况按排序组织得到的符号表将 　如图9.7所示： 3.散列组织： 一个符号在散列表中的位置，是由对该符号进行某种函数 　操作（杂凑函数）所得到的函数值来确定的 假设选定杂凑函数fhash，对符号代码值杂凑运算之后得 　到杂凑值是Vhash，可表示为： 　Vhash=fhash(符号代码值) 设符号的散列位置Lhash则有：Lhash=mod(Vhash,N)， 　其中N为散列表的表长 一个具有符号代码值为Vsymbol的表项散列如图9.8： 散列冲突：不同符号散列到同一表项位置的现象 解决办法：表长N取一个素数、多次散列 杂凑函数的选取是构造散列表的关键 目前编译程序中，一般采用对符号代码的位操作作为杂凑 　函数，见得最多的是符号代码的字符段叠加或加权叠加 　以及符号代码的对折或多折等位操作 三.关键字域的组织 在编译程序中，符号表的关键字域就是符号本身，它可以 　是语言的保留字，操作符号或标识符（包括变量名、函 　数名、记录结构标志等） 规定外部规则的目的是考虑到操作系统、汇编程序及其需 　要联系的系统之间的匹配，而规定内部规则的目的是考 　虑到编译程序本身对标识符的识别和区分 比如上述C语言的关键字段长度可以是32个（其中31个是 　存放名字，余下一个是存放字符串结束标志︼，这是C 　语言处理所需要的），如图9.9所示： 既要保证关键字段的等长，又要减少甚至消除冗余，采用 　关键字池的索引结构是可取的 例如，一组标识符： an exemplar of key-words field 关键字段的组织结构如图9.10所示： 四.其他域的组织 1.等长属性值域组织： 可以取相应的数据类型表达属性值 表示该符号布尔性质的属性域，可用1个bit位来表示，也 　可用1个布尔量表示： defined 1表示已定义　　defined 0表示没定义　 defined true 表示已定义　defined false表示没定义 表示符号的基本数据类型可以用3个bit位来表示，也可用 1个整型量来