《编译原理 绪论》PPT课件

1 编 译 原 理 2 题 外 话 一 、 本 课 程 讨 论 的 领 域 和 希 望 达 到 的 目 的1 2 CCC 2002 中 国 计 算 机 科 学 与 技 术 学 科 专 业 发 展 战 略 研 究 报 告 与 专 业 规 范（ 试 行 ） 提 出 了 计 算 机 科 学 与 技 术 学 科 的 知 识 体 系 ， 包 括 了 141个 基本 的 知 识 领 域 。 与 本 课 程 相 关 的 ： 1 程 序 设 计 基 础 （ PF） ： 程 序 设 计 基 本 结 构 、 算 法 与 问 题 求 解 、基 本 数 据 结 构 、 递 归 、 事 件 驱 动 程 序 设 计 。 （ PLA） 2 程 序 设 计 语 言 （ PL） ： 程 序 设 计 语 言 概 论 、 虚 拟 机 、 语 言 翻译 简 介 、 声 明 和 类 型 、 抽 象 机 制 、 面 向 对 象 程 序 设 计 （ 以 上 是 核 心 ） ； 函 数 程 序 设 计 、 语 言 翻 译 系 统 、 类 型 系 统 、 程 序 设 计 语 言 的语 义 、 程 序 设 计 语 言 的 设 计 （ 以 上 是 选 修 ） 。 （ PLA、 PLT、 PLD） 1 1 领 域程 序 设 计 语 言 的 应 用 程 序 设 计 （ PLA）程 序 设 计 语 言 的 翻 译 编 译 器 的 构 造 （ PLT）程 序 设 计 语 言 的 设 计 语 法 、 语 义 （ PLD） 3 题 外 话 （ 续 1）1 3 目 的1 了 解 PL的 基 本 要 素 、 工 作 原 理 、 语 言 翻 译 的 基 本 方 法 ；2 用 不 同 的 PL进 行 程 序 设 计 ， 即 自 学 计 算 机 语 言 的 能 力 ；3 具 备 语 言 翻 译 的 基 本 技 能 。二 、 学 习 方 法 2 1 本 课 程 的 特 点 理 论 与 实 践 并 重 理 论 学 习 要 严 谨 、 方 法 掌 握 要 灵 活 提 高 自 学 能 力 （ push与 pull）2 2 理 论 与 技 术 的 关 系 适 应 飞 速 变 化 的 技 术 的 根 本 是 注 重 基 础 理 论 学 习 理 论 的 演 变 是 缓 慢 的 、 理 论 基 础 是 相 通 的 相 同 的 原 理 可 以 应 用 于 不 同 的 技 术 4 题 外 话 （ 续 2）2 3 勤 动 手 、 多 实 践 、 提 高 学 习 能 力 学 到 的 知 识 是 死 的 ， 总 有 过 时 的 时 候 。 只 有 通 过 学 习 知 识提 高 学 习 能 力 ， 才 是 立 于 不 败 之 地 的 保 证 。 记 笔 记 ： 好 记 性 不 如 烂 笔 头 ， 通 过 动 手 加 深 理 解 和 记 忆 。 做 作 业 、 做 上 机 题 ： 自 己 动 手 为 主 ， 参 考 “ 解 答 ” 为 辅 。 2 4 如 何 使 用 习 题 与 上 机 题 解 答 合 理 利 用 “ 解 答 ” 有 助 于 课 程 学 习 。 “ 解 答 ” 既 不 完 全 正确 也 不 是 最 好 的 。 习 题 解 答 ： 先 做 作 业 ， 后 看 解 答 。 如 不 符 ， 思 考 原 因 ， 找出 最 好 答 案 。 上 机 解 答 ： 先 看 题 目 要 求 ， 根 据 要 求 自 己 设 计 并 实 现 。 如有 困 难 ， 部 分 参 考 解 答 。 提 倡 独 立 思 考 ， 对 发 现 解 答 错 误 并 给 出 正 确 解 法 、 做 出 选做 题 和 上 机 题 扩 充 部 分 者 ， 给 予 加 分 奖 励 。 （ 只 给 第 一 组 ， 写 明 姓 名 、 日 期 。 加 分 按 人 平 分 ） 根 据 需 要 上 习 题 课 。 5 题 外 话 （ 续 3）三 、 其 他3 1 课 代 表 与 辅 导 课 代 表 的 职 责 ： 收 缴 作 业 ； 安 排 上 机 时 间 、 联 系 上 机 事 宜 ；反 映 同 学 意 见 ； 监 督 老 师 的 工 作 。 辅 导 时 间 ： 每 周 一 次 ， 课 代 表 与 同 学 商 量 后 确 定 。3 2 作 业 与 上 机 作 业 第 二 、 五 章 收 缴 一 次 ， 第 三 、 四 章 收 缴 两 次 。 有 独 立 见 解 的可 直 接 交 给 主 讲 老 师 ， 包 括 指 出 解 答 的 错 误 并 给 出 正 确 答 案 、选 做 题 答 案 等 。 （ 仅 以 第 一 个 收 到 的 为 准 ， 包 括 上 届 ） 验 收 上 机 题 ， 并 收 缴 上 机 报 告 。 报 告 内 容 根 据 个 人 对 题 目 要求 的 理 解 写 。 6 题 外 话 （ 续 4）中 文 ： 清 华 大 学 出 版 社 ， 吕 映 芝 等 ， “ 编 译 原 理 ” 国 防 工 业 出 版 社 ， 陈 火 旺 等 ， “ 程 序 设 计 语 言 编 译 原 理 ”（ 第 三 版 ） 西 北 工 业 大 学 出 版 社 ， 蒋 立 源 等 ， “ 编 译 原 理 ”3 3 参 考 书 目英 文 ： 人 民 邮 电 出 版 社 ， Aho等 ， “ 编 译 原 理 技 术 与 工 具 ” （ 影 印版 ） 高 等 教 育 出 版 社 ， Andrew W.Appel， “ 现 代 编 译 程 序 实 现 Java语 言 ” （ 影 印 版 ） 机 械 工 业 出 版 社 ， Steven S.Muchnick， “ 高 级 编 译 器 设 计与 实 现 ” （ 影 印 版 ） 清 华 大 学 出 版 社 ， Hopcroft等 ， “ 自 动 机 理 论 、 语 言 和 计 算 机 导 论 ” （ 影 印 版 ） 7 3 3 参 考 书 目Computer Systems: A Programmers Perspective作者： Randal E.Bryant; David OHallaron深入理解计算机系统 译者：龚奕利，雷迎春 翻译版 8 第 一 章 引 言 1.1 从 面 向 机 器 的 语 言 到 面 向 人 类 的 语 言面 向 机 器 的 语 言 ： 机 器 指 令 、 汇 编 语 言面 向 人 类 的 语 言 ： 通 用 程 序 设 计 语 言 、 非 过 程 式 语 言 ， 等 等例 1 : 通 用 程 序 设 计 语 言 与 汇 编 语 言 （ 包 括 机 器 指 令 ） Pascal语 句 ： x := a+b；C+语 句 ： x = a+b；汇 编 指 令 ： 十 六 进 制 代 码 汇 编 指 令A10002 MOV AX, A 8B1E0202 MOV BX, B 01D8 ADD AX, BX A30402 MOV X, AX 计 算 机 语 言 举 例 9 计 算 机 语 言 举 例 （ 续 1）给 出 003号 学 生 所 选 课 程 与 成 绩 :Select 学 号 ,姓 名 ,课 程 名 ,成 绩 from 学 生 ,选 课 where 学 生 .学 号 =“ 003” ;例 2 SQL 学 生 ： 选 课 ：学 号 姓 名 性 别001 张 梧 男002 李 煦 男003 王 沁 女004 刘 荔 女 学 号 课 程 代 码 课 程 名 成 绩001 0104 离 散 数 学 80001 0205 数 据 结 构 90003 0104 离 散 数 学 85003 0205 数 据 结 构 95学 号 姓 名 课 程 名 成 绩003 王 沁 离 散 数 学 85003 王 沁 数 据 结 构 95 10 计 算 机 语 言 举 例 （ 续 2）例 3： LEX的 正 规 式 ： char(char|digit)* return idYacc的 产 生 式 ： E : E + E | E * E | id 例 4： Unix的 shell命 令SHELL=/bin/sh# include env_precomp.mkCPDIR = /u/pbsrc/chpORAHOME = /oracle/app/oracle/product/734. 11 按 范 型 划 分 的 程 序 设 计 语 言CCC2002 PL：1. Simple Procedural Languages： FORTRAN C 2. Block-Structured Procedural Languages： Pascal3. Object-Based Languages： Ada C+ Smalltalk4. Functional Languages： LISP ML Haskell OCaml5. Logic Programming Languages： Prolog 清 华 大 学 出 版 社 ， Terrence W.Pratt等 ， PROGRAMMING LANGUAGES Design and Implementation(影 印 版 )1. 过 程 式 语 言 、 面 向 对 象 语 言 ： 通 用 程 序 设 计 语 言 ， 包 括FORTRAN、 Pascal、 C/C+、 Ada83/Ada95、 Java等 ；2. 函 数 语 言 ： 面 向 特 点 领 域 的 、 递 归 特 性 ， 典 型 代 表 ： Lisp；3. 说 明 性 、 非 算 法 式 语 言 ： 浓 厚 的 数 学 特 征 ， 典 型 代 表 ：LEX/YACC、 SQL； 4. 脚 本 式 语 言 ： 仅 是 一 种 安 排 ， 没 有 复 杂 的 逻 辑 关 系 ， 典 型 代表 ： shell语 言 。 12 其 他 面 向 特 定 应 用 领 域 的 语 言1 互 连 网 应 用 ： HTML、 XML2 计 算 机 辅 助 设 计 ： MATLAB3 集 成 电 路 设 计 ： VHDL、 Verilog4 虚 拟 现 实 与 人 机 交 互 ： VRML问 题 ： 如 何 将 形 形 色 色 的 语 言 翻 译 成 可 以 在 计 算 机 上 运 行 的 0、 1串 13 1.2 语 言 之 间 的 翻 译 习 惯 称 法 ： 汇 编 语 言 机 器 指 令 ： 汇 编 （ 或 交 叉 汇 编 ） 程 序 设 计 语 言 汇 编 语 言 或 机 器 指 令 ： 编 译 （ 或 解 释 ） 高 级 语 言 之 间 ： 转 换 （ 或 预 编 译 ） 逆 向 ： 反 汇 编 、 反 编 译 14 1.3 编 译 器 与 解 释 器 语 言 翻 译 的 两 种 基 本 形 态1.先 翻 译 后 执 行 2. 边 翻 译 边 执 行 例 5 假 设 有 源 程 序 ： read(x); write(x=, x); 15 1.3 编 译 器 与 解 释 器 （ 续 ）1. 特 点 ： 编 译 器 ： 工 作 效 率 高 ， 即 时 间 快 、 空 间 省 ； 交 互 性 与 动态 特 性 差 、 可 移 植 性 差 。 大 多 数 PL采 用 此 方 法 翻 译 ； 解 释 器 ： 工 作 效 率 低 ， 即 时 间 慢 、 空 间 费 ； 交 互 性 与 动态 特 性 好 、 可 移 植 性 好 。 早 期 的 Basic和 Java等 ；2. 基 本 功 能 ： 二 者 相 同 ；3. 所 采 用 的 技 术 ： 从 翻 译 的 角 度 来 讲 ， 两 种 方 式 所 涉 及 的 原理 、 方 法 、 技 术 相 似 。 16 1.4 编 译 器 的 工 作 原 理 与 基 本 组 成1.4.1 通 用 程 序 设 计 语 言 的 主 要 成 份1 从 语 言 抽 象 的 演 变 看 ：过 程 抽 象 数 据 类 型 （ ADT， 程 序 包 ） 类2 共 同 特 点 ： 两 大 部 分 组 成 ： 声 明 操 作 完 整 定 义3 以 过 程 式 语 言 为 例 ：声 明 性 语 句 ： 提 供 操 作 对 象 的 性 质 ， 如 数 据 类 型 、 值 、 作 用 域 等 ；操 作 性 语 句 ： 确 定 操 作 的 计 算 次 序 ， 完 成 实 际 操 作 。过 程 头 过 程 体 过 程 定 义 4 编 译 器 对 两 类 语 句 的 翻 译 ： 声 明 ： 生 成 相 应 的 环 境 ， 一 般 是 配 置 存 储 空 间 。 操 作 ： 生 成 可 执 行 的 代 码 序 列 。 例 6 一 个 Pascal过 程 17 1.4.2 以 阶 段 划 分 编 译 器 1 自 然 语 言 的 翻 译 过 程 ：识 别 单 词识 别 句 子 结 构理 解 意 思译 成 中 文 并 修 饰 2 编 译 器 的 工 作 过 程 ：词 法 分 析 语 法 分 析语 义 分 析目 标 代 码 生 成3 编 译 器 的 阶 段 （ 逻 辑 模 块 划 分 ）4 中 间 代 码 的 重 要 作 用 18 1.4.3 编 译 器 各 阶 段 的 工 作例 7 Pascal源 程 序 语 句 如 下 ： var x, y, z : real; x := y + z * 60;（ 源 程 序 ） var x, y, z : real; x := y + z * 60; （ 记 号 流 ） var id1, id2, id3 : real; id1 := id2+id3*60; （ 语 法 树 ） 19 1.4.3 编 译 器 各 阶 段 的 工 作 （ 续 1） 中 间 代 码 的 形 式 与 作 用 ：(序 号 )(op， arg1, arg2, result) result := arg1 op arg2 (1) (itr, 60, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id1) 20 1.4.3 编 译 器 各 阶 段 的 工 作 （ 续 2）(1) (itr, 60, , T1)(2) (*, id3, T1, T2)(3) (+, id2, T2, T3)(4) (:=, T3, , id1) (1) (*, id3, 60.0, T1)(2) (+, id2, T1, id1) MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1 MOVF R1, id1 R2 := id3R2 := R2 * 60.0R1 := id2R1 := R1 + R2id1 := R1id1 := id2 + id3 * 60.0 x := y + z * 60; 21 1.4.3 编 译 器 各 阶 段 的 工 作 （ 续 3）各 阶 段 工 作 的 归 纳 1. 词 法 分 析 ： 识 别 单 词 ， 至 少 分 以 下 几 大 类 ： 关 键 字 （ 保 留 字 ） 、标 识 符 、 字 面 量 、 特 殊 符 号 ；2. 语 法 分 析 ： 得 到 语 言 结 构 并 以 树 的 形 式 表 示 ；3. 语 义 分 析 ： 考 察 结 构 正 确 的 句 子 是 否 语 义 合 法 ， 修 改 树 结 构 ；4. 中 间 代 码 生 成 （ 可 选 ） ： 生 成 一 种 既 接 近 目 标 语 言 ， 又 与 具 体机 器 无 关 的 表 示 ， 便 于 优 化 与 代 码 生 成 ； （ 到 目 前 为 止 ， 编 译 器 与 解 释 器 可 以 一 致 ） 5. 中 间 代 码 优 化 （ 可 选 ） :局 部 优 化 、 循 环 优 化 、 全 局 优 化 等 ； 优化 实 际 上 是 一 个 等 价 变 换 ， 变 换 前 后 的 指 令 序 列 完 成 同 样 的 功能 ， 但 在 占 用 的 空 间 上 和 程 序 执 行 的 时 间 上 都 更 省 、 更 有 效 。6. 目 标 代 码 生 成 ： 不 同 形 式 的 目 标 代 码 汇 编 、 可 重 定 位 、 内 存形 式 （ Load-and-Go） ;7. 符 号 表 管 理 ： 合 理 组 织 符 号 ， 便 于 各 阶 段 查 找 、 填 写 等 ； 8. 出 错 处 理 ： 错 误 的 种 类 词 法 错 、 语 法 错 、 静 态 语 义 错 、 动 态语 义 错 。 22 1.4.4 编 译 器 的 分 析 /综 合 模 式 前 端 ： 语 言 结 构 和 意 义 的 分 析 ； 后 端 ： 语 言 意 义 处 理 ； 中 间 代 码 ： 前 端 与 后 端 的 分 界 ； 23 1.4.4 编 译 器 的 分 析 /综 合 模 式 （ 续 1）4 编 译 器 基 础 架 构 （ Infrastructure） ： 源 代 码 的 中 间 表示 、 一 组 前 端 、 一 组 后 端 ； 24 1.4.5 编 译 器 扫 描 的 遍 数 1. 每 个 阶 段 将 程 序 完 整 分 析 一 遍 的 工 作 模 式 称 为 一 遍 扫 描 。 早期 编 译 器 的 一 遍 定 义 为 从 外 存 读 入 内 存 再 写 到 外 存 ；2. 确 定 扫 描 遍 数 的 因 素 ： 软 、 硬 件 条 件 ， 如 内 存 太 小 ， 或 全 局 优 化 语 言 结 构 ， 如 规 定 标 识 符 的 先 声 明 后 引 用x := f(a, b, c);function f(a:integer; b:integer):integer; 编 译 技 术 ， 如 拉 链 回 填 goto lab1;lab1: 25 1.5 编 译 器 的 编 写 1. 直 接 使 用 汇 编 语 言 和 程 序 设 计 语 言 ；2. 利 用 编 译 器 编 写 工 具 ： 词 /语 法 、 语 法 制 导 翻 译 、 代 码 生成 、 数 据 流 分 析 等 ；3. 基 于 编 译 器 基 础 架 构 的 编 译 器 构 造 系 统 （ 开 放 式 编 译 器 ，如 GCC、 SUIF等 ） 。 26 1.6 本 章 小 结 1 语 言 与 语 言 的 翻 译2 编 译 器 的 基 本 组 成 （ 工 作 ）3 编 译 器 的 分 析 /综 合 模 式 ， 编 译 器 基 础 架 构4 扫 描 遍 数5 编 译 器 的 编 写其 它1. 作 业 ： 教 材 中 除 标 记 *的 全 做 ； 根 据 课 程 进 度 做 ； 第 二 、五 章 交 一 次 ， 第 三 、 四 章 交 各 两 次 ；2. 课 代 表 ： 收 缴 作 业 、 联 系 上 机 、 反 映 同 学 意 见 ， 等3. 答 疑 ： 待 定 ；4. 上 机 作 业 ： 交 上 机 报 告 ， 作 业 由 辅 导 教 师 验 收 。 27 第 一 章 结 束 28返 回 例 6 一 Pascal的 过 程 如 下 (1) procedure sample(y: integer); 过 程 头 (2) var x : integer; 过 程 体 （ 开 始 ） (3) begin x := y;(4) if x100 then x := 0(5) end; 过 程 体 （ 结 束 ） (1)是 过 程 头 ， 它 是 一 个 声 明 性 的 语 句 ， 为 使 用 者 提 供 调 用 信 息 ， 包 括 过程 名 、 参 数 、 返 回 值 （ 若 有 的 话 ） 等 。 （ 接 口 ） (2)至 (5)是 过 程 体 ， 它 是 一 个 语 句 序 列 。 语 句 序 列 中 既 包 括 声 明 性 语 句 也包 括 操 作 性 语 句 。 （ 实 现 ） (2)是 声 明 性 语 句 ， 而 (3)至 (5)是 操 作 性 语 句 。 编 译 器 对 声 明 性 语 句 的 处 理 一 般 是 生 成 相 应 的 环 境 (存 储 空 间 )， 而 对 操作 性 语 句 则 是 生 成 此 环 境 中 的 可 执 行 代 码 序 列 。 为 了 便 于 编 译 器 的 处 理 ， 操 作 性 语 句 中 使 用 的 每 个 操 作 对 象 ， 均 应 在 使用 前 声 明 ， 即 符 合 先 声 明 后 引 用 的 原 则 。