教学要点
符号表的组织和作用
整理和查找
哈希函数
LeBlanc-Cook符号表处理方法
关联表和中心引用表第八章 符号表
符号表：
将名字映射到编译器已知的有关信息的一个字典。
符号表的作用,
一致性检查和作用域分析 ;
辅助代码生成,
符号表的组织与作用
符号表的每一项 (入口 )包含两大栏,
名字栏，也称主栏，关键字栏
信息栏，记录相应的不同属性，如：地址、值、
作用域等，分为若干子栏,
对符号表的操作,
填入名称 （ insert）
查找名字 （ lookup）
访问信息
填写修改信息
删除符号表的内容
符号表的信息栏中登记了每个名字的有关性质
类型：整、实或布尔等
种属：简单变量、数组、过程等
大小：长度，即所需的存储单元字数
相对数：指分配给该名字的存储单元的相对地址
对符号表进行操作的时机：
定义性出现
使用性出现
按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表,…
符号的组织方式,
1,安排各项各栏的存储单元为固定长度
2,用间接方式安排各栏存储单元固定长度 的 符号表
有些语言对标识符有长度限制，如：不超过 8个字符，则可用固定长度（两个机器字）
的符号表。
间接方式的符号表
有些语言对标识符无长度限制或者范围很宽，如：
100个字符，则都用 25个字很浪费，
一般引入一个字符数组来存放有关信息，在符号表的地址栏存放对应的指针。
通过符号表访问内情向量
不同的符号，所需信息空间长度不一样，可把共同属性放在符号表中，而把特殊属性存放在别的地方，在符号表中设一个指针指示信息的存放位置。
一个 可存放 N项的 符号表 在内存中可采用下列两种方式之一（假设每项需要 K个字）,
1,把每一项置于连续 K个 存储单元中，构成一张 K*N的表
2,把整个符号表分成 m个子表，如 T1,T2,…T m，
每个子表含有 N项,
例,PASCAL程序段：
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.1 符号名表 SNT
NAME INFORMATION
M 形式参数,整型,值参数
N 形式参数,整型,值参数
K 整型,变量表 0.2 常数表 CT
值
(VALUE)
(1) 1
(2) 4
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.3 入口名表 ENT
NAME INFORMATION
(1) INCWAP 二目子程序,
入口四元式,1
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.4 标号表 LT
NAME INFORMATION
(1) START 四元式,(4)
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.1 符号名表 SNT
NAME INFORMATION
M 形式参数,整型,值参数
N 形式参数,整型,值参数
K 整型,变量表 0.2 常数表 CT
值
(VALUE)
(1) 1
(2) 4表 0.3 入口名表 ENT
NAME INFORMATION
(1) INCWAP 二目子程序,
入口四元式,1
表 0.4 标号表 LT
NAME INFORMATION
(1) START 四元式,(4)
表 0.5 四元式表 QT
OPR OPN1 OPN2 RESULT
(1) link
(2) par INCWAP 1 M
(3) par INCWAP 2 N
(4) + M 1 K
(5) + N 4 M
(6),= K N
(7) return
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
整理和查找
1,线性查找
按关键字出现的顺序填写各项。
填表快，查找慢。
结构简单，节省空间，效率低，查找时间 复杂度,O(n)。
改进,自适应线性表
给每项附设一个指示器，这些指示器把所有的项按“最新最近”
访问顺序连接成一条链。每次查表时都按这条链所指的顺序，一旦查到之后就即时改造这条链，使得链头指向刚才查到的那个项。
每当填入新项时，总让链头指向这个最新项。含有这种链条的线性表叫做自适应线性表。
2,二分查找
表格中的项按名字的,大小,顺序整理排列。
填表慢,查找快。查找时间 复杂度,O(Log2n)
改进：组织成二叉树。
二叉树的形成过程是：令第一个碰到的名字作为“根”结点，它的左、右指示器均置为 null。
当要加入新结点时，首先把它和根结点的值作比较，小者放在右枝上，大者放在左枝上。如果根结点的左（右）枝已成子树，则让新结点和子树的根再作比较。重复上述步骤，直至把新结点插入使它成为二叉树的一个端末结点
（叶）为止。
二分查找
（ a）按名字大小顺利整理 （ b）二叉树二叉树
二叉树的查找效率比对折查找效率显然要低一点，而且由于附设了左、右指示器，
存储空间也得多耗费一些。但它所需的顺序化时间显然要少得多，而且每查找一项所需的比较次数仍是和 log2N成比例的。因此，它是一种可取的办法。
3,杂凑查找 (HASH技术 )
杂凑函数 H(SYM),0~N-1
N,符号表的项数。
要求,1,计算简单高效
2,函数值分布均匀
填表快，查找快杂凑表的大小
编译器编写者必须回答的一个问题是要初始化多大的“桶”数组。
通常，在编译器构成时，“桶“的大小就固定了，其范围从几百到上千。
一般，“桶”数组的大小要求是一个素数，
可使杂凑函数运行得更好。
通用杂凑函数
在符号表中使用的杂凑函数将字符串 (标识符名字 )
转换成 0...size-1范围内的一个整数。
一般分 3步进行,
将字符串中的每个字符转换成一个非负整数。
将这些整数用一定的方法组合成一个整数。
把结果调到 0...size-1范围。
将每个字符转换成非负整数
通常使用编译器实现语言内嵌的转换机构把每个字符转换成非负整数。
如 Pascal的 ord函数将字符串转换成整数
（ ASCII值）。类似地，在 C语言中，如果在算术表达式中使用字符或把它赋给一个整型变量，就会自动地将其转换成整数。
把结果调到 0...size-1范围
使用取模 (modulo)函数能调整一个非负整数到
0...size-1范围内，它返回用 size去除一个数所得的余数。
这个函数在 Pascal中称作 mod，在 C中用 %表示。
使用这种方法时,size最好是一个素数。否则，
随机分配的整数集不会将目标值随机分配到
0...size-1范围内，容易造成造成冲突。
把多个整数整合为一个整数
杂凑表实现需要考虑每个名字中所有的字符对应的整数怎样整合为一个整数。
一种方案：忽略许多字符，只把开头的几个字符，
或第一个、中间的和最后一个字符的值加在一起。
XTEMP和 TEMPX就可能出现整数值相同的情况！！
因此，整合时需要各字符出现的位置问题，而不能作简单相加。
把多个整数整合为一个整数
为不同位置出现的字符赋以不同的权值。
设某个名字对应的字符串为 c１ c２ … c ｎ,ci是第 i个字符的数字值，考虑在对名字进行比较时都从左至右进行，所以第ｉ位的权值应该比第ｉ＋１位高，
故可设计第ｉ个字符对应的权值为 αｎ－ｉ 。
把多个整数整合为一个整数
若 ci是第 i个字符的数字值，则整合的公式如下：
αn-1c1+αn-2c2+…+αc n-1+cn＝
ｎ
=(∑αn-ici)
ｉ =1
α的选择非常重要。可选 16或 128，这样乘法可用移位完成。
构造杂凑函数
若 ci是第 i个字符的数字值，这里 n是名字中的字符个数。公式如下：
h=(αn-1c1+αn-2c2+…+αc n-1+cn)mod size
ｎ
=(∑αn-ici) mod sizeｉ =1
编程实现时常用递推式，设 hi是在第 i步计算的部分杂凑值，那么 hi根据下面的递归公式计算：h
0=0,hi=αhi－ 1+ci，最后的杂凑值用 h=hn mod size计算。
构造杂凑函数
在公式中ｈ有时可能溢出导致负数，特别是在双字节整数的机器中当 α较大时。
注意到在循环过程中的每一步都可以进行求 MOD运算减小ｈ的值，而不影响最后求
MOD的结果。
所以编程值常用的递归公式实际为：
h0=0,hi=（ αhi－ 1+ci）ｍｏｄ ｓｉｚｅ
程序清单 符号表的杂凑函数
#define SIZE,..
#define SHIFT 4
int hash ( char * key )
{ int temp = 0;
int i = 0;
while (key[i] != '\0')
{ temp = ((temp << SHIFT) + key[i]) % SIZE;
+ + i ;
}
return temp;
}
LeBlanc-Cook符号表处理方法
在遇到每个作用域时按顺序给它赋一个序号，最外层的作用域赋 0。
所有的编号都不相同，并不表示词法的嵌套层次，但内层作用域的序号大于外层作用域的序号。
所有名字以名字为关键字哈希后被放入一个大散列表中。
每项含名字、类属（常量、变量、类型、过程、参数、域名字等）、作用域编号、类型（指向另一个符号表项的指针）等。
符号表还包括一个作用域堆栈。
它按顺序指明组成当前引用环境的所有作用域。在语义分析器扫描过程中，在进入或退出程序时分别压栈和弹栈。
每项包括作用域编号、是否闭区域等信息。
LeBlanc-Cook符号表处理方法
当需要查找名字时，根据该名字的哈希值顺着对应的链表向下找。
对于每个匹配项，都向下扫描作用域堆栈，看这个项所在的作用域是否可见。
对于作用域编号为 0的项，不需要查找堆栈。
堆栈的查找深度不应超过最上面的闭区域。
让导入项、导出项在它们的作用域外可见的方法是在表中加字段，让其包含指向实际项的指针。
Module-2程序
LeBlanc-Cook符号表处理方法找到最外层作用域关联表和中心引用列表
实践中，动态作用域的实现常采用两种组织方式
关联表 （ A表,LISP中采用）
一个名字 /值对表，类似于堆栈。
当执行过程中进入一个作用域时，解释器把该作用域的名字压入表的前端，退出时删去，查找时从表的前端开始查找
中心引用列表关联表关联表和中心引用列表
关联表的问题是查找一个名字可能要花很多时间，特别是当该名字很早就定义时。
为解决这一问题，引入了中心引用列表。
在中心引用列表中，每个不同的名字都有一个表（堆栈），其最近的约束出现在表的顶端。
查找加快。
在 LISP组中，用关联表实现动态作用域的方式称为深约束，而用中心引用列表称为浅约束。
中心引用表
符号表的组织和作用
整理和查找
哈希函数
LeBlanc-Cook符号表处理方法
关联表和中心引用表第八章 符号表
符号表：
将名字映射到编译器已知的有关信息的一个字典。
符号表的作用,
一致性检查和作用域分析 ;
辅助代码生成,
符号表的组织与作用
符号表的每一项 (入口 )包含两大栏,
名字栏，也称主栏，关键字栏
信息栏，记录相应的不同属性，如：地址、值、
作用域等，分为若干子栏,
对符号表的操作,
填入名称 （ insert）
查找名字 （ lookup）
访问信息
填写修改信息
删除符号表的内容
符号表的信息栏中登记了每个名字的有关性质
类型：整、实或布尔等
种属：简单变量、数组、过程等
大小：长度，即所需的存储单元字数
相对数：指分配给该名字的存储单元的相对地址
对符号表进行操作的时机：
定义性出现
使用性出现
按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表,…
符号的组织方式,
1,安排各项各栏的存储单元为固定长度
2,用间接方式安排各栏存储单元固定长度 的 符号表
有些语言对标识符有长度限制，如：不超过 8个字符，则可用固定长度（两个机器字）
的符号表。
间接方式的符号表
有些语言对标识符无长度限制或者范围很宽，如：
100个字符，则都用 25个字很浪费，
一般引入一个字符数组来存放有关信息，在符号表的地址栏存放对应的指针。
通过符号表访问内情向量
不同的符号，所需信息空间长度不一样，可把共同属性放在符号表中，而把特殊属性存放在别的地方，在符号表中设一个指针指示信息的存放位置。
一个 可存放 N项的 符号表 在内存中可采用下列两种方式之一（假设每项需要 K个字）,
1,把每一项置于连续 K个 存储单元中，构成一张 K*N的表
2,把整个符号表分成 m个子表，如 T1,T2,…T m，
每个子表含有 N项,
例,PASCAL程序段：
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.1 符号名表 SNT
NAME INFORMATION
M 形式参数,整型,值参数
N 形式参数,整型,值参数
K 整型,变量表 0.2 常数表 CT
值
(VALUE)
(1) 1
(2) 4
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.3 入口名表 ENT
NAME INFORMATION
(1) INCWAP 二目子程序,
入口四元式,1
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.4 标号表 LT
NAME INFORMATION
(1) START 四元式,(4)
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
表 0.1 符号名表 SNT
NAME INFORMATION
M 形式参数,整型,值参数
N 形式参数,整型,值参数
K 整型,变量表 0.2 常数表 CT
值
(VALUE)
(1) 1
(2) 4表 0.3 入口名表 ENT
NAME INFORMATION
(1) INCWAP 二目子程序,
入口四元式,1
表 0.4 标号表 LT
NAME INFORMATION
(1) START 四元式,(4)
表 0.5 四元式表 QT
OPR OPN1 OPN2 RESULT
(1) link
(2) par INCWAP 1 M
(3) par INCWAP 2 N
(4) + M 1 K
(5) + N 4 M
(6),= K N
(7) return
PROCEDURE INCWAP(M,N:INTEGER);
LABEL START;
VAR
K:INTEGER;
BEGIN
START:
K:=M+1;
M:=N+4;
N:=K;
END.
整理和查找
1,线性查找
按关键字出现的顺序填写各项。
填表快，查找慢。
结构简单，节省空间，效率低，查找时间 复杂度,O(n)。
改进,自适应线性表
给每项附设一个指示器，这些指示器把所有的项按“最新最近”
访问顺序连接成一条链。每次查表时都按这条链所指的顺序，一旦查到之后就即时改造这条链，使得链头指向刚才查到的那个项。
每当填入新项时，总让链头指向这个最新项。含有这种链条的线性表叫做自适应线性表。
2,二分查找
表格中的项按名字的,大小,顺序整理排列。
填表慢,查找快。查找时间 复杂度,O(Log2n)
改进：组织成二叉树。
二叉树的形成过程是：令第一个碰到的名字作为“根”结点，它的左、右指示器均置为 null。
当要加入新结点时，首先把它和根结点的值作比较，小者放在右枝上，大者放在左枝上。如果根结点的左（右）枝已成子树，则让新结点和子树的根再作比较。重复上述步骤，直至把新结点插入使它成为二叉树的一个端末结点
（叶）为止。
二分查找
（ a）按名字大小顺利整理 （ b）二叉树二叉树
二叉树的查找效率比对折查找效率显然要低一点，而且由于附设了左、右指示器，
存储空间也得多耗费一些。但它所需的顺序化时间显然要少得多，而且每查找一项所需的比较次数仍是和 log2N成比例的。因此，它是一种可取的办法。
3,杂凑查找 (HASH技术 )
杂凑函数 H(SYM),0~N-1
N,符号表的项数。
要求,1,计算简单高效
2,函数值分布均匀
填表快，查找快杂凑表的大小
编译器编写者必须回答的一个问题是要初始化多大的“桶”数组。
通常，在编译器构成时，“桶“的大小就固定了，其范围从几百到上千。
一般，“桶”数组的大小要求是一个素数，
可使杂凑函数运行得更好。
通用杂凑函数
在符号表中使用的杂凑函数将字符串 (标识符名字 )
转换成 0...size-1范围内的一个整数。
一般分 3步进行,
将字符串中的每个字符转换成一个非负整数。
将这些整数用一定的方法组合成一个整数。
把结果调到 0...size-1范围。
将每个字符转换成非负整数
通常使用编译器实现语言内嵌的转换机构把每个字符转换成非负整数。
如 Pascal的 ord函数将字符串转换成整数
（ ASCII值）。类似地，在 C语言中，如果在算术表达式中使用字符或把它赋给一个整型变量，就会自动地将其转换成整数。
把结果调到 0...size-1范围
使用取模 (modulo)函数能调整一个非负整数到
0...size-1范围内，它返回用 size去除一个数所得的余数。
这个函数在 Pascal中称作 mod，在 C中用 %表示。
使用这种方法时,size最好是一个素数。否则，
随机分配的整数集不会将目标值随机分配到
0...size-1范围内，容易造成造成冲突。
把多个整数整合为一个整数
杂凑表实现需要考虑每个名字中所有的字符对应的整数怎样整合为一个整数。
一种方案：忽略许多字符，只把开头的几个字符，
或第一个、中间的和最后一个字符的值加在一起。
XTEMP和 TEMPX就可能出现整数值相同的情况！！
因此，整合时需要各字符出现的位置问题，而不能作简单相加。
把多个整数整合为一个整数
为不同位置出现的字符赋以不同的权值。
设某个名字对应的字符串为 c１ c２ … c ｎ,ci是第 i个字符的数字值，考虑在对名字进行比较时都从左至右进行，所以第ｉ位的权值应该比第ｉ＋１位高，
故可设计第ｉ个字符对应的权值为 αｎ－ｉ 。
把多个整数整合为一个整数
若 ci是第 i个字符的数字值，则整合的公式如下：
αn-1c1+αn-2c2+…+αc n-1+cn＝
ｎ
=(∑αn-ici)
ｉ =1
α的选择非常重要。可选 16或 128，这样乘法可用移位完成。
构造杂凑函数
若 ci是第 i个字符的数字值，这里 n是名字中的字符个数。公式如下：
h=(αn-1c1+αn-2c2+…+αc n-1+cn)mod size
ｎ
=(∑αn-ici) mod sizeｉ =1
编程实现时常用递推式，设 hi是在第 i步计算的部分杂凑值，那么 hi根据下面的递归公式计算：h
0=0,hi=αhi－ 1+ci，最后的杂凑值用 h=hn mod size计算。
构造杂凑函数
在公式中ｈ有时可能溢出导致负数，特别是在双字节整数的机器中当 α较大时。
注意到在循环过程中的每一步都可以进行求 MOD运算减小ｈ的值，而不影响最后求
MOD的结果。
所以编程值常用的递归公式实际为：
h0=0,hi=（ αhi－ 1+ci）ｍｏｄ ｓｉｚｅ
程序清单 符号表的杂凑函数
#define SIZE,..
#define SHIFT 4
int hash ( char * key )
{ int temp = 0;
int i = 0;
while (key[i] != '\0')
{ temp = ((temp << SHIFT) + key[i]) % SIZE;
+ + i ;
}
return temp;
}
LeBlanc-Cook符号表处理方法
在遇到每个作用域时按顺序给它赋一个序号，最外层的作用域赋 0。
所有的编号都不相同，并不表示词法的嵌套层次，但内层作用域的序号大于外层作用域的序号。
所有名字以名字为关键字哈希后被放入一个大散列表中。
每项含名字、类属（常量、变量、类型、过程、参数、域名字等）、作用域编号、类型（指向另一个符号表项的指针）等。
符号表还包括一个作用域堆栈。
它按顺序指明组成当前引用环境的所有作用域。在语义分析器扫描过程中，在进入或退出程序时分别压栈和弹栈。
每项包括作用域编号、是否闭区域等信息。
LeBlanc-Cook符号表处理方法
当需要查找名字时，根据该名字的哈希值顺着对应的链表向下找。
对于每个匹配项，都向下扫描作用域堆栈，看这个项所在的作用域是否可见。
对于作用域编号为 0的项，不需要查找堆栈。
堆栈的查找深度不应超过最上面的闭区域。
让导入项、导出项在它们的作用域外可见的方法是在表中加字段，让其包含指向实际项的指针。
Module-2程序
LeBlanc-Cook符号表处理方法找到最外层作用域关联表和中心引用列表
实践中，动态作用域的实现常采用两种组织方式
关联表 （ A表,LISP中采用）
一个名字 /值对表，类似于堆栈。
当执行过程中进入一个作用域时，解释器把该作用域的名字压入表的前端，退出时删去，查找时从表的前端开始查找
中心引用列表关联表关联表和中心引用列表
关联表的问题是查找一个名字可能要花很多时间，特别是当该名字很早就定义时。
为解决这一问题，引入了中心引用列表。
在中心引用列表中，每个不同的名字都有一个表（堆栈），其最近的约束出现在表的顶端。
查找加快。
在 LISP组中，用关联表实现动态作用域的方式称为深约束，而用中心引用列表称为浅约束。
中心引用表
