《编译原理和技术》PPT课件

编 译 原 理 和 技 术 http:/ 课 程 简 介课 程 内 容 介 绍 编 译 器 构 造 的 一 般 原 理 和 基 本 实 现 方 法 包 括 的 理 论 知 识 ： 形 式 语 言 和 自 动 机 理 论 、 语 法制 导 的 定 义 和 属 性 文 法 、 类 型 论 与 类 型 系 统 、 程序 分 析 原 理 等 强 调 形 式 描 述 技 术 和 自 动 生 成 技 术 强 调 对 编 译 原 理 和 技 术 的 宏 观 理 解 ， 不 把 注 意 力分 散 到 枝 节 算 法 ， 不 偏 向 于 任 何 源 语 言 或 目 标 机器 http:/ 课 程 简 介学 习 意 义 对 编 程 语 言 的 设 计 和 实 现 有 深 刻 的 理 解 ， 对 和 编程 语 言 有 关 的 理 论 有 所 了 解 ， 对 宏 观 上 把 握 编 程语 言 来 说 ， 起 一 个 奠 基 的 作 用 从 软 件 工 程 看 ， 编 译 器 是 一 个 很 好 的 实 例 ， 所 介绍 的 概 念 和 技 术 能 应 用 到 一 般 的 软 件 设 计 之 中 编 译 技 术 的 应 用 和 编 译 技 术 的 发 展高 级 语 言 设 计 、 计 算 机 体 系 结 构 的 优 化 （ 并 行 、 内存 分 层 ） 、 新 型 计 算 机 体 系 结 构 设 计 、 程 序 翻 译 、提 高 软 件 开 发 效 率 的 工 具 、 高 可 信 软 件 http:/ 课 程 简 介教 材 和 参 考 书 陈 意 云 、 张 昱 ， 编 译 原 理 ， 高 等 教 育 出 版 社 ，2008 张 昱 、 陈 意 云 ， 编 译 原 理 实 验 教 程 ， 高 等 教 育 出版 社 ， 2009 A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools , 2nd edition, Addison-Wesley, 2007 陈 意 云 、 张 昱 ， 编 译 原 理 习 题 精 选 与 解 析 ， 高 等教 育 出 版 社 ， 2005 教 学 资 源 网 页 ： http:/ http:/ http:/ dae_meng 课 程 简 介课 程 要 求 质 量 上 的 目 标 ： 师 生 共 同 努 力 ， 达 国 内 最 好 水 平 讲 课 进 展 较 快 ， 平 时 不 复 习 并 加 深 理 解 ， 后 面 将听 不 懂 作 业 ： 少 而 精 ， 周 一 课 间 交 作 业 课 程 设 计 ： 自 己 动 手 ， 大 有 收 获 考 试 ： 开 卷 ， 灵 活 运 用 知 识 学 期 总 评 = 考 试 成 绩 占 60%， 作 业 占 10%， 课 程设 计 30% 上 课 、 设 计 、 考 试 时 间 大 体 安 排 http:/ 课 程 简 介课 程 设 计 要 求 内 容 ： 独 立 地 研 发 扩 展 PL/0语 言 的 编 译 器 和 解 释器 目 标 ： 巩 固 对 理 论 和 技 术 的 理 解 ， 提 高 程 序 设 计能 力 技 术 准 备 ： VC+的 编 程 环 境 ， C语 言 编 程 考 查 与 评 分 ： 对 截 止 时 间 前 提 交 的 程 序 ， 通 过 测试 和 答 辩 进 行 公 开 评 分 前 四 年 课 程 设 计 的 经 验 和 教 训 对 该 课 程 设 计 的 综 合 性 认 识 不 足 对 考 查 的 “ 动 真 格 ” 认 识 不 足http:/ 对 课 程 的 评 论 本 校 少 年 班 1994级 一 个 同 学 ， Stanford大 学博 士 （ 1999年 ） Actually I think the quality of the compiler course in USTC is really very good and can be compared with any universities here. 本 系 某 考 研 同 学 （ 2006年 ）感 觉 您 出 的 题 目 很 有 创 意 ， 也 很 有 深 度 ， 没 有局 限 于 固 定 的 算 法 和 题 型 ， 只 看 课 本 和 复 习 往 年 的题 目 而 不 深 入 思 考 的 人 是 做 不 出 来 的 ， 能 够 真 正 从本 质 上 考 察 一 个 考 生 的 水 平 http:/ 对 课 程 的 评 论 西 南 科 技 大 学 某 考 研 学 生 （ 2004年 ）看 过 你 编 的 书 后 ， 感 觉 编 译 的 原 理 可 以 一 下 子和 我 平 常 学 的 很 多 学 科 和 语 言 都 联 系 起 来 了 ， 可 以学 到 很 多 可 以 实 际 用 到 的 东 西 ， 虽 然 是 在 讲 同 样 的东 西 ， 但 您 的 教 学 方 式 让 我 很 适 应 ， 学 起 来 也 很 有兴 趣 ， 大 大 减 轻 了 我 考 研 的 疲 劳 感 http:/ 第 一 章 引 论 名 词 解 释 翻 译 器 (translator)、 编 译 器 (compiler) 解 释 器 (interpreter) 编 译 器 从 逻 辑 上 可 以 分 成 若 干 个 阶 段 每 个 阶 段 把 源 程 序 从 一 种 表 示 变 换 成 另 一 种表 示 本 章 通 过 描 述 编 译 器 的 各 个 阶 段 来 介 绍 编 译这 个 课 题 http:/ 1.1 编 译 器 概 述词 法 分 析 器语 法 分 析 器语 义 分 析 器源 程 序中 间 代 码 生 成 器 独 立 于 机 器 的 代 码 优 化 器代 码 生 成 器依 赖 于 机 器 的 代 码 优 化 器目 标 机 器 代 码符 号 表 http:/ 符 号 表 positioninitialrate . . . . . . .123词 法 分 析 器id, 1 = id, 2 + id, 3 60position = initial + rate 601.1 编 译 器 概 述 记 号 流 字 符 流 http:/ 1.1 编 译 器 概 述表 达 式 的 语 法 特 征 任 何 一 个 标 识 符 都是 表 达 式 任 何 一 个 数 都 是 表达 式 如 果 e1和 e2都 是 表达 式 ， 那 么 e1 + e2 e 1 * e2 (e1)也 都 是 表 达 式 表 达 式表 达 式 表 达 式标 识 符 表 达 式表 达 式(initial) 标 识 符(rate) 数(60)*+initial + rate * 60的 分 析 树http:/ 符 号 表 positioninitialrate . . . . . . .123语 法 分 析 器id, 1 = id, 2 + id, 3 60= + 60id, 1 id, 2id, 3 语 法 树1.1 编 译 器 概 述 记 号 流 http:/ 符 号 表 positioninitialrate . . . . . . .1231.1 编 译 器 概 述语 义 分 析 器= + 60id, 1 id, 2id, 3= + inttofloatid, 1 id, 2id, 3 60 语 法 树 语 法 树 http:/ 符 号 表 positioninitialrate . . . . . . .123中 间 代 码 生 成 器t1 = inttofloat(60)t2 = id3 t1t3 = id2 + t2id1 = t3= + inttofloatid, 1 id, 2id, 3 601.1 编 译 器 概 述 三 地 址 中 间 代 码 语 法 树 http:/ 符 号 表 positioninitialrate . . . . . . .123代 码 优 化 器t1 = inttofloat(60)t2 = id3 t1t3 = id2 + t2id1 = t3t1 = id3 * 60.0id1 = id2 + t11.1 编 译 器 概 述 三 地 址 中 间 代 码 三 地 址 中 间 代 码 http:/ 符 号 表 positioninitialrate . . . . . . .123代 码 生 成 器MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1t1 = id3 * 60.0id1 = id2 + t11.1 编 译 器 概 述 三 地 址 中 间 代 码 汇 编 代 码 http:/ 1.1 编 译 器 概 述解 释 器 和 编译 器 的 区 别词 法 分 析 器语 法 分 析 器语 义 分 析 器源 程 序中 间 代 码 生 成 器 独 立 于 机 器 的 代 码 优 化 器代 码 生 成 器依 赖 于 机 器 的 代 码 优 化 器目 标 机 器 代 码解 释 器 不 生 成 目 标 代码 ， 而 是 直 接 执 行 源程 序 所 指 定 的 运 算 解 释 器 也 需要 对 源 程 序进 行 词 法 、语 法 和 语 义分 析 ,中 间代 码 生 成 http:/ 1.1 编 译 器 概 述 BASIC年 代 的 解 释 器 功 能 ： 它 将 高 级 语 言 的 源 程 序 翻 译 成 一 种 中 间 语言 程 序 ， 然 后 对 中 间 语 言 程 序 进 行 解 释 执 行 在 那 个 年 代 ， 编 译 和 解 释 两 个 功 能 是 合 在 一 个 程序 中 ， 该 程 序 被 称 为 解 释 器 Java年 代 的 解 释 器 上 述 两 个 功 能 分 在 两 个 程 序 中 前 一 个 叫 做 编 译 器 ， 它 把 源 程 序 翻 译 成 一 种 叫 做字 节 码 的 中 间 语 言 程 序 后 一 个 叫 做 解 释 器 ， 它 对 字 节 码 程 序 进 行 解 释 执行 http:/ 1.1 编 译 器 概 述 阶 段 分 组前 端后 端词 法 分 析 器语 法 分 析 器语 义 分 析 器源 程 序中 间 代 码 生 成 器 独 立 于 机 器 的 代 码 优 化 器代 码 生 成 器依 赖 于 机 器 的 代 码 优 化 器目 标 机 器 代 码 http:/ 1.1 编 译 器 概 述词 法 分 析 器语 法 分 析 器语 义 分 析 器源 程 序中 间 代 码 生 成 器 独 立 于 机 器 的 代 码 优 化 器代 码 生 成 器依 赖 于 机 器 的 代 码 优 化 器目 标 机 器 代 码阶 段 分 组遍 http:/ 1.2 编 译 器 技 术 的 应 用 高 级 语 言 的 实 现 高 级 编 程 语 言 易 于 编 程 ， 但 程 序 运 行 较 慢 低 级 语 言 编 程 时 可 实 施 更 有 效 的 控 制 方 式 ， 得 到更 有 效 的 代 码 ， 但 难 编 写 、 易 出 错 、 难 维 护 流 行 编 程 语 言 的 大 多 数 演 变 都 是 朝 着 提 高 抽 象 级别 的 方 向 每 一 轮 编 程 语 言 新 特 征 的 出 现 都 刺 激 编 译 器 优 化的 新 研 究 http:/ 1.2 编 译 器 技 术 的 应 用 高 级 语 言 的 实 现每 一 轮 编 程 语 言 新 特 征 的 出 现 都 刺 激 编 译 器 优化 的 新 研 究 支 持 用 户 定 义 的 聚 合 数 据 类 型 和 高 级 控 制 流 ， 如数 组 和 记 录 、 循 环 和 过 程 调 用 ： C、 Fortran 面 向 对 象 的 主 要 概 念 是 数 据 抽 象 和 性 质 继 承 ， 使得 程 序 更 加 模 块 化 并 易 于 维 护 ： Smalltalk、 C+、C#、 Java 类 型 安 全 的 语 言 ： Java没 有 指 针 ， 也 不 允 许 指 针算 术 。 它 用 无 用 单 元 收 集 机 制 来 自 动 地 释 放 那 些不 再 使 用 的 变 量 占 据 的 内 存 Java设 计 来 支 持 代 码 移 植 和 代 码 移 动 http:/ 1.2 编 译 器 技 术 的 应 用 针 对 计 算 机 体 系 结 构 的 优 化 计 算 机 体 系 结 构 的 迅 速 演 化 引 起 对 新 的 编 译 器 技术 一 种 不 知 足 的 需 要 并 行 化 编 译 器 重 新 整 理 指 令 ， 使 得 指 令 级 并 行 更 有 效 编 译 器 从 传 统 的 串 行 程 序 自 动 生 成 并 行 代 码 ，使 之 运 行 于 多 处 理 器 上 内 存 分 层 编 译 器 优 化 历 来 集 中 在 优 化 处 理 器 的 执 行 上 ，但 是 现 在 更 强 调 要 使 内 存 分 层 更 有 效 http:/ 1.2 编 译 器 技 术 的 应 用 新 计 算 机 体 系 结 构 的 设 计 现 在 计 算 机 系 统 的 性 能 不 仅 仅 取 决 于 它 的 原 始 速度 ， 还 取 决 于 编 译 器 是 否 能 生 成 充 分 利 用 其 特 征的 代 码 在 现 代 计 算 机 体 系 结 构 的 研 究 中 ， 在 处 理 器 的 设计 阶 段 就 开 发 编 译 器 ， 并 将 编 译 生 成 的 代 码 在 模拟 器 上 运 行 ， 以 评 价 拟 采 用 体 系 结 构 的 特 征 编 译 器 技 术 影 响 计 算 机 体 系 结 构 设 计 的 一 个 著 名例 子 是 精 简 指 令 集 计 算 机 （ RISC） 的 发 明 http:/ 1.2 编 译 器 技 术 的 应 用 程 序 翻 译 二 进 制 翻 译 编 译 器 技 术 可 用 于 把 一 种 机 器 的 二 进 制 代 码 翻 译成 另 一 种 机 器 的 代 码 ， 以 运 行 原 先 为 别 的 指 令 集编 译 的 代 码 数 据 库 查 询 解 释 器 数 据 库 查 询 由 一 些 谓 词 组 成 ， 这 些 谓 词 由 包 含 关系 运 算 的 布 尔 表 达 式 组 成 ， 可 以 被 解 释 执 行 ,也 可以 被 编 译 成 搜 索 数 据 库 的 命 令 http:/ 1.2 编 译 器 技 术 的 应 用 提 高 软 件 开 发 效 率 的 工 具源 于 编 译 器 中 代 码 优 化 技 术 的 程 序 分 析 一 直 在改 进 软 件 开 发 效 率 类 型 检 查 类 型 检 查 是 一 种 捕 捉 程 序 中 前 后 不 一 致 的 成 熟 而有 效 的 技 术 边 界 检 查 数 据 流 分 析 技 术 可 用 来 定 位 缓 冲 区 溢 出 内 存 管 理 自 动 的 内 存 管 理 删 除 内 存 泄 漏 等 内 存 管 理 错 误 http:/