编译原理课件

《编译原理课件》由会员分享，可在线阅读，更多相关《编译原理课件（123页珍藏版）》请在装配图网上搜索。

1、CompilerPrinciples 1 第 一 讲 引 论u课 程 信 息u编 译 程 序 概 述u高 级 语 言 的 语 法 描 述 CompilerPrinciples 3 1.课 程 信 息一 、 课 程 名 称 ： 编 译 原 理v基 本 内 容 是 介 绍 编 译 程 序 构 造 的 基 本 原 理 、方 法 和 技 术 ， 包 括 词 法 分 析 、 语 法 分 析 、语 义 分 析 与 中 间 代 码 产 生 、 代 码 优 化 及 目标 代 码 产 生 等 。 简 言 之 ， 就 是 介 绍 如 何 将源 程 序 翻 译 成 目 标 代 码 程 序 。 CompilerPri

2、nciples 4 二 、 课 程 性 质 ： 专 业 基 础 课 ， 必 修v编 译 程 序 （ 器 ） 出 现 于 上 世 纪 50年 代 后 期（ 第 一 个 高 级 语 言 1958年 ）v60年 代 70年 代 是 研 究 高 峰 期v60年 代 中 期 开 始 在 高 校 中 开 设 课 程v80年 代 开 始 作 为 计 算 机 科 学 与 技 术 专 业 的必 修 基 础 课 程 CompilerPrinciples 5 CompilerPrinciples 6 三 、 课 程 特 点 ：v 充 分 体 现 了 计 算 学 科 中 抽 象 、 理 论 和 设 计 三 个 学 科

3、形 态v 该 课 程 涉 及 多 门 课 程 的 内 容 综 合 运 用 ，程 序 设 计 语 言 、 计 算 机 体 系 结 构 、 语 言 理 论 及 算 法 等数 据 结 构 、 离 散 数 学v 该 课 程 涉 及 的 原 理 、 方 法 和 技 术 具 有 十 分 普 遍 的 意义 每 一 个 计 算 机 科 学 与 技 术 工 作 者 的 职 业 生 涯 中 反 复 用 到 ，“ 享 用 一 辈 子 ” 这 儿 接 受 的 训 练 很 难 在 其 他 地 方 获 得 ， 如 ： 抽 象 与 形 式化 方 法 、 局 部 与 全 局 优 化 方 法 、 构 造 技 术 、 证 明 方

4、 法 等 CompilerPrinciples 7 四 、 学 习 该 课 程 的 意 义v编 译 程 序 是 计 算 机 系 统 不 可 缺 少 的 重 要 组 成部 分对 程 序 设 计 语 言 的 设 计 与 实 现 能 有 更 深 刻 的 理解对 程 序 设 计 语 言 有 关 理 论 有 所 了 解从 宏 观 上 把 握 程 序 设 计 语 言 掌 握 了 编 译 原理 后 ， 就 不 能 再 说 ： “ 某 语 言 未 学 过 ， 所 以 不会 ”有 助 于 快 速 理 解 、 定 位 和 解 决 程 序 调 试 与 运 行中 出 现 的 问 题 CompilerPrinciple

5、s 8 v 编 译 方 法 与 技 术 有 着 广 泛 应 用安 全 技 术 、 程 序 理 解 、 软 件 逆 向 工 程 、 应 用 软 件 与 软件 工 具 开 发 、 软 件 测 试 与 验 证 等v 编 译 课 程 蕴 含 着 计 算 学 科 中 解 决 问 题 的 思 路 、 抽象 和 方 法 ， 这 些 与 高 等 数 学 一 样 ， 使 你 “ 享 用 一辈 子 ”v 课 程 所 涉 及 的 内 容 至 今 非 常 活 跃自 然 语 言 的 翻 译软 件 移 植网 络 安 全形 式 化 方 法 形 式 语 义 学 等 CompilerPrinciples 9 鉴 于 以 上 所

6、 述 ， 作 为 计 算 机 科学 与 技 术 专 业 的 学 生 必 须 学 习 和掌 握 编 译 原 理 这 门 课 程 ， 当 然 由于 其 综 合 性 、 处 理 问 题 的 复 杂 性等 ， 学 习 起 来 有 一 定 难 度 ， 这 就需 要 艰 苦 奋 斗 的 精 神 和 良 好 的 学习 方 法 CompilerPrinciples 10 五 、 学 习 方 法v编 译 程 序 的 构 造 是 一 个 庞 大 而 复 杂 的 系 统工 程 ， 无 论 是 概 念 还 是 理 论 、 方 法 ， 对 初学 者 来 说 许 多 都 是 新 的 ， 学 习 起 来 会 感 到困 难

7、大 一 些 ， 这 一 点 必 须 有 充 分 认 识 ， 为此 建 议 学 习 方 法 上 注 意 以 下 几 点 ： CompilerPrinciples 11 课 前 预 习 ， 课 堂 认 真 听 讲 ， 课 后 复 习 加 深 理解 ， 特 别 要 经 常 有 意 识 地 将 前 后 内 容 联 系 起来 融 会 贯 通 。因 为 编 译 程 序 是 一 个 庞 大 的 程 序 系 统 ， 讲 解过 程 必 须 “分 而 治 之 ”（ 这 也 是 人 们 处 理 复 杂问 题 的 基 本 方 法 ） ， 这 就 要 求 大 家 在 学 习 过程 中 ， 始 终 以 处 理 过 程 为

8、 主 线 ， 把 前 后 联 系起 来 考 虑 。 CompilerPrinciples 12 理 论 联 系 实 际 亲 自 动 手 ， 构 造 一 个演 示 性 编 译 程 序 ， 至 少 要 完 成 扫 描 器 和语 法 分 析 器 ， 以 及 语 法 制 导 翻 译 产 生 中间 代 码 （ 课 程 设 计 ） 认 真 完 成 作 业 ， 进 一 步 巩 固 并 加 深 理 解所 学 知 识 特 别 要 下 功 夫 认 真 学 习 如 何 从 实 际 问 题进 行 抽 象 并 形 式 化 ， 最 终 建 立 实 际 问 题的 模 型 （ 上 升 为 理 性 认 识 ） ， 并 借 助

9、模型 进 一 步 设 计 实 现 ， 这 将 对 你 能 力 的 提高 大 有 益 处 CompilerPrinciples 13 六 、 教 材 程 序 设 计 语 言 编 译 原 理 （ 第 3版 ）国 防 工 业 出 版 社 陈 火 旺 等 内 容 详 实 丰 富 ， 理 论 与 技 术 相 结 合 较 为 全 面 介 绍 了 编 译 程 序 构 造 的 基 本原 理 、 方 法 与 技 术 厚 度 适 中 大 多 数 院 校 一 直 采 用 ， 硕 士 入 学 考 试参 考 书1. 所 谓 教 材 ， 实 为 第 一 参 考 书 而 已 CompilerPrinciples 14 七

10、、 参 考 书 目1. 编 译 原 理 第 2版 赵 建 华 等 译 ， A.V.Aho, M.S.Lam,Ravi Sethi, J.D.Ullman著 ， 机 械 工 业 出 版 社 ， 2009；2. 编 译 原 理 课 程 设 计 王 雷 等 著 ， 机 械 工 业出 版 社 ， 2005；八 、 期 末 总 评平 时 成 绩 ： 10%课 程 设 计 ： 20%期 终 考 试 ： 70% CompilerPrinciples 15 CompilerPrinciples 16 2.编 译 程 序 概 述一 、 翻 译 程 序 （ Translator）能 够 把 一 种 语 言 程 序

11、 （ 称 为 源 语 言程 序 ） 转 换 成 另 一 种语 言 程 序 （ 称 为 目 标 语 言 程 序 ） 的程 序 CompilerPrinciples 17 v任 何 非 机 器 语 言 程 序 都 需 要 翻 译 程 序v翻 译 程 序 的 工 作 就 是 进 行 等 价 变 换 （ 映 射 ）v两 个 程 序 逻 辑 上 等 价 是 指 对 相 同 输 入 得 到相 同 的 输 出翻 译 程 序 解 释 程 序汇 编 程 序编 译 程 序 CompilerPrinciples 18 汇 编 程 序 (Assembler)把 汇 编 语 言 程 序 转 变 为 机 器 语 言 程

12、序 的 翻 译 程 序 解 释 程 序 (Interpreter)把 源 程 序 作 为 输 入 接 收 ， 边 解 释 边 执 行 的 翻 译 程 序源 程 序数 据 解 释程 序 结 果 CompilerPrinciples 19 编 译 程 序将 高 级 语 言 程 序 转 变 为 低 级 语 言 程 序 的 翻 译 程 序源 程 序 编 译程 序 目 标程 序 CompilerPrinciples 20 CompilerPrinciples 21 v 编 译 程 序 又 可 根 据 用 途 和 侧 重 点 的 不 同 ，进 一 步 分 类 为 ： 诊 断 编 译 程 序 (Diagno

13、stic Compiler) 专 门 用 于 帮 助 程 序 开 发 和 调 试 的 编 译 程 序 优 化 编 译 程 序 (Optimizing Compiler) 着 重 于 提 高 目 标 代 码 效 率 的 编 译 程 序 交 叉 编 译 程 序 (Cross Compiler) 能 够 产 生 不 同 于 其 宿 主 机 机 器 代 码 的 编 译 程 序 可 变 目 标 编 译 程 序 (Retargetable complier) 无 须 重 写 与 机 器 无 关 部 分 就 能 改 变 目 标 机 的 编 译 程 序 CompilerPrinciples 22 二 、 与

14、编 译 程 序 相 关 的 程 序 本 讲 义 只 介 绍 编 译 程 序 （ 器 ） 构 造 的 基 本 原理 、 方 法 与 技 术 ， 但 在 一 个 完 整 的 语 言 开 发（ 或 称 程 序 设 计 ） 环 境 中 ， 除 了 编 译 器 这 一主 要 工 具 外 ， 还 需 要 其 他 一 些 工 具 ， 如 编 辑器 、 连 接 器 、 装 入 程 序 等 。 现 代 计 算 机 系 统常 将 这 些 相 互 独 立 的 程 序 设 计 工 具 集 成 起 来 ，构 成 一 个 集 成 化 的 程 序 开 发 环 境 ， 以 提 高 程序 设 计 效 率 和 程 序 的 质 量

15、 。 如 Turbo C、Visual C+等 语 言 环 境 都 是 集 成 化 的 程 序 设计 环 境 。 而 Ada语 言 的 集 成 环 境 是 这 方 面 的典 型 代 表 。 CompilerPrinciples 23 如 Ada语 言 的 集 成 环 境 是 一 个 分 层 的 程 序 开 发 环 境编 译 程 序MAPSE编 辑 程 序 连接 程序宿 主 机OSAPSE 工 具 界 面用 户 界 面KAPSE 调 试程 序配 置 管理 程 序 命 令解 释程 序其 他工 具 CompilerPrinciples 24 这 儿 要 强 调 的 是 ： 尽管 本 课 程 只 介

16、绍 编 译的 基 本 理 论 、 方 法 和技 术 ， 但 这 些 基 本 理论 、 方 法 与 技 术 对 其他 工 具 的 构 造 同 样 起作 用 ！ CompilerPrinciples 25 编 辑 器 (Editor)完 成 源 程 序 输 入 、 编 辑 并 产 生 标 准 文 件（ 如 ASCII文 件 ） 的 程 序 。v 近 来 已 与 编 译 器 和 其 他 程 序 捆 绑 进 一 个 交互 开 发 环 境 IDE中v 尽 管 这 样 的 编 辑 器 仍 生 成 标 准 文 件 ， 但 会转 向 正 被 讨 论 的 程 序 设 计 语 言 的 格 式 或 结构 （ 称 为

17、 基 于 结 构 的 ） ， 且 已 包 含 了 编 译器 的 某 些 操 作 ； 因 此 在 程 序 编 写 时 而 不 是编 译 时 就 可 得 知 错 误 ， 甚 至 也 可 调 用 编 译器 CompilerPrinciples 26 预 处 理 程 序 (Preprocessor)在 真 正 翻 译 开 始 之 前 产 生 编 译 程 序 的 输 入的 程 序v 处 理 宏 及 注 释 ： 宏 是 被 经 常 使 用 的 较 长 结构 的 缩 写v 处 理 文 件 包 含 ： 把 头 文 件 包 含 到 程 序 正 文中 （ 如 C的 文 件 包 含 include ）v “ 理 解

18、 ” 预 处 理 器 ： 把 现 代 控 制 流 和 数 据结 构 机 制 添 加 到 比 较 老 式 的 语 言 中v 语 言 扩 充 ： 通 过 大 量 的 内 部 宏 定 义 来 增 强语 言 的 能 力 ， 如 Equel语 言 是 一 种 嵌 套 在 C语 言 中 的 数 据 库 查 询 语 言 CompilerPrinciples 27 连 接 程 序 (Linker)又 称 为 连 接 编 辑 器 。将 分 别 在 不 同 的 目 标 文 件 中 编 译 （ 或 汇 编 ）的 代 码 、 所 用 标 准 库 函 数 的 代 码 以 及 操 作系 统 提 供 的 资 源 （ 如 存

19、 储 分 配 程 序 及 输 入 /输 出 设 备 ） 收 集 到 一 个 可 直 接 执 行 的 文 件中 的 程 序 装 配 程 序 (Loader) 完 成 程 序 的 装 入 和 连 接 编 辑 两 项 功 能 。 装 入 过 程 包 括 读 入 可 重 定 位 机 器 代 码 、 修改 可 重 定 位 地 址 、 并 将 修 改 后 的 指 令 和 数据 放 到 内 存 的 适 当 位 置 。 装 入 程 序 使 得 可 执 行 代 码 更 加 灵 活 CompilerPrinciples 28 调 试 程 序 (Debugger) 可 在 被 编 译 了 的 程 序 中 判 定 执

20、 行 错 误 的 程序v 它 经 常 与 编 译 程 序 一 起 放 在 IDE中v 运 行 一 个 带 有 调 试 程 序 的 程 序 与 直 接 执 行不 同 ， 这 是 因 为 调 试 程 序 保 存 着 所 有 的 或大 多 数 源 代 码 信 息 ， 它 可 以 在 预 先 指 定 的位 置 （ 断 点 BreakPoint） 暂 停 执 行 ， 并 提 供有 关 信 息 （ 已 调 用 的 函 数 、 变 量 名 的 当 前值 等 ） CompilerPrinciples 29 其 他 有 关 的 还 有v 描 述 器 (Profiler)执 行 中 搜 集 目 标 程 序 行为

21、统 计 的 程 序v 项 目 管 理 程 序 (Project Manager)如Unix系 统 中 的 SCCS（ 源 代 码 控 制 系 统 ） 和RCS（ 修 正 控 制 系 统 ） 和 汇 编 程 序 等综 上 所 述 可 给 出 一 个 “ 语 言 处 理 系 统 ” 的 图 示 ： CompilerPrinciples 30我 们 这 个 课 只 介 绍 编 译 程 序 这 一 部 分 CompilerPrinciples 31 三 、 编 译 过 程 与 编 译 程 序 结 构 1.编 译 过 程 ： 输 入 输 出（ 高 级 语 言 源 程 序 ） （ 低 级 语 言 目 标

22、程 序 ） 编 译 程 序 工 作 过 程 如 下 ：l识 别 出 一 个 个 的 单 词l分 析 句 子 的 语 法 结 构l分 析 句 子 的 语 义 并 进 行 初 步 翻 译l对 初 步 翻 译 进 行 优 化l整 理 出 目 标 程 序对 以 上 过 程 进 一 步 整 理 可 得 如 下 编 译 程 序 结 构 总 框 ：编 译 程 序 CompilerPrinciples 32 2.编 译 程 序 总 框 ： 词 法 分 析 器语 法 分 析 器语 义 分 析 与 中 间 代 码 产 生 器优 化 器目 标 代 码 生 成 器单 词 符 号语 法 单 位中 间 代 码中 间 代

23、码 出错处理表格管理 源 程 序 目 标 代 码 CompilerPrinciples 33 3.五 个 阶 段 简 介l第 一 阶 段 ： 词 法 分 析 依 据 语 言 构 词 规则 ， 识 别 出 一 个 个 单 词 （ 符 号 ） 单 词 种 类l保 留 字 ： for if whilel算 符 ： l界 符 ： ， ； （ ） l标 识 符 ： a1 a2 pil常 数 ： 9 1024 4.8 6E6 无 穷 性有 穷 性思 考 ： 识 别 有 穷 集 合 VS 识 别 无 穷 集 合 CompilerPrinciples 34 词 法 分 析 工 作 由 词 法 分 析 器 （

24、或 称 扫 描器 ） 完 成 。 扫 描 器 输 出 为 等 长 度 的 单 词 符 号 （ 二 元式 ） 流 。 例 ：Position =initial+rate*60词 法 分 析 （ 扫 描 器 ） 保 留 字 表 (06,Position) (11,) (06,initial) (12,) (06,rate) (13, ) (07,60的 二 进 制 ) CompilerPrinciples 35 l第 二 阶 段 ： 语 法 分析 依 据 语 言 的语 法 规 则 ， 把 扫 描器 提 供 的 单 词 符 号串 分 解 成 各 种 语 法单 位 （ 范 畴 ） ， 如“ 短 语 ”

25、 、 “ 子句 ” 、 “ 句 子 ” 乃至 “ 程 序 ” 。 同 时进 行 语 法 检 查 ， 以确 定 输 入 串 是 否 正确 ， 该 工 作 是 由 语法 分 析 器 完 成 的 。 如 ： Position=initial+rate*60 是 一个 “ 赋 值 表 达 式 ” （ C语 言 中 ）Position = 表 达 式表 达 式表 达 式 + 表 达 式 标 识 符 表 达 式 * 表 达 式initial 标 识 符 常 数rate 60标 识 符 CompilerPrinciples 36 l 第 三 阶 段 ： 语 义 分 析 与 中 间 代 码 产 生 针 对各

26、类 不 同 的 语 法 范 畴 ， 按 语 言 的 语 义 规 则 进 行语 义 分 析 和 初 步 翻 译 工 作 ， 产 生 某 种 中 间 语 言形 式 的 中 间 代 码 （ 即 一 种 结 构 简 单 ， 含 义 明 确的 记 号 系 统 ） 。该 阶 段 工 作 通 常 包 括 两 个 方 面 的 工 作 ： 对 每 种 语 法 范 畴 进 行 静 态 语 义 检 查 ， 包 括 ：l变 量 是 否 定 义 过l类 型 是 否 正 确l是 否 用 了 0作 除 数 CompilerPrinciples 37 l将 语 法 范 畴 翻 译 成 某 种 形 式 的 中 间 代 码 ，如

27、 四 元 式 ：Op ARG1 ARG2 Result rate 60 T1 initial T1 T2 = T2 Position CompilerPrinciples 38 l 第 四 阶 段 ： 优 化 对 前 阶 段 产 生 的 中 间代 码 进 行 加 工 变 换 ， 以 期 在 最 后 阶 段 能 产生 出 高 效 （ 节 省 时 、 空 ） 的 目 标 代 码 ， 这一 任 务 是 由 优 化 器 来 完 成 的l根 据 优 化 的 范 围 不 同 ， 可 分 为 ：局 部 优 化 ， 循 环 优 化 和 全 局 优 化l一 个 循 环 优 化 的 例 子 ： CompilerP

28、rinciples 39 1 K I M J 100 K J N 10 K T1 1 K I T1 M J 100 K 10 K T2 M 10 M J T2 N N 10 N K 1 K K 1 K 循 环 For(k=1;k=100;k+) M=I+10*k; N=J+10*k;优 化 前 用 了 两 个 临 时 工 作 单 元 (T1,T2), 优 化 后 没 有 用 临 时 单 元优 化 前 循 环 体 中 要 做 300次 加 、 200次 乘 ， 优 化 后 循 环 体 内 只 做 300次 加 CompilerPrinciples 40 l 第 五 阶 段 ： 目 标 代 码 生

29、 成 把 中 间 代 码翻 译 成 目 标 代 码l 显 然 这 阶 段 要 依 赖 于 硬 体 系 统 结 构 和 指令 系 统l 涉 及 存 贮 分 配 、 寄 存 器 调 度这 一 阶 段 工 作 是 由 代 码 生 成 器 完 成 的说 明 ： 以 上 各 阶 段 （ 或 称 工 序 ） 并 不 是 截 然 分 开 的 ， 尤 其 编 译 程 序 结 构 十 分 复 杂 、 体 积 相当 庞 大 ， 所 以 有 时 人 们 把 几 个 阶 段 的 工 作有 机 地 组 合 在 一 起 、 穿 插 进 行 ， 构 成 遍 。 CompilerPrinciples 41 v 遍 （ Pas

30、s） ： 对 源 程 序 或 源 程 序 的 中 间 代码 从 头 到 尾 扫 描 一 次 并 做 相 应 处 理 加 工 分 遍 的 好 处 是 结 构 清 晰 、 节 省 内 存 （ 每遍 都 从 外 存 获 取 前 一 遍 的 结 果 作 为 开 始 ，工 作 结 果 仍 记 入 外 存 ， 每 遍 几 乎 可 使 用全 部 内 存 ） 分 不 分 遍 、 如 何 分 遍 要 视 具 体 情 况 计 算 机 内 存 容 量 、 源 语 言 的 繁 简 、 从 事编 译 程 序 设 计 人 员 的 情 况 等 CompilerPrinciples 42 如 某 PL/0编 译 程 序 的

31、结 构词 法 分 析 程序语 法 语 义 分 析 程 序代 码 生 成 程 序PL/0源 程 序目 标 程 序表 格管 理程 序 出 错处 理程 序 CompilerPrinciples 43 4.前 端 与 后 端 ： 概 念 上 讲 ， 编 译 程 序 的 五 个阶 段 可 进 一 步 划 分 为 前 端 和 后 端 ： 前 端 ： 主 要 由 与 源 语 言 有 关 而 与 目 标 机 无关 的 部 分 组 成 ， 包 括 词 法 分 析 、 语 法 分 析 、语 义 分 析 和 中 间 代 码 产 生 。 代 码 优 化 一 般也 包 含 在 前 端 。 后 端 ： 主 要 由 与 目

32、 标 机 有 关 的 部 分 组 成 ，包 括 目 标 代 码 生 成 和 与 目 标 机 有 关 的 优 化等 。 CompilerPrinciples 44 源程序 词法分析 语法分析 语 义分 析和 中间 代码 产生 中间语言中间代码优化 目标代码生成 目标代码优化 目标语言前 端 后 端 CompilerPrinciples 45 l 划 分 前 端 和 后 端 ， 就 可 以 仅 改 写 后 端而 生 成 不 同 目 标 机 上 的 目 标 程 序 ， 当 然也 可 考 虑 对 不 同 语 言 仅 稍 加 改 变 前 端 而产 生 相 同 的 中 间 代 码 ， 经 同 一 后 端

33、生 成相 同 目 标 机 的 目 标 代 码 。 就 目 前 来 说 ，针 对 相 同 中 间 代 码 适 应 不 同 目 标 机 的 工作 较 多 ， 如 Ada语 言 的 APSE(Ada程 序 设计 环 境 )中 使 用 的 Diana中 间 代 码 ， Java语 言 定 义 的 虚 拟 机 代 码 Bytecode中间 语 言 ， 都 是 定 义 良 好 的 中 间 语 言 。 CompilerPrinciples 46 Java的 传 统 环 境Java源 程 序(.java)编 译 环 境Java编 译 器Java字 节 码 (.class) Java 字 节 码（ 本 地 或网

34、 络 传 输 ） 运 行 环 境类 加 载 程 序字 节 码 验 证 Java类 库Java解 释 器 即 时 编 译 器Java虚 拟 机硬 件 CompilerPrinciples 47 5.表 格 与 表 格 管 理 表 格 记 录 源 程 序 中 的 各 类 有 用 信 息 名字 、 函 数 、 标 号 、 过 程 、 数 值 等 每 个 阶 段 的 工 作 都 要 与 表 格 打 交 道 ： 查 、填 、 改 等 表 格 的 结 构 与 处 理 方 法 ： 统 一 的 大 表 与 分类 的 小 表 统 一 大 表名 字 栏 为 主 栏 （ 关 键 字 栏 ） ， 信 息 栏 又 分成

35、 若 干 子 栏 种 属 、 类 型 等NAME INFORMATION CompilerPrinciples 48 分 类 小 表 ： 每 类 一 张 表 ， 如 ：符 号 名 表 (SNT)常 数 表 (CT) 3.141592648X 哑 元 实 型A 数 组 整 型 CompilerPrinciples 49DO 编 号 (03) L1 入 口 地 址Swap 二 目 子 程 序 入 口 地 址入 口 表 (ENT)标 号 表 (LBT)基 本 字 表 (KWT) CompilerPrinciples 50 6.出 错 处 理 ： 这 是 编 译 程 序 的 又 一 重 要 组 成 部

36、 分 ，因 为 编 译 的 各 个 阶 段 都 有 可 能 发 现 源程 序 中 的 错 误 。 一 旦 发 现 这 样 或 那 样的 错 误 ， 就 应 把 错 误 的 性 质 及 位 置 报告 给 用 户 ， 并 且 使 编 译 能 继 续 下 去 。思 考 ：l如 何 准 确 地 报 告 错 误l如 何 从 错 误 中 恢 复 过 来 CompilerPrinciples 51 四 、 编 译 程 序 的 构 造 过 程1.需 求 分 析 ， 确 定 语 言 文 本(1)确 定 语 言 的 种 类 ： 按 语 言 范 型 分 类 ， 当 今 大 多 数 程 序 语 言 可 分 为 四 类

37、 ：v 过 程 式 (强 制 式 语 言 )： 命 令 驱 动 ， 面 向 语 句 ， 如FORTRAN、 PASCAL、 Ada及 C等v 函 数 式 (应 用 式 )语 言 ： 功 能 驱 动 ， 面 向 函 数 ， 如LISP、 SNOBOL及 ML等v 逻 辑 式 (基 于 规 则 的 )语 言 ： 依 据 条 件 进 行 逻 辑 推 演 ，如 Prolog等v OO语 言 ： 支 持 封 装 性 、 继 承 性 、 多 态 性 及 动 态 聚束 等 ， 以 对 象 为 运 行 单 位 ， 如 Smalltalk、 Java、C+等 CompilerPrinciples 52 通 过

38、用 户 提 供 的 应 用 范 围 ， 决 定 采 用 何 种 语言 。 例 如 ： 偏 重 于 科 学 计 算 的 则 选 用 Fortran； 偏 重 于 符 号 处 理 的 则 选 用 Lisp或 Snobol； 偏 重 于 事 务 处 理 的 则 选 用 Cobol或 数 据 库 管 理语 言 ； CompilerPrinciples 53 (2)深 刻 理 解 语 言 的 结 构 、 语 法 及 语 义 这 就 是 说 不 仅 仅 是 用 程 序 设 计 语 言 编 几 个 程 序 的问 题 ， 而 是 要 在 语 法 和 语 义 方 面 下 一 些 功 夫 。 具体 说 来 有 以

39、 下 几 个 方 面 ： 程 序 语 言 的 定 义 ： 任 何 程 序 语 言 都 是 某 个 确 定 的 字 符 集 上 的 符 号 按照 一 定 规 则 组 成 的 有 穷 序 列 。 这 里 所 谓 的 规 则 是 从 两 个 方 面 来 谈 的 ： 语 法 规 则 ： 用 于 形 成 和 产 生 一 个 正 确 的 程 序 的 一 组 规 则 。 语 义 规 则 ： 用 于 定 义 程 序 意 义 的 一 组 规 则 。 CompilerPrinciples 54 例 如 ： 从 语 法 的 角 度 看 ， 标 识 符 和 名 字 是 一 个 东西 ， 都 是 以 字 母 开 头 的

40、 字 母 数 字 串 ； 但 从 语义 的 角 度 看 ， 标 识 符 是 一 个 没 有 任 何 意 义 的字 符 序 列 ， 而 名 字 却 有 确 定 的 意 义 和 属 性 ，而 且 具 有 一 定 的 作 用 域 和 定 义 域 ， 即 有 局 部和 全 部 之 分 。又 如 ： 程 序 从 语 法 角 度 看 ， 是 一 些 语 法 范 畴 构 成的 如 下 层 次 结 构 ： CompilerPrinciples 55 程 序分 程 序 或 子 程 序 （ 过 程 、 函 数 等 ）语 句表 达 式数 据 引 用 算 符 函 数 调 用而 从 语 义 的 角 度 来 说 ， 程

41、序 是 描 述 一 定的 数 据 结 构 及 其 处 理 过 程 。 CompilerPrinciples 56 程 序 结 构 ： 现 代 高 级 语 言 程 序 通 常 由 若 干 子 程 序 段（ 过 程 、 函 数 等 ） 构 成 ， 许 多 语 言 还 引 入 了类 、 程 序 包 等 更 高 级 的 结 构 。 例 如 ， Fortran 、 C程 序 是 块 结 构 的 ；Pascal程 序 是 过 程 嵌 套 的 ； Algol既 有 分 程 序嵌 套 ， 又 有 过 程 嵌 套 ； Java与 C+是 面 向 对 象的 ， 它 们 很 重 要 的 方 面 是 类 和 继 承

42、的 概 念 ，同 时 支 持 多 态 性 和 动 态 聚 束 等 特 性 ； 而 在 Ada中 引 入 了 程 序 包 ， 它 可 以 把 数 据 和 操 作 代 码封 装 在 一 起 ， 支 持 数 据 抽 象 。 （ 详 见 教 材 P 15-18） CompilerPrinciples 57 语 言 的 基 本 成 分 ： 包 括 数 据 类 型 、 表 达 式 、 语 句 、 过 程 或 函 数 等 ，这 些 在 学 习 语 言 课 时 都 已 经 学 过 了 ， 但 从 编 译 的 角度 出 发 ， 应 如 何 了 解 这 些 基 本 成 分 呢 ？ 初 等 数 据 类 型 ： 牵

43、扯 到 存 储 空 间 的 问 题 ； 结 构 数 据 类 型 ： 牵 扯 到 下 标 、 维 数 、 存 放 方 式 、 分 配 时 间 -动 态 与 静 态 等 ； 表 达 式 ： 牵 扯 到 运 算 分 量 、 运 算 符 、 形 成 规 则 、 运 算 顺 序 等 ； 语 句 ： 顺 序 、 控 制 、 循 环 等 ； 过 程 与 参 数 传 递 ： 传 地 址 、 传 值 、 传 名 、 得 结 果 等 ； 存 储 管 理 ： 静 态 存 储 分 配 、 动 态 存 储 分 配 ； CompilerPrinciples 58 2.由 程 序 设 计 环 境 确 定 编 译 程 序 构

44、 造 的 方 式和 方 法 最 早 是 直 接 使 用 机 器 语 言 或 汇 编 语 言 现 在 一 般 使 用 高 级 语 言 Pascal或 C语 言好 处 ： 编 译 方 式 还 是 解 释 方 式 便 于 阅 读 、 理 解 和 移 植 提 高 程 序 设 计 效 率 易 于 查 错 和 修 改 CompilerPrinciples 59 任 何 一 个 编 译 程 序 至 少 要 涉 及 三 种 语言 ： 源 语 言 （ S） 、 目 标 语 言 （ T） 和编 译 程 序 实 现 语 言 （ I） ， 可 用 如 下 T型图 来 表 示 三 者 之 间 的 关 系 ：S TI C

45、ompilerPrinciples 60Ada语 言 A代 码 Ada语 言 A代 码C C A代 码 A代 码A代 码用 C语 言 编 写 Ada编 译 程 序 如 若 A机 上 已 经 有 了 一 个 用 A机 器 语 言 （ 称A代 码 ） 实 现 的 C语 言 编 译 程 序 ， 则 可 用 C语 言 作 为 工 具 编 写 Ada语 言 的 编 译 程 序 。 这样 Ada语 言 的 编 译 程 序 经 过 C语 言 编 译 程 序编 译 后 就 可 得 到 A代 码 的 Ada语 言 编 译 程 序 。可 图 示 如 下 ： CompilerPrinciples 61 l 现 在

46、常 用 构 造 编 译 程 序 的 方 式 除 高 级 语 言 实现 外 ， 经 常 还 用 ：v自 展 （ 自 编 译 ） ： 类 似 于 滚 雪 球 。 先 确 定 一个 非 常 简 单 的 核 心 L0， 用 低 级 语 言 写 出 其 编译 程 序 C0。 再 把 L0扩 充 为 L1 ， ，并 用 L0来 编 写 L1的 编 译 程 序 。 如 此 逐 渐 扩 展下 去 ， 可 得 到 一 个 系 统 编 程 语 言 族 ：而 Lk便 是 我 们 要 编 译 的 语 言 ， 其 编 译 程 序Ck可 用 Lk-1编 写 。 这 种 滚 雪 球 式 的 自 展 方 法可 大 大 减 少

47、 开 发 工 作 量 。 kLLLL 210 10 LL CompilerPrinciples 62 交 叉 编 译 ： 在 机 器 A上 产 生 机 器 B的 目 标 代码 ， 这 种 编 译 程 序 称 为 交 叉 编 译 。 这 儿 A称宿 主 机 ， B称 为 目 标 机 。 这 种 情 况 一 般 是 宿主 机 上 有 丰 富 的 工 具 软 件 ， 而 B机 上 没 有 任何 高 级 语 言 可 用 。 图 示 为 ：C B代 码 C B代 码C C B代 码 B代 码A代 码 CompilerPrinciples 63 移 植 ： 如 果 一 个 程 序 能 比 较 容 易 地

48、从 一台 机 器 上 搬 到 另 一 台 机 器 上 运 行 ， 则 称其 为 可 移 植 的 ， 移 植 一 个 程 序 的 工 作 量要 远 小 于 开 发 它 的 工 作 量 才 有 意 义 。 显 然 一 个 编 译 程 序 要 可 移 植 ， 则 其前 端 与 后 端 的 界 面 要 清 晰 、 简 单 ， 这 样仅 需 改 写 后 端 即 可 。 改 写 后 亦 可 通 过 交叉 编 译 的 方 法 得 到 。 CompilerPrinciples 64 编 译 程 序 生 成 器 ： 根 据 语 言 要 求 、 设 计实 现 的 算 法 ， 能 自 动 产 生 编 译 程 序 的

49、 工具 软 件 。 可 图 示 为 ： CompilerPrinciples 65 3.确 定 编 译 方 法 ： 本 课 程 要 介 绍 若 干 方法 ， 但 不 可 能 全 采 用 ， 只 能 根 据 语言 特 点 采 用 其 中 一 种 或 二 种4.总 体 设 计 ： 分 不 分 遍 、 分 几 遍 、 前 端与 后 端 接 口 并 画 出 总 框5.详 细 设 计 ： 进 一 步 细 划 总 框6.实 现 及 调 试 ： 采 用 何 种 方 式 实 现 、 分调 与 连 调 等 CompilerPrinciples 66 本 节 目 的 ：为 语 言 的 语 法 描 述 寻 求 形

50、式 化 工 具 工 具 就 是 对 程 序 设 计 语 言 给 出 精 确 无 二义 的 语 法 描 述 。 （ 严 谨 、 简 洁 、 易 读 ） 形 式 化 工 具 就 是 将 形 式 语 言 抽 象 地 定 义为 一 个 数 学 系 统 。 “ 形 式 ” 是 指 这 样 的 事实 ： 语 言 的 所 有 规 则 是 以 什 麽 符 号 串 能 出现 的 方 式 来 陈 述 。 3.高 级 语 言 的 语 法 描 述 CompilerPrinciples 67 本 节 主 要 内 容 预 备 知 识 上 下 文 无 关 文 法 及 其 语 言 的 形 式 定 义 文 法 的 等 价 性

51、语 法 树 及 文 法 二 义 性 文 法 的 类 型 语 法 分 析 的 一 些 思 考 CompilerPrinciples 68 一 、 预 备 知 识1.文 法 的 直 观 概 念 当 我 们 表 述 一 种 语 言 时 ， 无 非 是 说 明 这 种 语 言的 句 子 ， 如 果 语 言 只 含 有 有 穷 多 个 句 子 ， 则 只 需 列出 句 子 的 有 穷 集 就 行 了 ， 但 对 于 含 有 无 穷 多 个 句 子的 语 言 来 讲 ， 存 在 着 如 何 给 出 它 有 穷 表 示 的 问 题 。 以 自 然 语 言 为 例 ， 人 们 无 法 列 出 全 部 句 子

52、， 但是 人 们 可 以 给 出 一 些 规 则 ， 用 这 些 规 则 来 说 明 (或 者定 义 )句 子 的 组 成 结 构 ， 比 如 汉 语 句 子 可 以 是 由 主 语后 随 谓 语 而 成 ， 构 成 谓 语 的 是 动 词 和 直 接 宾 语 。 例 如 ： CompilerPrinciples 69 “ 我 是 大 学 生 ” 是 汉 语 的 一 个 句 子对 该 句 子 我 们 可 以 通 过 下 列 一 组 规 则 描 述 ： 句 子 = 主 语 谓 语 主 语 = 代 词 名 词 代 词 = 我 你 他 名 词 = 王 明 大 学 生 工 人 英 语 谓 语 = 动

53、词 直 接 宾 语 动 词 = 是 学 习 直 接 宾 语 = 代 词 名 词 有 了 这 组 规 则 以 后 ， 可 按 如 下 方 式 导 出 句 子 ： 先 找 =左 端 的 带 有 句 子 的 规 则 ， 并 将 它 用 =右 端 的 符 号 串 代 替 ， 于 是 表 示 成 ： CompilerPrinciples 70 句 子 主 语 谓 语 然 后 在 得 到 的 串 主 语 谓 语 中 ， 选 取 主语 或 谓 语 ， 再 用 相 应 规 则 的 =右 端 代 替 之 。比 如 ， 选 取 了 主 语 ， 并 采 用 规 则 主 语 = 代 词 ， 那 么 得 到 ： 主 语

54、 谓 语 代 词 谓 语 依 此 类 推 ， 句 子 “ 我 是 大 学 生 ” 的 全 部 导 出 过 程 是 ： 句 子 主 语 谓 语 代 词 谓 语 我 谓 语 我 动 词 直 接 宾 语 我 是 直 接 宾 语 我 是 名 词 我 是 大 学 生 CompilerPrinciples 71 “ 我 是 大 学 生 ” 的 构 成 符 合 上 述 规 则 ， 而“ 我 大 学 生 是 ” 不 符 合 上 述 规 则 ， 我 们 说 它不 是 句 子 。 这 些 规 则 成 为 我 们 判 别 句 子 结 构合 法 与 否 的 依 据 。 换 句 话 说 ， 这 些 规 则 看 成是 一

55、 种 元 语 言 ， 用 它 描 述 汉 语 ， 仅 仅 涉 及 汉语 句 子 的 结 构 描 述 。 这 里 “ ” 读 作 “ 导 出 ” 或 “ 派 生 出 ” 。 而 “ :=”（ 通 常 又 简 记 为 “ ” ） 读 作“ 定 义 为 ” 或 “ 由 组 成 ” ， 而 每 一 条 规 则又 称 作 是 产 生 式 或 重 写 式 。 这 样 的 一 种 描 述形 式 就 称 作 是 BNF（ Backus-Naur Form） 。 CompilerPrinciples 72 v例 ： 赋 值 表 达 式 可 描 述 为 = | a1|b123|salary|stu_age 18|

56、123|4.5| + |- |* |/ CompilerPrinciples 73 2.语 言 概 述语 言 是 由 句 子 组 成 的 集 合 。汉 语 -所 有 符 合 汉 语 语 法 的 句 子 的 全 体 。英 语 -所 有 符 合 英 语 语 法 的 句 子 的 全 体 。程 序 设 计 语 言 -所 有 符 合 该 语 言 语 法 的 程 序 的 全 体 。 每 个 句 子 构 成 的 规 则研 究 语 言 每 个 句 子 的 含 义 每 个 句 子 和 使 用 者 的 关 系 CompilerPrinciples 74 研 究 程 序 设 计 语 言 每 个 程 序 构 成 的

57、规 则 每 个 程 序 的 含 义 每 个 程 序 和 使 用 者 的 关 系语 言 研 究 的 三 个 方 面 : 语 法 (Syntax) - 表 示 构 成 语 言 句 子 的 各 个 记 号 之 间 的 组 合 规 则 语 义 (Semantics) - 表 示 各 个 记 号 的 特 定 含 义 。 （ 各 个 记 号 和 记 号 所 表 示 的 对 象 之 间 的 关 系 ） 语 用 (Pragmatics) -表 示 在 各 个 记 号 所 出 现 的 行 为 中 ， 它 们 的 来 源 、 使 用 和 影 响 。 CompilerPrinciples 75 每 种 语 言 具

58、有 两 个 可 识 别 的 特 性 ， 即 语言 的 形 式 和 该 形 式 相 关 联 的 意 义 。 语 言 的 实 例 若 在 语 法 上 是 正 确 的 ， 其 相关 联 的 意 义 可 以 从 两 个 观 点 来 看 ， 其 一 是 该句 子 的 创 立 者 所 想 要 表 示 的 意 义 ， 另 一 是 接收 者 所 检 验 到 的 意 义 。 这 两 个 意 义 并 非 总 是一 样 的 ， 前 者 称 为 语 言 的 语 义 ， 后 者 是 其 语用 意 义 。 幽 默 、 双 关 语 和 谜 语 就 是 利 用 这 两方 面 意 义 间 的 差 异 。 CompilerPri

59、nciples 76 如 果 不 考 虑 语 义 和 语 用 ， 即 只 从 语 法这 一 侧 面 来 看 语 言 ， 这 种 意 义 下 的 语 言 称作 形 式 语 言 。 形 式 语 言 抽 象 地 定 义 为 一 个数 学 系 统 。 该 数 学 系 统 称 为 文 法 。 “ 形 式 ”是 指 这 样 的 事 实 ： 语 言 的 所 有 规 则 描 述 什麽 符 号 串 以 什 么 方 式 出 现 。 形 式 语 言 理 论是 对 符 号 串 集 合 的 表 示 法 、 结 构 及 其 特 性的 研 究 ， 是 程 序 设 计 语 言 语 法 分 析 研 究 的基 础 。 Compi

60、lerPrinciples 77 3.有 关 定 义 和 记 号 回 顾符 号 ： 可 以 相 互 区 别 的 记 号 （ 元 素 ） 。字 母 表 ： 符 号 （ 元 素 ） 的 非 空 有 穷 集 合 。符 号 串 (字 )： 由 字 母 表 中 的 符 号 组 成 的 任 何 有穷 序 列 称 为 该 字 母 表 上 的 符 号 串 。 空 字 (没 有 符 号 的 符 号 串 )是 上 的 符 号 串 ； 若 x是 上 的 符 号 串 ,a是 的 元 素 ,则 xa是 上 的 符 号 串 ； y是 上 的 符 号 串 ,当 且 仅 当 它 可 以 由 和 导 出 。 例 如 ： =a,

61、b ,a,b,aa,ab,aabba 都 是 上 的 符 号 串 CompilerPrinciples 78 符 号 串 s的 前 缀 ： 符 号 串 s的 任 何 首 部 。 如 :、 b、 ba、 都 是 符 号 串 banana的 前 缀 . 符 号 串 s的 后 缀 ： 符 号 串 s的 任 何 尾 部 。 如 : 、 a、 na、 都 是 符 号 串 banana的 后 缀 .符 号 串 s的 子 串 ： 从 s中 删 去 一 个 前 缀 和 一 个 后 缀得 到 的 符 号 串 . 如 :ana是 符 号 串 banana的 一 个 子 串 .符 号 串 s的 真 前 缀 ： xs

62、且 x的 任 何 前 缀 x。s的 真 后 缀 ， 真 子 串 可 以 类 似 地 定 义 。 CompilerPrinciples 79 符 号 串 的 运 算 ： 符 号 串 的 长 度 ： 符 号 串 中 符 号 的 个 数 .符 号 串 s 的 长度 记 为 |s|。 的 长 度 为 0连 接 ： 符 号 串 x、 y的 连 接 ,是 把 y的 符 号 写 在 x的 符 号 之 后 得 到 的 符 号 串 xy 如 x=ab,y=cd 则 xy=abcd 又 如 a = a 方 幂 ： 符 号 串 自 身 连 接 n次 得 到 的 符 号 串 a n 定 义 为 aa aa n个 a

63、a0= ,a1=a, a2=aa CompilerPrinciples 80 符 号 串 集 合 ： 若 集 合 A中 所 有 元 素 都 是 某 字 母表 上 的 符 号 串 ， 则 称 A为 字 母 表 上 的 符 号串 集 合 。符 号 串 集 合 A和 B的 乘 积 ： AB =xy|xA且 yB 若 集 合 A=ab,cde B = 0,1 则 AB =ab1,ab0,cde0,cde1 的 闭 包 ： 上 的 一 切 符 号 串 （ 包 括 ） 组 成的 集 合 ， 记 为 * 。 的 正 闭 包 ： 上 的 除 外 的 所 有 符 号 串 组成 的 集 合 ， 记 为 + 。 C

64、ompilerPrinciples 81 例 ： =a,b *= ,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab, . 2* . 32* CompilerPrinciples 82 语 言 ： 由 句 子 构 成 的 集 合 。 换 言 之 ,字 母 表 上的 一 个 语 言 是 上 的 一 些 符 号 串 的 集 合 (字 母表 上 的 每 个 语 言 是 *的 一 个 子 集 )。例 如 ： 字 母 表 =a,b, *= ,a,b,aa,ab,ba,bb,aaa,aab, 集 合 ab,aabb,aaabbb, ,anbn, 或 表

65、示 为w|w *且 w=anbn,n 1为 字 母 表 上 的 一 个 语 言 。集 合 a,aa,aaa, 或 表 示 为 w|w *且 w=an,n 1 为 字 母 表 上 的 一 个 语 言 。 是 一 个 语 言 ， 即 也 是 一 个 语 言 。 CompilerPrinciples 83 二 、 上 下 文 无 关 文 法 及 其 语 言 的 形 式 定 义1.如 何 来 描 述 一 种 语 言 ？ 如 果 语 言 是 有 穷 的 （ 只 含 有 有 穷 多 个 句 子 ） ， 可以 将 句 子 逐 一 列 出 来 表 示 ； 如 果 语 言 是 无 穷 的 ， 找 出 语 言 的

66、 有 穷 表 示 。语 言 的 有 穷 表 示 有 两 个 途 径 ： 生 成 方 式 ： 语 言 中 的 每 个 句 子 可 以 用 严 格 定 义 的规 则 来 构 造 。 识 别 方 式 ： 用 一 个 过 程 ， 当 输 入 的 一 任 意 串 属 于语 言 时 ， 该 过 程 经 有 限 次 计 算 后 就 会 停 止 并 回 答“ 是 ” ， 若 不 属 于 ， 要 麽 能 停 止 并 回 答 “ 不 是 ” ，要 麽 永 远 继 续 下 去 。 CompilerPrinciples 84 文 法 是 从 生 成 方 式 描 述 语 言 的 ， 而 自 动 机 则 是 从 识 别 的角 度 来 描 述 语 言 的 。 本 节 仅 介 绍 有 关 文 法 的 概 念 。 前 面 关 于 “我 是 大 学 生 ”及 “赋 值 表 达 式 ”的 例 子 中 ， 涉 及 到如 下 的 概 念 ：l 所 表 示 的 是 一 个 类 概 念 ， 通 常 称 作 语 法 范 畴 或 语 法 变 量 ， 如 果用 一 个 符 号 来 代 替 ,也 称 为 非 终 结 符 (nontermi