第六章 符号表的组织与管理

第六章符号表的组织与管理符号表(SymbolTable）作用：记录源程序中各种标识符的属性和特征等有关信息。内容：名字，有关信息（种属、类型等）表项的建立：运用：语义检查、产生中间代码、地址分配的依据6.1符号表的作用在编译的各个阶段，每当遇到标识符时，都要查找符号表。因此，合理组织符号表，使其占用的存储空间较少、易于访问，对提高编译的效率很重要。根据说明语句的功能，记录标识符的相关信息为上下文语义的合法性检查提供依据生成目标代码时，符号表的内容是分配存储地址的依据

符号表的表项包括名字栏和信息栏查填符号表一般通过匹配名字来实现。对符号表的操作一般有：对给定的名字，查询其是否已在表中；添加新名字；访问某个名字的某些信息；添加或更新某个名字的某些信息；删除一个或一组无用的项。6.2符号表的组织符号表的内容:名字栏、信息栏符号表的信息栏中记录了每个名字的有关性质，如类型、种属、大小、以及相对数等。不同的程序语言对于名字性质的定义各有不同。一个名字的有关信息常常是分几次填入信息栏中的。符号表中信息栏的具体组织取决于所翻译的具体的源语言和目标机器。6.2符号表的组织直接方式：表中各项各栏的长度固定。间接方式：符号表中的相应栏存指针，指向存储具体信息的位置。符号表NAMEINFORMATION

，6

，4SAMPLELOOP6.2符号表的组织按标识符的种属分别建立符号表。简单变量名表数组名表函数名表．．．符号表信息栏的组织方式：固定信息栏内容的符号表；仅记载信息地址的间接方式。设置信息栏内容时，要考虑标识符的作用域。

符号表的实现：可采用链式表结构：所有的标识符构成一个标识符链所有函数名构成一条函数链每个函数都有一条函数参数链每个函数都有一条局部变量链表单元的具体结构如P140-1416.3符号表的建立与查找编译工作的相当一大部分时间是花费在查填符号表上。如何构造和处理符号表？线性表、二叉树、Hash表1、线性表实现最简单，节省空间，效率低按名字出现的顺序填写各个项；查找时可以从表头顺序查找，也可以从表尾反序查找。平均查找时间n/2改进方法：自适应线性表2、二分查找与二叉树在构造表的时候，各项按名字的“大小”顺序排列；查找时可用对折法；最长查找时间为1+log2N。缺点：顺序化费时。把符号表组织成一棵二叉树。比对折查找效率低一点、需要附加的存储空间，但顺序化效率更高。P142图6.7图6.83、Hash表与查找使查表与填表都能高效地进行。引进Hash函数，函数的构造要求：计算简单高效，函数值分布均匀，有好的解决“地址冲突”的方法。效率与装填因子有关。使用Hash表通过间接方式查填符号表P143图6.9第8章运行时的存储组织与管理在生成目标代码前，需要把程序静态的正文和实现这个程序的运行时的环境联系起来。存储组织与管理：静态、动态（栈式、堆式）8.1概述生成目标代码前要进行目标程序运行环境的设计和数据空间的分配。运行时的环境：目标计算机的存储器和寄存器结构，管理存储器并保存执行过程所需的信息。3种存储环境：完全静态、基于栈的、基于堆的目标程序运行时所需的存储空间：程序的各种数据对象的存储、过程调用所需的连接单元、输入/输出所需的缓冲区、保留中间结果和传递参数的临时单元。运行时存储器的划分为使目标程序能够运行,要从操作系统中获得一块存储空间。并对这块空间进行划分，以便存放目标代码、数据对象、栈等。目标代码区静态数据区栈堆用来管理过程的活动存放动态数据

活动记录活动记录(activationrecord)：为了管理过程在一次执行中所需要的信息，而使用的一个连续的存储块。TOPSP参数空间返回地址局部数据的空间局部临时变量的空间

存储分配策略静态分配策略：编译时对所有数据对象分配固定的存储单元，并且在运行时始终保持不变。栈式动态分配策略：在运行时把存储器作为一个栈进行管理，“先申请后归还,后申请先归还”堆式动态分配策略：运行时把存储器组织成堆结构，更便于申请和归还。按需申请和归还。

具体采用那种分配策略，取决于程序语言关于名称的作用域和生存期的定义规则。8.2静态存储分配在编译时就确定目标程序运行时的数据空间，和每个数据项的单元地址。例如，FORTRAN语言，适合静态分配。静态存储分配是一种非常简单的策略。目标代码静态数据区P169图8.48.3栈式存储分配考虑一种语言：允许过程的递归调用。(如C)这样，关于局部变量的存储分配，可以直接采用栈式存储分配策略。把存储空间组织成一个栈，运行时，每当进入一个过程，就把它的活动记录压入栈，从而在栈顶形成过程工作时的数据区；该活动结束时，把它的活动记录弹出栈。过程的每一次调用都需要一个活动记录。8.3.1简单栈式存储分配没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。该语言可以采用简单栈式存储分配策略。(如C语言)C语言的活动记录C的非局部量可采用静态分配策略，编译时确定其地址；局部变量和形式参数运行时在栈上的绝对地址：

X[SP]=活动记录基地址(SP)+相对地址临时单元内情向量简单局部变量形式单元参数个数返回地址老SP值TOPSP局部数据连接数据简单栈式存储分配示例：P的活动记录Main的活动记录全局数据区C程序运行时的存储空间组织TOPSPSP指向现行过程活动记录的起点；TOP始终指向栈顶单元。P170图8.6图8.7Intx=2;Voidp(int);Voidq(intn);{…p(n);…}Voidp(intm){…if(m>1){q(m-1);x--;p(m-1);}

…}Main(){p(x);}Q的活动记录P的活动记录TOPSP简单栈式存储分配示例：P的活动记录Main的活动记录全局数据区C程序运行时的存储空间组织SP指向现行过程活动记录的起点；TOP始终指向栈顶单元。P170图8.6图8.7Intx=2;Voidp(int);Voidq(intn);{…p(n);…}Voidp(intm){…if(m>1){q(m-1);x--;p(m-1);}

…}Main(){p(x);}Q的活动记录P的活动记录P的活动记录TOPSPC的过程调用、过程进入、过程返回过程调用的四元式系列：

parT1……parTncallP,n每个parTi可以翻译成目标指令：

(i+3)[TOP]=Ti

（传值）或(i+3)[TOP]=addr(Ti)(传地址)callP,n翻译成目标指令：

1[TOP]=SP（保存现行SP）

3[TOP]=n(传送参数个数)JSRP（转子指令，转向P的第一条指令）返回值对应指令：return(E)过程返回时，应先执行指令：

TOP=SP-1SP=0[SP]X=2[TOP]UJ0[X]转进过程P后,首先应执行指令：

SP=TOP+1（定义新SP）

1[SP]=返回地址(保护返回地址)TOP=TOP+L(定义新TOP)L(活动记录的大小)在编译时可以静态地计算出来。8.3.2嵌套过程语言的栈式存储分配允许过程嵌套定义的语言(如Pascal)层数：嵌套的层次主程序的层数为0直接外层过程、内层过程层数作为过程名的一个属性levellevel遇过程定义开始则+1，遇过程定义结束则-1对于Pascal语言，在运行时，过程中的局部变量和形式参数在栈上的存储可以用简单栈式存储分配来解决；但由于允许嵌套，非局部量的访问就比较复杂。图8.8程序非局部名字的访问的实现为了在活动记录中查找非局部名字所对应的存储单元，过程运行时必须知道它的所有外层过程的最新活动记录的地址；由于允许递归，过程的活动记录的位置往往是变动的。跟踪每个外层过程的最新活动记录的位置：通过嵌套层次显示表（display）嵌套层次显示表(display)和活动记录引用一个指针数组，嵌套层次显示表：每进入一个过程后，在建立它的活动记录区的同时，建立一张display。display的体积在编译时可以静态确定。非局部量的绝对地址的计算：display[静态层数]+相对地址为便于处理，将display作为活动记录的一部分。临时单元内情向量局部变量display形参单元参数个数全局display地址返回地址动态链(老SP值)TOPSP通过display访问非局部变量：在现行过程中引用某一外层过程（层数为k）的变量X，变址指令得到X的值。当过程P1调用过程P2而进入P2后，P2如何建立自己的display表？(若P2的层数为I2，则其display表含有I2+1项)方法：从P1的display表自底向上地取I2项，再添上进入P2后新建立的SP值，就构成了P2的display表。图8.9、8.10、8.118.4堆式动态存储分配允许用户自由地申请数据空间和归还数据空间。空间被分成许多大小不一的“块”分配时必须考虑以下情况：当运行程序要求一块体积为N的空间时，分配哪一块比N大的给它；当运行程序要求一块体积为N的空间，没有比N大的块，但所有空闲块的总和比N大；当运行程序要求一块体积为N的空间，但所有空闲块的总和也不够N。堆式动态存储分配的实现1.定长块管理:

初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域。占用占用占用空闲空闲空闲AVAILABLE归还时，把所归还的块插入链表。如，插到链表头。占用空闲占用空闲空闲空闲AVAILABLE2.变长块管理根据需要分配长度不同的存储块，初始化时堆存储空间是一个整块。初次分配时，按需要分割整块来分配；归还时，需要将新归还的块与现有空闲块进行合并，不能合并时，链成一个链表；再进行分配时，从空闲块链表中找出满足要求的一块进行分配。有多个满足要求的块时，按以下三种策略进行分配：(1)首次匹配法：(2)最优匹配法：(3)最差匹配法：(2)适用于请求分配的内存大小范围较广的情况；(3)适用于请求分配的内存大小范围较窄的情况。8.5临时变量的存储分配临时变量是编译时为暂存中间结果而引进的，对于代码优化很有好处。都是简单变量。如果两个临时变量名的作用域不相交，则可以共用一个存储单元。因此，对新的临时变量名分配存储单元时，只有当它的作用域与所有已分配的临时变量的作用域冲突时，才分配一个新单元。此时，单元的分配信息包括相应变量名的作用域。例如，用于暂存表达式中间结果的临时变量，只存在一次定值和一次引用，并且在定值和引用之间不存在分叉转移。其作用域的确定非常简单，因而其存储分配也可以用一种非常简易的办法（栈）实现。临时变量的栈式地址分配：赋值语句：X=A*B-C*D+E*F四元式序列：四元式临时变量名

(1)*ABT1T1(2)*CDT2T2(3)-T1T2T3T3

(4)*EFT4T4(5)+T3T4T5T5(6)=T5XSTACKk对于引进的五个临时