第十章 目标程序运行时的组织.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第十章 目标程序运行时的组织.ppt》由用户(hyngb9260)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十章 目标程序运行时的组织 第十 目标 程序 运行 组织
- 资源描述:
-
1、第十章第十章 目标程序目标程序运行时的运行时的组织组织 10.1 概述概述10.2数据表示数据表示10.3目标程序运行时的栈式存储组织目标程序运行时的栈式存储组织10.4 参数传递参数传递10.5堆式存储组织的讨论堆式存储组织的讨论概述-代码生成解决语义gap高级语言支持的概念Type value expressionVariable procedureFunction parameters目标机支持的概念 bits bytes wordsRegistersStack addressRoutine(sub routine)概述代码生成前如何安排目标机资源运行时组织的几个问题运行时组织的几个问题
2、数据表示-如何在目标机中表示每个源语言类型的值表达式求值-如何组织表达式的计算存储分配-如何组织不同作用域变量的存储过程实现-如何以例程实现过程,函数,参数传递概述概述任务:编译程序对目标程序运行时的组织(设任务:编译程序对目标程序运行时的组织(设计运行环境和分配存储)计运行环境和分配存储)如如 通常存储区布局通常存储区布局可为:可为:目标代码区目标代码区 静态数据区静态数据区 Stack heap运行环境和存储分配运行环境和存储分配设计分析设计分析逻辑阶段:在目标代码生成前,作准备逻辑阶段:在目标代码生成前,作准备实质:实质:关联(关联(Binding)将源程序的文本将源程序的文本 程序运行
3、动作的实现程序运行动作的实现 源文件中的名字源文件中的名字N 运行时的存储运行时的存储S S在语义学中,使用术语在语义学中,使用术语environment函数表示函数表示env:NS (NS (N到到S S的映射的映射)静静态态文文本本中中 运运行行时时动动作作及及为为实实现现其其动动作作的的准准备备 (与与运运行行时时数数据据对对象象的的表表示示有有关关)过过程程定定义义 过过程程名名执执行行过过程程体体 过过程程体体 控控制制数数据据对对象象的的分分配配,为为执执行行过过程程体体使使用用源源文文本本中中同同样样的的名名字字 目目标标程程序序中中不不同同的的数数据据空空间间因因为为一一个个过
4、过程程可可以以是是递递归归的的,这这时时同同一一个个名名字字在在不不同同的的时时间间可可能能代代表表不不同同的的存存储储单单元元决定运行管理复杂程度的因素决定运行管理复杂程度的因素源语言本身源语言本身1.允许的数据类型的多少允许的数据类型的多少2语言中允许的数据项是语言中允许的数据项是 静态确定静态确定 动态确定动态确定3程序结构程序结构 决定名字的作用域的规则和结构决定名字的作用域的规则和结构A 段结构段结构B 过程定义不嵌套,只允许过程递归调用过程定义不嵌套,只允许过程递归调用C 分程序结构分程序结构分程序嵌套分程序嵌套过程定义嵌套过程定义嵌套 4 4存储类别的多少存储类别的多少Globa
5、lStaticLocaldynamic术语术语 静态:如果一个名字的性质通过说明语句静态:如果一个名字的性质通过说明语句或隐或显规则而定义,则称这种性质是或隐或显规则而定义,则称这种性质是“静态静态”确定的。确定的。动态:如果名字的性质只有在程序运行时动态:如果名字的性质只有在程序运行时才能知道,则称这种性质为才能知道,则称这种性质为“动态动态”确定确定的。的。例例 procedure A(m,n:integer);begin real z;array Bm:n;begin end;end;声明的作用域声明的作用域 词法作用域词法作用域 动态作用域动态作用域例:例:(1)program dyn
6、amic(i,0);(2)var r:real(3)procedure show;(4)begin write(r:5:3)end;(5)procedrue small;(6)var r:real;(7)begin r:=0.125;show end;(8)begin(9)r:=0.25;(10)show;small;write/n;(11)show;small;write/n;(12)end.lexical scope0.250 0.2500.250 0.250dynamic scope0.250 0.1250.250 0.125数据表示各种数据对象的存储分配数据对象的属性 name 名字,
7、名称 type 类型 location 内存地址 value 值 component 成分 数据表示(固定长度,直接或间接表示)简单变量:char:1 byteintegers:2 or 4 bytesfloats:4 to 16 bytesbooleans:1 bit(but usually 1 byte)指针:unsigned integers一维数组:一块连续的存储区多维数组:一块连续的存储区,按行存放结构(记录):把所有域(field)存放在一块连续的存储区对象:类的实例变量象结构的域一样存放在一块连续的存储区,但方法(成员函数)不存在该对象里指令:例:按行例:按行 A是是 10 20
8、 的二维数组的二维数组A1,1A1,2.第一行第一行.A1,20A2,1.第二行第二行.A10,20 第十行第十行数组元素的地址计算数组元素的地址计算设设 A1,1的地址为的地址为 a,每个元素占一个字,每个元素占一个字Ai,j的地址:的地址:a+(i-1)20+(j-1)=(a-21)+(20i+j)一般:一般:arrayAl1:u1,l2:u2,ln:un令令 di=ui-li+1元素元素 Ai1,i2,in的地址的地址 D D=a+(i1-l1)d2d3dn+(i2-l2)d3d4dn+(in-1-l n-1)dn+(in-ln)经因子分解后得经因子分解后得 D=CONSPART+VAR
9、PART其中其中 CONSPART=a-C C=(l1d2+l2)d3+l3)d4+l n-1)dn+ln VARPART=(i1d2+i2)d3+i3)d4+i n-1)dn+in四元式四元式 两组两组 VARPART T CONSPARTT1T1 T表示数组元素的地址表示数组元素的地址数组元素引用:数组元素引用:X:=T1 T对数组元素赋值:对数组元素赋值:T1 T:=Xl 可变可变(动态动态)数组数组:若一个数组所需的存储空间的大小在编译时就已知道,则称它为确定数组,否则称为可变(动态)数组。数组内情向量:数组内情向量::编译将数组的有关信息记录在一些单元中,称为数组的“内内情向量情向量
10、”Al 1:u 1,l 2:u 2,l ln n :u un n l1 u1 l2 u2 :type a(首地址)(首地址)n C目标程序运行时的存储组织目标程序运行时的存储组织存储分配策略:存储分配策略:简单的栈式分配方案简单的栈式分配方案 嵌套过程的栈式分配方案嵌套过程的栈式分配方案 分程序结构的存储分配方案分程序结构的存储分配方案静态存储分配静态存储分配动态存储分配动态存储分配栈式栈式堆式堆式l 术语术语-过程活动记录过程活动记录AR:为说明方便,假定程序是由过程组成,过程区分为源文本,为说明方便,假定程序是由过程组成,过程区分为源文本,运行时称作过程的激活。运行时称作过程的激活。一个过
11、程的一次执行所需要的信息使用一个连续的存储区来一个过程的一次执行所需要的信息使用一个连续的存储区来管理,这个区管理,这个区(块)叫做一个活动记录或(块)叫做一个活动记录或frame(帧帧)一般这个段要记录:一般这个段要记录:l 临时值,如计算表达式时的中间工作单元。临时值,如计算表达式时的中间工作单元。l 局部变量局部变量(数据)(数据)l 保存运行过程前的状态保存运行过程前的状态(返回地址,寄存器值(返回地址,寄存器值)l 存取链存取链(可选)(可选)对于非局部量的引用。对于非局部量的引用。l 控制链控制链(可选)(可选)指向调用者的活动记录,释放栈。指向调用者的活动记录,释放栈。l 实参实
12、参(形式单元)(形式单元)l 返回值返回值(对函数)(对函数)(有时可使用寄存器存放返回值)(有时可使用寄存器存放返回值)简单的栈式分配方案简单的栈式分配方案 程序结构特点程序结构特点:过程定义不嵌套,过程可过程定义不嵌套,过程可递归调用,含可变数组递归调用,含可变数组;例例:main 全局变量的说明全局变量的说明 proc R end R;proc Q end Q;主程序执行语句主程序执行语句 end mainMain-Q-R Main-Q-Q TOP-R 的活动记录的活动记录 Q 的活动记录的活动记录 SP-Q 的活动记录的活动记录 Q 的活动记录的活动记录 主程序全局主程序全局 主程序全
13、局主程序全局 数据区数据区 数据区数据区TOP-临时工作单元临时工作单元 局部简单变量局部简单变量 局部数组的内情向量局部数组的内情向量 保存运保存运 行过程前的状态行过程前的状态(返回地址,寄存器值)(返回地址,寄存器值)实参实参(形式单元)和参数个数(形式单元)和参数个数 SP-控制链控制链(老(老 SP)TOP R 的数组区的数组区 SP R 的活动记录的活动记录 Q 的活动记录的活动记录 主程序全局主程序全局 数据区数据区 嵌套过程语言的栈式嵌套过程语言的栈式分配方案分配方案l主要特点主要特点:(语言)一个过程可以引用包围它的任(语言)一个过程可以引用包围它的任一外层过程所定义的标识符
14、(如变量,一外层过程所定义的标识符(如变量,数组或过程等)。数组或过程等)。(实现)一个过程可以引用它的任一外(实现)一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。层过程的最新活动记录中的某些数据。关键技术:解决对非局部量的引用(存关键技术:解决对非局部量的引用(存取)。取)。设法跟踪每个外层过程的最新活动记录设法跟踪每个外层过程的最新活动记录AR的位置。的位置。跟踪办法:跟踪办法:1.用静态链(如用静态链(如PL/0的的SL)。)。2.用用DISPLAY表。表。const a=10;const a=10;var var b,c;b,c;procedure p;procedure
15、 p;beginbegin c:=b+a;c:=b+a;end;end;beginbegin read(b);read(b);while while b#0b#0 do do begin begin call p;call p;write(2 write(2*c);c);read(b);read(b);end endend.end.(0)(0)jmpjmp 0 8 0 8 转向转向主程序入口主程序入口(1)(1)jmpjmp 0 2 0 2 转向转向过程过程p p入口入口(2)(2)intint 0 3 0 3 过程过程p p入口入口,为过程为过程p p开辟空间开辟空间(3)(3)lodlod
16、 1 1 3 3 取变量取变量b b的值到栈顶的值到栈顶(4)lit 0 10(4)lit 0 10 取常数取常数1010到栈顶到栈顶(5)(5)opropr 0 2 0 2 次栈顶与栈顶相加次栈顶与栈顶相加(6)(6)stosto 1 1 4 4 栈顶值送变量栈顶值送变量c c中中(7)(7)opropr 0 0 0 0 退栈并返回调用点退栈并返回调用点(16)(16)(8)(8)intint 0 5 0 5 主程序入口开辟主程序入口开辟5 5个栈空间个栈空间(9)(9)opropr 0 16 0 16 从命令行读入值置于栈顶从命令行读入值置于栈顶(10)(10)stosto 0 3 0 3
17、 将栈顶值存入变量将栈顶值存入变量b b中中(11)(11)lodlod 0 3 0 3 将变量将变量b b的值取至栈顶的值取至栈顶(12)lit 0 0 (12)lit 0 0 将常数值将常数值0 0进栈进栈(13)(13)opropr 0 9 0 9 次栈顶与栈顶是否不等次栈顶与栈顶是否不等(14)(14)jpcjpc 0 24 0 24 等时转等时转(24)(24)(条件不满足转条件不满足转)(15)(15)cal 0 2cal 0 2 调用过程调用过程p p(16)lit 0 2 (16)lit 0 2 常数值常数值2 2进栈进栈(17)(17)lodlod 0 0 4 4 将变量将变
18、量c c的值取至栈顶的值取至栈顶(18)(18)opropr 0 4 0 4 次栈顶与栈顶相乘次栈顶与栈顶相乘(2(2*c)c)(19)opr(19)opr 0 14 0 14 栈顶值输出至屏幕栈顶值输出至屏幕(20)(20)opropr 0 15 0 15 换行换行(21)(21)opropr 0 16 0 16 从命令行读取值到栈顶从命令行读取值到栈顶(22)(22)stosto 0 0 3 3 栈顶值送变量栈顶值送变量b b中中(23)(23)jmpjmp 0 11 0 11 无条件转到循环入口无条件转到循环入口(11)(11)(24)(24)opropr 0 0 0 0 结束退栈结束退
19、栈目标代码解释执行时数据栈的布目标代码解释执行时数据栈的布局(运行栈的存储分配)局(运行栈的存储分配)每个过程的每个过程的ARAR有有3 3个联系单元:个联系单元:SLSL:静态链静态链,指向,指向定义定义该过程的该过程的直接外过程直接外过程 (或主程序)运行时(或主程序)运行时最新最新数据段的基地址数据段的基地址。DLDL:动态链动态链,指向,指向调用调用该过程前正在运行过该过程前正在运行过 程的数据段基地址。程的数据段基地址。RARA:返回地址返回地址,记录调用该过程时,记录调用该过程时目标程序目标程序的的断点断点,即调用过程指令的下一条指令的地址。,即调用过程指令的下一条指令的地址。局部
20、变量中间结果 目标代码的解释执行目标代码的解释执行 运行栈运行栈S S M M调用过程调用过程P P RA RA DL DL SL SLb.ttbPM解决对非局部量的引用(存取)解决对非局部量的引用(存取)用用Display表表Display表表-嵌套层次显示表嵌套层次显示表当前激活过程的层次为当前激活过程的层次为K,它的,它的Display表含有表含有K+1个单元,依次存个单元,依次存放着现行层,直接外层放着现行层,直接外层直至最外层的每一过程的最新活动记录直至最外层的每一过程的最新活动记录的基地址的基地址例:例:program main(i,0);程序结构图程序结构图 proc R(c,d
21、);R end /*R*/proc P (a);主主 proc Q(b);P Q call R R(x,y);end /*Q*/call Q Q(z);call P end /*P*/call R P(W););R(U,V););end /*main*/用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R P 的的活动记录活动记录主程序的主程序的活动记录活动记录 d1d0displaysptop主程序的主程序的活动记录活动记录 d0spdisplaytop(1)(2)用用Display表的方案表的方案 主程序主程序-P-Q-RR 的的活动记录活动记录 Q 的的活动
22、记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 displayd2d1d0 d1d0 displaysptoptopsp(3)(4)DISPLAY表的维护和建立表的维护和建立 DISPLAY表表d 运行栈运行栈 0 主程活动记录地址主程活动记录地址 1 R活动记录地址活动记录地址 .0 老老 SP 1 返回地址返回地址 2 全局全局 DISPLAY地址地址 3 参数个数参数个数 4形式单元形式单元 .d DISPLAY .简单变量简单变量 数组内情向量数组内情向量 临时变量临时变量 当过程
23、的层次为当过程的层次为n,它的它的 display为为n+1个个值。值。一个过程被调用时,一个过程被调用时,从调用过程的从调用过程的DISPLAY表中自下向表中自下向上抄录上抄录n个个SP值,再加值,再加上本层的上本层的SP值。值。全局全局DISPLAY地址地址 分程序结构分程序结构Procedure A(m,n);integer m,n;B1:begin real z;array Bm:n;B2:begin real d,e;L3:2 end;B4:begin array C1:m;1 B5:begin real e;L6:5 4 end;end;L8:end;分程序结构的存储分程序结构的存
24、储分配方案分配方案 处理分程序结构存储分配方案的一种处理分程序结构存储分配方案的一种简单办法是,把分程序看成简单办法是,把分程序看成“无名无参过无名无参过 程程”,它在哪里定义就在哪里被调用。因,它在哪里定义就在哪里被调用。因此,可以把处理过程的存储办法应用到处此,可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。理分程序中。但这种做法是极为低效的。一则,每逢进入一则,每逢进入 一个分程序,就照样建立一个分程序,就照样建立连接数据和连接数据和DISPLAY表表,这是不必要的。这是不必要的。二则二则,当从内层分程序向外层转移时,可,当从内层分程序向外层转移时,可能同时要结束若干
25、个分程序。能同时要结束若干个分程序。按照过程处理办法,意味着必须一层按照过程处理办法,意味着必须一层一层地通过一层地通过“返回返回”来恢复所要到达的来恢复所要到达的那个分程序的数据区,但不能直接到达。那个分程序的数据区,但不能直接到达。例如:如果有一个从第例如:如果有一个从第5层分程序转出到达层分程序转出到达第第1层分程序的标号层分程序的标号L,虽然在第,虽然在第5层分程层分程序工作时知道序工作时知道L所属的层数,我们极易从所属的层数,我们极易从DISPLAY中获得第中获得第1层分程序的活动记层分程序的活动记录基址(录基址(SP),但是怎么知道第),但是怎么知道第1层分程层分程序进入时的序进入
展开阅读全文