一、符号表的作用是什么

1. 收集符号属性

• 例如，编译程序分析到下述两个说明语句

int A;
float B[5];

则在符号表中收集到关于符号A的属性是一个整型变量，关于符号B的属性是具有5个浮点型元素的一维数组。

2. 上下文语义的合法性检查的依据

同一个标识符可能在程序的不同地方出现，而有关该符号的属性是在这些不同情况下收集的。特别是在多趟编译及程序分段编译（在PASCAL及C中以文件为单位）的情况下，更需检查标识符属性在上下文中的一致性和合法性。通过符号表中属性记录可进行相应上下文的语义检查。

• 例如，在一个C语言程序中出现

int i [3,5]; //定义整型数组i
float i[4,2]; //定义实型数组i,重定义冲突

3. 作为目标代码生成阶段地址分配的依据

每个符号变量在目标代码生成时需要确定其在存储分配的位置（主要是相对位置）。语言程序中的符号变量由它被定义的存储类别（如在C、FORTRAN语言中）或被定义的位置（如分程序结构的位置）来确定。首先要确定其被分配的区域。

例如，在C语言中首先要确定该符号变量是分配在公共区（extern）、文件静态区（extern static）、函数静态区（函数中static）、还是函数运行时的动态区（auto）等。其次是根据变量出现的次序，（一般来说）决定该变量在某个区中所处的具体位置，这通常使用在该区域中相对区头的相对位置确定。而有关区域的标志及相对位置都是作为该变量的语义信息被收集在该变量的符号表属性中。

二、符号表的组织方式

1. 符号表分为几大栏,主键是什么？

• 名字栏: 也称主栏,关键字栏.
• 信息栏: 记录相应的不同属性,分为若干子栏

2. 什么是各项,各栏等长,说明利弊?

各项各栏所占存储单元的长度固定,
可以用固定分配空间,但是会有剩余空间未使用造成浪费

什么是间接方式安排符号表的信息？

如果各种名字所需的信息（INFORMATION ）空间长短不一，那么，我们可把 一些共同属性直接登记在符号表的信息栏中，而把某些特殊属性登记在别的 地方，并在信息栏中附设一指示器，指向存放特殊属性的地方

三、符号表的整理、查找

1. 顺序表；

使用一个一维数组或多个一维数组存放符号串名字和相关性息

• 特点：

1. 按名字出现的先后顺序依次填入;
2. 查找时从头到尾逐个查找;

• 缺点: 查找很慢
• 改进的思路:

1. 按照编程习惯可以反序查找。
2. 按“最新最近”访问原则形成一条指向表的链子,每次查找时都按着这条链所指的顺序查找

2. 对半查找与二叉树；

• 在造表时把表格中的项按名字的“大小”顺序整理排列。
• 所谓名字的“大小”通常是指名字的内码二进制。
• 对于经顺序化的表格的查找可用对折法。

a. 对折法的查找方法如下：

1. 首先把要查找的项和中项（即第[n/2]+1项）作比
   较，若相等，则宣布查找成功。
2. 若要查找的项小于中项，则继续在1〜[n/2]的各项
   中去查找。
3. 若要查找的项大于中项，则就到[n/2]+2〜n的各项
   中去查找。

平均查找次数1+log2n

b. 杂凑技术。

1. 假定有一个足够大的区域，这个区域用来填写一张含N项的符号表。构造一个地址函数H，对任何名字，H函数的取值在0至N-1之间。即不论对此项查表或填表，都能从H函数中获得它在表中的位置。
2. 对地址函数H有两点要求：
   1. 函数的计算要简单、高效；
   2. 函数值能比较均匀的分布在0至N-1之间。
3. 构造函数H的办法：

• 直接地址法、数字分析法、
• 平方取中法、折叠法、除留余数法、随机数法

4. 解决地址冲突的办法：

• 开放地址法、再哈希法、
• 链地址法、建立一个公共溢出区
• 杂凑技术：使用一张杂凑链表通过间接方式查填符号表。

将具有相同杂凑值符号名连成一串，便于线性查找。杂凑表是一个可容纳N个指示器值的一维数组，它的每个元素的初值全为null。符号表除了通常包含的栏外，还增设了一链接栏，他把所有持有相同杂凑值的符号名连接成一条链。

四、名字的作用范围

1. 什么是最近嵌套作用域原则，具体描述Pascal语言的名字是否满足最近嵌套作用域原则？

• 最近嵌套作用域规则：
  即对每个过程指定一个唯一的编号，以便跟踪过程里的局部名字。在符号表中，表示局部名字用一个二元组： < 名字,过程编号 >对一个名字查找符号表是：只有当表项中的名字其字符逐个匹配，并且该记录相关的编号和当前所处理的过程的编号匹配时，才能确定查找成功.

2. 嵌套结构型程序设计语言的符号表：

1. 针对符号表设计为栈符号表，新名字出现总是从栈顶填入。为了保证从内层向外层查，查找 操作从符号表的栈顶往底部查找。TOP指向栈顶第一个可用单元，P总是指向最新子符号表首地址。
2. 过程的嵌套层次表（display），是引入的一个显示层次关系表。其作用是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或 函数）相应的子符号表在栈符号表中的起始位置（相对地址）。
   display表本身也是一个栈，每进入一个新的过程（或函数），栈顶指针增1；每退出一个新的过程（或函数），栈顶指针减1。栈顶指针总是指向当前正在处理的最内层的过程在栈符号表中 的起始位置。
3. 在信息栏中引入一个指针域（previous)，用来链接它在同一个过程内的下一名字在表中的下标（相对位置）。每一层最后一个域名字，指针域之值为0。这样每当需要查找个新名字时，就能通过display表找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置。然后通过指针域可以找到同一个过程内的所有被说明的名字。

五、符号表的内容

（1）类型（整、实、双实、字符、指针等）；
（2）种属（简单变量、数组或结构体等）；
（3）长度（所需的存储单元数）；
（4）相对数（存储单元相对地址）；