第9章符号表08.pptVIP

第九章 符号表;符号表的主要功能： ⑴ 收集符号属性。根据(程序中)标识符的说明部分收集标识符的属性并填入在符号表中。 ⑵ 上下文语义检查的依据。 编译程序工作时必须检查标识符在上下文中的一致性和合法性--通过符号表中的属性记录进行语义检查。 ⑶ 作为目标代码生成阶段地址分配的依据。 每个符号变量在生成目标代码时都需要为其分配存储区域。而分配的依据是变量的存储类别以及在相应区域中的位置。;9.2 符号的主要属性及作用; ⑶ 符号的存储类别。由程序中符号的存储类别说明或定义位置得到，是编译过程的语义处理、检查和进行存储分配的依据，也决定了符号变量的作用域、可视性、生命周期等。 ⑷ 符号的作用域和可视性。 ? 作用域：程序中起作用的范围。由符号定义的存储类别或定义的位置决定。 ? 可视性：程序中是否可见(并真正起作用)。原因：函数的形参与外部变量同名；嵌套的分程序结构中不同层中的变量同名。 符号定义的存储类别、定义的层次位置决定了符号的作用域和可视性。 ⑸ 符号变量的存储分配信息。符号变量应分配的存储区域及在该区域中的具体位置。; ? 静态存储区：分配后该区域在整个程序运行过程中不变。 ? 动态存储区：调用符号变量所在的分程序时分配，调用结束立即释放。 ⑹ 符号的其它属性。主要有： ? 数组内情向量：数组内情信息(类型、维数、各维的上下限、首地址)，是对数组进行存储分配的依据。 ? 结构体类型成员信息：结构体内各个成员、成员之间的排列次序等，是确定结构体变量所需存储空间及成员位置的依据。 ? 函数或过程的形参：形参是局部变量又是函数或过程对外的接口，形参的个数、次序及每个形参的类型等体现了函数或过程调用的属性。;9.3 符号表的组织;⒉ 排序组织及二分表 按符号的字符代码串(整数值)的大小组织成二叉排序树(BST树)。 ? 优点：查找、插入、删除的效率远高于线性组织方式，特别当符号个数不确定时效率更高。 ? 缺点：存储空间的开销比线性组织方式大。 ⒊ 散列组织 目前大多数编译程序中的符号采用这种组织方式。散列表中表项位置是由对表项的关键字(符号的代码)的散列函数值确定。关键问题是： ? 散列函数的构造：散列表定长为N。 ? 冲突解决方法：采用多次散列法。;9.3.3 表项属性的组织;⒉ 其它属性项的组织 除关键字外，其它属性项按性质可分为两类，分别有不同的组织方式： ① 等长属性项：属性项具有相同的类型且都等长，用类型和长度定义。即用相应的类型表示属性值。 ? 数据类型：根据语言所规定的数据类型的种类用若干位(一般是3bits)或一个整型变量表示。 ? 符号间的关系：用指针或指针链构造。 ② 不等长属性项：符号表中的属性项定义为指针类型，实际的属性值保存在其它存储区域，其存储位置(存储空间的首地址)由符号表中相应的指针所指向。;⒊ 下推链域的组织 分程序结构中允许分层结构中使用同名(且同类型)的标识符，会出现在某一分层结构中同名标识符作用域重叠的情况。而真正起作用的是最内层中的标识符，但其它所有外层的标识符仍然存在。解决办法是：符号表中设立下推链域组织。 基本方法：当在内层结构中出现同名标识符的定义时，首先将当前符号表中外层的该符号表项下推到下推链中；然后在符号表中原被下推的表项处建立内层同名标识符的表项。当逐个退出分程序时，下推链被逐次回推到符号表项中。 详细讨论见符号表的管理。;9.4 符号表的管理;9.4.2 符号表的查找;9.4.3 分程序结构的符号表的管理; ? 当在语句中扫描到一个标识符时，首先查该层的标识符表：若查不到，再在其直接外层分程序的标识符表中去查找，如此等等，一旦在某外层的标识符表中查到了该标识符，从表中取出有关信息并作相应处理；若遍查所有外层分程序的标识符表都找不到该标识符，则表示标识符未定义，语法错误。 根据上述的分析，分程序结构的符号(标识符)表的组织有两种组织方式。 ⑴ 分层符号表组织 ① 分层组织符号表的表项。各程序单元的符号表登记项连续地组织在一起。 ② 建立“分程序表”。记录各程序单元所对应的符号表的有关信息。; “分程序表”中的登记项是在自左至右扫描源程序的过程中依次顺序填写，每一个程序单元对应一个登记表项，则登记表项的序号就表征了各程序单元的序号。 “分程序表”和“符号表”的结构如下图。“分程序”表的各属性说明如下： ? No：序号，表征了程序单元的序号； ? ecount：本程序单元的符号表中的登记项的数目； ? outern：本程序单元的直接外层程序单元的编号； ? point