第七章符号表.ppt

第七章: 符号表管理技术 7.1 概述 7.2 符号表的组织与内容 7.3 非分程序结构语言的符号表组织 7.4 分程序结构语言的符号表组织 7.1 概述 (1)什么是符号表? 在编译过程中，编译程序用于记录源程序中各种名字的特性信息， 所以也称为名字特性表。 名字： 程序名、过程名、函数名、用户定义类型、变量名、符号名字。 特性信息：名字种类、类型、维数、参数个数及目标地址（存储单元地址）等。 (2) 建表和查表的必要性 (符号表在编译过程中的作用) 源程序中变量要先声明，然后才能引用。 用户通过声明语句，声明各种名字，以及给出它们的类型维数等信息，编译程序在出来这些声明语句时，因将声明中的名字以及信息登录到符号表中，同时编译还要给变量分配存储单元，而存储单元地址也必须登录在符号表中。 当编译程序编译到引用所声明的变量时（赋值或引用其值）要进行语法语义正确性检查 类型是否符合要求和生成相应的目标程序，这就需要查符号表来取得相关信息。 例: int x,a,b; … … L: x:=a+b; … 1.语法分析和语义分析 说明语句赋值语句的语法规则 上下文有关分析；是否声明； 类型一致性检查 2. 生成目标代码 LOAD a 的地址 ADD b 的地址 STO x 的地址 (3) 有关符号表的操作：填表和查表 填表:当分析到程序中的说明或定义语句时应将说明或定义的名字以及与之有关的信息填入符号表中 例：Procedure P() 查表: (1) 填表前查表检查在程序的同一作用域内名字是否重复定义 (2) 检查名字的种类是否与说明一致 (3)对于强类型语言要检查表达式中各变量的类型是否一致 (4) 生成目标指令时要取得所需要的地址 7.2 符号表的组织与内容 (1)符号表的结构与内容 符号表的基本结构如下 名字 特性(信息) “名字”域:存放名字。一般为标识符的符号串，也可为指向标识符字符串串指针 名字 特性(信息) “特性”域：可包括多个子域，分别表示标识符的有 关信息。如： 名字（标识符）的种类：变量、函数、过程、数组、标号、参数等 类型：如整型、浮点型、字符型、指针等 性质：变量形参、值形参等 名字：常量名 地址：变量所分配单元的首址或地址位移 大小：所占的字节数 作用域的嵌套层次 对于数组：维数、上下界值、计算下标量地址所用的信息以及数组元素类型等 对于记录（结构、联合）：域的个数、每个域名、地址位移、类型等 对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等 对于指针：所指对象类型等 (2) 组织方式 1.统一符号表:无论什么名字都填入统一格式的符号表中 符号表表项应按信息量最大的名字设计 填表 查表比较方便 结构简单 但是浪费大量空间 2.对于不同种类的名字分别建立各种符号表 节省空间 但是填表和查表不方便 3.折中办法: 大部分共同信息组成统一格式的符号表。 特殊信息另设附表,两者用指针连接. 例：begin array B[1..100]…end 7.3非分程序结构语言的符号表组织 (1) 分程序的结构语言:每个可独立进行编译的程序单元是一个不包含有子模块的单一模块.如Fortran语言 Fortran程序构造 主程序 子程序 及函数 (2) 标识符的作用域及基本处理办法 1.作用域: 全局: 子程序名,函数名和公共区名 局部: 程序单元中定义的变量 2. 符号表的组织 3.基本处理办法 1 子程序函数名和公共区变量填入全局符号表 2 在声明部分读到标识符,造局部符号表 查本程序单元局部 符号表,有无同名 3 在语句部分读到标识符 查表 查本程序单元局部 符号表有无同名 (3) 符号表的组织方式 4.程序单元结束:释放该程序单元的局部符号表 5.程序编译完成:释放全部符号表 1.无序符号表:按扫描顺序建表,查表要逐项查找 查表操作的平均长度为:n+1/2 2. 有序符号表符号表按变量名进行字典式排序 线性查表:n+1/2 折半查表:log2n-1 3.散列符号表(Hash) 表: 符号表地址=Hash(标识符) 解决:冲突 7.4分程序结构语言的符号表组织 (1) 分程序的结构语言: 块内可嵌入子模块 (2) 标识符的作用域和基本处理方法 作用域:标识符局部于所定义的模块(最小模块) ①模块中所定义的标识符作用域是定义该标识符的子程序 A为内分程序局部变量 A为内分程序全局变量 begin ……