《编译原理——编译程序构造实践教程 教学课件 PPT 作者 张幸儿 戴新宇 901编译程序构造与实践教程第九章》由会员分享，可在线阅读，更多相关《编译原理——编译程序构造实践教程 教学课件 PPT 作者 张幸儿 戴新宇 901编译程序构造与实践教程第九章（23页珍藏版）》请在金锄头文库上搜索。
1、第9章 目标代码的运行 9.1 概述 如何保证正确地执行目标程序？除了目标代码正确外，必须为运行做好一切方面的准备: 目标代码+运行的支持环境。 除了语法结构目标代码的总体设计外，与运行紧密相关的就是： 运行时刻的存储管理、寄存器分配、运行子程序。 寄存器分配涉及太多的细节，不予讨论。存储管理涉及的是标识符，相应的是符号表，因此讨论问题： 运行时刻的存储管理； 符号表的管理； 运行时刻支持系统。,9.2 运行时刻的存储管理 9.2.1 变量情况分析 冯诺伊曼型计算机的核心是存储器： 变量存储字 变量与存储字的结合有多种情况，看下面的例子。,例 C程序： typedef struct NodeT
2、 int data; struct NodeT * next; NodeType； NodeType *P; (1),void CreateLink ( ) NodeType *p1, *q; (2) int j=1; q=(NodeType *)malloc (sizeof (NodeType); (3) p1=q; while (j) printf (“Input an integer value:“); scanf (“%d“, (5) /* CreateLink */,void display ( NodeType *q) NodeType *p1; (6) p1=q; while (
3、p1) printf (“%4d“, p1data); p1=p1next; main ( ) CreateLink ( ); display(p); ,请注意几种不同的变量： p（在（1）处定义） (全局变量) p1与q (分别在（2）与（6）处定义） (局部变量) 指针变量q与p1所指向的各个数据对象 （分别在（3）与（4）处创建） (无名变量) 对上述三类变量，看到是完全不同的三类。 注意：作用域 动态性 生命期,存储区域划分,存储分配策略： 静态存储分配 动态存储分配：栈式 堆式,9.2.2 静态存储分配 静态存储分配：编译时刻进行的存储分配 语言背景： 全局变量, C 语言的静态变量
4、等 编译时刻已知道它们的存在，且知道它们的大小 编译时刻由编译程序为它们进行存储分配 但C语言、PASCAL语言等不能仅静态存储分配。,9.2.3 栈式存储分配 动态存储分配的一种 语言背景：函数调用 运行时刻当函数调用时进行分配存储（活动记录）、运行结束返回时撤消存储（活动记录） 由谁在何处完成栈式存储分配,也即活动记录的分配与释放？ 由调用序列实现活动记录的存储分配，由返回序列实现活动记录的撤销。进一步说，是函数入口子程序实现对活动记录分配存储，由函数出口子程序实现对活动记录撤销存储。 栈式存储分配实质上是活动记录的分配与释放（在运行栈上）。,活动记录, 如何确定局部量的存储位置？ 函数中
5、的局部变量由它们在活动记录中（局部数据域）的相对地址来定位。 变量的存储位置的确定 函数中局部变量存储位置的确定 两个指针： top 指向运行栈的栈顶 (下一个活动记录的存储区域开始位置) ( 控制链域) top_sp 指向活动记录中机器状态域的末端 (局部数据域之紧前，即指向局部数据区域的首址) 局部量的生命期与所在函数的生命期相同。,9.2.4 堆式存储分配 动态存储分配的一种 语言背景：存储分配函数的调用 运行时刻，由调用malloc创建，由调用free撤消 一般说，只要出现下列情况中的任何一种情况，就必须采用堆式存储分配 数据对象随机地创建、随机地撤销； 当函数的活动结束时，局部变量的
6、值还得保存下来； 被调用函数活动的生命期比调用函数活动的生命期更长。 堆式存储分配的例子。 typedef struct Node int info; struct Node *Next; NodeType; NodeType *p; P=(NodeType *) malloc(sizeof(NodeType); Pinfo=1; pNext=NULL;,对已释放之存储的引用称为悬空引用。 注意： 要避免悬空引用，例如main函数中的dangle(5)。 typedef int *intp; intp p; intp dangle (int n) intp i, tmp; i=(intp) m
7、alloc (sizeof (int); *i=n； tmp=i; free(tmp); return i; main( ) p=dangle(5)； printf (“*p=%dn“,*p); 注意：也要避免无用单元，即， 动态分配时引起的不可达到的存储字 。,例 无用单元产生之例 #include struct cell int info; struct cell *next; ； typedef struct cell *link; link head; void insert (int i) link p; p=(link)malloc(sizeof(struct cell); pin
8、fo=i; pnext=head; head=p； void main( ) head=NULL; insert(1); insert(2); insert(3); free (headnext); printf (“%d“, headnextinfo); ,9.3 符号表 9.3.1 符号表的组织 符号表是标识符表的扩充。 符号表用来登录名字(标识符)及相关的信息。 源程序中每当遇到标识符便要查符号表，如果出现新的标识符或者已登录标识符的新信息，便要进行登录。 符号表存在于编译的全过程，甚至在目标程序运行时，为了得到标识符等信息，还可能需要符号表。 符号表条目的内容： 标识符、种类、属性(类
9、型)、作用域及存储分配。 考虑问题： 标识符的长度各不相同，如何统一？ 标识符的属性如何表示？ 标识符相关联的属性信息不一样，如何统一长度？ 如何提高查标识符表的效率？,1. 符号表的结构 符号表的条目: 名字栏与信息栏。 (1) 名字栏 标识符的长度不一致，如何统一名字栏的长度？ 另设标识符名表。 (2) 信息栏 符号表条目的信息栏中登录与标识符相关联对象的各种信息，对于C语言可以包括关联对象的种类（常量、变量、数组、结构、指针与函数等）、类型等属性（整型、实型、字符型与枚举型等）和作用域信息，以及为相关联数据对象所分配的存储区域的相对地址。 由于与标识符相关联的对象的类型不同而有所不同，符
10、号表一个条目难以容纳全部的内容，为保持符号表条目结构的统一，有一致的大小，往往把与标识符相关联的构造类型等信息保存在符号表外的某处，例如，数组信息表等。,2.非基本类型属性的处理 (1) 数组类型:引进数组信息表 (2) 结构类型:引进成员属性信息 (3) 指针类型:由信息栏种类指明 3.作用域信息 按照静态的最近的嵌套作用域原则确定作用域。 以函数序号作为作用域序号。 全局变量？ 4. 存储分配的信息 静态、栈式、堆式，不同情况，不同处理。,T Au1u2un A的数组信息表,总的说，一般采用相对地址，由编译程序计算为每个数据对象分配的存储字相对于某个基址的位移量。,9.3.2 符号表的数据
11、结构 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处建立条目； 使用性出现时，
12、计算m=h(id),取得条目。 要点：设计散列函数h 要求：均匀分布且计算速度快 散列函数的确定： 除法散列函数、 乘法散列函数、 多项式除法散列函数、 平方取中散列函数、 ,如果id1id2, 但h(id1)=h(id2), 这种情况称为冲突。 解决冲突可以有多种办法，这里引进条目链，把发生冲突的条目链接起来。如下图。,散列符号表的元素个数是固定的，但每个元素所指向的条目链的长度是可变的，因此，条目总数不是固定的，这种散列称为开散列。 使用散列技术,查找效率显然比线性表的效率高很多。假定散列表元素是M个，最多可指向M个条目链，而条目总共为N个，则条目链的平均长度是N/M，一次查找的平均比较次
13、数为N/M（N/M表示对N/M取整）。如果让N/M是一个较小的常数，例如2，那么，只要散列函数的计算是快速的，效率之提高是十分明显的。,9.4 运行时刻支持系统 一般说，从源程序翻译得到的等价的目标程序是一些目标模块，需要通过连接装配程序把这些模块连接装配成完全确定了装入的存储地址的可执行机器语言程序。但是,即使连接装配后，目标程序依然不能独立地运行。一个明显的事实是：必须有函数入口子程序与函数出口子程序的支持才能运行。一句话，目标程序必须有运行子程序的配合才能运行。,两大类运行子程序： 面向用户的：程序书写人员（用户）知道其存在，并能使用的运行子程序。例如，库函数一类子程序。 (例如，计算sin与cos等三角函数的子程序， 实现 scanf 与printf 等输入输出的子程序) 对用户隐匿的：为配合目标程序的运行而设计，程序书写人员（用户）并不了解其存在，且不能在源程序中显式应用的运行子程序。 (例如，函数入口子程序、函数出口子程序 数组元素地址计算子程序 数组动态存储管理子程序 运行时刻的错误处理子程序，等 ),概括 1. 运行时刻存储管理 分类： 静态、动态(栈式、堆式)存储分配 语言背景 存储分配时间 2. 符号表 作用、符号表组织（条目的结构） 符号表的数据结构 3. 运行时刻支持系统 作用、运行子程序的分类,
