1、编 译 原 理 课 后 习 题 答 案 第 一 章 第 1 章 引 论 第 1题 解 释 下 列 术 语 ： （1）编 译 程 序 （2）源 程 序 （3）目 标 程 序 （4）编 译 程 序 的 前 端 （5）后 端 （6）遍 答 案 ： （1） 编 译 程 序 ：如 果 源 语 言 为 高 级 语 言 ，目 标 语 言 为 某 台 计 算 机 上 的 汇 编 语 言 或 机 器 语 言 ，则 此 翻 译 程 序 称 为 编 译 程 序 。 （2） 源 程 序 ：源 语 言 编 写 的 程 序 称 为 源 程 序 。 （3） 目 标 程 序 ：目 标 语 言 书 写 的 程 序 称 为 目
2、标 程 序 。 （4） 编 译 程 序 的 前 端 ：它 由 这 样 一 些 阶 段 组 成 ：这 些 阶 段 的 工 作 主 要 依 赖 于 源 语 言 而 与 目 标 机 无 关 。通 常 前 端 包 括 词 法 分 析 、语 法 分 析 、语 义 分 析 和 中 间 代 码 生 成 这 些 阶 段 ，某 些 优 化 工 作 也 可 在 前 端 做 ，也 包 括 与 前 端 每 个 阶 段 相 关 的 出 错 处 理 工 作 和 符 号 表 管 理 等 工 作 。 （5） 后 端 ：指 那 些 依 赖 于 目 标 机 而 一 般 不 依 赖 源 语 言 ，只 与 中 间 代 码 有 关 的
3、 那 些 阶 段 ， 即 目 标 代 码 生 成 ，以 及 相 关 出 错 处 理 和 符 号 表 操 作 。 （6） 遍 ：是 对 源 程 序 或 其 等 价 的 中 间 语 言 程 序 从 头 到 尾 扫 视 并 完 成 规 定 任 务 的 过 程 。 第 2题 一 个 典 型 的 编 译 程 序 通 常 由 哪 些 部 分 组 成 ？ 各 部 分 的 主 要 功 能 是 什 么 ？ 并 画 出 编 译 程 序 的 总 体 结 构 图 。 答 案 ： 一 个 典 型 的 编 译 程 序 通 常 包 含 8 个 组 成 部 分 ，它 们 是 词 法 分 析 程 序 、语 法 分 析 程 序
4、、语 义 分 析 程 序 、中 间 代 码 生 成 程 序 、中 间 代 码 优 化 程 序 、目 标 代 码 生 成 程 序 、表 格 管 理 程 序 和 错 误 处 理 程 序 。其 各 部 分 的 主 要 功 能 简 述 如 下 。 词 法 分 析 程 序 ：输 人 源 程 序 ，拼 单 词 、检 查 单 词 和 分 析 单 词 ，输 出 单 词 的 机 内 表 达 形 式 。 语 法 分 析 程 序 ：检 查 源 程 序 中 存 在 的 形 式 语 法 错 误 ，输 出 错 误 处 理 信 息 。 语 义 分 析 程 序 ：进 行 语 义 检 查 和 分 析 语 义 信 息 ，并 把
5、分 析 的 结 果 保 存 到 各 类 语 义 信 息 表 中 。 中 间 代 码 生 成 程 序 ：按 照 语 义 规 则 ，将 语 法 分 析 程 序 分 析 出 的 语 法 单 位 转 换 成 一 定 形 式 的 中 间 语 言 代 码 ，如 三 元 式 或 四 元 式 。 中 间 代 码 优 化 程 序 ：为 了 产 生 高 质 量 的 目 标 代 码 ，对 中 间 代 码 进 行 等 价 变 换 处 理 。 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 1编 译 原 理 课 后 习 题 答 案 第 一 章 目 标 代 码 生 成 程 序 ：将 优 化 后 的 中 间 代 码
6、 程 序 转 换 成 目 标 代 码 程 序 。 表 格 管 理 程 序 ：负 责 建 立 、填 写 和 查 找 等 一 系 列 表 格 工 作 。表 格 的 作 用 是 记 录 源 程 序 的 各 类 信 息 和 编 译 各 阶 段 的 进 展 情 况 ，编 译 的 每 个 阶 段 所 需 信 息 多 数 都 从 表 格 中 读 取 ，产 生 的 中 间 结 果 都 记 录在 相 应 的 表 格 中 。可 以 说 整 个 编 译 过 程 就 是 造 表 、查 表 的 工 作 过 程 。需 要 指 出 的 是 ，这 里 的 “表 格 管 理 程 序 “并不 意 味 着 它 就 是 一 个 独
7、立 的 表 格 管 理 模 块 ，而 是 指 编 译 程 序 具 有 的 表 格 管 理 功 能 。 错 误 处 理 程 序 ：处 理 和 校 正 源 程 序 中 存 在 的 词 法 、语 法 和 语 义 错 误 。当 编 译 程 序 发 现 源 程 序 中 的 错 误 时 ，错 误 处 理 程 序 负 责 报 告 出 错 的 位 置 和 错 误 性 质 等 信 息 ，同 时 对 发 现 的 错 误 进 行 适 当 的 校 正 （修 复 ） ，目 的 是 使 编 译 程 序 能 够 继 续 向 下 进 行 分 析 和 处 理 。 注 意 ：如 果 问 编 译 程 序 有 哪 些 主 要 构 成
8、 成 分 ，只 要 回 答 六 部 分 就 可 以 。如 果 搞 不 清 楚 ， 就 回 答 八 部 分 。 第 3题 何 谓 翻 译 程 序 、编 译 程 序 和 解 释 程 序 ？ 它 们 三 者 之 间 有 何 种 关 系 ？ 答 案 ： 翻 译 程 序 是 指 将 用 某 种 语 言 编 写 的 程 序 转 换 成 另 一 种 语 言 形 式 的 程 序 的 程 序 ， 如 编 译 程 序 和 汇 编 程 序 等 。 编 译 程 序 是 把 用 高 级 语 言 编 写 的 源 程 序 转 换 （加 工 ）成 与 之 等 价 的 另 一 种 用 低 级 语 言 编 写 的 目 标 程 序
9、 的 翻 译 程 序 。 解 释 程 序 是 解 释 、执 行 高 级 语 言 源 程 序 的 程 序 。解 释 方 式 一 般 分 为 两 种 ：一 种 方 式 是 ， 源 程 序 功 能 的 实 现完 全 由 解 释 程 序 承 担 和 完 成 ，即 每 读 出 源 程 序 的 一 条 语 句 的 第 一 个 单 词 ， 则 依 据 这 个 单 词 把 控 制 转 移 到 实 现 这 条 语 句 功 能 的 程 序 部 分 ， 该 部 分 负 责 完 成 这 条 语 句 的 功 能 的 实 现 ，完 成后 返 回 到 解 释 程 序 的 总 控 部 分 再 读 人 下 一 条 语 句 继
10、续 进 行 解 释 、执 行 ，如 此 反 复 ；另 一 种 方 式 是 ，一 边 翻 译 一边 执 行 ，即 每 读 出 源 程 序 的 一 条 语 句 ，解 释 程 序 就 将 其 翻 译 成 一 段 机 器 指 令 并 执 行 之 ，然 后 再 读 人 下 一 条 语句 继 续 进 行 解 释 、执 行 ，如 此 反 复 。无 论 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 2编 译 原 理 课 后 习 题 答 案 第 一 章 是 哪 种 方 式 ，其 加 工 结 果 都 是 源 程 序 的 执 行 结 果 。目 前 很 多 解 释 程 序 采 取 上 述 两 种 方 式 的
11、 综 合 实 现 方 案 ，即先 把 源 程 序 翻 译 成 较 容 易 解 释 执 行 的 某 种 中 间 代 码 程 序 ，然 后 集 中 解 释 执 行 中 间 代 码 程 序 ，最 后 得 到 运 行 结 果 。 广 义 上 讲 ，编 译 程 序 和 解 释 程 序 都 属 于 翻 译 程 序 ，但 它 们 的 翻 译 方 式 不 同 ，解 释 程 序 是 边 翻 译 （解 释 ）边执 行 ，不 产 生 目 标 代 码 ，输 出 源 程 序 的 运 行 结 果 。而 编 译 程 序 只 负 责 把 源 程 序 翻 译 成 目 标 程 序 ，输 出 与 源 程序 等 价 的 目 标 程
12、序 ，而 目 标 程 序 的 执 行 任 务 由 操 作 系 统 来 完 成 ，即 只 翻 译 不 执 行 。 第 4题 对 下 列 错 误 信 息 ，请 指 出 可 能 是 编 译 的 哪 个 阶 段 （词 法 分 析 、语 法 分 析 、语 义 分 析 、 代 码 生 成 ）报 告 的 。 （1） else 没 有 匹 配 的 if （2） 数 组 下 标 越 界 （3） 使 用 的 函 数 没 有 定 义 （4） 在 数 中 出 现 非 数 字 字 符 答 案 ： （1） （2） （3） （4） 第 5题 语 法 分 析 语 义 分 析 语 法 分 析 词 法 分 析 编 译 程 序 大
13、 致 有 哪 几 种 开 发 技 术 ？ 答 案 ： （1）自 编 译 ：用 某 一 高 级 语 言 书 写 其 本 身 的 编 译 程 序 。 （2）交 叉 编 译 ：A 机 器 上 的 编 译 程 序 能 产 生 B 机 器 上 的 目 标 代 码 。 （3）自 展 ：首 先 确 定 一 个 非 常 简 单 的 核 心 语 言 L0，用 机 器 语 言 或 汇 编 语 言 书 写 出 它 的 编 译 程 序 T0，再 把 语 言 L0 扩 充 到 L1，此 时 L0 L1 ,并 用 L0 编 写 L1 的 编 译 程 序 T1，再 把 语 言 L1 扩 充 为 L2，有 L1 L2 ,并
14、用 L1 编 写 L2 的 编 译 程 序 T2， ，如 此 逐 步 扩 展 下 去 ， 好 似 滚 雪 球 一 样 ，直 到 我 们 所 要 求 的 编 译 程 序 。 （4）移 植 ：将 A 机 器 上 的 某 高 级 语 言 的 编 译 程 序 搬 到 B 机 器 上 运 行 。 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 3编 译 原 理 课 后 习 题 答 案 第 一 章 第 题 计 算 机 执 行 用 高 级 语 言 编 写 的 程 序 有 哪 些 途 径 ?它 们 之 间 的 主 要 区 别 是 什 么 ? 答 案 ： 计 算 机 执 行 用 高 级 语 言 编 写
15、的 程 序 主 要 途 径 有 两 种 ，即 解 释 与 编 译 。 像 Basic 之 类 的 语 言 ，属 于 解 释 型 的 高 级 语 言 。它 们 的 特 点 是 计 算 机 并 不 事 先 对 高 级 语 言 进 行 全 盘 翻 译 ，将 其 变 为 机 器 代 码 ，而 是 每 读 入 一 条 高 级 语 句 ，就 用 解 释 器 将 其 翻 译 为 一 条 机 器 代 码 ，予 以 执 行 ，然 后 再 读 入 下 一 条 高 级 语 句 ，翻 译 为 机 器 代 码 ，再 执 行 ，如 此 反 复 。 总 而 言 之 ，是 边 翻 译 边 执 行 。 像 C，Pascal 之
16、 类 的 语 言 ，属 于 编 译 型 的 高 级 语 言 。它 们 的 特 点 是 计 算 机 事 先 对 高 级 语 言 进 行 全 盘 翻 译 ，将 其 全 部 变 为 机 器 代 码 ，再 统 一 执 行 ，即 先 翻 译 ，后 执 行 。从 速 度 上 看 ， 编 译 型 的 高 级 语 言 比 解 释 型 的 高 级 语 言 更 快 。 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 4编 译 原 理 课 后 习 题 答 案 第 二 章 第 2 章 PL/0 编 译 程 序 的 实 现 第 1题 PL/0 语 言 允 许 过 程 嵌 套 定 义 和 递 归 调 用 ，试 问
17、 它 的 编 译 程 序 如 何 解 决 运 行 时 的 存 储 管 理 。 答 案 ： PL/0 语 言 允 许 过 程 嵌 套 定 义 和 递 归 调 用 ，它 的 编 译 程 序 在 运 行 时 采 用 了 栈 式 动 态 存 储 管 理 。（数 组 CODE 存 放 的 只 读 目 标 程 序 ，它 在 运 行 时 不 改 变 。）运 行 时 的 数 据 区 S 是 由 解 释 程 序 定 义的 一 维 整 型 数 组 ，解 释 执 行 时 对 数 据 空 间 S 的 管 理 遵 循 后 进 先 出 规 则 ，当 每 个 过 程 (包 括 主 程 序 )被 调 用时 ，才 分 配 数
18、据 空 间 ，退 出 过 程 时 ，则 所 分 配 的 数 据 空 间 被 释 放 。 应 用 动 态 链 和 静 态 链 的 方 式 分 别 解 决 递 归 调 用 和 非 局 部 变 量 的 引 用 问 题 。 第 2题 若 PL/0 编 译 程 序 运 行 时 的 存 储 分 配 策 略 采 用 栈 式 动 态 分 配 ，并 用 动 态 链 和 静 态 链 的 方 式 分 别 解 决递 归 调 用 和 非 局 部 变 量 的 引 用 问 题 ，试 写 出 下 列 程 序 执 行 到 赋 值 语 句 b=10 时 运 行 栈 的 布 局 示 意 图 。 var x,y; procedure
19、 p; var a; procedure q; var b; begin (q) b=10; end (q); procedure s; var c,d; procedure r; var e,f; begin (r) call q; end (r); begin (s) call r; end (s); begin (p) call s; 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 1编 译 原 理 课 后 习 题 答 案 第 二 章 end (p); begin (main) call p; end (main). 答 案 ： 程 序 执 行 到 赋 值 语 句 b=10 时
20、运 行 栈 的 布 局 示 意 图 为 ： 第 3题 写 出 题 2 中 当 程 序 编 译 到 r 的 过 程 体 时 的 名 字 表 table 的 内 容 。 name kind level/val adr size 答 案 ： 题 2 中 当 程 序 编 译 到 r 的 过 程 体 时 的 名 字 表 table 的 内 容 为 ： name kind level/val adr size x variable 0 dx y variable 0 dx+1 p procedure 0 过 程 p 的 入 口 （待 填 ） 5盛 威 网 （）专 业 的 计 算 机 学 习 网 站 2编
21、译 原 理 课 后 习 题 答 案 第 二 章 a variable 1 dx q procedure 1 过 程 q 的 入 口 4s procedure 1 过 程 s 的 入 口 （待 填 ） 5c variable 2 dx d variable 2 dx r procedure 2 过 程 r 的 入 口 5e variable 3 dx f variable 3 dx+1 注 意 ：q 和 s 是 并 列 的 过 程 ，所 以 q 定 义 的 变 量 b 被 覆 盖 。 第 4题 指 出 栈 顶 指 针 T，最 新 活 动 记 录 基 地 址 指 针 B，动 态 链 指 针 DL，
22、静 态 链 指 针 SL 与 返 回 地 址 RA 的 用 途 。 答 案 ： 栈 顶 指 针 T，最 新 活 动 记 录 基 地 址 指 针 B，动 态 链 指 针 DL，静 态 链 指 针 SL 与 返 回 地 址 RA 的 用 途 说 明 如 下 ： T： 栈 顶 寄 存 器 T 指 出 了 当 前 栈 中 最 新 分 配 的 单 元 (T 也 是 数 组 S 的 下 标 )。 B：基 址 寄 存 器 ，指 向 每 个 过 程 被 调 用 时 ，在 数 据 区 S 中 给 它 分 配 的 数 据 段 起 始 地 址 ， 也 称 基 地 址 。 SL： 静 态 链 ，指 向 定 义 该 过
23、 程 的 直 接 外 过 程 （或 主 程 序 ）运 行 时 最 新 数 据 段 的 基 地 址 ， 用 以 引 用 非 局 部 （包 围 它 的 过 程 ）变 量 时 ，寻 找 该 变 量 的 地 址 。 DL： 动 态 链 ，指 向 调 用 该 过 程 前 正 在 运 行 过 程 的 数 据 段 基 地 址 ，用 以 过 程 执 行 结 束 释 放 数 据 空 间 时 ，恢 复 调 用 该 过 程 前 运 行 栈 的 状 态 。 RA： 返 回 地 址 ，记 录 调 用 该 过 程 时 目 标 程 序 的 断 点 ，即 调 用 过 程 指 令 的 下 一 条 指 令 的 地 址 ，用 以
24、过 程 执 行 结 束 后 返 回 调 用 过 程 时 的 下 一 条 指 令 继 续 执 行 。 在 每 个 过 程 被 调 用 时 在 栈 顶 分 配 3 个 联 系 单 元 ，用 以 存 放 SL，DL， RA。 第 5题 PL/0 编 译 程 序 所 产 生 的 目 标 代 码 是 一 种 假 想 栈 式 计 算 机 的 汇 编 语 言 ，请 说 明 该 汇 编 语 言 中 下 列 指 令 各 自 的 功 能 和 所 完 成 的 操 作 。 （） INT 0 A （） OPR 0 0 （） CAL L A 答 案 ： PL/0 编 译 程 序 所 产 生 的 目 标 代 码 中 有 3
25、 条 非 常 重 要 的 特 殊 指 令 ，这 3 条 指 令 在 code 中 的 位 置 和 功 能 以 及 所 完 成 的 操 作 说 明 如 下 ： 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 3编 译 原 理 课 后 习 题 答 案 第 二 章 INT 0 A 在 过 程 目 标 程 序 的 入 口 处 ，开 辟 A 个 单 元 的 数 据 段 。A 为 局 部 变 量 的 个 数 +3。 OPR 0 0 在 过 程 目 标 程 序 的 出 口 处 ，释 放 数 据 段 （退 栈 ），恢 复 调 用 该 过 程 前 正 在 运 行 的 过 程 的 数 据 段 基 址 寄
26、存 器 B 和 栈 顶 寄 存 器 T 的 值 ，并 将 返 回 地 址 送 到 指 令 地 址 寄 存 器 P 中 ，以 使 调 用 前 的 程 序 从 断 点 开 始 继 续 执 行 。 CAL L A 调 用 过 程 ，完 成 填 写 静 态 链 、动 态 链 、返 回 地 址 ，给 出 被 调 用 过 程 的 基 地 址 值 ，送 入 基 址 寄 存 器 B 中 ，目 标 程 序 的 入 口 地 址 A 的 值 送 指 令 地 址 寄 存 器 P 中 ，使 指 令 从 A 开 始 执 行 。 第 6题 给 出 对 PL/0 语 言 作 如 下 功 能 扩 充 时 的 语 法 图 和 E
27、BNF 的 语 法 描 述 。 (1) 扩 充 条 件 语 句 的 功 能 使 其 为 ： if条 件 then语 句 else语 句 (2) 扩 充 repeat 语 句 为 ： repeat语 句 ； 语 句 until条 件 答 案 ： 对 PL/0 语 言 作 如 下 功 能 扩 充 时 的 语 法 图 和 EBNF 的 语 法 描 述 如 下 ： (1) 扩 充 条 件 语 句 的 语 法 图 为 ： EBNF 的 语 法 描 述 为 ： 条 件 语 句 := if条 件 then语 句 else语 句 (2) 扩 充 repeat 语 句 的 语 法 图 为 ： EBNF 的 语
28、法 描 述 为 ： 重 复 语 句 := repeat语 句 ；语 句 until条 件 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 4编 译 原 理 课 后 习 题 答 案 第 三 章 第 3章 文 法 和 语 言 第 1题 文 法 G (A,B,S,a,b,c,P,S)其 中 P 为 ： SAc|aB Aab Bbc 写 出 L(GS)的 全 部 元 素 。 答 案 ： L(GS)=abc 第 2题 文 法 GN为 ： ND|ND D0|1|2|3|4|5|6|7|8|9 GN的 语言 是 什 么 ？ 答 案 : GN的 语 言 是 V+。V=0,1,2,3,4,5,6,7,8
29、,9 N=ND=NDD. =NDDDD.D=D.D 或 者 ：允 许 0 开 头 的 非 负 整 数 ？ 第 题 为 只 包 含 数 字 、加 号 和 减 号 的 表 达 式 ，例 如 9-2 5，3-1，等 构 造 一 个 文 法 。 答 案 ： GS: S-S+D|S-D|D D-0|1|2|3|4|5|6|7|8|9 第 4题 已 知 文 法 GZ： ZaZb|ab 写 出 L(GZ)的 全 部 元 素 。 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 1编 译 原 理 课 后 习 题 答 案 第 三 章 答 案 ： Z=aZb=aaZbb=aaa.Z.bbb= aaa.ab.
30、bbb L(GZ)=anbn|n=1 第 5题 写 一 文 法 ，使 其 语 言 是 偶 正 整 数 的 集 合 。 要 求 ： (1) 允 许 0 打 头 ； (2)不 允 许 0 打 头 。 答 案 ： (1)允 许 0 开 头 的 偶 正 整 数 集 合 的 文 法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8 (2)不 允 许 0 开 头 的 偶 正 整 数 集 合 的 文 法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0 第 6题 已 知 文 法 G： := := * :=（） i 试 给 出 下 述 表 达 式 的 推 导 及 语 法 树 。 （）i+(i+i) （）i+i*i 盛 威 网 （）专 业 的 计 算 机 学 习 网 站 2
