第6章-符号表管理技术

1、第第7 7章章 符号表管理技术符号表管理技术(P149)(P149)n7.1 何时建立和访问符号表何时建立和访问符号表n7.2 符号表的组织和内容符号表的组织和内容n7.3 符号表上的操作符号表上的操作n7.4 非块程序结构语言的符号表结构非块程序结构语言的符号表结构n7.5 块程序结构语言的符号表组织块程序结构语言的符号表组织学学 习习 重重 点点n符号表的作用符号表的作用n符号表的内容符号表的内容n符号表上的符号表上的操作操作n符号表的符号表的组织组织第第7 7章章 符号表管理技术符号表管理技术n符号表：符号表：它是记录、存储和管理源程序中的各它是记录、存储和管理源程序中的各种信息的一些表

2、格，如常量表、数组信息表、保种信息的一些表格，如常量表、数组信息表、保留字表和标识符表等。留字表和标识符表等。n符号表的作用：符号表的作用：（1 1）收集符号的各种信息）收集符号的各种信息 （2 2）语义检查的依据）语义检查的依据 （3 3）目标代码生成阶段地址分配的依据）目标代码生成阶段地址分配的依据 7.1 7.1 何时建立和访问符号表何时建立和访问符号表（P149P149） n何时建立和访问符号表：何时建立和访问符号表：在词法分析时创建在词法分析时创建 只能在符号表中将标识符的名字填入符号表，只能在符号表中将标识符的名字填入符号表，而其他属性则要在语义分析和代码生成阶段填入。而其他属性则

3、要在语义分析和代码生成阶段填入。语法分析阶段只检查源程序语法的正确性，一般不语法分析阶段只检查源程序语法的正确性，一般不使用符号表。使用符号表。在语义分析时创建在语义分析时创建 如果在语义分析阶段创建符号表，那么与符号如果在语义分析阶段创建符号表，那么与符号表打交道的就仅局限于语义分析和代码生成部分。表打交道的就仅局限于语义分析和代码生成部分。7.2 7.2 符号表的组织和内容符号表的组织和内容（P150P150） n符号表的内容：符号表的内容：名字域名字域 用来存放符号的名字。用来存放符号的名字。属性域属性域 用来记录与该名字相对应的各种属性和特征。用来记录与该名字相对应的各种属性和特征。

4、7.2 7.2 符号表的组织和内容符号表的组织和内容 名字名字 目标地址目标地址 类型类型 维数维数 声明行声明行 引用行引用行 指针指针Computer 0 2 1 2 9,4,5 7 X1 4 1 0 3 12,14 0FORM 8 3 2 4 6B2 48 1 0 5 1ANS 52 1 0 5 4 M 56 6 0 6 2FIRST 64 1 0 7 3n符号表示例符号表示例（P150） 名字域名字域属性域属性域7.2 7.2 符号表的组织和内容符号表的组织和内容 n符号表的总体组织：符号表的总体组织：（1 1）多张）多张 把属性种类完全相同的那些符号组织在一起，把属性种类完全相同的那

5、些符号组织在一起，构造出表项是分别为等长的多个符号表。构造出表项是分别为等长的多个符号表。 （2 2）一张）一张 把所有符号都组织在一张符号表中，组成一张把所有符号都组织在一张符号表中，组成一张包括了所有属性的庞大的符号表。包括了所有属性的庞大的符号表。（3 3）前两种的折中）前两种的折中 根据符号属性相似程度分类组织成若干张表，根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。每张表中记录的符号都有比较多的相同属性。 7.2 7.2 符号表的组织和内容符号表的组织和内容n存储符号表的方法：存储符号表的方法：（1 1）定长存贮方法：）定长存贮方法：为标识符名字域规

6、定一个宽度，为标识符名字域规定一个宽度，标识符按左对齐方式存放在其中，特点是简单且存取速度标识符按左对齐方式存放在其中，特点是简单且存取速度快，缺点是空间利用率低，标识符长度不能超过名字域的快，缺点是空间利用率低，标识符长度不能超过名字域的宽度。宽度。（2 2）集中存贮方法：）集中存贮方法：开辟一个存放所有标识符的缓冲开辟一个存放所有标识符的缓冲区，而在标识符名字域中只存放标识符在缓冲区中的偏移区，而在标识符名字域中只存放标识符在缓冲区中的偏移地址和标识符的长度。特点是存储效率高，标识符无长度地址和标识符的长度。特点是存储效率高，标识符无长度限制，但存取效率低。限制，但存取效率低。Comput

7、erX1FORM1 名字位置名字位置 名字长度名字长度 其它属性其它属性 1892115集中存储符号表集中存储符号表 7.2 7.2 符号表的组织和内容符号表的组织和内容n符号表的分类符号表的分类（从编译系统建造符号表的过程（从编译系统建造符号表的过程来划分）：来划分）：（1 1）静态表）静态表 在编译前就已经构造好了的符号表，如保留在编译前就已经构造好了的符号表，如保留字表、标准函数名表等。字表、标准函数名表等。（2 2）动态表）动态表 在编译过程中根据需要构造的符号表，如变在编译过程中根据需要构造的符号表，如变量表、数组信息表、过程信息表等。量表、数组信息表、过程信息表等。 7.3 7.3

8、 符号表上的操作符号表上的操作（P152P152） n符号表上的操作：符号表上的操作：（1 1）在在声明部分，向表中声明部分，向表中插入插入一个新标识符。一个新标识符。（2 2）在表达式或语句中，对于给定一个标识符：）在表达式或语句中，对于给定一个标识符：p查找查找是否在表中；是否在表中；p访问它在表中的相关信息；访问它在表中的相关信息；p在表中填写或更新它的某些信息。在表中填写或更新它的某些信息。（3 3）更新或删除更新或删除一个或一组标识符，体现嵌套一个或一组标识符，体现嵌套作用规则和局部化。作用规则和局部化。7.47.4非块程序结构语言的符号表结构非块程序结构语言的符号表结构（P153P

9、153） n非块程序结构语言：非块程序结构语言：是指用它编写的每一个可独是指用它编写的每一个可独立编译的程序是一个不包含子块的单一模块程序，立编译的程序是一个不包含子块的单一模块程序，该模块中声明的所有变量是属于整个模块的。该模块中声明的所有变量是属于整个模块的。 7.47.4非块程序结构语言的符号表结构非块程序结构语言的符号表结构 n非块程序结构语言的符号表的组织方式：非块程序结构语言的符号表的组织方式：（1 1）无序表）无序表（或（或线性表线性表） 根据变量被声明的先后顺序填入符号表。无序表根据变量被声明的先后顺序填入符号表。无序表的插入及查找操作简单、易于实现，但查找效率低。的插入及查找

10、操作简单、易于实现，但查找效率低。适用于符号表较小的情况。适用于符号表较小的情况。（2 2）有序表）有序表 有序符号表的表项是根据变量名按字母顺序存放有序符号表的表项是根据变量名按字母顺序存放的。对于有序表，最常用的查找技术是折半查找法。的。对于有序表，最常用的查找技术是折半查找法。（3 3）散列符号表）散列符号表（或（或哈希符号表哈希符号表） 使用哈希函数，将程序中出现的符号通过哈希函使用哈希函数，将程序中出现的符号通过哈希函数进行映射，得到的函数值作为该符号在表中的位置。数进行映射，得到的函数值作为该符号在表中的位置。插入和查找效率高，为多数编译程序所采用。插入和查找效率高，为多数编译程序

11、所采用。7.47.4非块程序结构语言的符号表结构非块程序结构语言的符号表结构nHash表的基本思想：表的基本思想：为符号表设置一个足够大的空间为符号表设置一个足够大的空间N，即，即符号表的符号表的长度长度为为N；为符号为符号Ki构造一个散列函数构造一个散列函数Hash(Ki)，使得，使得0 Hash(Ki) N-1，其中，其中i=1，2，n；Hash(Ki)就决定了就决定了符号符号Ki在符号表中的位置在符号表中的位置 。7.47.4非块程序结构语言的符号表结构非块程序结构语言的符号表结构n用用“质数除余法质数除余法”来构造散列符号表的方法来构造散列符号表的方法(P154)：（1）根据各符号名中

12、的字符确定正整数）根据各符号名中的字符确定正整数H，即将标识，即将标识符中的每个字符转换为一个非负整数，将得到的各个整符中的每个字符转换为一个非负整数，将得到的各个整数组合成一个整数（可以将第一个、中间的和最后一个数组合成一个整数（可以将第一个、中间的和最后一个字符值加在一起，也可以将所有字符的值加起来）。字符值加在一起，也可以将所有字符的值加起来）。（2）将上一步确定的整数）将上一步确定的整数H除以符号表的长度除以符号表的长度N （N是质数），然后取其余数。这个余数就作为符号的散列是质数），然后取其余数。这个余数就作为符号的散列位置。位置。（3）处理冲突可采用链接法，即将出现冲突的符号用）处

13、理冲突可采用链接法，即将出现冲突的符号用指针连接起来。指针连接起来。7.47.4非块程序结构语言的符号表结构非块程序结构语言的符号表结构n例例（P154） 假设现有假设现有5个符号个符号C1、C2、C3、C4、C5，分别转换成正整数为分别转换成正整数为87、55、319、273和和214，符号表，符号表的长度是的长度是5，那么，利用质数除余法得到的散列地址为：，那么，利用质数除余法得到的散列地址为：2、0、4、3、4，结果如图所示。，结果如图所示。 散列符号表散列符号表 7.5 7.5 块程序结构语言的符号表组织块程序结构语言的符号表组织（P155P155）n按块程序结构语言的规定：变量的作用

14、域是定义按块程序结构语言的规定：变量的作用域是定义它的块程序；同一块内的变量不能重名，但不同块它的块程序；同一块内的变量不能重名，但不同块以及嵌套块之间的变量可以重名，使用时局部变量以及嵌套块之间的变量可以重名，使用时局部变量优先于全局变量。优先于全局变量。 n块程序结构语言：块程序结构语言：是指程序模块可包含嵌套的子是指程序模块可包含嵌套的子模块，每一子模块可以有一组自己的局部变量。模块，每一子模块可以有一组自己的局部变量。n例例(P155) 当编译程序编译到该当编译程序编译到该C程序某处时的相应的有效变量程序某处时的相应的有效变量: real x,y; char name; int fun

15、1(int ind) int x; x=m2(ind+1);int fun2(int j) int f10; bool test1; main() char name; x=2;y=5; printf(%dn,fun1(x/y);name,y,xind,fun1,name, y,xx,ind, fun1,name, y,xfun1,name, y,xj,fun2, fun1,name, y,xtest1,f, j,fun2, fun1,name, y,xj,fun2, fun1,name, y,xfun2, fun1,name, y,x main, fun2, fun1,name, y,xna

16、me, main, fun2, fun1,name, y,x7.5 7.5 块程序结构语言的符号表组织块程序结构语言的符号表组织n块程序结构语言的符号表结构为块程序结构语言的符号表结构为栈式符号表栈式符号表，它包它包括一个符号表栈及一个块索引栈括一个符号表栈及一个块索引栈。符号表栈记录变量。符号表栈记录变量的属性，块索引栈指出每个块在符号表中的开始位置。的属性，块索引栈指出每个块在符号表中的开始位置。n栈式符号表的插入操作栈式符号表的插入操作:（1）开始编译时，设符号表栈顶指针）开始编译时，设符号表栈顶指针TOP为为0，当，当第一个标识符出现时，将该标识符的属性入栈，同时第一个标识符出现时，将

17、该标识符的属性入栈，同时将该标识符的地址将该标识符的地址0压入块索引栈，然后栈顶指针压入块索引栈，然后栈顶指针TOP为为1。7.5 7.5 块程序结构语言的符号表组织块程序结构语言的符号表组织n栈式符号表的插入操作栈式符号表的插入操作:（2）后面再遇到标识符时，如果新的标识符与栈顶）后面再遇到标识符时，如果新的标识符与栈顶的标识符在同一块中，则只需将新记录压入符号表栈顶的标识符在同一块中，则只需将新记录压入符号表栈顶单元，然后，栈顶指针单元，然后，栈顶指针TOP加加1。如果新的标识符与栈。如果新的标识符与栈顶的标识符不在同一块中，表示刚才处理的程序块嵌套顶的标识符不在同一块中，表示刚才处理的程

18、序块嵌套着一个程序块，而现在进入了这个嵌套的程序块中，则着一个程序块，而现在进入了这个嵌套的程序块中，则要进行定位操作，即将栈顶指针要进行定位操作，即将栈顶指针TOP入块索引栈，再将入块索引栈，再将该标识符属性压入符号栈，然后栈顶指针该标识符属性压入符号栈，然后栈顶指针TOP加加1。（3）当编译遇到程序块的结尾时要进行重定位操作，）当编译遇到程序块的结尾时要进行重定位操作，即将块索引栈的栈顶单元出栈并将内容赋给栈顶指针即将块索引栈的栈顶单元出栈并将内容赋给栈顶指针TOP。n注意：注意：栈顶指针栈顶指针TOP始终指向符号表栈顶第一个空闲始终指向符号表栈顶第一个空闲的存储单元。的存储单元。 7.5

19、 7.5 块程序结构语言的符号表组织块程序结构语言的符号表组织n栈式符号表的查找操作栈式符号表的查找操作: 符号表从栈顶单元符号表从栈顶单元(TOP-1)开始到块索引栈的栈顶开始到块索引栈的栈顶单元所指的单元，逐一检查，并进行相应的存取操作。单元所指的单元，逐一检查，并进行相应的存取操作。特别地，如果查找到有与要插入的变量同名，则表示特别地，如果查找到有与要插入的变量同名，则表示源程序中存在变量重复声明的错误；如果没有，才可源程序中存在变量重复声明的错误；如果没有，才可将该标识符的属性入栈。将该标识符的属性入栈。n查表操作要对符号栈进行从顶查表操作要对符号栈进行从顶(TOP-1)到底进行线性到底进行线性搜索，这样确保找到的变量满足局部变量优先于全局搜索，这样确保找到的变量满足局部变量优先于全局变量的规则。由于栈式符号表中记录是无序的，因而变量的规则。由于栈式符号表中记录是无序的，因而查询效率比较差。查询效率比较差。 n 例例7-1(P156) 画出编译到画出编译到C程序中程序中a、b、c、d处的栈式符号表。处的栈式符号表。real x,y;char name;aint fun1(int ind) int x; b x=m2(ind+1);int fun2(int j) int f10; bool test1; c main() char name; d x=2;y=5; p