软工班级课件桂浩编译原理第10章

1、第第10章章 目标程序目标程序运行时的运行时的存储组织存储组织 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 段结构段结构(Fortran)(Fortran)B 过程定义不嵌套，只允许过程递归调用过程定义不嵌套，只允许过程递归调用C 分程序结构分程序结构分程序嵌套分程序嵌套过程定义嵌套过程定

5、义嵌套 4 4存储类别的多少存储类别的多少GlobalStaticLocaldynamic术语术语 静态：如果一个名字的性质通过说明语句静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是或隐或显规则而定义，则称这种性质是“静态静态”确定的。确定的。 动态：如果名字的性质只有在程序运行时动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为才能知道，则称这种性质为“动态动态”确定确定的。的。 例例 procedure A(m,n:integer); begin real z; array Bm:n; begin end; end;数据表示各种数据对象的存储分配数据对象的

6、属性 name 名字，名称 type 类型 location 内存地址 value 值 component 成分 数据表示简单变量： char: 1 byteintegers: 2 or 4 bytesfloats: 4 to 16 bytesbooleans: 1 bit (but usually 1 byte)指针：unsigned integers一维数组：一块连续的存储区多维数组：一块连续的存储区，按行存放结构（记录）：把所有域（field)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储区，但方法（成员函数）不存在该对象里指令：目标程序运行时的存储组织目标程

7、序运行时的存储组织存储分配策略：存储分配策略： 简单的栈式分配方案简单的栈式分配方案 嵌套过程的栈式分配方案嵌套过程的栈式分配方案 分程序结构的存储分配方案分程序结构的存储分配方案 堆式存储堆式存储静态存储分配静态存储分配动态存储分配动态存储分配栈式栈式堆式堆式术语术语- -过程活动记录过程活动记录AR:为说明方便，假定为说明方便，假定源源程序是由过程组成，程序是由过程组成，运行时称作过程的激活。运行时称作过程的激活。一个过程的一次执行所需要的信息使用一个连续的存储区来一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区管理，这个区 （块）叫做一个活动记录（块）叫做一个活动记录AR

8、或或 frame帧帧一般这个段要记录：一般这个段要记录：l 临时值，如计算表达式时的中间工作单元。临时值，如计算表达式时的中间工作单元。l 局部变量局部变量（数据）（数据）l 保存运行过程前的状态保存运行过程前的状态 （返回地址，寄存器值（返回地址，寄存器值）l 存取链存取链（可选）（可选） 对于非局部量的引用。对于非局部量的引用。l 控制链控制链（可选）（可选） 指向调用者的活动记录，释放栈。指向调用者的活动记录，释放栈。l 实参实参（形式单元）（形式单元）l 返回值返回值（对函数）（对函数）（有时可使用寄存器存放返回值）（有时可使用寄存器存放返回值） 简单的栈式分配方案简单的栈式分配方案

9、程序结构特点程序结构特点:过程定义不嵌套，过程可过程定义不嵌套，过程可递归调用，含可变数组递归调用，含可变数组; 例例: main 全局变量的说明全局变量的说明 proc R end R; proc Q end Q; 主程序执行语句主程序执行语句 end mainMain-Q-R Main-Q-Q TOP- R 的活动记录的活动记录 Q 的活动记录的活动记录 SP- Q 的活动记录的活动记录 Q 的活动记录的活动记录 主程序全局主程序全局 主程序全局主程序全局 数据区数据区 数据区数据区TOP- 临时工作单元临时工作单元 局部简单变量局部简单变量 局部数组的内情向量局部数组的内情向量 保存运保

10、存运 行过程前的状态行过程前的状态（返回地址，寄存器值）（返回地址，寄存器值） 实参实参（形式单元）和参数个数（形式单元）和参数个数 SP- 控制链控制链（老（老 SP） TOP R 的数组区的数组区 SP R 的活动记录的活动记录 Q 的活动记录的活动记录 主程序全局主程序全局 数据区数据区 嵌套过程语言的栈式嵌套过程语言的栈式分配方案分配方案l主要特点主要特点： （语言）一个过程可以引用包围它的任（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，一外层过程所定义的标识符（如变量，数组或过程等）。数组或过程等）。 （实现）一个过程执行时可以引用它的（实现）一个过程执行时可以

11、引用它的任一外层过程的最新活动记录中的某些任一外层过程的最新活动记录中的某些数据。数据。 关键技术：解决对非局部量的引用（存关键技术：解决对非局部量的引用（存取）。取）。 设法跟踪每个外层过程的最新活动记录设法跟踪每个外层过程的最新活动记录AR的位置。的位置。 跟踪办法：跟踪办法： 1. 用静态链（如用静态链（如PL/0的的SL）。）。 2. 用嵌套层次显示表用嵌套层次显示表DISPLAY。const a=10;const a=10;var b,c;var b,c;procedure p;procedure p; beginbegin c:=b+a; c:=b+a; end; end;begi

12、nbegin 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) jmp 0 8 ( 0) jmp 0 8 转向转向主程序入口主程序入口( 1) jmp 0 2 ( 1) jmp 0 2 转向转向过程过程p p入口入口( 2)( 2) int 0 3int 0 3 过程过程p p入口入口, ,为过程为过程p p开辟空间开辟空间( 3) lod ( 3) lod 1 1 3 3 取变

13、量取变量b b的值到栈顶的值到栈顶( 4) lit 0 10 ( 4) lit 0 10 取常数取常数1010到栈顶到栈顶( 5) opr 0 2 ( 5) opr 0 2 次栈顶与栈顶相加次栈顶与栈顶相加( 6) sto ( 6) sto 1 1 4 4 栈顶值送变量栈顶值送变量c c中中( 7) ( 7) opr 0 0opr 0 0 退栈并返回调用点退栈并返回调用点(16)(16)( 8)( 8) int 0 5 int 0 5 主程序入口开辟主程序入口开辟5 5个栈空间个栈空间( 9) opr 0 16 ( 9) opr 0 16 从命令行读入值置于栈顶从命令行读入值置于栈顶(10)

14、sto 0 3 (10) sto 0 3 将栈顶值存入变量将栈顶值存入变量b b中中(11) lod 0 3 (11) lod 0 3 将变量将变量b b的值取至栈顶的值取至栈顶(12) lit 0 0 (12) lit 0 0 将常数值将常数值0 0进栈进栈(13) opr 0 9 (13) opr 0 9 次栈顶与栈顶是否不等次栈顶与栈顶是否不等(14) (14) jpc 0 24jpc 0 24 等时转等时转(24)(24)（条件不满足转条件不满足转）(15) (15) cal 0 2cal 0 2 调用过程调用过程p p(16) lit 0 2 (16) lit 0 2 常数值常数值2

15、 2进栈进栈(17) lod (17) lod 0 0 4 4 将变量将变量c c的值取至栈顶的值取至栈顶(18) opr 0 4 (18) opr 0 4 次栈顶与栈顶相乘次栈顶与栈顶相乘(2(2* *c)c)(19) opr 0 14 (19) opr 0 14 栈顶值输出至屏幕栈顶值输出至屏幕(20) opr 0 15 (20) opr 0 15 换行换行(21) opr 0 16 (21) opr 0 16 从命令行读取值到栈顶从命令行读取值到栈顶(22) sto (22) sto 0 0 3 3 栈顶值送变量栈顶值送变量b b中中(23) jmp 0 11 (23) jmp 0 11

16、 无条件转到循环入口无条件转到循环入口(11)(11)(24) opr 0 0 (24) opr 0 0 结束退栈结束退栈目标代码解释执行时数据栈的布目标代码解释执行时数据栈的布局（运行栈的存储分配）局（运行栈的存储分配）每个过程的每个过程的ARAR有有3 3个联系单元：个联系单元：SLSL： 静态链静态链，指向，指向定义定义该过程的该过程的直接外过程直接外过程 （或主程序）运行时（或主程序）运行时最新最新数据段的基地址数据段的基地址。DLDL： 动态链动态链，指向，指向调用调用该过程前正在运行过该过程前正在运行过 程的数据段基地址。程的数据段基地址。RARA： 返回地址返回地址，记录调用该过

17、程时，记录调用该过程时目标程序目标程序的的断点断点，即调用过程指令的下一条指令的地址。，即调用过程指令的下一条指令的地址。局部变量中间结果 目标代码的解释执行目标代码的解释执行 运行栈运行栈S S M M调用过程调用过程P P RA RA DL DL SL SLb. ttbPM解决对非局部量的引用（存取）解决对非局部量的引用（存取）用用Display表表Display表表-嵌套层次显示表嵌套层次显示表当前激活过程的层次为当前激活过程的层次为K，它的，它的Display表含有表含有K+1个单元，依次存个单元，依次存放着现行层，直接外层放着现行层，直接外层直至最外层的每一过程的最新活动记录直至最外

18、层的每一过程的最新活动记录的基地址的基地址例：例：program main(i,0); 程序结构图程序结构图 proc R(c,d); 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主程序的主程序的活动

19、记录活动记录 d0spdisplaytop（1）（2）用用Display表的方案表的方案 主程序主程序-P-Q-RR 的的活动记录活动记录 Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录Q 的的活动记录活动记录 P 的的活动记录活动记录主程序的主程序的活动记录活动记录 displayd2d1d0 d1d0 displaysptoptopsp（3）（4）DISPLAY表的维护和建立表的维护和建立 放在过程的活动记录中放在过程的活动记录中 Display表中条目的数目表中条目的数目 当过程的层次为当过程的层次为n，它的它的 display为为n+1个个值。值。

20、一个过程被调用时，一个过程被调用时，从调用过程的从调用过程的DISPLAY表中自下向表中自下向上抄录上抄录n个个SP值，再加值，再加上本层的上本层的SP值。值。全局全局DISPLAY地址地址栈式存储组织review 数据空间的存储管理：栈式存储分配 过程(函数)的活动记录：是一段连续的存储区，存放过程(函数)的一次执行所需要的信息。 过程(函数)活动记录的内容：联系单元（静态链,动态链和返回地址）、局部变量和临时变量栈式存储分配的实现： 设置两个指针：栈顶指针Top和当前活动记录指针SP； 调用一个过程(函数)前，先把过程(函数)的参数压入数据栈； 在数据栈中为过程(函数)的活动记录分配空间；

21、 填写联系单元内容； 执行过程(函数)代码； 过程(函数)返回前，根据当前SP恢复Top指针，根据动态链恢复SP为外层过程(函数)的活动记录起始地址，根据返回地址得到下一条指令地址； 继续执行外层过程(函数)代码。过程的活动记录(AR)CPL0临时工作单位局部变量机器状态信息存取链控制链实参返回地址过程R的活动记录过程Q的活动记录过程P的活动记录主程序全局数据区 分程序结构分程序结构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 C

22、1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:end; 分程序结构的存储分程序结构的存储分配方案分配方案 处理分程序结构存储分配方案的一种处理分程序结构存储分配方案的一种简单办法是，把分程序看成简单办法是，把分程序看成 “无名无参过无名无参过 程程”，它在哪里定义就在哪里被调用。因，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。理分程序中。但这种做法是极为低效的。 一则，每逢进入一则，每逢进入 一个分程序，就照样建立一个分程序，就照样建立连接数据和连接数据和D

23、ISPLAY表表,这是不必要的。这是不必要的。 二则二则 ，当从内层分程序向外层转移时，可，当从内层分程序向外层转移时，可能同时要结束若干个分程序。能同时要结束若干个分程序。 按照过程处理办法，意味着必须一层按照过程处理办法，意味着必须一层一层地通过一层地通过“返回返回” 来恢复所要到达的来恢复所要到达的那个分程序的数据区，但不能直接到达。那个分程序的数据区，但不能直接到达。例如：如果有一个从第例如：如果有一个从第5层分程序转出到达层分程序转出到达第第1层分程序的标号层分程序的标号L，虽然在第，虽然在第5层分程层分程序工作时知道序工作时知道L所属的层数，我们极易从所属的层数，我们极易从DISP

24、LAY中获得第中获得第1层分程序的活动记层分程序的活动记录基址（录基址（SP），但是怎么知道第），但是怎么知道第1层分程层分程序进入时的序进入时的TOP呢？唯一的办法是从呢？唯一的办法是从 5,4,3和和2各层顺序退出。但这种办法是很各层顺序退出。但这种办法是很浪费时间的。浪费时间的。 为了解决上述问题，可采取两种措施。为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己第一，对每个过程或分程序都建立有自己的栈顶指示器的栈顶指示器TOP，每个，每个TOP的值保存的值保存在各自活动记录中。这样，上述的第二在各自活动记录中。这样，上述的第二个问题便可解决。个问题便可解决。第二，不

25、把分程序看作第二，不把分程序看作“无参过程无参过程”，每，每个分程序享用包围它的那个最近过程的个分程序享用包围它的那个最近过程的DISPLAY。每个分程序都隶属于某个确。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所定的过程，分程序的层次是相对于它所属的那个过程进行编号的。属的那个过程进行编号的。： 每个过程被当作是每个过程被当作是0层分程序。而过程体层分程序。而过程体分程序（假定是一个分程序）当作是它分程序（假定是一个分程序）当作是它所管辖的第所管辖的第1层分程序。层分程序。这样，每个过程的活动记录所含的内容有：这样，每个过程的活动记录所含的内容有：1.过程的过程的TOP值，它指

26、向过程活动记录的值，它指向过程活动记录的栈顶位置。栈顶位置。2.连接数据，共四项：连接数据，共四项： （1)老老SP值；值；（2)返回地址；返回地址； (3)全局全局DISPAY地址；地址；（4)调用时的栈顶单元地址，老调用时的栈顶单元地址，老TOP。 3. 参数个数和形式单元参数个数和形式单元 4. DISPAY表。表。5. 过程所辖的各分程序的局部数据单元。过程所辖的各分程序的局部数据单元。 对于每个分程序来说，它们包括：对于每个分程序来说，它们包括：（1)分程序的分程序的TOP值。当进入分程序时它值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的含现行栈顶地址，以后，用来定义栈的新高

27、度（分程序的新高度（分程序的TOP值）；值）；（2)分程序的局部变量，分程序的局部变量， 数组内情向量和数组内情向量和临时工作单元。临时工作单元。 变 量 e B5 的 T O P 数 组 C 的 内 情 向 量 变 量 e 和 d B4 的 T O PB2的 TOP 数 组 B 的 内 情 向 量 变 量 zKB1 的 T O PDD I S P L A Y6形 式 单 元 m,n5参 数 个 数：24调 用 时 的 栈 顶 地 址（老 T O P）3全 局 D I S P L A Y 地 址2返 回 地 址1老 S P0过 程 的 T O P，指 向 活 动 记 录 之 顶 参数传递参数传

28、递(1)procedure exchangel(i,j:integer);(2) var x:integer;(3) begin;(4) x:=ai; ai:=aj; aj:=x(5) end; 带有非局部变量和形参的带有非局部变量和形参的PASCAL过程过程非局变量非局变量ai和和aj的的值进行交换，值进行交换，i,j为形参（在为形参（在这里是传值）这里是传值） (1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x,y:integer);(4) var temp:integer;(5) be

29、gin (6) temp:=x;(7) x:=y;(8) y:=temp(9) end;(10)begin(11) a:=1; b:=2;(12) swap(a,b);(13) writeln(a=,a);writeln(b=,b)(14)end. 带有过程带有过程swap的的PASCAL程序程序 传地址（变量参数）传地址（变量参数） 例如：过程例如：过程 swap(var x,y:integer); swap(a,b）；（）；（ a,b为为调用时的调用时的实参实参 ） 调用结果调用结果a,b的值被改变。的值被改变。 传值（值调用）传值（值调用）特点是对形式参数的任何运算不影响实参的值。特点是

30、对形式参数的任何运算不影响实参的值。 例如：过程例如：过程 swap(x,y:integer); swap(a,b）；）；其结果：其结果： a,b调用前的值不改变。调用前的值不改变。传值传值的实现的实现 1.形式参数当作过程的局部变量处理，即形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。的形式单元（用以存放实参）。 2.调用过程计算实参的值，并将其放在对调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。应形式单元开辟的空间中。 3.被调

31、用过程执行时，就像使用局部变量被调用过程执行时，就像使用局部变量一样使用这些形式单元。一样使用这些形式单元。procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 调用swap(a,b) 过程将不会影响a和b的值。 其结果等价于执行下列运算： x :=a； y :=b； temp :=x； x :=y； y :=temp传地址传地址的实现的实现（call- by- reference )(call-by-address)(call-by-location) 把实在参数的地址传递给相应的形

32、参，即把实在参数的地址传递给相应的形参，即 调用过程把一个指向实参的存储地址的指针传调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：递给被调用过程相应的形参：1实在参数是一个名字，或具有左值的表达式实在参数是一个名字，或具有左值的表达式-传递左值传递左值2实在参数是无左值的表达式实在参数是无左值的表达式-计算值，放入一计算值，放入一存储单元，传此存储单元地址存储单元，传此存储单元地址3目标代码中，被调用过程对形参的引用变成对目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用传递给被调用过程的指针的间接引用procedure swap( x,y:integer); var temp:integer;