编译原理（王晓斌）第十三章.ppt

程序设计语言与编译 第十二章第十二章 运行时存储空间的组织运行时存储空间的组织 电子科技大学计算机科学与工程学院 要执行和实现目标程序，需要一个运行环境来 支持，要对程序中的变量进行存储分配，并提 供各种运行信息。 因此， 本章主要讨论: 运行时存储空间的组织 程序设计语言与编译 电子科技大学计算机科学与工程学院 第一节 程序的存储空间 程序投入运行的必要条件： 1.一组可运行的代码 2.一个运行环境 分配空间: 变量、临时变量、数组、单元 提供运行信息：返回地址、主调过程的存储区 程序设计语言与编译 电子科技大学计算机科学与工程学院 ip 代码存储器（代码存储器（C C ） 数据存储器（数据存储器（D D ） 假定当前指令指针ip的 值为i,则当前指令的存 储地址用Ci表示 一、代码空间 线性存放着目标指令序列 在GAM中, 当前执行的指令位置由指令指针ip指示 程序设计语言与编译 电子科技大学计算机科学与工程学院 二、数据空间 编译程序给源程序中的各种类型的变量和常数分配 的存诸空间，称为程序的数据空间。 ip 代码存储器（代码存储器（C C ） 数据存储器（数据存储器（D D ） 若某个变量分配在D的i个 单元，则用Di表示该变 量的存诸位置（地址） 数据空间在运行时是可 以改变的，即动态的 程序设计语言与编译 电子科技大学计算机科学与工程学院 (1)内容: 变量、常数、控制和管理信息、描述符等 (2)静态分配: 在运行前就可确定数据空间的大小 在编译时刻就能进行的存储分配 (3)动态分配: 运行时才能进行的存储分配 栈分配: 因变量生存期的嵌套性 堆分配: 因生存期的随机交叉特性 程序设计语言与编译 电子科技大学计算机科学与工程学院 临时变量 返回指针 动态链接 静态链接 现场保护 参数个数 参数单元 局部变量 被调用单元返回时的地址 指向调用单元最新活动记录的指针 指向被调用单元直接外层的 最新活动记录的指针 保存调用时的机器状态 调用单元向被调用单元传递 的单元个数 为形式参数分配的存储单元 为局部变量分配的存储单元 为临时变量分配的存储单元 三、活动记录 一个程序单元的一次激活所需的信息管理是通过相 应的活动记录来实施的。一个单元的每次激活，都 应建立相应的活动记录，它是单元实例的一部分。 程序设计语言与编译 除了变量存储区外, 其余部分存储长度编译 时可以确定, 则元素i的地址可用下式计算 D+offset(i) 其中, offset(i)是i在活动记录中的位移; D 是活动记录的首地址 活动记录的特点 电子科技大学计算机科学与工程学院 程序设计语言与编译 四、变量的存储分配 条件是: 语言允许递归调用 1. 静态变量: 不管在程序单元的哪一次活动中, 均绑定于相同的存储位置 条件是: 活动记录, 变量的存储位置在编译时可以确定 2. 半静态变量: 编译时确定相对位置, 单元被激活后, x绑定于D+Offset(x) 电子科技大学计算机科学与工程学院 程序设计语言与编译 3. 半动态变量: 动态数组 编译时在活动记录中建立描述符 例: 1m int a; 1n int b; 4. 动态变量: 动态分配 编译时在活动记录中为动态变量设置二个指针 , 一个指向该变量的描述符, 另一个指向该变 量的存储空间 电子科技大学计算机科学与工程学院 程序设计语言与编译 五、存储分配模式 1. 静态分配 只允许静态变量, 变量与存储区域的绑定关系 在编译时便可建立, 并完成存储分配。 不允许递归调用, 不允许动态数组, 不允许动 态类型的数据对象, 即不允许有非静态变量。 如: FORTRAN语言。 电子科技大学计算机科学与工程学院 程序设计语言与编译 2. 栈式分配 各单元之间的调用关系遵循“后进先出”模式 活动记录的建立和撤消也满足“后进先出”模式 用栈分配活动记录 分配方法: 当激活一个程序单元时, 其活动记 录就动态地分配于栈顶。 电子科技大学计算机科学与工程学院 程序设计语言与编译 R的活动记录 Q的活动记录 P的活动记录 如：P调用Q，Q调用R . 电子科技大学计算机科学与工程学院 程序设计语言与编译 3. 堆分配 由于动态变量表示的数据对象, 它的长度、个数都有 可能在执行中改变, 即在其生存期中动态改变, 就不 可能在栈上为这样的对象作分配。 出现下列情况时, 必须用堆式分配: (1)单元活动结束后, 局部变量的值还需保留 ; (2)调用单元与被调用单元的生存期不满足嵌 套关系, 即出现交叉现象。 电子科技大学计算机科学与工程学院 程序设计语言与编译 代码 静态数据 栈 堆 存储空间的组织 电子科技大学计算机科学与工程学院 程序设计语言与编译 第五节第五节 参数传递参数传递 先看例子: procedure swap (a , b : integer); var temp : integer; begin temp := a; a := b; b := temp end; call swap(x, y); . 形式参数 实在参数 程序设计语言与编译 1. 程序单元间通信方式有非局部环境和参数传递 2. 参数，形参，实参 3. 参数传递的三种类型： 数据参数传递 过程参数传递 类型参数传递 几点说明: 程序设计语言与编译 以调用 swap ( i , ai )为例，且调用前 i = 3 a 的几个元素分别为7，1，4，5，8 程序设计语言与编译 1.引用调用（传地址） 在单元中对形参的引用，实际上是对形式单元中实参 地址的间接引用 将实参的地址传递给相应的形参 程序设计语言与编译 swap(i,ai); 相当于执行: a:=i的地址; b:=a3的地址; temp:=a; (temp=3) a:=b; (i=4) b:=temp; (a3=temp=3) 执行结果: i=4, a3=3 程序设计语言与编译 2.值调用 形参只起局部变量作用 (1)传值:实参的值形式单元 (2)结果调用:形参的结果值实参单元 (3)传值得结果：实参的值形式单元 形参的结果值实参单元 实现技术：一个形参对应两个单元 程序设计语言与编译 对“传值得结果” swap(i,ai); 相当于执行: a1:=i的地址; a2:=3; b1:=a3的地址; b2:=4; temp:=a2; (temp=a2=3) a2:=b2; (a2=b2=4) b2:=temp; (b2=temp=3) a1:=a2; (i=a2=4) b1:=b2; (a3=b2=3) 执行结果: i=4, a3=3 程序设计语言与编译 3.名调用 用实参原样替换形参的出现 若被调用单元中的局部名与调用处的名发生冲突，则 对局部名重新命名 实现技术：把实参处理成一个子程序（thunk, 称为 参数子程序），对形参的每次引用就调用该子程序 程序设计语言与编译 swap(i,ai); 相当于执行: temp:=i; (temp=i=3) i:=ai; (i=a3=4) ai:=temp; (ai=a4=temp=3) 执行结果: i=4, a4=3 (a3不变) 程序设计语言与编译 练习 program main; var a,b: integer; procedure P(x,y,z) begin y := y + 1; z := z+x; end begin a := 2; b := 3; P(a+b, a , a); Write(a, b); End. 对引址调用、传值和名调用 三种参数传递方式，打印的 a, b的值分别是什么 程序设计语言与编译 电子科技大学计算机科学与工程学院* 早期的FORTRAN语言是典型的静态语言，它具有如下特点 ： 不允许过程的递归调用； 无动态数组和动态类型； 程序无嵌套层次结构； 以早期的FORTRAN为例进行静态分配。 ip 代码存储器代码存储器数据存储器数据存储器 单元n代码段 单元2代码段 单元1代码段 全局数据活动记录 单元n活动记录 单元2活动记录 单元1活动记录 第二节 静态分配 程序设计语言与编译 电子科技大学计算机科学与工程学院* INTEGER I, J COMMON I CALL X GOTO 10 10 CONTINUE END SUBROUTINE X INTEGER K , J COMMON I K = 5 I = 6 J = I + K RETURN END 以下面的FORTRAN程序说明静态分配 主程序 子程序 调用子过程X 空语句 返回语句 程序设计语言与编译 电子科技大学计算机科学与工程学院* 经过词法及语法分析生成如下描述符(表格) (MAIN,0)INTJ (COMMON,0 ) INTI 地址类型名字 主程序主程序MAINMAIN的符号表的符号表 C(MAIN,3)10 地址标号 标号表标号表 (X,0)X (MAIN,0)MAIN 地址名字 单元名表单元名表 (X,2)INTJ (COMMON,0 ) INTI (X,1)INTK 地址类型名字 子程序子程序X X的符号表的符号表 (COMMON,0)INTI 地址类型名字 公用区公用区COMMONCOMMON的符号表的符号表 (i,j)表示程序单元i的活动记录中 偏移为j的位置；公用区和主程序从 0开始分配，子程序从1开始分配 MAIN的第三条指令 程序设计语言与编译 电子科技大学计算机科学与工程学院 活动记录 程序的目标模块 JI J K 返回地址 MAINMAIN的活动记录的活动记录 X X的活动记录的活动记录 COMMONCOMMON的活动记录的活动记录 000 1 2 4 3 2 1 0 halt noop ip:= E call F; F call G; G call F; . 程序设计语言与编译 4.CALL P 的处理 返回地址 动态连接 返回地址 动态连接 A的活动记录 即将建立的 P的活动记录 current free A CALL p 程序设计语言与编译 (1)保存返回地址 D free := ？ (2)保存主调过程的current Dfree + 1 := current (3)建立P的current current := free (4)调整free free := free + L (5)转子 ip := P的代码段首地址 CALL P 程序设计语言与编译 返回地址 动态链 返回地址 动态链 A的活动记录 P的活动记录 current free 进入过程P以后 程序设计语言与编译 5.RETURN语句的处理 (1)恢复free free := current (2)恢复主调过程的current current := Dcurrent + 1 (3)返回 ip := D free 程序设计语言与编译 二、半动态变量的栈式分配 1. 活动记录内容 临时变量 返回指针 动态链接 静态链接 现场保护 参数个数 形式单元 局部变量 数组存储区 允许动态数组 程序设计语言与编译 2. 动态数组空间的分配 （1)编译时，分配内情向量表区，并产生在运行时 动态建立内情向量和分配数组空间的指令。 (2)一个单元激活后（进入该单元），遇到动态数组说 明时，调用上述指令（填内情向量，分配数组空间） ，并调整free := free + L 程序设计语言与编译 非局部环境的引用必须考虑变量的作用域 1. 静态作用域规则最近嵌套规则 最外层单元为0层，若P是Q的直接外层， 则Q的层次 = P的层次 1 (1)嵌套的层次 三、允许过程嵌套定义的栈式分配 非局部环境引用规则 程序设计语言与编译 unit A; y: int; unit B; end B; y: int; unit C; end D; end C; . unit D; . end E; z: int; unit F; end G; unit G; x,y: int; . . unit E; z:=x+y; end F; . end A; x: int; A B C D E FG 程序设计语言与编译 (2)最近嵌套规则 (I)变量x在单元U1中被说明，则x的作用 域局部于U1，或称x在U1中是可见的 (II)变量x在U1中没有被说明，则x的作用域 是包围U1的说明了x的最小外层单元 程序设计语言与编译 2.动态作用域规则 最近活动规则 对非局部变量的引用：最近外层中说明的 动态作用域的最近外层：指的是动态调用外层 如A-E-F-G-F的调用序列：当前F的调用外层为G 程序设计语言与编译 对非局部环境的引用 1. 静态作用域规则 对非局部变量，引用的应是最近 的“嵌套外层”中说明的变量 静态连接 ： 指向嵌套直接外层的最新活动记 录的指针，它处于活动记录位移 为2的存储单元中 静态链 ： 各嵌套程序单元的活动记录 中，静态连接的序列构成一 个静态链 （1）静态连接和静态莲 程序设计语言与编译 返回地址 动态链 current free 静态链 CALL P 程序设计语言与编译 内容回顾 1.静态分配 2.栈式分配 3.堆分配 变量与存储区域的绑定关系在编译时便可 建立，并完成存储分配 当一个程序单元被激活时, 在栈顶分配 其活动记录；当程序单元退出时，在栈 顶将其活动记录撤销 动态变量的首地址、长度、类型等 在编译时无法确定，在执行过程中 也可能改变 程序设计语言与编译 内容回顾 1.静态分配 2.栈式分配 3.堆分配 分配方式 递归调用 动态数组 过程嵌套定义 只含半静态变量的栈式分配 返回地址current free 动态链接 。 CALL P D free := IP+5 Dfree + 1 := current current := free free := free + L ip := P的代码段首地址 free := current current := Dcurrent + 1 ip := D free return 程序设计语言与编译 内容回顾 允许过程嵌套定义的栈式分配 静态作用域规则 动态作用域规则 返回地址 动态链接 current free 静态链接 程序设计语言与编译 D free := ip+5 Dfree + 1 := current free := free + L ip := P的代码段首地址 CALL P current := free 保存静态链接：Dfree + 2 := ？ 程序设计语言与编译 (2)非局部变量x的地址的求法 假设单元p中引用了单元t中的变量x， 且p ,t的深度分别为np, nt ，记： d = np nt Dt为t的最新活动记录的首地址 程序设计语言与编译 np