Part2-符号表.pptVIP

编译原理 符号表 授课：胡静 编译器的应用模型 符号表管理技术 概述 符号表的组织和作用 符号表的整理和查找 名字的作用域范围 非分程序结构语言的符号表组织 分程序结构语言的符号表组织 符号表的内容 概述 (1) 什么是符号表? 编译过程中，编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。这些信息通常记录在一张或几张符号表中。 符号表的每一项包含两部分： 名字（标识符）: 程序名、过程名、函数名、用户定义类型名、变量名、常量名、枚举值名、标号名等。 特性信息: 上述名字的种类、类型、维数、参数个数、数值及目标地址（存储单元地址）等。 概述 (2)建表和查表的必要性(符号表在编译过程中的作用) 源程序中变量要先声明，然后才能引用。 用户通过声明语句，声明各种名字，并给出它们的类型、维数等信息，编译程序在处理这些声明语句时，应该将声明中的名字及其信息登录到符号表中，同时编译程序还要给变量分配存储单元，而存储单元地址也必须登录在符号表中。 当编译程序编译到引用所声明的变量时(赋值或引用其值)，要进行语法语义正确性检查(类型是否符合要求)和生成相应的目标程序，这就需要查符号表以取得相关信息。 概述 (3)有关符号表的操作：填表和查表 填表：当分析到程序中的说明或定义语句时，应将说明或定义的名字，以及与之有关的信息填入符号表中。 例：Procedure P( ) 查表： (1) 填表前查表，检查在程序的同一作用域内名字是否重复定义； (2) 检查名字的种类是否与说明一致； (3) 对于强类型语言，要检查表达式中各变量的类型是否一致； (4) 生成目标指令时，要取得所需要的地址。 ......... 符号表的组织与作用 符号表的基本结构 “名字”域: 存放名字，一般为标识符的符号串,也可为指向标识符字符串的指针。 “信息”域: 可包括多个子域, 分别表示标识符的有关信息， 信息域表示标识符的相关信息 名字(标识符)的种类:简单变量、函数、过程、数组、标号、参数等 类型：如整型、浮点型、字符型、指针等 性质：变量形参、值形参等 值： 常量名所代表的数值 地址：变量所分配单元的首址或地址位移 大小：所占的字节数 作用域的嵌套层次: 对于数组: 维数、上下界值、计算下标变量地址所用的信息（数组信息向量）以及数组元素类型等。 对于记录（结构、联合）：域的个数，每个域的域名、地址位移、类型等。 对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等。 对于指针：所指对象类型等。 对符号表可能的操作 在整个编译期间，对符号表的操作大致可以归纳为五类： 对给定的名字，查询此名是否已在表中； 往表中填入一个新的名字 对给定名字，访问它的某些信息； 对给定名字，往表中填写或更新它的某些信息 删除一个或一组无用的项。 符号表的组织方式 1.统一符号表:不论什么名字都填入统一格式的符号表中 符号表表项应按信息量最大的名字设计,填表、查表比较方便, 结构简单, 但是浪费大量空间。 2.对于不同种类的名字分别建立各种符号表 节省空间, 但是填表和查表不方便。 3.折中办法:大部分共同信息组成统一格式的符号表，特殊信息另设附表,两者用指针连接。 符号表的整理和查找 符号表的初始化： 在编译程序刚开始时，符号表或者是空的，或者预先存放了一些保留字和标准函数名的有关项。 在编译的其他阶段，主要是对符号表进行查填的操作： 线性查找——方法最简单，但效率低 二叉树——查找效率高，但实现上略显困难 Hash表——效率最高，可实现比较复杂而且要消耗一些额外的存储空间。 线性表 构造符号表最简单和最容易的办法就是按符号出现的顺序填写各个项。 线性表中每一项的先后顺序是按先来者先填的原则安排的，编译程序不做任何排序的工作。 显式说明的程序设计语言，根据名字在说明部分出现的顺序填入表中（表尾） 隐式说明的程序设计语言，根据各名字首次引用的先后顺序填入表中。 当需要查找某个名字时，就从该表的第一项开始顺序查找。 查表操作的平均长度为(n+1)/2 对折查找与二叉树 在造表时把表格中的项按照名字的“大小”顺序整理排列。 这种经顺序整理了的表格的查找可以用对折法。 查表操作的平均长度Log2N ?1 对一遍扫描的编译程序来说，符号表是边填边引用的，这意味着每填进一个新项都需要做顺序化的整理工作。 折中办法是把符号表组织成一棵二叉树。 查找效率比对折查找要低一些，但顺序化时间要少很多 需要额外的存储空间。 Hash表 对于表格处理来说，根本问题在于如何保证查表与填表两方面工作都能高效的进行。 线性表：填表快，查表慢； 对折法：填表慢，查表快。 设有一个足够大的区域，可以填写一张含N项的符号表 构造一个地址函数H，对任何名字SYM