运行环境RunTimeEnvironm

《运行环境RunTimeEnvironm》由会员分享，可在线阅读，更多相关《运行环境RunTimeEnvironm（50页珍藏版）》请在装配图网上搜索。

1、第 8章 运行环境 (Run-Time Environments) 主要内容 绑定（ Binding） 存储 (Storage)组织 (Organization)与分配 (Allocation) 参数 (Parameter)传递 (Passing) 过程说明与调用 符号表 (Symbol Table)管理 8.1 绑定（ Binding） Binding的概念 将符号名和相应目标数据 (的地址 )对应起来 标识符与数据目标的对应 变量名 数据存储单元地址 过程名 、 函数名 程序段入口地址 相关问题 变量和过程的作用域 ， 决定绑定的有效期 分段式程序 Program layer Int a,

2、b,c Begin Sub(a+b,b,a) End Subroutine Sub(x,y,z) Real a,b,c Begin End 嵌套式程序 Program layer Int a,b,c Procedure Sub1(x,y,z) Int x,y,z Procedure add(a,b) Real a,b Begin Real x,y,z x=a y=x*2+b z=1/y End Begin End Procedure Sub2(x,y) Begin end 绑定的时机与策略 语言定义的标识符的生存期决定最 终绑定的时机 全局变量：全程有效 程序装入时 局部变量：分段有效 进入过

3、程或分 程序时 变量名的绑定 静态 (Static)绑定：编译时指定 （ 相对地址 ） 词法分析期间 在符号表中建立变量的表项 回忆：说明语句的语义分析：字节数计算 ， 填写变 量地址 动态 (Dynamic)绑定：运行时指定 （ 具体地址 / 相对地址 ） 如：动态数组 过程 /函数名的绑定 为过程指定程序代码段入口地址 静态绑定：编译时指定相对地址 （ 词法分析：在符号表中建立过程的表项 ） 语义分析：构造目标代码 ， 填写过程的入口地址 如：一般的函数 、 子例程 动态绑定 运行时指定 函数名作为形式参数 （ formals） 如：函数指针 、 虚函数 （ C+） 8.2 存储组织与分配

4、 (P257) 运行时刻的内存划分 (Partition) 局部数据的静态分配 (Static Allocation) 局部数据的动态分配 (Dynamic Allocation) 层次单元法 栈式 (Stack)存储分配策略 堆式 (Heap)存储分配策略 运行时刻的内存划分 代码段 全局静态数据 栈 堆 局部数据区中的一个栈单元 活动记录 (静态 /动态分配 ) 数组区 临时工作单元区 简单变量区 形式单元区 寄存器保护区 返回地址 静态存储分配 特点 编译时刻确定存储位置 访问效率高 主要用途 子程序的目标代码段 全局数据目标 （ 全局变量 ） ？ 用什么样的算法实现静态存储分配 静态存

5、储分配策略介绍 顺序分配算法 按照程序段出现的先后顺序逐段分配 1/22 2/15 3/18 4/17 6/10 5/23 程序段 区域 1 021 2 2236 3 3754 4 5571 5 7294 6 95104 共需要 105个存储单元 程序段之间的调用关系 程序段号 /所需数据空间 能用更少的空间么？ 分层分配算法 允许程序段之间的覆盖（覆盖可能性分析） 程序段 区域 6 09 5 022 4 016 3 2340 2 1731 1 4162 共需要 63个存储单元 1/22 2/15 3/18 4/17 6/10 5/23 思考：如何设计分配算法？ 7/80 静态存储分配无法克服

6、的问题 1 动态数组问题 层次单元法 层次单元 标准单元的使用 P4 嵌套式程序 program layer int a,b,c procedure Sub1(x,y,z) int x,y,z procedure add(a,b) real a,b begin Real x,y,z x=a y=x*2+b z=1/y end begin end procedure Sub2(x,y) begin sub1(a1,a2,a3) end P P3 P2 P 1 begin real x,y,z x=a y=x*2+b z=1/y begin int a,b,c begin char name,fr

7、om,a end end Sub2(x,y) end S1 S2 P 静态存储分配无法克服的问题 2 递归调用问题 栈式存储分配 栈 （ Stack） 式存储分配 用途 过程的局部环境 活动记录 特点 嵌套调用次序 先进后出 生存期限于本次调用 自动释放 活动记录 活动记录 活动记录 运行栈 过程数据 区结构 SPn SPn-1 SP1 SP0 数组存储区 本 过 程 所 辖 分 第 临时工作单元 程 一 序 层 局部数组说明 存 分 储 程 局部变量 区 序 分程序 TOP 本过程 Display 形式单元（ m+1个） 连 主调分程序 TOP 接 全局 Display地址 数 返回地址 据

8、 主调过程 SP 本过程 TOP SP SPn为第 n 层过程数 据区首址 静态存储分配无法克服的问题 3 被调用者的生存期超过调用者 /局部数据需 要保留（ save ） 堆式存储分配 堆 （ Heap） 式存储分配 用于动态数据结构 存储空间的动态分配和释放 实现方法： 将内存空间分为若干块 ， 根据用户要求分配 无法满足时 ， 调用无用单元收集程序将被释 放的块收集起来重新分配 8.3 参数传递 传值调用 call-by-value 过程调用时计算实参 (Actual)， 将值存到活动记录 形参 (Formal)绑定于活动记录的实参域 调用者 被调用者 直接使用 A 实际参数 A 形式参

9、数 X A的值 单向传值 引用调用 Call-by-Reference/Address 如果实在参数具有左值 ， 则存放其左值到活动记 录中；否则计算出表达式的值 ， 将此值存入一个 单元 ， 并将该单元的地址传给被调用者 。 调用者 被调用者间址访问实参 A A 实参 A 形参 X A的地址 传地址 复制恢复 Copy-Restore 将参数的左、右值同时传给被调用者， 被调用者直接使用右值，并将计算结果 按照左值返回给调用者 调用者 被调用者 A 实际参数 A 形式参数 X A的值 传值 /传地址 A的地址 传名调用 Call-by-Name 将被调过程的过程体复制到调用处，并 将每一个形

10、参 “ 文字地 ” 替换成实参 用换名子程序实现 Thunk 是一种早期的语言 ALGOL用的一种参数 传递方式 上次课主要内容 回填技术 S if C then S 1 的 翻译 C.true := newlabel; S1.next := S.next; C.false:= S.next; S.code := C.code |gen( C.true: ) |S1.code C.code S1.begin C.true S.next S1.code C.false 上次课主要内容 S if C then S 1 else S2 的 翻译 C.true := newlabel; C.false

11、 := newlabel; S1.next := S2.next := S.next; S.code := C.code | gen( C.true: )| S1.code | gen( goto S.next ) | gen( C.false: ) | S2.code C.code S1.begin C.true S.next S1.code C.false goto S.next S2.code 上次课主要内容 S while C do S 1翻译 S.begin := S1.next := newlabel; C.true := S1.begin := newlabel; C.false

12、 := S.next; S.code := gen( S.begin: ) | C.code | gen( C.true: ) | S1.code | gen( gotoS.begin ) C.code S1.code goto S.begin C.true S1.begin C.false S.next S.begin 上次课主要内容 运行环境 绑定：静态、动态 静态分配 动态分配 层次单元法 栈式 (Stack)存储分配策略 堆式 (Heap)存储分配策略 上次课主要内容 参数传递 传值调用 call-by-value 引用调用 Call-by-Reference/Address 复制恢复

13、 Copy-Restore 传名调用 Call-by-Name 子程序 P(X,Y,Z); Y:=Y+1; Z:=Z+X 传值调用： 2 传地址： X=T=5,Y=Z=A=2 A:=A+1=2+1 A:=A+T=3+5 8 复制恢复： X=T=5,Y=Z=A=2 Y:=Y+1=3 Z:=Z+X=2+5=7 Y A=3 Z A=7 7 换名 A:=A+1=3 A:=A+A+B=3+3+3 9 主程序 A:=2; B:=3; P(A+B, A, A); Print A 临时单元 : T:A+B=5 8.4 过程调用 过程 (procedure) 子程序 (subroutine)、函数 (funct

14、ion) 过程的定义与调用 形参和实参的结合：参数计算与传递 调用与返回 工作方式 调用方：当前环境的保存与恢复 被调方：构造环境，参数绑定 Main( ) Sub1( 10 ) Sub1( x ) Sub2( x + 1 ) Sub2( y ) Sub3( ) 过程调用实现 简单过程调用 实在参数的计算和保存 控制转移 、 返回地址的保存 实在参数和形式参数的结合 (多种结合方式 ) 局部变量的处理 返回值的处理 递归过程调用与过程参数 每层过程调用信息的保存与相应信息的查找 活动记录中过程所用信息 用于表达式的计算 局部数据 寄存器 、 程序计数器 （ 返回地址 ） 保存实在参数的值或地址

15、 存放返回值 保存调用者活动记录地址等 (SP) 用于存取嵌套外层过程中的非局部名 (Display) 访问链 控制链 返回值 实在参数 机器状态 局部变量 临时变量 例子 函数的活动记录 int sub( i, p ) int i; char *p; char buf32; bufi = *(p + i); return i + 1; 临时变量 : t1,t2,t3 局部变量 ： buf32 机器状态 ： R0, , R9, SP, PC, PS 参数 ： i, p 返回值 控制链 Display 过程说明语句的翻译 分析参数的类型 、 分配地址 统计参数和返回值的空间需求 与调用语句配合完

16、成形 /实参数的结合 符号表处理 完成过程名的属性登记 说明语句 ： Procedure id(X1,X2,X n) 过程说明语句代码结构 说明语句 ： Procedure id(X1,X2,X n) 代码结构 X1.code 按参数传递要求实现参数 X1的传递，或者完成传递准备 ； X2.code 按参数传递要求实现参数 X2的传递，或者完成传递准备 ； Xn.code 按参数传递要求实现参数 Xn的传递，或者完成传递准备 ； 完成动态存储分配相关的工作； 进入过程体 过程调用语句的代码结构 过程调用语句 id(E1,E2, ,En) E1.code a1:=E1.place En.code

17、 an:=En.place 动态存储分配相关工作 goto pc+n+1 param a1 param an call id.place， n 需要一个队列存放 a1, a2, , an，以生成 过程调用的实现 1) 在过程 f 中调用过程 p 时 a. f 对实在参数求值 ， 将结果存入 p 的 活动记录参数域 b. 在 p 的活动记录中存放返回地址和当 前栈顶指针 c. 按照活动记录的大小 ， 上移栈顶指针 d. 控制转到 p 的入口 （ 过程体 ） 临时变量 局部变量 机器状态 参数 返回值 控制链 Display e. p 存放寄存器值和其它状态 信息 f. 执行过程体 2. 从过程

18、p 返回：对应 return 语句 a. p 在返回值域中保存返回值 b. 恢复原栈顶指针和其它寄存 器 c. 按返回地址返回调用者 临时变量 局部变量 机器状态 参数 返回值 控制链 Display 过程调用语句的制导翻译定义 产生式 语义规则 S call id ( Elist ) S.code := Elist.code |gen(goto pc+Elist.num+1)| for 队列 q中的每一项 t do gen(param t ) | gen(call id.place,Elist.num) Elist E Elist.num := 1; Elist.code := E.code

19、 | t:=newtemp; gen(t:= E.place)； 建立队列 q， 并将 t 放入 q Elist Elist 1,E Elist.num := Elist 1.num+1; Elist.code := Elist 1.code | E.code | t:=newtemp; gen(t:= E.place);将 t 放入队列 q 生成的目标代码 t1 := 3 + a goto pc+3 param t1 param 6 call f, 2 函数调用 f(3+a,6)的翻译 函数调用 f(b*c-1,x+y,x,y)的翻译 t1:=b*c t2:=t1-1 t3:=x+y got

20、o pc+5 param t2 param t3 param x param y call f, 4 赋值语句 x:=a+b+ f(b*c-1,x+y,x,y)的翻译 t1:=a+b t2:=b*c t3:=t1-1 t4:=x+y goto pc+5 param t3 param t4 param x param y call f.place, 4 t5:=t1+f.val x:=t5 8.4 符号表管理 种类 关键字表 、 层次表 、 符号表 （ 过程表 、 变量表 、 标号表 ） 、 常数表 名字 信息 1 信息 n sum1 Real 定义 关键字表 表项结构 关键字标识 (整数 )

21、关键字名字 (字符串，如 while， if) 常用的操作： int IsKeyword( char Name ) 关键字名字 关键字标识 begin 112 end 113 while 114 层次表 保存各级分程序 、 循环语句 、 条件 语句的有关信息 如：局部名字 、 转移标号等 辅助实现标识符的管理 标识符的作用域 所在层 性质 起点 终点 直接外层 本层计数 符号表 保存名字及其属性 名字：变量名，过程名，标号名和常数名 属性：种类（ Kind），类型（ Type），长度，作用 域，标志（引用 /定义），地址等 种类：简单变量 、 数组 、 记录 、 结构 、 函数 、 常数 、

22、常量 类型：整 、 实 、 复 、 布尔 、 字符 、 指针 、 标号 名字 种类 类型 长度 地址 标志 符号表的作用 作用 记录源程序中出现的各种符号的相关属性，为 编译提供相应的信息：地址、类型 建立表项 以标识符为关键字 符号表的实现 实现方法： 线性表、散列表（ Hash）、二叉树 特殊问题 结构成员、函数参数、分程序结构 性能 优先考虑查找的效率 思考题 1 试分别给出下列语句的三地址码，并希望 你能讲清楚是如何转换出来的。 call sub(a+5,b*a,c) a+fun(a+5,b*a,c) 2 什么叫静态绑定？什么叫动态绑定？变 量的绑定和过程的绑定有什么区别？ 3 程序的执行过程中如何进行存储分配？ 何时为哪些数据目标分配存储空间？