第五章编译程序的数据结构和符号表.ppt

第五章: 编译程序的数据结构和符号表,5.1 分配型数据结构5.2 查找型数据结构,概述,在编译过程中需要建立并保持一批表格符号表。从提高编译程序 的工作效率上考虑，有关的数据结构的设计就显得非常重要。从使用角度上看可以分为：查找型数据结构和分配型数据结构。查找型数据结构在编译过程中用于构造不同的信息表，保存源程序中不同实体的属性信息。特点是每个实体的项只创建一次，但可以查询多次，所以查询效率很重要。分配型数据结构主要用于处理嵌套结构的程序。其特点是分配给实体的内存地址对实体用户是可知的。因此不会对其进行查询操作，但分配和回收的速度和内存的使用效率却是十分重要的。,5.2.1 查找型数据结构,(1)什么是符号表?在编译过程中，编译程序用于记录源程序中各种名字的特性信息， 所以也称为名字特性表。名字： 程序名、过程名、函数名、用户定义类型、变量名、符号名字。特性信息：名字种类、类型、维数、参数个数及目标地址（存储单元地址）等。,(2) 建表和查表的必要性 (符号表在编译过程中的作用),源程序中变量要先声明，然后才能引用。用户通过声明语句，声明各种名字，以及给出它们的类型维数等信息，编译程序在出来这些声明语句时，因将声明中的名字以及信息登录到符号表中，同时编译还要给变量分配存储单元，而存储单元地址也必须登录在符号表中。当编译程序编译到引用所声明的变量时（赋值或引用其值）要进行语法语义正确性检查 类型是否符合要求和生成相应的目标程序，这就需要查符号表来取得相关信息。,1.语法分析和语义分析 说明语句赋值语句的语法规则 上下文有关分析；是否声明； 类型一致性检查2. 生成目标代码LOAD a 的地址ADD b 的地址STO x 的地址,例: int x,a,b; L: x:=a+b; ,建表分配存贮,符号表,数据区,(3) 有关符号表的操作：填表和查表,填表:当分析到程序中的说明或定义语句时应将说明或定义的名字以及与之有关的信息填入符号表中 例：Procedure P()查表:(1) 填表前查表检查在程序的同一作用域内名字是否重复定义(2) 检查名字的种类是否与说明一致(3)对于强类型语言要检查表达式中各变量的类型是否一致(4) 生成目标指令时要取得所需要的地址,5.2.2 符号表的组织与内容,(1)符号表的结构与内容符号表的基本结构如下 名字 特性(信息) “名字”域:存放名字。一般为标识符的符号串，也可为指向标识符字符串串指针,“特性”域：可包括多个子域，分别表示标识符的有关信息。如：名字（标识符）的种类：变量、函数、过程、数组、标号、参数等类型：如整型、浮点型、字符型、指针等性质：变量形参、值形参等名字：常量名地址：变量所分配单元的首址或地址位移大小：所占的字节数,名字 特性(信息),作用域的嵌套层次,对于数组：维数、上下界值、计算下标量地址所用的信息以及数组元素类型等对于记录（结构、联合）：域的个数、每个域名、地址位移、类型等对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等对于指针：所指对象类型等,(2) 组织方式,1.统一符号表:无论什么名字都填入统一格式的符号表中符号表表项应按信息量最大的名字设计 填表查表比较方便 结构简单 但是浪费大量空间2.对于不同种类的名字分别建立各种符号表节省空间 但是填表和查表不方便3.折中办法: 大部分共同信息组成统一格式的符号表。 特殊信息另设附表,两者用指针连接.,例：begin array B1.100end,补充指针连接,