版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
《编译原理基础》1《编译原理基础》1S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序错误处理符号表管理编译程序在编译阶段要为源程序中出现的变量、常量等组织好在运行阶段的存储空间将这种组织形式通过生成的目标代码体现出来为运行阶段实现存储奠定基础2S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分第八章程序运行时的存储组织及管理教学目标要求明确静态存储分配和动态存储分配的含义了解栈式动态存储分配和活动记录的含义及组成了解堆式动态存储分配的分配方式和管理技术3第八章程序运行时的存储组织及管理教学目标要求明确静态存储8.1程序运行时的存储组织8.2静态存储分配8.3栈式动态存储分配8.4堆式动态存储分配教学内容48.1程序运行时的存储组织教学内容48.1程序运行时的存储组织运行时存储空间的划分代码空间数据空间目标代码区静态数据区运行栈区…运行堆区58.1程序运行时的存储组织运行时存储空间的划分代码空间数存储分配策略目标代码的长度在编译时就可确定,可放在静态区内;对于在编译时已知大小的数据对象(如常量,全局变量,静态变量等等),也可放在静态区内;为提高运行效率,应尽可能多地分配静态数据空间。FORTRAN,BASIC的分配一般可全部放在静态区内.像PASCAL,C这类语言的实现,由于子程序允许递归地调用,因此应用一数据栈来动态地管理内存分配.另外PASCAL和C还允许动态地申请的内存,这种数据的空间可由堆式分配实现.6存储分配策略目标代码的长度在编译时就可确定,可放在静态区内;活动记录(activerecord)执行过程时所需进行的信息管理,是通过活动记录实现的,活动记录连续存储在块中,其内容见右图。以过程为单位的动态存储分配方案:当一过程被调用时,就把其活动记录压入运行时存储栈顶,返回时弹出之。
临时变量
内情向量
形式单元
动态链
返回地址
静态链
局部变量
连接数据区
局部数据区
SP
TOP7活动记录(activerecord)执行过程时所需进行的信8.2静态存储分配若在编译阶段就能确定源程序中各个数据实体的存储空间大小,则可以采用较简单的静态存储管理。采用静态存储分配的语言必须满足下列条件:1)
不允许过程有递归调用。2)
不允许有可变大小的数据项,如可变数组或可变字符串。3)
不允许用户动态建立数据实体。满足上述条件的语言有FORTRAN、BASIC等。88.2静态存储分配若在编译阶段就能确定源程序中各个数据实8.2静态存储分配右下图是一个FORTRAN程序模块在采用静态存储分配策略时的典型数据区格局。隐式参数(返回地址、寄存器内容等)形式参数简单变量数组临时变量1)隐式参数主要用于和主调模块的通讯,在一般情况下这个参数可以是主调过程的返回地址,或在不能利用寄存器返回函数值时传回函数返回值。这些信息不会在程序中明显地出现,所以称为隐式参数。2)形式参数部分存放相应实在参数的地址或值。3)程序变量部分将作为简单变量、数组、记录以及编译程序所产生的临时变量的存储空间。98.2静态存储分配右下图是一个FORTRAN程序模块在采用静态存储分配←→动态存储分配静态存储分配在编译阶段由编译程序实现对存储空间的管理,为源程序中的变量分配存储单元。在编译时能够确定变量在运行时的数据空间大小运行时不改变动态存储分配在目标程序运行阶段由目标程序实现对存储空间的组织与管理,为源程序中的变量分配存储单元。在目标程序运行时进行分配编译时为运行阶段设计好存储组织形式,即为每个数据项安排好它在数据区中的相对位置10静态存储分配←→动态存储分配静态存储分配108.3栈式动态存储分配栈式分配适用于允许递归调用的程序设计语言;引入一运行栈,每调用一次过程,就把该过程的相应调用记录压入栈,过程执行完毕后再将其弹出栈;进入时:在栈顶为其分配一个数据区退出时:撤消过程数据区动作:1)申请2)释放3)嵌套调用118.3栈式动态存储分配栈式分配适用于允许递归调用的程序设下面我们通过一段C程序的运行来说明运行栈的变化情况。设有C程序如下:realx;…块1intm1(intind)……………块2{intx;x=m2(ind+1);}intm2(intj)………………块3{{intf[10];……………块4booltest1;}}main()………块5{intx;x=2;printf("%d\n",m1(x/5));}块4数据区
块3数据区
块2数据区
块5数据区
块1数据区
块3数据区
块2数据区
块5数据区
块1数据区
块2数据区
块5数据区
块1数据区
块5数据区
块1数据区
块1数据区
(a)(b)(c)(d)(e)12下面我们通过一段C程序的运行来说明运行栈的变化情况。设有C程1、参数区
参数区保存的内容包括:1)
隐式参数:隐式参数常包含下列几项:
返回地址:主调程序中调用语句的下一条可执行语句的地址。
指向前一个活动记录起始位置的指针:该基地址指针存放该模块的主调模块的活动记录的基地址,用于确保控制返回主调过程时,能使运行环境恢复到调用前的格局。
函数返回值:有的隐式参数区包含此项,有的不包括,还有更好的处理返回值的方法。2)显式参数:显式参数区是形式参数的通讯区。形式参数的传递有传值、传地址、传名等方法。有些语言如PASCAL语言即可传值、也可传地址。C语言采用的是传值的方式,这种参数传递方法,实在参数的值将赋给形式参数。当程序运行进入一个程序块时,就要在运行栈中为此程序块添加一个活动记录。活动记录中除了存储局部变量外,还包括一个参数区和一个display区。图8.3表示了一个典型的活动记录的概貌。
参数区
局部数据
DISPLAY131、参数区参数区保存的内容包括:当程序运行进入一个程序2、Display(嵌套层次显示表)区display区用于保存对当前正在执行的模块来说是全局的程序变量区的信息,它由一系列地址指针所组成,每一个指针指向一个程序块的活动记录的开始位置,而这个程序块对于当前正在执行的程序块来说是全局的。参数区
局部数据
DISPLAYP的活动纪录的地址Q的最新活动纪录的地址R的现行活动纪录地址210例如,令过程R的外层为Q,Q的外层为P,则过程R运行时display表的内容应为:142、Display(嵌套层次显示表)区参数区局部数据DI图8.4给出了图8.2(e)的运行栈中各活动记录的内容。块4的活动记录如下:DISPLAY区:指针d1和d2,分别指向全局变量区的地址Abp0和Abp3。隐式参数区:有两个参数,第一个是返回地址,因块4不是一个独立的函数,是一嵌套的块程序,所以,没有返回地址,同样也没有形参,第2个参数Abp3表示在运行栈中,前一个活动记录是开始地址为Abp3的m2活动记录。局部数据区:f和test。abp2os无前记录
xd1abp0xd1return2abp1indxd1return3jd1d2abp3ftest块4活动记录abp4
m2活动记录abp3m1活动记录abp2main活动记录abp1abp015图8.4给出了图8.2(e)的运行栈中各活动记录的内容。ab递归过程的处理下面程序的运行结果是什么?如果把第6行的(i+1)*fact()改成fact()*(i+1)的话,则程序的运行结果是有什么变化?试分析为什么会有这两种不同的结果。intfact(){staticinti=5;if(i==0)return1;else{i--;return((i+1)*fact());//第6行}}main(){printf("factorof5!=%d\n",fact());}16递归过程的处理下面程序的运行结果是什么?如果把第6行的(i8.4堆式动态存储分配当程序语言允许在运行时为变量动态申请和释放存储空间,采用堆式分配是最有效的解决方案。堆式分配的基本思想是,为正运行的程序划出适当大的空间(称为堆Heap),每当需要时可从堆的空闲区中分得一块,用完之后再退还给堆。如C语言中的malloc和free函数。如C++语言中的new和delete函数。178.4堆式动态存储分配当程序语言允许在运行时为变量动态申8.4.1堆分配方式当运行程序请求一块体积为N的空间时,应该如何分配呢?常采用的方法如下:1)
先遇到哪个大于N的空闲块就从中取出N个单元进行分配。2)
如果在堆中找不到大于N的空闲块,但所有空闲块的总和比N大,就需要将空闲块连接在一起,从而形成大于N的空闲块。如果所有空闲块的总和都小于N,则需要采用更复杂的办法。如废品回收技术,将那些运行程序已经不使用但还没有释放的块、或运行程序目前很少使用的块回收,再重新分配。188.4.1堆分配方式当运行程序请求一块体积为N的空间时,8.4.2堆式存储管理技术u1u2u3u4u5u6u7u8u1u3u4u7u8(a)程序运行初期:(b)运行一段时间后:当有新请求分配内存时,有两种策略分配空间:系统继续从高地址的空闲块中进行分配,而不查看已分配给用户的内存区是否已空闲,直到分配无法进行(即剩余的空闲块不能满足分配的请求)时,系统才去回收所有用户不再使用的空闲块。用户使用一旦结束,便将所占内存区释放成空闲块。同时,每当新的用户请求分配内存时,系统需要巡视整个内存中所有空闲块,并从中找出一个“合适”的空闲块加以分配。198.4.2堆式存储管理技术u1u2u3u4u5u6u7u0100002000030000(a)内存状态起始地址内存大小
使用情况
100005000空闲200003000空闲300008000空闲(b)可利用空间目录050002000003000300000800#10000HEAD100002000030000(c)可利用空间链表图8.7堆式存储管理的可利用空间表2001、定长块的管理将总的可被利用的堆存储区划分成大小适当的一系列块。这些块通过每块中的LINK域连接起来形成单向线性链表,即可利用空间表,如下图所示。200000300000#010000HEAD100002000030000211、定长块的管理将总的可被利用的堆存储区划分成大小适当的一系2、变长块的管理变长块的管理是常用的堆式存储管理方法。系统在运行期间分配给用户的内存块的大小不固定,可以随请求而变。因此,“可利用空间表”中的结点,即空闲块的大小也是随意的。结点的数据结构如下∶TAG:标记,0表示空闲,1表示占用。SIZE:记录结点大小,指示空闲块的存储量。LINK:指向下一个结点。SPACE:地址连续的内存空间。TAGSIZELINKSPACE222、变长块的管理变长块的管理是常用的堆式存储管理方法。SPA变长块内存的分配假设用户请求一个大小为n的存储块,而“可利用空间表”中仅有一块大小为m≥n的空闲块,则分配时只需将大小为n的部分分配给申请的用户,同时将剩余的m-n部分作为一个结点留在链表中即可。若可利用空间表中有若干个大于n的空闲块时,可采用下列方法分配:1、首次满足法
2、最优满足法3、最差满足法23变长块内存的分配假设用户请求一个大小为n的存储块,而“可利用8.4.2堆式存储管理技术三种分配方式各有所长最优满足法:产生内存碎片,保留了大内存块,以备响应后面可能发生的对大存储空间的请求。最差满足法:使链表中的结点空间大小趋于均匀,因此,它适用于请求分配的内存大小范围较窄的系统。首次满足法:分配随机,适用于事先对系统运行期间可能出现的内存分配和释放情况不能准确把握的场合。248.4.2堆式存储管理技术三种分配方式各有所长248.4.2堆式存储管理技术从时间上对三种分配法进行比较查询“可利用空间表”首次满足法最差满足法最优满足法分配时需查询-需查询回收时-需查询需查询258.4.2堆式存储管理技术从时间上对三种分配法进行比较查询3、释放方法最简单的释放方法是作为一个新的空闲块插入到无序的“可利用空间表”中。将两个连续的块合并成一个块。需要对“可利用空间表”按块的地址顺序进行组织,同时为了要确定当前释放块的插入位置,还需要对可利用空间表进行搜索。有的程序设计语言干脆不做释放的工作,直到内存空间用完为止。263、释放方法最简单的释放方法是作为一个新的空闲块插入到无序的小结静态存储分配和动态存储分配的含义活动记录的含义及组成静态、动态存储分配的策略27小结静态存储分配和动态存储分配的含义27《编译原理基础》28《编译原理基础》1S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序错误处理符号表管理编译程序在编译阶段要为源程序中出现的变量、常量等组织好在运行阶段的存储空间将这种组织形式通过生成的目标代码体现出来为运行阶段实现存储奠定基础29S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分第八章程序运行时的存储组织及管理教学目标要求明确静态存储分配和动态存储分配的含义了解栈式动态存储分配和活动记录的含义及组成了解堆式动态存储分配的分配方式和管理技术30第八章程序运行时的存储组织及管理教学目标要求明确静态存储8.1程序运行时的存储组织8.2静态存储分配8.3栈式动态存储分配8.4堆式动态存储分配教学内容318.1程序运行时的存储组织教学内容48.1程序运行时的存储组织运行时存储空间的划分代码空间数据空间目标代码区静态数据区运行栈区…运行堆区328.1程序运行时的存储组织运行时存储空间的划分代码空间数存储分配策略目标代码的长度在编译时就可确定,可放在静态区内;对于在编译时已知大小的数据对象(如常量,全局变量,静态变量等等),也可放在静态区内;为提高运行效率,应尽可能多地分配静态数据空间。FORTRAN,BASIC的分配一般可全部放在静态区内.像PASCAL,C这类语言的实现,由于子程序允许递归地调用,因此应用一数据栈来动态地管理内存分配.另外PASCAL和C还允许动态地申请的内存,这种数据的空间可由堆式分配实现.33存储分配策略目标代码的长度在编译时就可确定,可放在静态区内;活动记录(activerecord)执行过程时所需进行的信息管理,是通过活动记录实现的,活动记录连续存储在块中,其内容见右图。以过程为单位的动态存储分配方案:当一过程被调用时,就把其活动记录压入运行时存储栈顶,返回时弹出之。
临时变量
内情向量
形式单元
动态链
返回地址
静态链
局部变量
连接数据区
局部数据区
SP
TOP34活动记录(activerecord)执行过程时所需进行的信8.2静态存储分配若在编译阶段就能确定源程序中各个数据实体的存储空间大小,则可以采用较简单的静态存储管理。采用静态存储分配的语言必须满足下列条件:1)
不允许过程有递归调用。2)
不允许有可变大小的数据项,如可变数组或可变字符串。3)
不允许用户动态建立数据实体。满足上述条件的语言有FORTRAN、BASIC等。358.2静态存储分配若在编译阶段就能确定源程序中各个数据实8.2静态存储分配右下图是一个FORTRAN程序模块在采用静态存储分配策略时的典型数据区格局。隐式参数(返回地址、寄存器内容等)形式参数简单变量数组临时变量1)隐式参数主要用于和主调模块的通讯,在一般情况下这个参数可以是主调过程的返回地址,或在不能利用寄存器返回函数值时传回函数返回值。这些信息不会在程序中明显地出现,所以称为隐式参数。2)形式参数部分存放相应实在参数的地址或值。3)程序变量部分将作为简单变量、数组、记录以及编译程序所产生的临时变量的存储空间。368.2静态存储分配右下图是一个FORTRAN程序模块在采用静态存储分配←→动态存储分配静态存储分配在编译阶段由编译程序实现对存储空间的管理,为源程序中的变量分配存储单元。在编译时能够确定变量在运行时的数据空间大小运行时不改变动态存储分配在目标程序运行阶段由目标程序实现对存储空间的组织与管理,为源程序中的变量分配存储单元。在目标程序运行时进行分配编译时为运行阶段设计好存储组织形式,即为每个数据项安排好它在数据区中的相对位置37静态存储分配←→动态存储分配静态存储分配108.3栈式动态存储分配栈式分配适用于允许递归调用的程序设计语言;引入一运行栈,每调用一次过程,就把该过程的相应调用记录压入栈,过程执行完毕后再将其弹出栈;进入时:在栈顶为其分配一个数据区退出时:撤消过程数据区动作:1)申请2)释放3)嵌套调用388.3栈式动态存储分配栈式分配适用于允许递归调用的程序设下面我们通过一段C程序的运行来说明运行栈的变化情况。设有C程序如下:realx;…块1intm1(intind)……………块2{intx;x=m2(ind+1);}intm2(intj)………………块3{{intf[10];……………块4booltest1;}}main()………块5{intx;x=2;printf("%d\n",m1(x/5));}块4数据区
块3数据区
块2数据区
块5数据区
块1数据区
块3数据区
块2数据区
块5数据区
块1数据区
块2数据区
块5数据区
块1数据区
块5数据区
块1数据区
块1数据区
(a)(b)(c)(d)(e)39下面我们通过一段C程序的运行来说明运行栈的变化情况。设有C程1、参数区
参数区保存的内容包括:1)
隐式参数:隐式参数常包含下列几项:
返回地址:主调程序中调用语句的下一条可执行语句的地址。
指向前一个活动记录起始位置的指针:该基地址指针存放该模块的主调模块的活动记录的基地址,用于确保控制返回主调过程时,能使运行环境恢复到调用前的格局。
函数返回值:有的隐式参数区包含此项,有的不包括,还有更好的处理返回值的方法。2)显式参数:显式参数区是形式参数的通讯区。形式参数的传递有传值、传地址、传名等方法。有些语言如PASCAL语言即可传值、也可传地址。C语言采用的是传值的方式,这种参数传递方法,实在参数的值将赋给形式参数。当程序运行进入一个程序块时,就要在运行栈中为此程序块添加一个活动记录。活动记录中除了存储局部变量外,还包括一个参数区和一个display区。图8.3表示了一个典型的活动记录的概貌。
参数区
局部数据
DISPLAY401、参数区参数区保存的内容包括:当程序运行进入一个程序2、Display(嵌套层次显示表)区display区用于保存对当前正在执行的模块来说是全局的程序变量区的信息,它由一系列地址指针所组成,每一个指针指向一个程序块的活动记录的开始位置,而这个程序块对于当前正在执行的程序块来说是全局的。参数区
局部数据
DISPLAYP的活动纪录的地址Q的最新活动纪录的地址R的现行活动纪录地址210例如,令过程R的外层为Q,Q的外层为P,则过程R运行时display表的内容应为:412、Display(嵌套层次显示表)区参数区局部数据DI图8.4给出了图8.2(e)的运行栈中各活动记录的内容。块4的活动记录如下:DISPLAY区:指针d1和d2,分别指向全局变量区的地址Abp0和Abp3。隐式参数区:有两个参数,第一个是返回地址,因块4不是一个独立的函数,是一嵌套的块程序,所以,没有返回地址,同样也没有形参,第2个参数Abp3表示在运行栈中,前一个活动记录是开始地址为Abp3的m2活动记录。局部数据区:f和test。abp2os无前记录
xd1abp0xd1return2abp1indxd1return3jd1d2abp3ftest块4活动记录abp4
m2活动记录abp3m1活动记录abp2main活动记录abp1abp042图8.4给出了图8.2(e)的运行栈中各活动记录的内容。ab递归过程的处理下面程序的运行结果是什么?如果把第6行的(i+1)*fact()改成fact()*(i+1)的话,则程序的运行结果是有什么变化?试分析为什么会有这两种不同的结果。intfact(){staticinti=5;if(i==0)return1;else{i--;return((i+1)*fact());//第6行}}main(){printf("factorof5!=%d\n",fact());}43递归过程的处理下面程序的运行结果是什么?如果把第6行的(i8.4堆式动态存储分配当程序语言允许在运行时为变量动态申请和释放存储空间,采用堆式分配是最有效的解决方案。堆式分配的基本思想是,为正运行的程序划出适当大的空间(称为堆Heap),每当需要时可从堆的空闲区中分得一块,用完之后再退还给堆。如C语言中的malloc和free函数。如C++语言中的new和delete函数。448.4堆式动态存储分配当程序语言允许在运行时为变量动态申8.4.1堆分配方式当运行程序请求一块体积为N的空间时,应该如何分配呢?常采用的方法如下:1)
先遇到哪个大于N的空闲块就从中取出N个单元进行分配。2)
如果在堆中找不到大于N的空闲块,但所有空闲块的总和比N大,就需要将空闲块连接在一起,从而形成大于N的空闲块。如果所有空闲块的总和都小于N,则需要采用更复杂的办法。如废品回收技术,将那些运行程序已经不使用但还没有释放的块、或运行程序目前很少使用的块回收,再重新分配。458.4.1堆分配方式当运行程序请求一块体积为N的空间时,8.4.2堆式存储管理技术u1u2u3u4u5u6u7u8u1u3u4u7u8(a)程序运行初期:(b)运行一段时间后:当有新请求分配内存时,有两种策略分配空间:系统继续从高地址的空闲块中进行分配,而不查看已分配给用户的内存区是否已空闲,直到分配无法进行(即剩余的空闲块不能满足分配的请求)时,系统才去回收所有用户不再使用的空闲块。用户使用一旦结束,便将所占内存区释放成空闲块。同时,每当新的用户请求分配内存时,系统需要巡视整个内存中所有空闲块,并从中找出一个“合适”的空闲块加以分配。468.4.2堆式存储管理技术u1u2u3u4u5u6u7u0100002000030000(a)内存状态起始地址内存大小
使用情况
100005000空闲200003000空闲300008000空闲(b)可利用空间目录050002000003000300000800#10000HEAD100002000030000(c)可利用空间链表图8.7堆式存储管理的可利用空间表470
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 继发性多发性关节病
- 眼底病早期诊断与治疗进展
- 芪苈强心胶囊结合倍他乐克治疗扩张型心肌病的临床疗效分析
- 2027年寒假开学摸底考试九年级地理易错题卷及答案
- 生脉活血汤联合达格列净治疗冠心病合并型糖尿病的临床疗效观察
- 医院内科低钙血症临床思维诊疗指南
- 八年级生物模拟卷(2026-2027学年下学期期末考试)
- 八年级化学测试卷(2026-2027学年上学期期末考试)
- 2027年春季开学考试高三地理检测卷及答案解析
- 2027年春季开学考试九年级历史专题训练卷及答案解析
- 2026浙江宁波市宁海县国有企业招聘考试参考题库及答案解析
- 2026年中国抗体药物市场现状调研分析及前景预测报告
- 2026消防宣传月培训课件(含火灾案例)
- 2026医工交叉研究发展分析及跨学科创新预测报告
- 2024年12月规培结业考试呼吸内科胸腔积液康复基础巩固题及答案
- 基于PDCA循环的长期医嘱口服药发放质量改进与安全管理实践
- 家装托管服务合同协议书
- 2026河南政治高考真题试卷(含答案解析)
- 2026年4月自考00144企业管理概论试题试题及答案含评分参考
- 35kv集电线路运行规程
- 2024中医内科临床诊疗指南眩晕病(原发性高血压)
评论
0/150
提交评论