编译-第5章-符号表管理技术

5.1 概述

5.1.1 符号表的概念及建立和访问时间

用来记录源程序中各种名字的特性信息，因此也叫名字特性表

名字（标识符）：程序名，过程名，函数名，用户定义类型名，变量名，常量名等

特性信息：种类，类型（浮点型等），维数，参数个数及目标地址等

源程序中变量先声明，才能引用

所以当遇到声明语句时，将声明中的名字及信息登录到符号表

在语法分析阶段不使用表处理程序，因为到语义分析和代码生成时，许多与标识符有关的属性才能够相继填入符号表

在一遍中完成词法分析，语法分析，语义分析和代码生成阶段的任务。由声明语句所说明的标识符的属性，在代码生成期间识别出来能立即填入表中

5.1.3 在符号表上的操作

• 填表
• 查表
  • 填表前先查表，在同一作用域内是否重复定义
  • 名字的种类是否与说明一致

5.2 符号表的组织和内容

5.2.1 符号表的结构和内容

符号表由一系列行组成，每行均包含“名字”域和“特性”域

• 名字域：存放名字。一般为标识符的符号串，也可以为指向标识符字符串的指针
• 特性域：特性域包括很多个子域

5.2.2 符号表的组织方式

1. 统一符号表
   1. 表项按照最大信息量的名字设计
   2. 查表方便，结构简单，浪费大量的空间
2. 对于不同种类的名字分别建立各种符号表
   1. 节省空间
   2. 填表和查表不方便
3. 折中办法——共同信息组成统一格式的符号表，特使信息设置附表，用指针连接

5.3 非分程序结构语言的符号表组织

非分程序结构语言：不允许有嵌套

以FORTRAN为例：

5.3.1 标识符（用户自定义的）的作用域及基本处理方法

1. 作用域

   1. 全局：子程序名，函数名和公共区名 common
   2. 局部：程序单元中定义的变量

2. 符号表的组织：

   

3. 基本处理办法

   1. 将函数名，子程序和公共区变量填全局符号表
   2. 在程序单元读到声明部分，构造局部符号表
   3. 在程序的可执行语句部分读到标识符，查表先局部后全局
   4. 程序单元编译结束，如果是一遍扫描的编译程序，释放局部符号表
   5. 当程序编译完成，释放全部符号表

5.3.2 符号表的组织方式

1. 无序符号表——扫一个建一个，查表要逐项查，n条记录的平均查找长度为$(n+1)/2$
2. 有序符号表——字典序，二分查表
   1. 如果是线形查表，平均查找长度仍然为$(n+1)/2$，和无序符号表对比，几乎没有任何值得注意的优点，只是可用于直接产生交叉引用表
   2. 如果是二分查表，平均查找长度为$log_2(n+1)$
3. 散列符号表

5.4 分程序结构语言的符号表组织

主流的语言，能嵌套

5.4.1 标识符的作用域及基本处理办法

1. 作用域：局部于最小模块
2. 基本处理办法
   1. 建表：不能重复，不能遗漏
   2. 查表：按照标识符的作用域查找

5.4.2 分程序表结构

• outern——指明该分程序的直接外层分程序的编号
• ecount——记录该分程序符号表登记项的个数
• pointer——指向该分程序符号表的起始位置

• 分程序索引表的形成顺序——每个模块头的出现顺序
• 分程序符号表的形成顺序——每个模块的识别顺序
  • 闭分程序的次序（程序中END出现的次序）
  • 构造一个栈
  • why？保证分程序的符号表能连续的挨在一起

函数名和函数的参数分布在不同层，参数一般分布在下一层