本 章 主 要 内 容 运 行 时 环 境 (Runtime Environment) 目 标 程 序 运 行 时 的 活 动 运 行 存 储 的 划 分 静 态 存 储 分 配 栈 式 存 储 分 配 堆 式 动 态 存 储 分 配 LI L. 1 运 行 时 环 境 变 量 名 的 绑 定 完 全 静 态 环 境 FORTRAN 基 于 栈 的 环 境 C C++ Pascal JavaC++ 完 全 动 态 环 境 LISP 静 态 绑 定 : 编 译 时 指 定 ( 相 对 地 址 ) 词 法 分 析 期 间 在 符 号 表 中 建 立 变 量 的 表 项 说 明 语 句 的 语 义 分 析 : 字 节 数 的 计 算, 填 写 变 量 地 址 动 态 绑 定 : 运 行 时 指 定 ( 具 体 地 址 / 相 对 地 址 ) 如 : 动 态 数 组 编 译 技 术 及 应 用 李 莉 1
过 程 / 函 数 名 的 绑 定 过 程 调 用 为 过 程 指 定 程 序 代 码 段 入 口 地 址 静 态 绑 定 : 编 译 时 指 定 相 对 地 址 语 义 分 析 : 构 造 目 标 代 码, 填 写 过 程 的 入 口 地 址 如 : 一 般 的 函 数 子 例 程 动 态 绑 定 运 行 时 指 定 函 数 名 作 为 形 式 参 数 如 : 函 数 指 针 虚 函 数 过 程 的 定 义 与 调 用 形 参 和 实 参 的 结 合 : 参 数 计 算 和 传 递 调 用 和 返 回 工 作 方 式 调 用 方 : 当 前 环 境 的 保 存 与 恢 复 被 调 用 方 : 构 造 环 境, 参 数 绑 定 目 标 程 序 运 行 时 的 活 动 过 程 调 用 过 程 定 义 是 一 个 声 明 过 程 名 + 过 程 体 当 过 程 名 出 现 在 可 执 行 语 句 中, 则 称 过 程 在 该 点 被 调 用 形 参 和 实 参 过 程 体 的 每 一 次 执 行 称 为 该 过 程 的 一 个 活 动 一 个 活 动 的 生 存 期 递 归 的 过 程 简 单 过 程 调 用 实 参 的 计 算 和 保 存 控 制 转 移 的 保 存 实 参 和 形 参 的 结 合 局 部 变 量 的 处 理 返 回 值 的 处 理 递 归 过 程 调 用 与 过 程 参 数 每 层 过 程 调 用 信 息 的 保 存 与 相 应 信 息 的 查 找 编 译 技 术 及 应 用 李 莉 2
运 行 时 存 储 器 的 划 分 运 行 时 存 储 器 的 划 分 编 译 器 为 目 标 程 序 分 配 存 储 空 间 以 存 储 生 成 的 目 标 代 码 数 据 对 象 和 跟 踪 过 程 活 动 的 控 制 栈 目 标 代 码 静 态 数 据 栈 堆 管 理 过 程 的 活 动 栈 和 堆 可 以 随 程 序 运 行 动 态 改 变 存 放 动 态 的 数 据 临 时 变 量 局 部 变 量 机 器 状 态 实 参 静 态 链 动 态 链 返 回 值 目 标 代 码 静 态 数 据 栈 堆 局 部 数 据 区 的 一 个 栈 单 元 活 动 记 录 活 动 记 录 表 示 一 次 执 行 活 动 中 的 相 关 信 息 活 动 记 录 完 全 静 态 运 行 时 环 境 连 接 数 据 临 时 变 量 局 部 变 量 机 器 状 态 实 参 静 态 链 动 态 链 返 回 值 用 于 表 达 式 的 计 算 局 部 数 据 寄 存 器 程 序 计 数 器 ( ) 保 存 实 参 的 值 用 于 存 取 非 局 部 数 据 保 存 调 用 者 活 动 记 录 地 址 等 存 放 返 回 值 编 译 时 对 所 有 数 据 对 象 分 配 固 定 的 存 储 单 元, 且 在 运 行 时 始 终 不 变 在 编 译 时 就 能 确 定 一 个 程 序 在 运 行 时 所 需 要 的 存 储 空 间 的 大 小, 并 分 配 目 标 程 序 运 行 时 需 要 的 全 部 存 储 空 间 编 译 技 术 及 应 用 李 莉 3
完 全 静 态 运 行 时 环 境 静 态 存 储 分 配 主 程 序 的 代 码 过 程 1 的 代 码 过 程 n 的 代 码 全 局 数 据 区 域 主 过 程 的 活 动 记 录 过 程 1 的 代 码 过 程 n 的 代 码 代 码 区 域 数 据 区 域 特 点 编 译 时 确 定 存 储 位 置 访 问 效 率 高 主 要 用 途 子 程 序 的 目 标 代 码 段 全 局 数 据 目 标 ( 全 局 变 量 ) 静 态 存 储 分 配 栈 式 存 储 分 配 无 法 克 服 的 问 题 数 据 对 象 的 长 度 和 它 在 内 存 中 位 置 的 约 束 在 编 译 时 必 须 知 道 数 据 结 构 不 能 动 态 建 立 ( 动 态 数 组 ) 不 允 许 递 归 调 用 将 存 储 组 成 一 个 栈, 运 行 时, 每 当 进 入 一 个 过 程 ( 一 个 新 的 活 动 开 始 ) 时, 就 把 它 的 活 动 记 录 压 入 栈 中, 形 成 当 前 工 作 的 数 据 区 一 个 过 程 的 活 动 记 录 的 体 积 在 编 译 时 是 可 静 态 确 定 的 当 活 动 结 束 ( 过 程 退 出 ) 时, 再 将 它 的 活 动 记 录 弹 出 栈 编 译 技 术 及 应 用 李 莉 4
全 局 数 据 说 明 Main() Main 中 的 数 据 说 明 Q; Void R( ) R 中 的 数 据 说 明 Void Q( ) Q 中 的 数 据 说 明 R; 栈 式 存 储 分 配 SP TOP 全 局 数 据 区 Main 的 活 动 记 录 Q 的 活 动 记 录 R 的 活 动 记 录 #include <stdio.h> int x, y; int gcd(int u, int v) if (v==0) return u; else return gcd(v, u%v); main() scanf( %d%d, &x, &y); printf( %d \n, gcd(x, y)); return 0; fp sp x:15 y:10 u: 15 v: 10 u: 10 v: 5 u: 5 v: 0 自 由 空 间 全 局 / 静 态 区 域 main 的 活 动 记 录 第 一 次 调 用 gcd 时 的 活 动 记 录 第 二 次 调 用 gcd 时 的 活 动 记 录 第 三 次 调 用 gcd 时 的 活 动 记 录 栈 生 长 的 方 法 int x=2; void g(int); void f(int n) static int x=1; g(n); x--; void g(int m) int y=m-1; if(y>0) f(y); x--; g(y); main() g(x); return 0; fp sp x:2 x(from f):1 m: 2 y:1 n: 1 m: 1 y: 0 自 由 空 间 全 局 / 静 态 区 域 main 的 活 动 记 录 调 用 g 时 的 活 动 记 录 调 用 f 时 的 活 动 记 录 调 用 g 时 的 活 动 记 录 栈 生 长 的 方 法 int x=2; void g(int); void f(int n) static int x=1; g(n); x--; void g(int m) int y=m-1; if(y>0) f(y); x--; g(y); main() g(x); return 0; fp sp x: 1 x(from f):0 m: 2 y:1 m: 1 y: 0 自 由 空 间 全 局 / 静 态 区 域 main 的 活 动 记 录 调 用 g 时 的 活 动 记 录 调 用 g 时 的 活 动 记 录 栈 生 长 的 方 法 编 译 技 术 及 应 用 李 莉 5
void f(int x, char c) int a[10]; double y;. fp x c a[9] a[0] y x 偏 移 量 c 偏 移 量 a 偏 移 量 y 偏 移 量 调 用 序 列 调 用 过 程 计 算 自 变 量 并 将 其 存 放 在 过 程 的 新 活 动 目 录 中 的 正 确 位 置 将 fp 作 为 存 放 到 新 的 活 动 记 录 中 改 变 fp 以 使 其 指 向 新 的 活 动 记 录 的 开 始 将 存 放 在 新 的 活 动 记 录 中 ( 如 果 需 要 ) 完 成 到 被 调 用 的 过 程 的 代 码 的 一 个 转 移 调 用 序 列 从 调 用 中 返 回 将 fp 复 制 到 sp 中 将 装 载 到 fp 中 完 成 到 的 一 个 转 移 改 变 sp 以 弹 出 自 变 量 临 时 变 量 和 嵌 套 说 明 x[i]=(i+j)*(i/k + f(j)) fp sp x[i] [] 的 地 址 i+j 的 结 果 i/j 的 结 果 包 含 表 达 式 过 程 的 活 动 记 录 临 时 变 量 调 用 f 时 ( 将 要 创 建 的 ) 的 新 活 动 记 录 编 译 技 术 及 应 用 李 莉 6
Program nonlocalref procedure p; var n: integer; procedure q; begin // 存 在 对 n 的 引 用 end; procedure r(n:integer) begin q; end; begin n := 1; r(2); end; begin p; end fp sp 具 有 局 部 过 程 的 基 于 栈 的 环 境 无 访 问 链 n:1 n:2 访 问 链 访 问 链 主 程 序 的 活 动 记 录 调 用 p 时 的 活 动 记 录 调 用 r 时 的 活 动 记 录 调 用 q 时 的 活 动 记 录 栈 式 存 储 分 配 特 点 嵌 套 调 用 次 序 先 进 后 出 生 存 期 仅 限 于 本 次 调 用 自 动 释 放 主 要 用 途 过 程 的 局 部 变 量 活 动 记 录 堆 式 存 储 分 配 堆 式 存 储 分 配 大 多 语 言 需 要 一 些 动 态 的 功 能 以 处 理 指 针 分 配 和 重 新 分 配 堆 堆 通 常 是 存 储 区 的 一 个 线 性 块, 根 据 需 要 可 以 生 长 分 配 操 作 和 释 放 操 作 用 户 可 以 动 态 的 申 请 和 释 放 空 间, 且 不 满 足 先 请 后 还, 后 请 后 还 malloc, free 操 作 new, delete 操 作 X W Y Z W X Y Z 编 译 技 术 及 应 用 李 莉 7
堆 式 动 态 存 储 分 配 的 实 现 堆 式 动 态 存 储 分 配 的 实 现 定 长 块 管 理 占 用 占 用 占 用 空 闲 空 闲 空 闲 占 用 空 闲 占 用 available 空 闲 空 闲 空 闲 变 长 块 管 理 根 据 需 要 分 配 长 度 不 同 的 存 储 块 分 配 策 略 首 次 满 足 法 最 优 满 足 法 最 差 满 足 法 available 垃 圾 回 收 方 法 垃 圾 回 收 方 法 引 用 计 数 ( Reference Counting ) 算 法 标 记 - 清 除 ( Mark-Sweep ) 算 法 第 一 种 实 用 和 完 善 的 垃 圾 收 集 算 法 J. McCarthy 等 人 在 1960 年 提 出 并 成 功 地 应 用 于 Lisp 语 言 复 制 (Coping) 算 法 M. L. Minsky 于 1963 年 发 表 了 著 名 的 论 文 A LISP Garbage Collector Algorithm Using Serial Secondary Storage S. Arnborg 成 功 地 将 复 制 算 法 应 用 到 了 Simula 语 言 中 标 记 - 整 理 ( Mark-Compact ) 算 法 增 量 收 集 ( Incremental Collecting ) 算 法 分 代 收 集 ( Generational Collecting ) 算 法 并 发 ( Concurrent ) 收 集 编 译 技 术 及 应 用 李 莉 8
堆 式 存 储 分 配 名 字 的 绑 定 特 点 存 储 空 间 的 动 态 分 配 和 释 放 主 要 用 途 用 于 存 储 动 态 数 据 结 构 实 现 方 法 将 内 存 空 间 分 为 若 干 块, 根 据 用 户 需 求 分 配 无 法 满 足 时, 调 用 无 用 单 元 收 集 程 序 将 已 释 放 的 块 收 集 起 来 重 新 分 配 即 使 每 个 名 字 在 程 序 中 只 声 明 一 次, 同 一 个 名 字 在 运 行 时 可 能 代 表 不 同 的 数 据 对 象 数 据 对 象 : 保 存 值 的 存 储 单 元 环 境 : 将 名 字 映 射 到 存 储 单 元 的 函 数 状 态 : 将 存 储 单 元 映 射 到 它 所 保 存 的 值 的 函 数 环 境 状 态 名 字 存 储 单 元 值 名 字 的 绑 定 参 数 传 递 如 果 环 境 把 存 储 单 元 s 与 名 字 x 联 系 起 来, 则 称 x 绑 定 到 s 变 量 名 数 据 存 储 单 元 地 址 过 程 名 函 数 名 程 序 段 入 口 地 址 静 态 概 念 过 程 的 定 义 名 字 的 声 明 声 明 的 作 用 域 动 态 对 应 物 过 程 的 活 动 名 字 的 绑 定 绑 定 的 生 命 期 形 参 和 实 参 左 值 和 右 值 i := j 左 值 : 表 达 式 表 示 的 存 储 单 元 右 值 : 这 个 存 储 单 元 中 所 存 的 值 编 译 技 术 及 应 用 李 莉 9
参 数 传 递 参 数 传 递 值 传 递 (pass by value) 引 用 传 递 (pass by reference) 值 结 果 传 递 (pass by value-result) lt) 名 字 传 递 (pass by name) 值 传 递 过 程 调 用 时 计 算 实 参, 并 将 值 传 给 被 调 用 过 程 void inc( int x) ++x; 实 参 A A 单 向 传 播 形 参 X A 的 值 参 数 传 递 参 数 传 递 引 用 传 递 如 果 实 参 是 有 左 值 的 名 字 或 表 达 式, 则 传 递 这 个 左 值 本 身 如 果 实 参 是 a+b 或 2 这 样 的 表 达 式, 没 有 左 值, 则 计 算 该 表 达 式 的 值 并 存 入 新 的 存 储 单 元, 然 后 传 递 这 个 单 元 的 地 址 实 参 A A 传 地 址 被 调 用 者 间 址 访 问 形 参 X A 的 地 址 引 用 传 递 void swap(int &x, int &y) int tmp; tmp = x; x = y; y = tmp; void f(const int &x) x ++ ; void f(const int *x) (*x) ++ ; 编 译 技 术 及 应 用 李 莉 10
参 数 传 递 参 数 传 递 值 结 果 传 递 ( 复 制 - 恢 复 复 制 进 复 制 出 ) 传 值 调 用 和 传 地 址 调 用 的 混 合 在 控 制 流 进 入 被 调 用 过 程 之 前 计 算 实 参, 实 参 的 右 值 像 传 值 一 样 传 递 给 被 调 用 过 程 当 控 制 返 回 时, 将 形 参 的 当 前 右 值 复 制 回 实 参 的 左 值, 该 左 值 是 上 述 调 用 前 计 算 的 左 值 名 字 传 递 将 被 调 用 过 程 的 过 程 体 复 制 到 调 用 处, 并 将 每 一 个 形 参 文 字 地 替 换 为 实 参 是 一 种 早 期 的 语 言 Algol 用 的 一 种 参 数 传 递 方 式 实 参 A A 传 地 址 传 值 形 参 X A 的 地 址 主 程 序 : A=2; B=3; P(A+B, A, A); print A; 子 程 序 : P(X, Y, Z) Y = Y+1; Z = Z+X; 形 式 传 值 引 用 复 制 恢 复 传 名 调 用 过 程 临 时 单 元 : T: A+B=5 X=T=5, Y=Z=A=2 A=A+1=2+1 A=A+T=3+5 X=T=5, Y=Z=A=2 Y=Y+1=3 Z=Z+X=2+5=7 Y A=3 Z A=7 结 果 2 8 7 9 A=A+1=3 A=A+A+B=3 +3+3=9 存 储 空 间 动 态 分 配 的 问 题 悬 空 引 用 引 用 某 个 已 经 释 放 的 存 储 单 元 main() int *p; p = dangle(); int *dangle() int i = 10; return &i; 编 译 技 术 及 应 用 李 莉 11
存 储 空 间 动 态 分 配 的 问 题 存 储 空 间 动 态 分 配 的 问 题 垃 圾 单 元 动 态 分 配 的 单 元 可 能 变 得 不 可 访 问 head head 23 42 10 nil 23 nil 42 10 nil 野 指 针 好 习 惯 :char *p = NULL; char *str = (char *) malloc(100); 好 习 惯 : 执 行 申 请 空 间 后, 判 断 是 否 申 请 成 功 指 针 p 被 free 或 者 delete 之 后, 没 有 置 为 NULL, 让 人 误 以 为 p 是 个 合 法 的 指 针 本 章 小 结 本 章 小 结 影 响 存 储 分 配 策 略 的 语 言 特 征 过 程 是 否 递 归 ; 当 控 制 从 一 个 活 动 的 过 程 返 回 时, 局 部 变 量 的 值 是 否 要 保 留 过 程 能 否 访 问 非 局 部 过 程 调 用 的 参 数 传 递 方 式 过 程 能 否 被 作 为 参 数 传 递 过 程 能 否 作 为 结 果 值 传 递 存 储 块 能 否 在 程 序 控 制 下 动 态 地 分 配 存 储 块 是 否 必 须 显 式 地 释 放 静 态 绑 定 和 动 态 绑 定 参 数 的 传 递 方 式 活 动 记 录 中 各 种 数 据 域 的 安 排 和 作 用 程 序 执 行 过 程 中 如 何 进 行 存 储 分 配 的? 何 时 为 哪 些 数 据 分 配 存 储 空 间? 编 译 技 术 及 应 用 李 莉 12