编译原理教程 第六章 符号表的组织与管理.ppt

第六章 符号表的组织与管理 符号表(Symbol Table） 作用：记录源程序中各种标识符的属性和特征等有关信息。 内容：名字，有关信息（种属、类型等） 表项的建立： 运用：语义检查、产生中间代码、地址分配的依据 6.1 符号表的作用 ?在编译的各个阶段，每当遇到标识符时，都要查找符号表。 因此，合理组织符号表，使其占用的存储空间较少、易于访问，对提高编译的效率很重要。 符号表的表项包括名字栏和信息栏 ?查填符号表一般通过匹配名字来实现。 ?对符号表的操作一般有： 对给定的名字，查询其是否已在表中； 添加新名字； 访问某个名字的某些信息； 添加或更新某个名字的某些信息； 删除一个或一组无用的项。 6.2 符号表的组织 符号表的信息栏中记录了每个名字的有关性质，如类型、种属、大小、以及相对数等。 不同的程序语言对于名字性质的定义各有不同。 一个名字的有关信息常常是分几次填入信息栏中的。 符号表中信息栏的具体组织取决于所翻译的具体的源语言和目标机器。 6.2 符号表的组织 ?直接方式：表中各项各栏的长度固定。 ?间接方式：符号表中的相应栏存指针，指向存储具体信息的位置。 6.2 符号表的组织 ?按标识符的种属分别建立符号表。 　简单变量名表 　　数组名表 　　函数名表 　　．．． 符号表的实现： ?可采用链式表结构： 所有的标识符构成一个标识符链 所有函数名构成一条函数链 每个函数都有一条函数参数链 每个函数都有一条局部变量链 表单元的具体结构如P135-136 6.3 符号表的建立与查找 编译工作的相当一大部分时间是花费在查填符号表上。 如何构造和处理符号表？ 线性表、二叉树、Hash表 1、 线性表 实现最简单，节省空间，效率低 按名字出现的顺序填写各个项；查找时可以从表头顺序查找，也可以从表尾反序查找。 平均查找时间n/2 改进方法：自适应线性表 2、二分查找与二叉树 在构造表的时候，各项按名字的“大小”顺序排列；查找时可用对折法；最长查找时间为1+log2N。缺点：顺序化费时。 把符号表组织成一棵二叉树。比对折查找效率低一点、需要附加的存储空间，但顺序化效率更高。 P137图6.7 图6.8 3、Hash表与查找 使查表与填表都能高效地进行。 引进Hash函数，函数的构造要求：计算简单高效，函数值分布均匀，有好的解决“地址冲突”的方法。效率与装填因子有关。 使用Hash表通过间接方式查填符号表 第8章 运行时的存储组织与管理 在生成目标代码前，需要把程序静态的正文和实现这个程序的运行时的环境联系起来。 存储组织与管理：静态、动态（栈式、堆式） 8.1 概述 ?生成目标代码前要进行目标程序运行环境的设计和数据空间的分配。 运行时的环境：目标计算机的存储器和寄存器结构，管理存储器并保存执行过程所需的信息。3种存储环境：完全静态、基于栈的、基于堆的 目标程序运行时所需的存储空间：程序的各种数据对象的存储、过程调用所需的连接单元、输入/输出所需的缓冲区、保留中间结果和传递参数的临时单元。 运行时存储器的划分 ?为使目标程序能够运行,要从操作系统中获得一块存储空间。并对这块空间进行划分，以便存放目标代码、数据对象、栈等 活动记录 ?活动记录(activation record)：为了管理过程在一次执行中所需要的信息，而使用的一个连续的存储块。 存储分配策略 ?静态分配策略：编译时对所有数据对象分配固定的存储单元，并且在运行时始终保持不变。 ?栈式动态分配策略：在运行时把存储器作为一个栈进行管理，“先申请后归还,后申请先归还” ?堆式动态分配策略：运行时把存储器组织成堆结构，更便于申请和归还。按需申请和归还。 8.2 静态存储分配 ?在编译时就确定目标程序运行时的数据空间，和每个数据项的单元地址。例如，FORTRAN语言，适合静态分配。 ?静态存储分配是一种非常简单的策略。 8.3 栈式存储分配 ?考虑一种语言：允许过程的递归调用。(如C)这样，关于局部变量的存储分配，可以直接采用栈式存储分配策略。 ?把存储空间组织成一个栈，运行时，每当进入一个过程，就把它的活动记录压入栈，从而在栈顶形成过程工作时的数据区；该活动结束时，把它的活动记录弹出栈。过程的每一次调用都需要一个活动记录。 8.3.1 简单栈式存储分配 ?没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。该语言可以采用简单栈式存储分配策略。 (如C语言) C语言的活动记录 ?C的非局部量可采用静态分配策略，编译时确定其地址； ?局部变量和形式参数运行时在栈上的绝对地址： X[SP]=活动记录基地址(SP)+相对地址 简单栈式存储分配示例： 简单栈式存储分配示例： C的过程调用、过程进入、过程返回 ?过程调用的