编译程序构造与实践教程第九章

第9章目标代码的运行9.1概述如何保证正确地执行目标程序？除了目标代码正确外，必须为运行做好一切方面的准备:

目标代码+运行的支持环境。除了语法结构目标代码的总体设计外，与运行紧密相关的就是：运行时刻的存储管理、寄存器分配、运行子程序。寄存器分配涉及太多的细节，不予讨论。存储管理涉及的是标识符，相应的是符号表，因此讨论问题：

·运行时刻的存储管理；

·符号表的管理；

·运行时刻支持系统。9.2运行时刻的存储管理9.2.1变量情况分析

冯•诺伊曼型计算机的核心是存储器：变量存储字变量与存储字的结合有多种情况，看下面的例子。例C程序：typedef

struct

NodeT{intdata;struct

NodeT

*next;}NodeType；NodeType

*P;

(1)

voidCreateLink(){NodeType

*p1,*q;(2)

intj=1;q=(NodeType

*)malloc(sizeof(NodeType));(3)p1=q;while(j){printf("Inputanintegervalue:");

scanf("%d",&j);if(j){p1→next=(NodeType

*)malloc(sizeof(NodeType));(4)p1=p1→next;p1→data=j;}}p1→next=NULL;p=q→next;free(q);(5)}/*CreateLink*/

voiddisplay(NodeType

*q){NodeType

*p1;(6)p1=q;while(p1){printf("%4d",p1→data);p1=p1→next;}}main(){CreateLink();

display(p);}请注意几种不同的变量：

·p（在（1）处定义）(全局变量)·p1与q(分别在（2）与（6）处定义）(局部变量)·指针变量q与p1所指向的各个数据对象（分别在（3）与（4）处创建）(无名变量)对上述三类变量，看到是完全不同的三类。

注意：作用域动态性生命期

目标程序静态数据区栈

↓

↑堆存储区域划分存储分配策略：静态存储分配动态存储分配：栈式堆式9.2.2静态存储分配

•静态存储分配：编译时刻进行的存储分配

•语言背景：全局变量,C语言的静态变量等

•编译时刻已知道它们的存在，且知道它们的大小编译时刻由编译程序为它们进行存储分配

•但C语言、PASCAL语言等不能仅静态存储分配。9.2.3栈式存储分配

•动态存储分配的一种

•

语言背景：函数调用运行时刻当函数调用时进行分配存储（活动记录）、运行结束返回时撤消存储（活动记录）由谁在何处完成栈式存储分配,也即活动记录的分配与释放？由调用序列实现活动记录的存储分配，由返回序列实现活动记录的撤销。进一步说，是函数入口子程序实现对活动记录分配存储，由函数出口子程序实现对活动记录撤销存储。

•

栈式存储分配实质上是活动记录的分配与释放（在运行栈上）。

返回值实在参数控制链访问链机器状态局部数据临时数据活动记录•如何确定局部量的存储位置？函数中的局部变量由它们在活动记录中（局部数据域）的相对地址来定位。•

变量的存储位置的确定函数中局部变量存储位置的确定两个指针：

top指向运行栈的栈顶

(下一个活动记录的存储区域开始位置)(控制链域)top_sp指向活动记录中机器状态域的末端

(局部数据域之紧前，即指向局部数据区域的首址)•局部量的生命期与所在函数的生命期相同。9.2.4堆式存储分配

•动态存储分配的一种

•

语言背景：存储分配函数的调用

运行时刻，由调用malloc创建，由调用free撤消•一般说，只要出现下列情况中的任何一种情况，就必须采用堆式存储分配

·

数据对象随机地创建、随机地撤销；

·

当函数的活动结束时，局部变量的值还得保存下来；

·被调用函数活动的生命期比调用函数活动的生命期更长。

堆式存储分配的例子。typedef

structNode{intinfo;structNode*Next;}NodeType;NodeType

*p;P=(NodeType

*)malloc(sizeof(NodeType));P→info=1;p→Next=NULL;对已释放之存储的引用称为悬空引用。

注意：要避免悬空引用，例如main函数中的dangle(5)。typedef

int

*intp;intpp;intpdangle(intn){intpi,tmp;i=(intp)malloc(sizeof(int));*i=n；

tmp=i;free(tmp);returni;}main(){p=dangle(5)；printf("*p=%d\n",*p);}注意：也要避免无用单元，即，

动态分配时引起的不可达到的存储字。例无用单元产生之例#include<malloc.h>structcell{intinfo;structcell*next;}；typedef

structcell*link;linkhead;voidinsert(inti){linkp;p=(link)malloc(sizeof(structcell));

p→info=i;p→next=head;head=p；}voidmain(){head=NULL;insert(1);insert(2);insert(3);

free(head→next);

printf("%d",head→next→info);}9.3符号表9.3.1符号表的组织•符号表是标识符表的扩充。符号表用来登录名字(标识符)及相关的信息。•源程序中每当遇到标识符便要查符号表，如果出现新的标识符或者已登录标识符的新信息，便要进行登录。符号表存在于编译的全过程，甚至在目标程序运行时，为了得到标识符等信息，还可能需要符号表。

•符号表条目的内容：标识符、种类、属性(类型)、作用域及存储分配。•考虑问题：标识符的长度各不相同，如何统一？标识符的属性如何表示？标识符相关联的属性信息不一样，如何统一长度？如何提高查标识符表的效率？1.符号表的结构

符号表的条目:名字栏与信息栏。(1)名字栏标识符的长度不一致，如何统一名字栏的长度？另设标识符名表。(2)信息栏符号表条目的信息栏中登录与标识符相关联对象的各种信息，对于C语言可以包括关联对象的种类（常量、变量、数组、结构、指针与函数等）、类型等属性（整型、实型、字符型与枚举型等）和作用域信息，以及为相关联数据对象所分配的存储区域的相对地址。由于与标识符相关联的对象的类型不同而有所不同，符号表一个条目难以容纳全部的内容，为保持符号表条目结构的统一，有一致的大小，往往把与标识符相关联的构造类型等信息保存在符号表外的某处，例如，数组信息表等。

2.非基本类型属性的处理(1)数组类型:引进数组信息表(2)结构类型:引进成员属性信息(3)指针类型:由信息栏种类指明3.作用域信息按照静态的最近的嵌套作用域原则确定作用域。

以函数序号作为作用域序号。全局变量？4.存储分配的信息静态、栈式、堆式，不同情况，不同处理。

TA[u1][u2]…[un]A的数组信息表其中,各维下界=0,上界=u-1,个数d=u

维数下界1上界1个数1

下界2上界2个数2

┇

下界n上界n个数n

首址base

常量C

数组元素类型

┇总的说，一般采用相对地址，由编译程序计算为每个数据对象分配的存储字相对于某个基址的位移量。

9.3.2符号表的数据结构1.线性符号表线性表，一个元素对应一个条目，即，由名字栏和信息栏组成的结构。

对符号表的操作主要是两种，即，在符号表中为标识符建立条目和按标识符查找条目。

线性表可以用数组来实现，也可以用链表来实现。考虑用数组实现的情况。n个条目的线性表中，查找一次的平均比较次数是：

(n+1)/2为建立n个条目,并在建立n个条目后查找m次所需的平均比较次数共计：

¼n(n+1)+½(n+1)m=¼(n+1)(n+2m)

当n与m较大时，所花费的时间将十分可观。

2.散列符号表思路：名id符号表地址h(id)

定义性出现时，计算m=h(id),在m处建立条目；使用性出现时，计算m=h(id),取得条目。要点：设计散列函数h•要求：均匀分布且计算速度快

•散列函数的确定：除法散列函数、乘法散列函数、多项式除法散列函数、平方取中散列函数、

…如果id1≠id2,但h(id1)=h(id2),这种情况称为冲突。解决冲突可以有多种办法，这里引进条目链，把发生冲突的条目链接起来。如下图。

散列符号表的元素个数是固定的，但每个元素所指向的条目链的长度是可变的，因此，条目总数不是固定的，这种散列称为开散列。使用散列技术,查找效率显然比线性表的效率高很多。假定散列表元素是M个，最多可指向M个条目链，而条目总共为N个，则条目链的平均长度是N/M，一次查找的平均比较次数为N/M（N/M表示对N/M取整）。如果让N/M是一个较小的常数，例如2，那么，只要散列函数的计算是快速的，效率之提高是十