《ch9-10 运行时环境_(张素琴)》由会员分享，可在线阅读，更多相关《ch9-10 运行时环境_(张素琴)（34页珍藏版）》请在金锄头文库上搜索。
1、1第10章 目标程序运行时的 存储组织21.存储组织为了使目标程序运行，编译程序从操作系 统得到一块内存存储区，存储区容纳:1. 生成的目标代码空间; 2. 目标代码运行需要的数据空间，包括用 户定义的变量和常量，临时工作单元，过程 调用所需的联系单元，输入输出缓冲区; 3. 用于保存过程活动踪迹的一个控制栈。3目标代码静态数据栈活动记录堆1. 编译后知道目标代码的大 小。如 Pascal, C ，Fortran ；2. 静态数据区存放编译时 就能确定所占用空间大小 的数据；3. 栈堆区:用于存放可变数 据以及管理过程活动记录 的控制信息，如Pascal,C语 言。2.运行时刻内存的划分： 数
2、据空间43.活动记录对于pascal语言来说，运行过程中， 当调用一个过程时，在栈顶构筑它的活动 记录；一个活动所需要的信息的每个数据项 有相同的生存期，因此，组织成一个活动 记录是很自然的。当这个过程的活动执行完后，把它 从栈顶弹出。把过程的一个活动所需要的信息组织 成一块连续的存储单元，称为活动记录。5返回值实在参数控制链访问链保存机器状态局部变量 临时变量临时变量：编译产生。保存机器状态：调用过程 的活动在调用点的机器状 态，包括计数器，各种寄 存器的值。局部数据：过程中定义的 局部量。访问链：指向本活动要访 问的非局部数据所在的活 动记录.控制链:指向主调过程的活 动记录的首地址。 形
3、式单元内情向量连 接 数 据局 部 数 据sptopPascal的活动记录6函数environment把一个名字映射为一个l- value（左-值）,4.名字与存储的绑定引进两个函数，environment和state。 environment把名字映射到一个存储单元 上； state把存储单元映射到那里所存放的 值上。而函数state把一个l-value （左-值）映射为一个r-value（右-值）。 如下图所示。名字与存储单元的绑定是指把源程序中的 数据名字映射到目标机存储单元的过程。7名字存储单元值存储分配程序运行environmentstatel-valuer-value图：从名字到值
4、的两个阶段映射8编译结束，知道每个过程的活动记录的长度， 将其填写到相应的过程符号表中；运行时，调用哪个过程，就在运行栈顶，推进 那个过程的活动记录。一个名字所需的存贮空间的数量是由它的类型 确定的；多字节对象存放于连续的字节中，以第一个 字节的地址作为该对象的地址；910.1 数据空间的三种不同管理方法 3 .1 静态存储分配:FORTRAN3 .2 栈式存储分配:PASCAL, C3 .3 堆式存储分配: PASCAL, C采用哪种分配策略是由源语言的语 义决定的。1010.1 .1 静态存储分配 如Fortran语言，各子程序段中的局部变量彼此 独立，不会在不同子程序间引用、赋值，每个
5、变量的存储空间大小都是常量，整个程序所需 的数据空间的总量在编译时完全确定，从而每 个变量的内存空间可以静态分配。在编译时刻为每个数据项目确定出在运行时刻 的存储空间中的位置，且这种绑定在运行时刻 不再发生变化。11限制： 1.在编译时刻知道数据目标的大小和它 们在内存位置上 约束； 2.不能递归调用过程； 3.不能动态地建立数据结构。12与静态分配不同的是，在每次活动开始时把 局部名字和新的存储单元绑定，在活动结束 时，活动记录从栈中弹出，局部名字的存储 空间随之释放。对于具备递归调用、可变数组、允许用户申 请和释放内存空间的高级语言，就需要采用 动态存储管理技术管理内存，主要包括两种 动态
6、存储分配方式：栈和堆式。10.1.2 动态存储分配13基于栈存储分配的原理：存储空间被组织成栈， 活动记录的推入和弹出，分别对应于活动的开始和 结束。每当调用一个子程序时，它所需的数据存储 空间就分配在栈顶，当该子程序运行结束就释放这 部分内存存储数据空间；子程序的数据空间: (1)生存期在本过程本次活动 中的数据对象，如局部变量、参数单元、临时变量 等；(2)用于管理活动记录的信息，如当A调用B时， A被中断，则A当前寄存器和返回地址等信息。当 执行完，便根据栈中信息回复的运行。适合Pascal 、C、Algol语言。 数据空间使用遵从“先申请后释放，后申请先释放 ”。10.1.3 栈式动态
7、存储分配14如果一个程序语言让用户自由申请内存数据 空间和退还数据空间的机制,如C+中的 new,delete。空间使用不遵从“先申请后释放 ，后申请先释放”，这样就不能使用栈式存 储分配方式。需要使用堆式存储方式。堆是一片足够 大的存贮空间，每当需要时， 就从这片空间中分配一块， 用完时，再归还 给堆。经过一段时间运行后，运行空间被划 分成许多块，需要整理。10.1.4 堆式动态存储分配1510.2 栈式存贮分配的实现条件：C满足上述条件C程序结构全局数据说明Main()Main数据说明Void R() R数据说明Void Q() Q数据说明不允许嵌套定义允许递归调用10.2.1 简单栈式存
8、贮分配的实现16假设调用顺序： 对于全局数据， main的活动记录 全局静态数据区Q的活动记录R的活动记录topsp是可以静态确定的， 因 此在编译时就可确定这些非局部数据的 存贮分配main调用Q，Q调用RMain调用Q，Q调用QMain调用Q，然后main调用R 课本p235图10.8程序运行时存贮组织为：17C每个子程序的活动记录:老SP返回地址参数个数 n形式单元简单变量内情向量临时工作单元SPTO P老sp即是控制链，调用该过程的那个过程最新活 动记录的起始指针。012指针SP指向现正运行过程活动记 录的起点TOP指向已经占有的栈顶单元184被调用者初始化其局部数据并开始执行。3被调
9、用者存放寄存器值和其它状态信息。 2调用者在被调用者的活动记录中存放返 回地址和老sp之值，之后调用者改变 TOP的值 。 目标代码需要完成任务：1. 调用者对实在参数求值，并把它们传送给 被调用过程的活动记录的参数域。 19返回序列，return目标代码完成的任务是： 1被调用者将返回值放入临近主调者的活 动记录的地方2利用状态域中的信息，被调用者恢复sp和其它寄存器，并且按返回地址转移到调用者的代码之中。3调用者复制返回值到自己的活动记录中 。20R的返回语句：return(E)E为返回值，放在临时单元中接下来恢复调用现场：top=sp-1x=1sp (返回地址)sp=0spjump x
10、(转向Q的下一条指令)首先：将送入特定寄存器21Program sort;var a: array010 of integer; x:integer;Begin a=0;quicksort;endProcedure quicksort(m,n:integer);var k,v:integer;Begin .endquicksortfunction partition(y,z:integer):integer;var i,j:integer;Begin avexchange(i,j); end;Procedure exchange(i,j: integer);Begin x:=ai;ai:=aj
11、; aj:=x end;122310.2.2 嵌套过程语言的栈式实现(pascal语言)2Procedure readarray;Var I integer;Begin aend;嵌套定义关系sortreadarrayexchangequicksortpartition22过程readarray和exchange引用了最外层过程说明的a ；过程exchange引用了最外层过程说明的x；一、非局部名字的访问局部变量和形参可以用上节的方法处理非局部名字的访问所要解决的问题就是: 如何找到所有外层过程活动记录的地址.嵌套说明深度：主程序为123跟踪外层过程最新活动记录的方法： 访问链1、访问链和活动
12、记录访问链为活动记 录的一个域,它是从一 个过程当前活动记录 指向其定义的直接外 层的活动记录首地址 的一个指针。 控制链(老SP)返回地址访问链参数个数实参单元临时单元 内情向量 简单变量SPTOP访问链活动记录24top执行顺序sort quicksort quicksort partition exchange存取链控制链局部变量i,j存取链控制链局部变量 k,v存取链控制链局部变量 k,v存取链控制链变量a,xsp exchange的 活动记录partition的 活动记录quicksort的 活动记录quicksort的 活动记录sort活动记录嵌套定义关系 sortreadarra
13、yexchangequicksortpartition25Program p;Var a,x:integerBegin a=0;S;endProcedure Q(b:integer);Var i:integer;Begin .R(1,x);endProcedure R(u:integer;var v:integer)Var c,d:integer;Begin If u=1 then R(u+1,v);v=(a+c)*(b-d);endProcedure SVar c,i:integer;Begin a=1; Q( c);end1223课堂作业：写出p调用S，S调 用Q,Q调用R运行时数据栈26
14、Program main;Var a,b,c: real;Beginx;end.Procedure x;Var d,e: real;Begin10:y;11:z; end;Procedure y;Var f,g:real;Begin endProcedure zVar h,i,j:real;Begin y; end;1233课堂练习2：当主程序调用x时，给出以下时刻 数据栈的情况。 (1)已经开始但尚未执行完标号为10的语句； (2)已经开始但尚未执行完标号为11的语句.2710.3 参数传递（课堂讨论）P244-24510.3.1 传值P245-24610.3.2 传地址作业：p248 ex
15、5, ex62810. 4 符号表(书ch9)编译器的一个基本功能是记录源程序中使 用的标识符并收集与每个标识符相关的各种属 性信息，并将它们记载到符号表中。 若是普通变量名 ：名字、类型、 存贮位置、作用 域若是过程名：还 包括参数个数、 类型、传递方法 及返回值类型符号表是一个数据结构 。每个标识符在符号表中都 有一条记录名字记号信息栏id1id2initialposition固定长标识符29符号表的实现固定长标识符：采用线性链表不定长标识符：使用单独的数组lexemes存放 标识符的字符串,符号表中存放标识符在 lexemes的起始位置和相应记号i f eos i n t eos p o s i t i o n eos i n i t i a l eosIf int id1 id230符号表中信息栏的内容：变量：类型(int 、float、double、boolean、char）种属（简单变量、数组、记录、过程名）长度（所需存贮单元数）偏移量（存贮单元相对地址，若为数组 ，则记录内情向量表）嵌套深度 31过程：是否为程序的外部过程若为函数，类型是什么是否递归？形式参数？.32关于符号表的进一步讨论：1. 符号表的数椐结构（a） 线性表；( b ) 散列表；（ c ）树结构。2. 符号表上的运算：（a）插入（insert）；（b）查找（lookup）；（c )
