1、编译原理基础1S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序错误处理符号表管理编译程序在编译阶段要为源程序中出现的变量、常量等组织好在运行阶段的存储空间将这种组织形式通过生成的目标代码体现出来为运行阶段实现存储奠定基础2第八章 程序运行时的存储组织及管理 教学目标1.要求明确静态存储分配和动态存储分配的含义2.了解栈式动态存储分配和活动记录的含义及组成3.了解堆式动态存储分配的分配方式和管理技术38.1 程序运行时的存储组织8.2 静态存储分配8.3 栈式动态存储分配8.4 堆式动态存储分配教学内容48.1 程序运行时的存储组织 运行时存储空间的划分代码空间数据
2、空间目标代码区静态数据区运行栈区 运行堆区5存储分配策略p目标代码的长度在编译时就可确定,可放在静态区内;p对于在编译时已知大小的数据对象(如常量,全局变量,静态变量等等), 也可放在静态区内;p为提高运行效率,应尽可能多地分配静态数据空间。FORTRAN,BASIC的分配一般可全部放在静态区内.p像PASCAL,C这类语言的实现,由于子程序允许递归地调用,因此应用一数据栈来动态地管理内存分配.p另外PASCAL和C还允许动态地申请的内存,这种数据的空间可由堆式分配实现.6活动记录（active record）p执行过程时所需进行的信息管理，是通过活动记录实现的，活动记录连续存储在块中，其内容
3、见右图。p以过程为单位的动态存储分配方案：n当一过程被调用时，就把其活动记录压入运行时存储栈顶，返回时弹出之。 临时变量 内情向量 形式单元 动态链 返回地址 静态链 局部变量 连接数据区 局部数据区 SP TOP78.2 静态存储分配 p若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的静态存储管理。p采用静态存储分配的语言必须满足下列条件：1） 不允许过程有递归调用。2） 不允许有可变大小的数据项，如可变数组或可变字符串。3） 不允许用户动态建立数据实体。满足上述条件的语言有FORTRAN、BASIC等。88.2 静态存储分配右下图是一个FORTRAN程序模块在采用
4、静态存储分配策略时的典型数据区格局。隐式参数隐式参数（返回地址、寄（返回地址、寄存器内容等）存器内容等）形式参数形式参数简单变量简单变量数组数组临时变量临时变量1) 隐式参数主要用于和主调模块的通讯，在一般情况下这个参数可以是主调过程的返回地址，或在不能利用寄存器返回函数值时传回函数返回值。这些信息不会在程序中明显地出现，所以称为隐式参数。2) 形式参数部分存放相应实在参数的地址或值。3) 程序变量部分将作为简单变量、数组、记录以及编译程序所产生的临时变量的存储空间。9静态存储分配动态存储分配静态存储分配在编译阶段由编译程序实现对存储空间的管理，为源程序中的变量分配存储单元。在编译时能够确定变
5、量在运行时的数据空间大小运行时不改变动态存储分配在目标程序运行阶段由目标程序实现对存储空间的组织与管理，为源程序中的变量分配存储单元。在目标程序运行时进行分配 编译时为运行阶段设计好存储组织形式，即为每个数据项安排好它在数据区中的相对位置108.3 栈式动态存储分配 p栈式分配适用于允许递归调用的程序设计语言;p引入一运行栈,每调用一次过程,就把该过程的相应调用记录压入栈,过程执行完毕后再将其弹出栈;进入时：在栈顶为其分配一个数据区退出时：撤消过程数据区动作：1)申请2)释放3)嵌套调用11下面我们通过一段C程序的运行来说明运行栈的变化情况。设有C程序如下：realx;块1intm1(inti
6、nd)块2intx;x=m2(ind+1);intm2(intj)块3intf10;块4booltest1;main()块5intx;x=2;printf(%dn,m1(x/5);块4数据区块3数据区块2数据区块5数据区块1数据区块3数据区块2数据区块5数据区块1数据区块2数据区块5数据区块1数据区块5数据区块1数据区块1数据区 (a) (b) (c) (d) (e)121、 参数区 参数区保存的内容包括：1) 隐式参数：隐式参数常包含下列几项： 返回地址：主调程序中调用语句的下一条可执行语句的地址。 指向前一个活动记录起始位置的指针：该基地址指针存放该模块的主调模块的活动记录的基地址，用于确
7、保控制返回主调过程时，能使运行环境恢复到调用前的格局。 函数返回值：有的隐式参数区包含此项，有的不包括，还有更好的处理返回值的方法 。2) 显式参数：显式参数区是形式参数的通讯区。 形式参数的传递有传值、传地址、传名等方法。有些语言如PASCAL语言即可传值、也可传地址。C语言采用的是传值的方式，这种参数传递方法，实在参数的值将赋给形式参数。当程序运行进入一个程序块时，就要在运行栈中为此程序块添加一个活动记录。活动记录中除了存储局部变量外，还包括一个参数区和一个display区。图8.3表示了一个典型的活动记录的概貌。 参数区局部数据DISPLAY132、Display（嵌套次示表）区disp
8、lay区用于保存当前正在行的模来是全局的程序量区的信息，它由一系列地址指所成，每一个指指向一个程序的活 的开始位置，而个程序 于当前正在行的程序来是全局的。参数区局部数据DISPLAYP的活动纪录的地址Q的最新活动纪录的地址R的现行活动纪录地址210例如，令过程R的外层为Q，Q的外层为P，则过程R运行时display表的内容应为：14图8.4给出了图8.2(e)的运行栈中各活动记录的内容。块4的活动记录如下：DISPLAY区：指针d1和d2，分别指向全局变量区的地址Abp0和Abp3。隐式参数区：有两个参数，第一个是返回地址，因块4不是一个独立的函数，是一嵌套的块程序，所以，没有返回地址，同样
9、也没有形参，第2个参数Abp3表示在运行栈中，前一个活动记录是开始地址为Abp3的m2活动记录。局部数据区：f和test。 abp2os无前记录xd1abp0 xd1return2abp1indxd1return3jd1d2abp3ftest块4活动记录abp4 m2活动记录abp3 m1活动记录abp2 main活动记录abp1abp015递归过程的处理 下面程序的运行结果是什么？如果把第6行的(i+1)*fact( )改成fact( )*(i+1)的话，则程序的运行结果是有什么变化？试分析为什么会有这两种不同的结果。int fact() static int i=5; if(i=0) re
10、turn 1; else i-; return( (i+1)*fact() ); /第6行 main() printf(factor of 5!=%dn,fact(); 168.4 堆式动态存储分配 p当程序语言允许在运行时为变量动态申请和释放存储空间，采用堆式分配是最有效的解决方案。p堆式分配的基本思想是，为正运行的程序划出适当大的空间(称为堆Heap)，每当需要时可从堆的空闲区中分得一块，用完之后再退还给堆。p如C语言中的malloc和free函数。p如C+语言中的new和delete函数。178.4.1 堆分配方式 当运行程序请求一块体积为N的空间时，应该如何分配呢？常采用的方法如下：1
11、） 先遇到哪个大于N的空闲块就从中取出N个单元进行分配。2） 如果在堆中找不到大于N的空闲块，但所有空闲块的总和比N大，就需要将空闲块连接在一起，从而形成大于N的空闲块。如果所有空闲块的总和都小于N，则需要采用更复杂的办法。如废品回收技术，将那些运行程序已经不使用但还没有释放的块、或运行程序目前很少使用的块回收，再重新分配。 188.4.2 堆式存储管理技术 u1u2u3u4u5u6u7u8u1u3u4u7u8(a)程序运行初期： (b)运行一段时间后：当有新请求分配内存时，有两种策略分配空间：1) 系统继续从高地址的空闲块中进行分配，而不查看已分配给用户的内存区是否已空闲，直到分配无法进行(
12、即剩余的空闲块不能满足分配的请求)时，系统才去回收所有用户不再使用的空闲块。2) 用户使用一旦结束，便将所占内存区释放成空闲块。同时，每当新的用户请求分配内存时，系统需要巡视整个内存中所有空闲块，并从中找出一个“合适”的空闲块加以分配。190 10000 20000 30000(a)内存状态 起始地址内存大小使用情况100005000空闲200003000空闲300008000空闲(b)可利用空间目录 050002000003000300000800#10000HEAD 10000 20000 30000(c)可利用空间链表图8.7堆式存储管理的可利用空间表 201、定长块的管理p将总的可被利
13、用的堆存储区划分成大小适当的一系列块。p这些块通过每块中的LINK域连接起来形成单向线性链表，即可利用空间表，如下图所示。200000300000#010000HEAD 10000 20000 30000212、变长块的管理p变长块的管理是常用的堆式存储管理方法。p系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。因此，“可利用空间表”中的结点，即空闲块的大小也是随意的。p结点的数据结构如下TAG：标记，0表示空闲，1表示占用。SIZE：记录结点大小，指示空闲块的存储量。LINK：指向下一个结点。SPACE：地址连续的内存空间。TAGSIZELINKSPACE22变长块内存的分配p
14、假设用户请求一个大小为n的存储块，而“可利用空间表”中仅有一块大小为mn的空闲块，则分配时只需将大小为n的部分分配给申请的用户，同时将剩余的m-n部分作为一个结点留在链表中即可。p若可利用空间表中有若干个大于n的空闲块时，可采用下列方法分配：1、首次满足法2、最优满足法3、最差满足法238.4.2 堆式存储管理技术p三种分配方式各有所长p最优满足法：产生内存碎片，保留了大内存块，以备响应后面可能发生的对大存储空间的请求。p最差满足法：使链表中的结点空间大小趋于均匀，因此，它适用于请求分配的内存大小范围较窄的系统。p首次满足法：分配随机，适用于事先对系统运行期间可能出现的内存分配和释放情况不能准
15、确把握的场合。248.4.2 堆式存储管理技术p从时间上对三种分配法进行比较查询“可利用空间表”首次满足法 最差满足法 最优满足法分配时需查询需查询回收时需查询需查询253、释放方法p最简单的释放方法是作为一个新的空闲块插入到无序的“可利用空间表”中。p将两个连续的块合并成一个块。需要对“可利用空间表”按块的地址顺序进行组织，同时为了要确定当前释放块的插入位置，还需要对可利用空间表进行搜索。p有的程序设计语言干脆不做释放的工作，直到内存空间用完为止。26小结p静态存储分配和动态存储分配的含义p活动记录的含义及组成p静态、动态存储分配的策略279、静夜四无，荒居旧 。三月-21三月-21Sund
16、ay, March 28, 202110、雨中黄叶，灯下白人。14:39:0714:39:0714:393/28/2021 2:39:07 PM11、以我独沈久，愧君相 。三月-2114:39:0714:39Mar-2128-Mar-2112、故人江海，几度隔山川。14:39:0714:39:0714:39Sunday, March 28, 202113、乍翻疑梦，相悲各年。三月-21三月-2114:39:0714:39:07March 28, 202114、他生白，旧国青山。28 三月 20212:39:07 下午14:39:07三月-2115、比不了得就不比，得不到的就不要。三月 212:
17、39 下午三月-2114:39March 28, 202116、行出成果，工作出富。2021/3/28 14:39:0714:39:0728 March 202117、做前，能 四周；做，你只能或者最好沿着以脚起点的射向前。2:39:07 下午2:39 下午14:39:07三月-219、没有失，只有 停止成功！。三月-21三月-21Sunday, March 28, 202110、很多事情努力了未必有果，但是不努力却什么改也没有。14:39:0714:39:0714:393/28/2021 2:39:07 PM11、成功就是日复一日那一点点小小努力的累。三月-2114:39:0714:39Ma
18、r-2128-Mar-2112、世成事，不求其 ，留一份不足，可得无限完美。14:39:0714:39:0714:39Sunday, March 28, 202113、不知香寺，数里入云峰。三月-21三月-2114:39:0714:39:07March 28, 202114、意志强的人能把世界放在手中像泥一任意揉捏。28 三月 20212:39:07 下午14:39:07三月-2115、楚塞三湘接， 九派通。三月 212:39 下午三月-2114:39March 28, 202116、少年十五二十，步行得胡 。2021/3/28 14:39:0714:39:0728 March 202117、
19、空山新雨后，天气晚来秋。2:39:07 下午2:39 下午14:39:07三月-219、柳散和，青山澹吾。三月-21三月-21Sunday, March 28, 202110、 一切好如同和去最杰出的人 。14:39:0714:39:0714:393/28/2021 2:39:07 PM11、越是没有本的就越加自命不凡。三月-2114:39:0714:39Mar-2128-Mar-2112、越是无能的人，越喜挑剔人的儿。14:39:0714:39:0714:39Sunday, March 28, 202113、知人者智，自知者明。人者有力，自者强。三月-21三月-2114:39:0714:39
20、:07March 28, 202114、意志强的人能把世界放在手中像泥一任意揉捏。28 三月 20212:39:07 下午14:39:07三月-2115、最具挑性的挑莫于提升自我。三月 212:39 下午三月-2114:39March 28, 202116、余生活要有意，不要越。2021/3/28 14:39:0714:39:0728 March 202117、一个人即使已登上峰，也仍要自强不息。2:39:07 下午2:39 下午14:39:07三月-21MOMODA POWERPOINTLorem ipsum dolor sit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis amet, consectetur adipiscing elit. Fusce id urna blanditut cursus. 感谢您的下载观看家告
