第1章.doc

Transcription

1 目 录 第 1 章 编 译 程 序 概 论 1.1 引 论 1.2 编 译 器 简 介 1.3 编 译 过 程 概 述 1.4 编 译 程 序 的 结 构 1.5 编 译 程 序 生 成 与 构 造 第 2 章 词 法 分 析 2.1 扫 描 处 理 2.2 词 法 分 析 器 的 要 求 2.3 状 态 转 换 图 与 词 法 分 析 器 设 计 2.4 正 则 表 达 式 2.5 有 穷 自 动 机 2.6 从 正 则 表 达 式 到 DFA 2.7 词 法 分 析 器 的 自 动 构 造 工 具 第 3 章 文 法 和 程 序 语 言 描 述 3.1 文 法 的 概 念 3.2 文 法 和 语 言 的 形 式 定 义 3.3 形 式 语 言 概 述 3.4 上 下 文 无 关 文 法 及 语 法 树 3.5 句 型 的 分 析 第 4 章 语 法 分 析 自 上 而 下 分 析 4.1 自 上 而 下 的 分 析 思 想 4.2 递 归 下 降 分 析 法 4.3 LL(1) 文 法 分 析 4.4 自 上 而 下 分 析 程 序 中 的 错 误 校 正

2 第 5 章 语 法 分 析 自 下 而 上 优 先 分 析 法 5.1 自 下 而 上 优 先 分 析 法 概 述 5.2 简 单 优 先 分 析 法 5.3 算 符 优 先 分 析 法 第 6 章 语 法 分 析 程 序 的 自 动 构 造 6.1 LR 分 析 概 述 6.2 LR(0) 分 析 6.3 SLR(1) 分 析 6.4 LR(1) 分 析 6.5 YACC: 产 生 LALR(1) 分 析 程 序 的 生 成 器 6.6 自 下 而 上 分 析 程 序 中 的 错 误 校 正 第 7 章 语 法 制 导 翻 译 和 中 间 代 码 生 成 7.1 语 法 制 导 翻 译 概 述 7.2 各 种 常 见 中 间 语 言 形 式 7.3 简 单 赋 值 语 句 到 四 元 式 的 翻 译 7.4 布 尔 表 达 式 到 四 元 式 的 翻 译 7.5 控 制 语 句 的 中 间 代 码 生 成 7.6 数 组 和 结 构 的 翻 译 7.7 过 程 和 函 数 调 用 的 代 码 生 成 第 8 章 符 号 表 8.1 符 号 表 和 符 号 8.2 符 号 表 的 结 构 8.3 关 于 符 号 表 的 几 点 说 明 8.4 作 用 域 规 则 和 块 结 构 8.5 同 层 说 明 的 相 互 作 用 第 9 章 目 标 程 序 运 行 时 环 境 9.1 程 序 运 行 时 的 存 储 器 分 配 9.2 程 序 完 全 静 态 运 行 时 环 境 9.3 程 序 基 于 栈 的 运 行 时 环 境 9.4 动 态 存 储 器 管 理 9.5 参 数 传 递

3 第 10 章 代 码 优 化 10.1 优 化 概 述 10.2 优 化 的 数 据 结 构 和 技 术 10.3 优 化 的 分 类 实 现 简 介 第 11 章 代 码 生 成 11.1 一 个 计 算 机 模 型 11.2 一 个 简 单 的 代 码 生 成 器 11.3 寄 存 器 分 配 11.4 代 码 生 成 的 研 究 现 状

4 第 1 章 编 译 程 序 概 论 1.1 引 论 使 用 过 计 算 机 的 人 都 知 道, 大 多 数 用 户 都 是 应 用 高 级 语 言 来 实 现 他 们 所 需 要 的 计 算 的 编 译 程 序 是 现 代 计 算 机 系 统 的 基 本 组 成 部 分 之 一, 也 是 用 户 最 直 接 关 心 的 工 具 之 一 多 数 计 算 机 系 统 都 含 有 不 止 一 个 高 级 语 言 的 编 译 程 序, 对 有 些 高 级 语 言 甚 至 配 置 了 几 个 不 同 性 能 的 编 译 程 序, 供 用 户 按 不 同 的 需 要 进 行 选 择 一 个 高 级 语 言 程 序 在 计 算 机 上 的 执 行 过 程 可 以 分 为 两 步 : 第 一 步, 用 一 个 编 译 程 序 把 高 级 语 言 翻 译 成 机 器 语 言 程 序 ; 第 二 步, 运 行 所 得 的 机 器 语 言 程 序 来 求 得 计 算 结 果 从 功 能 上 看, 一 个 编 译 程 序 就 是 一 个 语 言 翻 译 程 序 通 常 所 说 的 编 译 程 序 就 是 指 能 把 某 一 种 语 言 程 序 ( 称 为 源 语 言 程 序 ) 改 造 成 另 一 种 语 言 程 序 ( 称 为 目 标 语 言 程 序 ), 而 且 这 两 者 在 逻 辑 上 是 等 价 的 例 如, 汇 编 程 序 是 一 个 翻 译 程 序, 它 把 汇 编 语 言 程 序 翻 译 成 机 器 语 言 程 序 若 源 语 言 是 诸 如 Fortran Pascal Algol 或 C 等 这 样 的 高 级 语 言, 而 目 标 语 言 是 诸 如 汇 编 语 言 或 机 器 语 言 之 类 的 低 级 语 言, 则 这 样 的 翻 译 程 序 就 称 为 编 译 程 序 编 译 程 序 所 执 行 的 功 能 可 以 用 图 1-1 来 说 明 : 高 级 语 言 程 序 ( 源 程 序 ) 编 译 程 序 低 级 语 言 程 序 ( 目 标 程 序 ) 图 1-1 编 译 程 序 的 功 能 编 译 程 序 的 重 要 性 体 现 在 它 使 得 大 多 数 的 计 算 机 用 户 不 必 考 虑 与 机 器 有 关 的 繁 琐 细 节, 即 机 器 对 用 户 是 透 明 的, 使 得 程 序 员 专 心 于 程 序 设 计 而 不 必 考 虑 机 器 的 差 异 这 对 于 当 今 机 器 的 种 类 和 数 量 不 断 增 长 的 年 代 尤 为 重 要

5 编 译 原 理 1.2 编 译 器 简 介 何 谓 编 译 器? 编 译 器 就 是 将 一 种 语 言 翻 译 为 另 一 种 语 言 的 计 算 机 程 序 编 译 器 将 源 程 序 (Source Language) 编 写 的 程 序 作 为 输 入, 产 生 用 目 标 语 言 (target language) 编 写 的 等 价 程 序 通 常 地, 源 程 序 为 高 级 语 言 (High-level Language), 如 C 或 C++, 而 目 标 语 言 则 是 目 标 机 器 的 目 标 代 码 (Object Code), 有 时 也 称 作 机 器 代 码 (Machine Code), 也 就 是 写 在 计 算 机 机 器 指 令 中 的 用 于 运 行 的 代 码 这 一 过 程 可 以 如 图 1-2 所 示 源 程 序 编 译 器 图 1-2 编 译 器 的 作 用 目 标 程 序 编 译 器 是 一 种 相 当 复 杂 的 程 序, 其 代 码 的 长 度 可 从 行 到 行 不 等 编 写 甚 至 读 懂 这 样 的 一 个 程 序 都 非 易 事, 大 多 数 的 计 算 机 科 学 家 和 专 业 人 员 也 从 来 没 有 编 写 过 一 个 完 整 的 编 译 器 但 是, 几 乎 所 有 形 式 的 计 算 均 要 用 到 编 译 器, 而 且 任 何 一 个 与 计 算 机 打 交 道 的 专 业 人 员 都 应 掌 握 编 译 器 的 基 本 结 构 和 操 作 除 此 之 外, 计 算 机 应 用 程 序 中 经 常 遇 到 的 一 个 任 务 就 是 命 令 解 释 程 序 和 界 面 程 序 的 开 发, 这 比 编 译 器 要 小, 但 使 用 的 却 是 相 同 的 技 术 因 此, 掌 握 这 一 技 术 具 有 非 常 大 的 实 际 意 义 编 译 器 的 历 史 及 其 发 展 在 20 世 纪 40 年 代, 由 于 冯 诺 伊 曼 在 存 储 - 程 序 计 算 机 方 面 的 先 锋 作 用, 编 写 一 串 代 码 或 者 程 序 已 经 成 为 必 要, 这 样 计 算 机 就 可 以 执 行 所 需 的 计 算 开 始 时, 这 些 程 序 都 是 用 机 器 语 言 (Machine Language) 编 写 的 机 器 语 言 就 是 表 示 机 器 实 际 操 作 的 数 字 代 码, 例 如 : C 表 示 在 IBM PC 上 使 用 的 Intel 8x86 处 理 器 将 数 字 2 移 至 地 址 0000(16 进 制 ) 的 指 令 当 然, 编 写 这 样 的 代 码 是 十 分 费 时 和 乏 味 的, 这 种 代 码 形 式 很 快 就 被 汇 编 语 言 (Assembly Language) 代 替 了 在 汇 编 语 言 中, 都 是 以 符 号 形 式 给 出 指 令 和 存 储 地 址 的 例 如, 汇 编 语 言 指 令 MOV X, 2 就 与 前 面 的 机 器 指 令 等 价 ( 假 设 符 号 存 储 地 址 X 是 0000) 汇 编 程 序 (Assembler) 将 汇 编 语 言 的 符 号 代 码 和 存 储 地 址 翻 译 成 与 机 器 语 言 相 对 应 的 数 字 代 码 汇 编 语 言 大 大 提 高 了 编 程 的 速 度 和 准 确 度, 人 们 至 今 仍 在 使 用 着 它, 在 编 码 需 要 极 2

6 第 1 章 编 译 程 序 概 论 快 的 速 度 和 极 高 的 简 洁 程 度 时 尤 为 如 此 但 是, 汇 编 语 言 也 有 许 多 缺 点 : 编 写 起 来 也 不 容 易, 阅 读 和 理 解 很 难 ; 而 且 汇 编 语 言 的 编 写 严 格 依 赖 于 特 定 的 机 器, 所 以 为 一 台 计 算 机 编 写 的 代 码 在 应 用 于 另 一 台 计 算 机 时 必 须 完 全 重 写 很 明 显, 发 展 编 程 技 术 的 下 一 个 重 要 步 骤 就 是 以 一 个 更 类 似 于 数 学 定 义 或 自 然 语 言 的 简 洁 形 式 来 编 写 程 序 的 操 作, 它 应 与 任 何 机 器 都 无 关, 而 且 也 可 由 一 个 程 序 翻 译 为 可 执 行 的 代 码 例 如, 前 面 的 汇 编 语 言 代 码 可 以 写 成 一 个 简 洁 的 与 机 器 无 关 的 形 式 x=2, 起 初 人 们 担 心 这 是 不 可 能 的, 或 者 即 使 可 能, 目 标 代 码 也 会 因 效 率 不 高 而 没 有 多 大 用 处 在 1954 年 至 1957 年 期 间,IBM 的 John Backus 带 领 的 一 个 研 究 小 组 对 FORTRAN 语 言 及 其 编 译 器 的 开 发, 使 得 上 面 的 担 忧 不 必 要 了 但 是, 由 于 当 时 处 理 中 所 涉 及 到 的 大 多 数 程 序 设 计 语 言 的 翻 译 并 不 为 人 所 掌 握, 所 以 这 个 项 目 的 成 功 也 伴 随 着 巨 大 的 辛 劳 几 乎 与 此 同 时, 人 们 也 在 开 发 着 第 一 个 编 译 器, Noam Chomsky 开 始 了 他 的 自 然 语 言 结 构 的 研 究 他 的 发 现 最 终 使 得 编 译 器 结 构 异 常 简 单, 甚 至 还 带 有 了 一 些 自 动 化 Chomsky 的 研 究 导 致 了 根 据 语 言 文 法 (Grammar, 指 定 其 结 构 的 规 则 ) 的 难 易 程 度 以 及 识 别 它 们 所 需 的 算 法 来 为 语 言 分 类 正 如 现 在 所 称 的 与 乔 姆 斯 基 分 类 结 构 (Chomsky hierarchy) 一 样 包 括 了 文 法 的 4 个 层 次 :0 型 1 型 2 型 和 3 型 文 法, 且 其 中 的 每 一 个 都 是 其 前 者 的 专 门 化 2 型 ( 或 上 下 文 无 关 文 法 (Context-free Grammar)) 被 证 明 是 程 序 设 计 语 言 中 最 有 用 的, 而 且 今 天 它 已 代 表 着 程 序 设 计 语 言 结 构 的 标 准 方 式 分 析 问 题 (Parsing Problem, 用 于 限 定 上 下 文 无 关 语 言 的 识 别 的 有 效 算 法 ) 的 研 究 是 在 20 世 纪 60 年 代 和 20 世 纪 70 年 代, 它 相 当 完 善 地 解 决 了 这 一 问 题, 现 在 它 已 是 编 译 理 论 的 一 个 标 准 部 分 有 穷 自 动 机 (Finite Automata) 和 正 则 表 达 式 (Regular Expression) 同 上 下 文 无 关 文 法 紧 密 相 关, 它 们 与 乔 姆 斯 基 的 3 型 文 法 相 对 应 对 它 们 的 研 究 与 乔 姆 斯 基 的 研 究 几 乎 同 时 开 始, 并 且 引 出 了 表 示 程 序 设 计 语 言 的 单 词 ( 或 称 为 记 号 ) 的 符 号 方 式 人 们 接 着 又 深 化 了 生 成 有 效 的 目 标 代 码 的 方 法, 这 就 是 最 初 的 编 译 器, 它 们 被 一 直 使 用 至 今 人 们 通 常 将 其 误 称 为 优 化 技 术 (Optimization Technique), 但 因 其 从 未 真 正 地 得 到 过 被 优 化 了 的 目 标 代 码 而 仅 仅 改 进 了 它 的 有 效 性, 因 此 实 际 上 应 称 作 代 码 改 进 技 术 (Code Improvement Technique) 当 分 析 问 题 变 得 好 懂 起 来 时, 人 们 就 在 开 发 程 序 上 花 费 了 很 大 的 功 夫 来 研 究 这 一 部 分 的 编 译 器 的 自 动 构 造 这 些 程 序 最 初 被 称 为 编 译 程 序 - 编 译 器, 但 更 确 切 地 应 称 为 分 析 程 序 生 成 器 (Parser Generator), 这 是 因 为 它 们 仅 仅 能 够 自 动 处 理 编 译 的 一 部 分 这 些 程 序 中 最 著 名 的 是 Yacc(Yet Another Compiler-compiler), 它 是 由 Steve Johnson 在 1975 年 为 Unix 系 统 编 写 的 类 似 地, 有 穷 自 动 机 的 研 究 也 发 展 了 另 一 种 称 为 扫 描 程 序 生 成 器 (Scanner Generator) 的 工 具,Lex( 与 Yacc 同 时, 由 Mike Lesk 为 Unix 系 统 开 发 的 ) 是 这 其 中 的 佼 佼 者 3

7 编 译 原 理 在 20 世 纪 70 年 代 后 期 和 20 世 纪 80 年 代 早 期, 大 量 的 项 目 都 关 注 于 编 译 器 其 它 部 分 的 生 成 自 动 化, 这 其 中 就 包 括 了 代 码 生 成 这 些 尝 试 并 未 取 得 多 少 成 功, 这 大 概 是 因 为 操 作 太 复 杂 而 人 们 又 对 其 不 甚 了 解, 在 本 书 中 不 做 详 述 就 最 近 的 发 展 来 说 : 首 先, 编 译 器 包 括 了 更 为 复 杂 的 算 法 的 应 用 程 序, 它 用 于 推 断 或 简 化 程 序 中 的 信 息 ; 这 又 与 更 为 复 杂 的 程 序 设 计 语 言 ( 可 允 许 此 类 分 析 ) 的 发 展 结 合 在 一 起 其 中 典 型 的 有 用 于 函 数 语 言 编 译 的 Hindley-Milner 类 型 检 查 的 统 一 算 法 其 次, 编 译 器 已 越 来 越 成 为 基 于 窗 口 的 交 互 开 发 环 境 (Interactive Development Environment,IDE) 的 一 部 分, 它 包 括 了 编 辑 器 链 接 程 序 调 试 程 序 以 及 项 目 管 理 程 序 这 样 的 IDE 的 标 准 并 没 有 多 少, 但 是 已 沿 着 这 一 方 向 对 标 准 的 窗 口 环 境 进 行 开 发 了 尽 管 近 年 来 对 此 进 行 了 大 量 的 研 究, 但 是 基 本 的 编 译 器 设 计 在 近 20 年 中 都 没 有 多 大 的 改 变, 而 且 它 们 正 迅 速 地 成 为 计 算 机 科 学 课 程 中 的 中 心 一 环 与 编 译 器 相 关 的 程 序 描 述 1. 解 释 程 序 (Interpreter) 解 释 程 序 是 如 同 编 译 器 的 一 种 语 言 翻 译 程 序 它 与 编 译 器 的 不 同 之 处 在 于 : 它 立 即 执 行 源 程 序 而 不 是 生 成 在 翻 译 完 成 之 后 才 执 行 的 目 标 代 码 从 原 理 上 讲, 任 何 程 序 设 计 语 言 都 可 被 解 释 或 被 编 译, 但 是 根 据 所 使 用 的 语 言 和 翻 译 情 况, 很 可 能 会 选 用 解 释 程 序 而 不 用 编 译 器 例 如, 我 们 经 常 解 释 BASIC 语 言 而 不 是 去 编 译 它 类 似 地, 诸 如 LISP 的 函 数 语 言 也 常 常 是 被 解 释 的 解 释 程 序 也 经 常 用 于 教 育 和 软 件 的 开 发, 此 处 的 程 序 很 有 可 能 被 翻 译 若 干 次 而 另 一 方 面, 当 执 行 的 速 度 是 最 为 重 要 的 因 素 时 就 使 用 编 译 器, 这 是 因 为 被 编 译 的 目 标 代 码 比 被 解 释 的 源 代 码 要 快 得 多, 有 时 要 快 10 倍 或 更 多 但 是, 解 释 程 序 具 有 许 多 与 编 译 器 共 享 的 操 作, 而 两 者 之 间 也 有 一 些 混 合 之 处 2. 汇 编 程 序 (Assembler) 汇 编 程 序 是 用 于 特 定 计 算 机 上 的 汇 编 语 言 的 翻 译 程 序 正 如 前 面 所 提 到 的, 汇 编 语 言 是 计 算 机 的 机 器 语 言 的 符 号 形 式, 它 极 易 翻 译 有 时, 编 译 器 会 生 成 汇 编 语 言 以 作 为 其 目 标 语 言, 然 后 再 由 一 个 汇 编 程 序 将 它 翻 译 成 目 标 代 码 3. 连 接 程 序 (Linker) 编 译 器 和 汇 编 程 序 都 经 常 依 赖 于 连 接 程 序, 它 将 分 别 在 不 同 的 目 标 文 件 中 编 译 或 汇 编 的 代 码 收 集 到 一 个 可 直 接 执 行 的 文 件 中 在 这 种 情 况 下, 目 标 代 码, 即 还 未 被 连 接 的 机 器 代 码, 与 可 执 行 的 机 器 代 码 之 间 就 有 了 区 别 连 接 程 序 还 连 接 目 标 程 序 和 用 于 标 准 库 函 数 的 代 码, 以 及 连 接 目 标 程 序 和 由 计 算 机 的 操 作 系 统 提 供 的 资 源 ( 例 如, 存 储 分 配 程 序 及 输 入 与 输 出 设 备 ) 有 趣 的 是, 连 接 程 序 现 在 正 在 完 成 编 译 器 最 早 的 一 个 主 要 活 动 ( 这 也 是 编 译 一 词 的 用 法, 4

8 第 1 章 编 译 程 序 概 论 即 通 过 收 集 不 同 的 来 源 来 构 造 ) 因 为 连 接 过 程 对 操 作 系 统 和 处 理 器 有 极 大 的 依 赖 性, 本 书 也 就 不 研 究 它 了 我 们 也 就 不 细 分 连 接 的 目 标 代 码 和 可 执 行 的 代 码, 这 是 因 为 对 于 编 译 技 术 而 言, 这 个 区 别 并 不 重 要 4. 装 入 程 序 (Loader) 编 译 器 汇 编 程 序 或 连 接 程 序 生 成 的 代 码 经 常 还 不 完 全 适 用 或 不 能 执 行, 但 是 它 们 的 主 要 存 储 器 访 问 却 可 以 在 存 储 器 的 任 何 位 置 中 且 与 一 个 不 确 定 的 起 始 位 置 相 关 这 样 的 代 码 被 称 为 是 可 重 定 位 的 (Relocatable), 而 装 入 程 序 可 处 理 所 有 的 与 指 定 的 基 地 址 或 起 始 地 址 有 关 的 可 重 定 位 的 地 址 装 入 程 序 使 得 可 执 行 代 码 更 加 灵 活, 但 是 装 入 处 理 通 常 是 在 后 台 ( 作 为 操 作 环 境 的 一 部 分 ) 或 与 连 接 相 联 合 时 才 发 生, 装 入 程 序 极 少 会 是 实 际 的 独 立 程 序 5. 预 处 理 器 (Preprocessor) 预 处 理 器 是 在 真 正 的 翻 译 开 始 之 前 由 编 译 器 调 用 的 独 立 程 序 预 处 理 器 可 以 删 除 注 释 包 含 其 它 文 件 以 及 执 行 宏 ( 宏 Macro 是 一 段 重 复 文 字 的 简 短 描 写 ) 替 代 预 处 理 器 可 由 语 言 ( 如 C) 要 求 或 以 后 作 为 提 供 额 外 功 能 ( 诸 如 为 FORTRAN 提 供 Ratfor 预 处 理 器 ) 的 附 加 软 件 6. 编 辑 器 (Editor) 编 译 器 通 常 接 受 由 任 何 生 成 标 准 文 件 ( 例 如 ASCII 文 件 ) 的 编 辑 器 编 写 的 源 程 序 最 近, 编 译 器 已 与 另 一 个 编 辑 器 和 其 它 程 序 捆 绑 进 一 个 交 互 的 开 发 环 境 IDE 中 此 时, 尽 管 编 辑 器 仍 然 生 成 标 准 文 件, 但 会 转 向 正 被 讨 论 的 程 序 设 计 语 言 的 格 式 或 结 构 这 样 的 编 辑 器 称 为 基 于 结 构 的 (Structure Based), 且 它 早 已 包 括 了 编 译 器 的 某 些 操 作 ; 因 此, 程 序 员 就 会 在 程 序 的 编 写 时 而 不 是 在 编 译 时 就 得 知 错 误 了 从 编 辑 器 中 也 可 调 用 编 译 器 以 及 与 它 共 用 的 程 序, 这 样 程 序 员 无 需 离 开 编 辑 器 就 可 执 行 程 序 7. 调 试 程 序 (Debugger) 调 试 程 序 是 可 在 被 编 译 了 的 程 序 中 判 定 执 行 错 误 的 程 序, 它 也 经 常 与 编 译 器 一 起 放 在 IDE 中 运 行 一 个 带 有 调 试 程 序 的 程 序 与 直 接 执 行 不 同, 这 是 因 为 调 试 程 序 保 存 着 所 有 的 或 大 多 数 源 代 码 信 息 ( 诸 如 行 数 变 量 名 和 过 程 ) 它 还 可 以 在 预 先 指 定 的 位 置 ( 称 为 断 点 (Breakpoint)) 暂 停 执 行, 并 提 供 有 关 已 调 用 的 函 数 以 及 变 量 的 当 前 值 的 信 息 为 了 执 行 这 些 函 数, 编 译 器 必 须 为 调 试 程 序 提 供 恰 当 的 符 号 信 息, 而 这 有 时 却 相 当 困 难, 尤 其 是 在 一 个 要 优 化 目 标 代 码 的 编 译 器 中 8. 描 述 器 (Profiler) 描 述 器 是 在 执 行 中 搜 集 目 标 程 序 行 为 统 计 的 程 序 程 序 员 特 别 感 兴 趣 的 统 计 是 每 一 个 过 程 的 调 用 次 数 和 每 一 个 过 程 执 行 时 间 所 占 的 百 分 比 这 样 的 统 计 对 于 帮 助 程 序 员 提 高 程 序 的 执 行 速 度 极 为 有 用 有 时 编 译 器 也 甚 至 无 需 程 序 员 5

9 编 译 原 理 的 干 涉 就 可 利 用 描 述 器 的 输 出 来 自 动 改 进 目 标 代 码 9. 项 目 管 理 程 序 (Project Manager ) 现 在 的 软 件 项 目 通 常 大 到 需 要 由 一 组 程 序 员 来 完 成, 这 时 对 那 些 由 不 同 人 员 操 作 的 文 件 进 行 整 理 就 非 常 重 要 了, 而 这 正 是 项 目 管 理 程 序 的 任 务 例 如, 项 目 管 理 程 序 应 将 由 不 同 的 程 序 员 制 作 的 文 件 的 各 个 独 立 版 本 整 理 在 一 起, 它 还 应 保 存 一 组 文 件 的 更 改 历 史, 这 样 就 能 维 持 一 个 正 在 开 发 的 程 序 的 连 贯 版 本 了 ( 这 对 那 些 由 单 个 程 序 员 管 理 的 项 目 也 很 有 用 ) 项 目 管 理 程 序 的 编 写 可 与 语 言 无 关, 但 当 其 与 编 译 器 捆 绑 在 一 起 时, 它 就 可 以 保 持 有 关 特 定 的 编 译 器 和 建 立 一 个 完 整 的 可 执 行 程 序 的 链 接 程 序 操 作 的 信 息 在 Unix 系 统 中 有 两 个 流 行 的 项 目 管 理 程 序 :sccs(source Code Control System ) 和 rcs(revision Control System ) 翻 译 步 骤 编 译 器 内 部 包 括 了 许 多 步 骤 或 称 为 阶 段 (phase), 它 们 执 行 不 同 的 逻 辑 操 作 将 这 些 阶 段 设 想 为 编 译 器 中 一 个 个 单 独 的 片 断 是 很 有 用 的, 尽 管 在 应 用 中 它 们 是 经 常 组 合 在 一 起 的, 但 它 们 确 实 是 作 为 单 独 的 代 码 操 作 来 编 写 的 图 1-3 是 编 译 器 中 的 阶 段 和 与 以 下 阶 段 ( 文 字 表 符 号 表 和 错 误 处 理 器 ) 或 其 中 的 一 部 分 交 互 的 3 个 辅 助 部 件 这 里 只 是 简 要 地 描 述 一 下 每 个 阶 段, 今 后 大 家 还 会 更 详 细 地 学 到 它 们 扫 语 法 语 义 源 代 码 代 码 目 标 代 源 代 码 描 分 析 分 析 优 化 程 生 成 码 优 化 目 标 代 码 文 字 表 符 号 表 错 误 处 理 图 1-3 编 译 器 的 阶 段 1. 扫 描 程 序 (scanner) 在 这 个 阶 段 编 译 器 实 际 阅 读 源 程 序 ( 通 常 以 字 符 流 的 形 式 表 示 ) 扫 描 程 序 执 行 词 法 分 析 (Lexical analysis ): 它 将 字 符 序 列 收 集 到 称 作 记 号 (token) 的 有 意 义 单 元 中, 记 号 同 自 然 语 言, 如 英 语 中 的 字 词 相 似 因 此 可 以 认 为 扫 描 6

10 第 1 章 编 译 程 序 概 论 程 序 执 行 与 拼 写 相 似 的 任 务 例 如 在 下 面 的 代 码 行 ( 它 可 以 是 C 程 序 的 一 部 分 ) 中 : a [index] = 这 个 代 码 包 括 了 12 个 非 空 字 符, 但 只 有 8 个 记 号 : a 标 识 符 [ 左 括 号 index 标 识 符 ] 右 括 号 = 赋 值 4 数 字 + 加 号 2 数 字 每 一 个 记 号 均 由 一 个 或 多 个 字 符 组 成, 在 进 一 步 处 理 之 前 它 已 被 收 集 在 一 个 单 元 中 扫 描 程 序 还 可 完 成 与 识 别 记 号 一 起 执 行 的 其 它 操 作 例 如, 它 可 将 标 识 符 输 入 到 符 号 表 中, 将 文 字 (literal) 输 入 到 文 字 表 中 ( 文 字 包 括 诸 如 的 数 字 常 量, 以 及 诸 如 Hello, world! 的 引 用 字 符 串 ) 2. 语 法 分 析 程 序 (parser) 语 法 分 析 程 序 从 扫 描 程 序 中 获 取 记 号 形 式 的 源 代 码, 并 完 成 定 义 程 序 结 构 的 语 法 分 析 (syntax analysis), 这 与 自 然 语 言 中 句 子 的 语 法 分 析 类 似 语 法 分 析 定 义 了 程 序 的 结 构 元 素 及 其 关 系 通 常 将 语 法 分 析 的 结 果 表 示 为 分 析 树 (parse tree) 或 语 法 树 (syntax tree ) 分 析 树 对 于 显 示 程 序 的 语 法 或 程 序 元 素 很 有 帮 助, 但 是 对 于 表 示 该 结 构 却 显 得 力 不 从 心 了 分 析 程 序 更 趋 向 于 生 成 语 法 树, 语 法 树 是 分 析 树 中 所 含 信 息 的 浓 缩 ( 有 时 因 为 语 法 树 表 示 从 分 析 树 中 的 进 一 步 抽 取, 所 以 也 被 称 为 抽 象 的 语 法 树 (abstract syntax tree )) 3. 语 义 分 析 程 序 (semantic analyzer) 程 序 的 语 义 就 是 它 的 意 思, 它 与 语 法 或 结 构 不 同 程 序 的 语 义 确 定 程 序 的 运 行, 但 是 大 多 数 的 程 序 设 计 语 言 都 具 有 在 执 行 之 前 被 确 定 而 不 易 由 语 法 表 示 和 由 分 析 程 序 分 析 的 特 征 这 些 特 征 被 称 作 静 态 语 义 (static semantic), 而 语 义 分 析 程 序 的 任 务 就 是 分 析 这 样 的 语 义 ( 程 序 的 动 态 语 义 具 有 只 有 在 程 序 执 行 时 才 能 确 定 的 特 性, 由 于 编 译 器 不 能 执 行 程 序, 所 以 它 不 能 由 编 译 器 来 确 定 ) 一 般 的 程 序 设 计 语 言 的 典 型 静 态 语 义 包 括 声 明 和 类 型 检 查 由 语 义 分 析 程 序 计 算 的 额 外 信 息 ( 诸 如 数 据 类 型 ) 被 称 为 属 性 (attribute), 它 们 通 常 是 作 为 注 释 或 装 饰 增 加 到 树 中 ( 还 可 将 属 性 添 加 到 符 号 表 中 ) 在 正 运 行 的 C 表 达 式 : a [index] =

11 编 译 原 理 中, 该 行 分 析 之 前 收 集 的 典 型 类 型 信 息 可 能 是 :a 是 一 个 整 型 值 的 数 组, 它 带 有 来 自 整 型 子 范 围 的 下 标 ;index 则 是 一 个 整 型 变 量 接 着, 语 义 分 析 程 序 将 用 所 有 的 子 表 达 式 类 型 来 标 注 语 法 树, 并 检 查 赋 值 是 否 使 这 些 类 型 有 意 义 了, 如 若 没 有, 则 声 明 一 个 类 型 匹 配 错 误 在 上 例 中, 所 有 的 类 型 均 有 意 义, 有 关 语 法 树 的 语 义 分 析 结 果 可 用 注 释 了 的 树 来 表 示 4. 源 代 码 优 化 程 序 (source code optimizer) 编 译 器 通 常 包 括 许 多 代 码 改 进 或 优 化 步 骤 绝 大 多 数 最 早 的 优 化 步 骤 是 在 语 义 分 析 之 后 完 成 的, 而 此 时 代 码 改 进 可 能 只 依 赖 于 源 代 码 这 种 可 能 性 是 通 过 将 这 一 操 作 提 供 为 编 译 过 程 中 的 单 独 阶 段 指 出 的 每 个 编 译 器 不 论 在 已 完 成 的 优 化 种 类 方 面 还 是 在 优 化 阶 段 的 定 位 中 都 有 很 大 的 差 异 在 上 例 中, 我 们 包 括 了 一 个 源 代 码 层 次 的 优 化 机 会, 也 就 是 : 表 达 式 可 由 编 译 器 计 算 先 得 到 结 果 6 ( 这 种 优 化 称 为 常 量 合 并 (constant folding )) 当 然, 还 会 有 更 复 杂 的 情 况 ( 有 些 将 在 以 后 的 章 节 中 提 到 ) 另 一 个 常 见 的 选 择 是 P- 代 码 (P-code), 它 常 用 于 Pascal 编 译 器 中 在 前 面 的 例 子 中, 原 先 的 C 表 达 式 的 三 元 式 代 码 应 是 : t = a [index] = t ( 请 注 意, 这 里 利 用 了 一 个 额 外 的 临 时 变 量 t 存 放 加 法 的 中 间 值 ) 这 样, 优 化 程 序 就 将 这 个 代 码 改 进 为 两 步 首 先 计 算 加 法 的 结 果 : t = 6 a [index] = t 接 着, 将 t 替 换 为 该 值 以 得 到 三 元 语 句 a [index] = 6 源 代 码 优 化 程 序 可 能 通 过 将 其 输 出 称 为 中 间 代 码 (intermediate code) 来 使 用 三 元 式 代 码 中 间 代 码 一 直 是 指 一 种 位 于 源 代 码 和 目 标 代 码 ( 例 如 三 元 式 代 码 或 类 似 的 线 性 表 示 ) 之 间 的 代 码 表 示 形 式 但 是, 我 们 可 以 更 概 括 地 认 为 它 是 编 译 器 使 用 的 源 代 码 的 任 何 一 个 内 部 表 示 此 时, 也 可 将 语 法 树 称 作 中 间 代 码, 源 代 码 优 化 程 序 则 确 实 能 继 续 在 其 输 出 中 使 用 这 个 表 示 有 时, 这 个 中 间 代 码 也 称 作 中 间 表 示 (intermediate representation,ir) 5. 代 码 生 成 器 (code generator) 代 码 生 成 器 得 到 中 间 代 码 (IR), 并 生 成 目 标 机 器 的 代 码 尽 管 大 多 数 编 译 器 直 接 生 成 目 标 代 码, 但 是 为 了 便 于 理 解, 本 书 用 汇 编 语 言 来 编 写 目 标 代 码 正 是 在 编 译 的 这 个 阶 段 中, 目 标 机 器 的 特 性 成 为 了 主 要 因 素 当 它 存 在 于 目 标 机 器 时, 使 用 指 令 不 仅 是 必 须 的 而 且 数 据 的 形 式 表 示 也 起 着 重 要 的 作 用 例 如, 整 型 数 据 类 型 的 变 量 和 浮 点 数 据 类 型 的 变 量 在 存 储 器 中 所 占 的 字 节 数 或 字 数 也 8

12 很 重 要 第 1 章 编 译 程 序 概 论 在 上 面 的 示 例 中, 现 在 必 须 决 定 怎 样 存 储 整 型 数 来 为 数 组 索 引 生 成 代 码 例 如, 下 面 是 所 给 表 达 式 的 一 个 可 能 的 样 本 代 码 序 列 ( 在 假 设 的 汇 编 语 言 中 ): MOV R 0, index ; ; value of index -> R 0 MUL R 0, 2 ; ; double value in R 0 MOV R 1, &a ; ; address of a -> R 1 ADD R 1, R 0 ; ; add R 0 to R 1 MOV *R 1, 6 ; ; constant 6 -> address in R 1 在 以 上 代 码 中, 为 编 址 模 式 使 用 了 一 个 类 似 C 的 协 定, 因 此 &a 是 a 的 地 址 ( 也 就 是 数 组 的 基 地 址 ),* R 1 则 意 味 着 间 接 寄 存 器 地 址 ( 因 此 最 后 一 条 指 令 将 值 6 存 放 在 R 1 包 含 的 地 址 中 ) 这 个 代 码 还 假 设 机 器 执 行 字 节 编 址, 并 且 整 型 数 占 据 存 储 器 的 两 个 字 节 ( 所 以 在 第 2 条 指 令 中 用 2 作 为 乘 数 ) 6. 目 标 代 码 优 化 程 序 (target code optimizer) 在 这 个 阶 段 中, 编 译 器 尝 试 着 改 进 由 代 码 生 成 器 生 成 的 目 标 代 码 这 种 改 进 包 括 选 择 编 址 模 式 以 提 高 性 能 将 速 度 慢 的 指 令 更 换 成 速 度 快 的, 以 及 删 除 多 余 的 操 作 在 上 面 给 出 的 样 本 目 标 代 码 中, 还 可 以 做 许 多 更 改 : 在 第 2 条 指 令 中, 利 用 移 位 指 令 替 代 乘 法 ( 通 常 地, 乘 法 很 费 时 间 ), 还 可 以 使 用 更 有 效 的 编 址 模 式 ( 例 如 用 索 引 地 址 来 执 行 数 组 存 储 ) 使 用 了 这 两 种 优 化 后, 目 标 代 码 就 变 成 : MOV R 0, index ; ; value of index -> R 0 SHL R 0 ; ; double value in R 0 MOV &a[r 0 ], 6 ; ; constant 6 -> address a+r 0 到 这 里, 对 编 译 器 阶 段 的 简 要 描 述 就 结 束 了, 但 我 们 还 应 特 别 强 调 这 些 讲 述 仅 仅 是 示 意 性 的, 也 无 需 表 示 出 正 在 工 作 中 的 编 译 器 的 实 际 结 构 编 译 器 在 其 结 构 细 节 上 确 实 差 别 很 大, 然 而, 上 面 讲 到 的 阶 段 总 会 出 现 在 几 乎 所 有 的 编 译 器 的 某 个 形 式 上 编 译 器 的 结 构 点 编 译 器 的 结 构 可 以 从 不 同 的 角 度 来 考 察, 下 面 分 别 介 绍 两 种 种 最 普 遍 的 观 1. 前 端 和 后 端 本 观 点 认 为, 将 编 译 器 分 成 了 只 依 赖 于 源 语 言 ( 前 端 (Front End)) 的 操 作 和 只 依 赖 于 目 标 语 言 ( 后 端 (Back End)) 的 操 作 两 部 分 这 与 将 其 分 成 分 析 和 综 合 两 部 分 是 类 似 的 : 扫 描 程 序 分 析 程 序 和 语 义 分 析 程 序 是 前 端, 代 码 生 成 器 是 后 端 但 是 一 些 优 化 分 析 可 以 依 赖 于 目 标 语 言, 这 样 就 是 属 于 后 端 了, 9

13 编 译 原 理 然 而 中 间 代 码 的 综 合 却 经 常 与 目 标 语 言 无 关, 因 此 也 就 属 于 前 端 了 在 理 想 情 况 下, 编 译 器 被 严 格 地 分 成 这 两 部 分, 而 中 间 表 示 则 作 为 其 间 的 交 流 媒 介 如 图 1-4 所 示 源 代 码 前 端 中 间 代 码 后 端 目 标 代 码 图 1-4 从 前 端 和 后 端 的 角 度 来 看 编 译 器 的 结 构 这 一 结 构 对 于 编 译 器 的 可 移 植 性 (Portability) 十 分 重 要, 此 时 设 计 的 编 译 器 既 能 改 变 源 代 码 ( 它 涉 及 到 重 写 前 端 ), 又 能 改 变 目 标 代 码 ( 它 还 涉 及 到 重 写 后 端 ) 在 实 际 中, 这 是 很 难 做 到 的, 而 且 称 作 可 移 植 的 编 译 器 仍 旧 依 赖 于 源 语 言 和 目 标 语 言 其 部 分 原 因 是 程 序 设 计 语 言 和 机 器 构 造 的 快 速 发 展 以 及 根 本 性 的 变 化, 但 是 有 效 地 保 持 移 植 一 个 新 的 目 标 语 言 所 需 的 信 息 或 使 数 据 结 构 普 遍 地 适 合 改 变 为 一 个 新 的 源 语 言 所 需 的 信 息 却 十 分 困 难 然 而 人 们 不 断 分 离 前 端 和 后 端 的 努 力 会 带 来 更 方 便 的 可 移 植 性 2. 分 析 和 综 合 在 这 种 观 点 中, 已 经 将 分 析 源 程 序 以 计 算 其 特 性 的 编 译 器 操 作 归 为 编 译 器 的 分 析 (Analysis) 部 分, 而 将 生 成 翻 译 代 码 时 所 涉 及 到 的 操 作 称 作 编 译 器 的 综 合 (Synthesis) 部 分 当 然, 词 法 分 析 语 法 分 析 和 语 义 分 析 均 属 于 分 析 部 分, 而 代 码 生 成 却 是 综 合 部 分 在 优 化 步 骤 中, 分 析 和 综 合 都 有 分 析 正 趋 向 于 易 懂 和 更 具 有 数 学 性, 而 综 合 则 要 求 更 深 的 专 业 技 术 因 此, 将 分 析 步 骤 和 综 合 步 骤 两 者 区 分 开 来 以 便 发 生 变 化 时 互 不 影 响 是 很 有 用 的 遍 的 概 念 编 译 器 发 现, 在 生 成 代 码 之 前 多 次 处 理 整 个 源 程 序 很 方 便 这 些 重 复 就 是 遍 (Pass) 所 谓 的 遍, 也 称 为 趟, 是 对 源 程 序 或 其 等 价 的 中 间 语 言 程 序 从 头 到 尾 扫 视 并 完 成 规 定 任 务 的 过 程 一 个 编 译 过 程 可 由 一 遍 两 遍 或 多 遍 完 成 首 遍 是 从 源 程 序 中 构 造 一 个 语 法 树 或 中 间 代 码, 在 它 之 后 的 遍 是 由 处 理 中 间 表 示 向 它 增 加 信 息 更 换 结 构 或 生 成 不 同 的 表 示 组 成 遍 可 以 和 阶 段 相 应, 也 可 无 关 遍 中 通 常 含 有 若 干 个 阶 段 实 际 上, 根 据 语 言 的 不 同, 编 译 器 可 以 是 一 遍 (One Pass) 所 有 的 阶 段 由 一 遍 完 成, 其 结 果 是 编 译 得 很 好, 但 代 码 却 不 太 有 效 Pascal 语 言 和 C 语 言 均 允 许 单 遍 编 译 (Modula-2 语 言 的 结 构 则 要 求 编 译 器 至 少 有 两 遍 ) 大 多 数 带 有 优 化 的 编 译 器 都 需 要 超 过 一 遍, 典 型 的 安 排 是 将 一 遍 用 于 扫 描 和 分 析, 另 一 遍 用 于 语 义 分 析 和 源 代 码 层 优 化, 第 3 10

14 第 1 章 编 译 程 序 概 论 遍 用 于 代 码 生 成 和 目 标 层 的 优 化 更 深 层 的 优 化 则 可 能 需 要 更 多 的 遍 :5 遍 6 遍 甚 至 8 遍 都 是 可 能 的 1.3 编 译 过 程 概 述 编 译 程 序 完 成 从 源 程 序 到 目 标 程 序 的 翻 译 工 作, 这 是 一 个 非 常 复 杂 的 过 程 这 个 过 程 可 以 划 分 成 若 干 个 阶 段, 每 个 阶 段 将 源 程 序 的 一 种 表 示 形 式 转 变 成 另 一 种 表 示 形 式, 各 个 阶 段 的 工 作 在 逻 辑 上 是 紧 密 连 接 的 一 般 来 说, 这 整 个 过 程 可 以 划 分 成 五 个 阶 段 : 词 法 分 析 语 法 分 析 中 间 代 码 生 成 代 码 优 化 和 目 标 代 码 生 成, 下 面 分 别 介 绍 各 个 阶 段 的 主 要 任 务 1. 词 法 分 析 词 法 分 析 是 第 一 阶 段, 其 主 要 任 务 是 从 左 到 右 一 个 字 符 一 个 字 符 的 读 入 源 程 序, 对 源 程 序 的 字 符 串 进 行 扫 描 和 分 解, 识 别 出 一 个 个 的 单 词 ( 也 称 为 单 词 符 号 或 符 号 ) 这 里 所 谓 的 单 词 是 指 逻 辑 上 紧 密 相 连 的 一 组 字 符, 这 些 字 符 具 有 集 体 含 义 如 基 本 字 (begin end if for while 等 ) 标 识 符 常 数 算 符 和 界 符 ( 标 点 符 号 左 右 括 号 等 等 ) 等 例 如, 下 面 给 出 的 Fortran 语 句 DO 105 I = 1, 100 词 法 分 析 的 结 果 是 识 别 出 如 下 的 单 词 符 号 : (1) 基 本 字 DO (2) 标 号 105 (3) 标 识 符 I (4) 等 号 = (5) 整 常 数 1 (6) 逗 点, (7) 整 常 数 100 这 些 单 词 是 构 成 此 Fortran 语 句 的 基 本 符 号 单 词 符 号 是 语 言 的 基 本 组 成 成 份, 是 人 们 理 解 和 编 写 程 序 的 基 本 要 素 识 别 和 理 解 这 些 要 素 是 翻 译 的 基 础 在 词 法 分 析 阶 段 的 工 作 中 所 依 循 的 是 语 言 的 构 词 规 则 2. 语 法 分 析 语 法 分 析 是 第 二 阶 段, 其 主 要 任 务 是 在 词 法 分 析 的 基 础 上, 根 据 语 言 的 语 法 规 则 ( 文 法 规 则 ), 将 单 词 序 列 分 解 成 各 类 语 法 单 位 ( 语 法 范 畴 ), 如 程 序 短 语 表 达 式 等 等 通 过 语 法 分 解, 确 定 整 个 输 入 串 是 否 构 成 一 个 语 法 上 正 确 的 程 序 语 法 分 析 所 依 循 的 是 语 言 的 语 法 规 则, 即 描 述 程 序 结 构 的 规 11

15 编 译 原 理 则 例 如, 在 一 般 的 面 向 科 学 工 程 计 算 的 语 言 中, 符 号 串 5 X+Y 代 表 一 个 算 术 表 达 式 因 而, 语 法 分 析 的 任 务 是 识 别 这 个 符 号 串 属 于 算 术 表 达 式 的 范 畴 语 法 分 析 和 语 义 分 析 本 质 上 都 是 对 源 程 序 的 结 构 进 行 分 析 但 词 法 分 析 的 任 务 仅 对 源 程 序 进 行 线 性 扫 描 即 可 完 成, 比 如 识 别 标 识 符 但 这 种 线 性 扫 描 不 能 用 于 识 别 递 归 定 义 的 语 法 成 分, 比 如 就 不 能 用 此 办 法 去 匹 配 表 达 式 中 的 括 号 3. 中 间 代 码 生 成 中 间 代 码 生 成 是 第 三 阶 段, 其 主 要 任 务 是 对 各 类 不 同 语 法 范 畴 按 语 言 的 语 义 进 行 初 步 的 翻 译 工 作 在 进 行 了 上 述 的 语 法 分 析 和 语 义 分 析 的 工 作 之 后, 有 的 编 译 程 序 将 源 程 序 变 成 一 种 内 部 的 表 示 形 式, 这 种 内 部 的 表 示 形 式 叫 做 中 间 语 言 或 者 中 间 代 码 所 谓 的 中 间 代 码 是 一 种 结 构 简 单 含 有 明 确 的 记 号 系 统, 这 种 记 号 系 统 可 以 设 计 成 为 多 种 多 样 的 形 式, 重 要 的 设 计 原 则 有 两 点 : 一 是 易 生 成 ; 二 是 易 将 它 翻 译 成 目 标 代 码 例 如, 很 多 编 译 程 序 采 用 了 一 种 与 三 地 址 指 令 非 常 近 似 的 四 元 式 作 为 中 间 代 码 这 种 四 元 式 的 形 式 是 : 算 符 左 操 作 数 右 操 作 数 结 果 它 的 意 义 是 : 对 左 右 操 作 数 进 行 某 种 运 算 ( 由 算 符 指 明 ), 把 运 算 所 得 的 值 作 为 结 果 保 留 下 来 在 采 用 四 元 式 作 为 中 间 代 码 的 情 况 下, 中 间 代 码 产 生 阶 段 的 任 务 是 按 语 言 的 语 义 规 则 把 各 类 语 法 范 畴 翻 译 成 四 元 式 序 列 例 如, 下 面 的 语 句 : Z =(X + 0.5) Y / W 可 以 被 翻 译 成 如 下 的 四 元 式 序 列 : 序 号 算 符 左 操 作 数 右 操 作 数 结 果 (1) + X 0.5 T 1 (2) T 1 Y T 1 (3) / T 2 W Z 其 中 :T 1 和 T 2 是 编 译 期 间 引 进 的 临 时 变 量 ; 第 一 个 四 元 式 的 意 义 是 把 X 的 值 加 上 0.5 存 放 于 变 量 T 1 中 ; 第 二 个 四 元 式 的 意 义 是 把 T 1 的 值 和 Y 的 值 相 乘 之 后 存 放 于 T 2 中 ; 第 三 个 四 元 式 是 指 将 T 2 的 值 除 以 Y 的 值 结 果 于 Z 中 把 语 法 范 畴 翻 译 成 中 间 代 码 所 依 循 的 是 语 言 的 语 义 规 则 一 般 而 言, 中 间 代 码 是 一 种 独 立 于 具 体 硬 件 的 记 号 系 统 常 用 的 中 间 代 码, 除 四 元 式 之 外, 还 12

16 第 1 章 编 译 程 序 概 论 有 三 元 式 间 接 三 元 式 和 逆 波 兰 式 记 号 等 但 是 对 于 一 个 具 体 的 编 译 程 序 来 说, 为 了 后 续 的 代 码 优 化 和 目 标 代 码 生 成 阶 段 的 方 便, 中 间 代 码 的 选 择 往 往 与 所 采 用 的 优 化 技 术 和 目 标 机 器 的 体 系 结 构 有 关 4. 代 码 优 化 代 码 优 化 是 第 四 阶 段, 其 主 要 任 务 是 对 前 一 阶 段 产 生 的 中 间 代 码 进 行 变 换 或 进 行 改 造, 目 的 是 使 产 生 的 目 标 代 码 更 为 高 效, 即 省 时 间 和 省 空 间 优 化 的 主 要 方 面 有 : 公 共 子 表 达 式 的 提 取 循 环 优 化 算 符 归 约 等 等 优 化 所 依 循 的 原 则 是 程 序 的 等 价 变 换 规 则 代 码 优 化 的 具 体 工 作 将 在 后 面 的 章 节 中 介 绍 5. 目 标 代 码 生 成 目 标 代 码 生 成 是 第 五 阶 段, 其 主 要 任 务 是 把 中 间 代 码 ( 或 经 优 化 处 理 后 ) 变 换 成 特 定 机 器 上 的 绝 对 指 令 代 码 或 可 重 新 定 位 的 指 令 代 码 或 汇 编 指 令 代 码 这 是 编 译 的 最 后 阶 段, 它 的 工 作 依 赖 于 机 器 的 硬 件 系 统 结 构 和 其 机 器 指 令 的 含 义 这 阶 段 的 工 作 也 是 最 复 杂 的, 它 涉 及 到 硬 件 系 统 功 能 部 件 的 运 用 机 器 指 令 的 选 择 各 种 数 据 类 型 变 量 的 存 储 空 间 分 配 及 寄 存 器 和 后 缓 寄 存 器 的 调 度 等 如 何 产 生 出 足 以 充 分 发 挥 硬 件 效 率 的 目 标 代 码 是 困 难 的 如 果 最 终 所 得 到 的 目 标 代 码 是 绝 对 机 器 指 令 代 码, 则 这 种 目 标 代 码 是 可 立 即 执 行 的 如 果 目 标 代 码 是 汇 编 指 令 代 码, 则 这 种 目 标 代 码 需 经 编 译 器 编 译 之 后 才 可 运 行 必 须 指 出, 现 代 多 数 实 用 编 译 程 序 所 产 生 的 目 标 代 码 都 是 一 种 可 重 新 定 位 的 指 令 代 码 这 种 目 标 代 码 在 运 行 前 须 借 助 于 一 个 连 接 装 配 程 序 把 各 个 目 标 模 块 连 接 在 一 起, 确 定 程 序 变 量 或 常 数 在 主 存 中 的 位 置, 对 指 令 地 址 部 分 进 行 代 真, 使 之 成 为 一 个 可 独 立 运 行 的 绝 对 指 令 代 码 程 序 前 面 提 到 的 编 译 过 程 的 阶 段 划 分 是 一 种 典 型 处 理 模 式, 事 实 上 并 非 所 有 的 编 译 程 序 都 分 成 这 样 几 个 阶 段, 有 些 编 译 程 序 并 不 要 生 成 中 间 代 码, 有 些 编 译 程 序 不 进 行 优 化, 优 化 阶 段 即 可 省 去, 有 些 最 简 单 的 编 译 程 序 在 语 法 分 析 的 阶 段 同 时 产 生 目 标 指 令 代 码 但 是 大 多 数 实 用 的 编 译 程 序 都 采 用 上 述 的 几 个 阶 段 的 工 作 过 程 1.4 编 译 程 序 的 结 构 上 述 编 译 过 程 的 5 个 阶 段 是 编 译 程 序 工 作 时 的 动 态 特 征 编 译 程 序 的 结 构 可 以 按 照 这 5 个 阶 段 的 主 要 任 务 分 模 块 设 计 编 译 程 序 的 一 个 典 型 的 总 体 框 图 1-5 所 示 13

17 编 译 原 理 源 程 序 词 法 分 析 器 表 格 管 理 语 法 分 析 器 中 间 代 码 生 成 器 优 化 段 出 错 处 理 目 标 代 码 生 成 器 目 标 程 序 图 1-5 编 译 程 序 结 构 框 图 图 中 的 词 法 分 析 器 语 法 分 析 器 中 间 代 码 生 成 器 优 化 段 和 目 标 代 码 生 成 器 将 分 别 完 成 上 节 中 5 个 阶 段 的 主 要 编 译 任 务 每 个 阶 段 的 输 出 为 下 一 阶 段 的 输 入, 第 一 阶 段 的 输 入 为 源 程 序, 最 后 阶 段 的 输 出 为 目 标 代 码 程 序 每 个 阶 段 的 工 作 都 和 表 格 管 理 和 出 错 处 理 这 两 部 分 功 能 模 块 相 关 (1) 词 法 分 析 器, 又 称 扫 描 器, 输 入 源 程 序, 进 行 词 法 分 析, 输 出 单 词 符 号 (2) 语 法 分 析 器, 又 称 分 析 器, 对 单 词 符 号 串 进 行 语 法 分 析 ( 根 据 语 法 规 则 进 行 推 导 或 归 约 ), 输 出 由 语 法 单 位 构 成 的 语 法 树, 判 断 输 入 串 是 否 构 成 语 法 上 正 确 的 程 序 (3) 中 间 代 码 生 成 器, 按 照 语 义 规 则 把 语 法 分 析 器 归 约 出 ( 或 推 导 出 ) 的 语 法 单 位 翻 译 成 一 定 形 式 的 中 间 代 码, 譬 如 四 元 式 在 有 些 编 译 程 序 中, 上 述 三 部 分 不 是 截 然 分 开 的, 而 是 相 互 穿 插 在 一 起 的, 这 样 可 以 大 大 提 高 编 译 程 序 的 执 行 效 率 (4) 优 化 段, 对 中 间 代 码 进 行 优 化 (5) 目 标 代 码 生 成 器, 把 中 间 代 码 翻 译 成 目 标 程 序 代 码 编 译 过 程 中 源 程 序 的 各 种 信 息 被 保 留 在 各 种 不 同 的 表 格 里, 编 译 各 阶 段 的 工 作 都 涉 及 到 构 造 查 找 或 更 新 有 关 的 表 格 因 此 在 编 译 程 序 中 必 须 含 有 一 组 14

18 第 1 章 编 译 程 序 概 论 管 理 各 种 表 格 的 程 序 如 果 源 程 序 有 错, 编 译 程 序 应 该 设 法 发 现, 把 出 错 信 息 报 告 给 用 户 这 部 分 也 应 该 由 专 门 的 程 序 ( 称 为 出 错 处 理 程 序 ) 来 完 成, 此 程 序 应 能 尽 可 能 的 发 现 源 程 序 中 的 错 误, 指 出 错 误 的 性 质 和 出 错 地 点, 并 且 将 错 误 所 造 成 的 影 响 限 制 在 尽 可 能 小 的 范 围 内, 使 得 源 程 序 的 其 余 部 分 能 继 续 被 编 译 下 去, 以 便 进 一 步 发 现 其 它 可 能 的 错 误 进 一 步 讲, 如 果 能 发 现 错 误 并 能 自 动 改 正 错 误, 那 当 然 更 好 了 但 是 自 动 校 正 错 误 的 代 价 是 非 常 高 的 1.5 编 译 程 序 生 成 与 构 造 以 前 人 们 构 造 编 译 程 序 大 多 数 是 用 机 器 语 言 或 汇 编 语 言 作 工 具 的 这 种 工 具 能 够 充 分 发 挥 各 种 不 同 硬 件 系 统 的 效 率, 满 足 各 种 不 同 的 具 体 要 求 但 是, 随 着 计 算 机 技 术 的 发 展, 越 来 越 多 的 人 倾 向 于 使 用 高 级 语 言 作 工 具 来 构 造 编 译 程 序 这 是 因 为 高 级 语 言 编 写 程 序 可 以 节 省 大 量 的 程 序 设 计 时 间, 而 且 构 造 出 来 的 编 译 程 序 易 于 阅 读 修 改 和 移 植 现 在 已 经 有 了 多 种 编 制 部 分 编 译 程 序 或 整 个 编 译 程 序 的 有 效 工 具 有 些 可 以 自 动 产 生 扫 描 器, 有 些 可 用 于 自 动 产 生 语 法 分 析 器, 有 些 甚 至 可 以 自 动 产 生 整 个 的 编 译 程 序 这 些 构 造 编 译 程 序 的 工 具 有 : 编 译 程 序 - 编 译 程 序 编 译 程 序 产 生 器 编 译 程 序 书 写 系 统 等, 它 们 是 按 照 对 源 语 言 和 目 标 语 言 ( 或 机 器 ) 的 形 式 描 述 ( 作 为 输 入 数 据 ) 而 自 动 产 生 编 译 程 序 的 近 年 来, 有 人 主 张 采 用 自 编 译 方 式 来 产 生 编 译 程 序 意 思 是 先 对 语 言 的 核 心 部 分 构 造 一 个 小 小 的 编 译 程 序, 再 以 它 为 工 具 构 造 一 个 能 够 编 译 更 多 语 言 成 分 的 较 大 的 编 译 程 序 如 此 继 续 下 去, 最 后 形 成 所 期 望 的 整 个 编 译 程 序 这 种 通 过 一 系 列 自 展 途 径 而 形 成 编 译 程 序 的 过 程 叫 做 自 编 译 过 程 现 在 有 些 编 译 程 序 是 通 过 移 植 而 得 到 的 即 把 某 一 台 机 器 上 的 编 译 程 序 移 植 到 另 一 台 机 器 上 这 需 要 寻 找 某 种 适 当 的 中 间 语 言 但 是, 由 于 建 立 通 用 的 中 间 语 言 是 非 常 非 常 困 难 的, 因 此, 移 植 也 只 能 再 有 限 的 几 种 语 言 和 几 种 机 器 之 间 进 行 要 在 某 一 台 机 器 上 为 某 种 语 言 构 造 一 个 编 译 程 序, 必 须 了 解 三 方 面 的 内 容 : (1) 源 程 序 对 被 编 译 的 源 语 言 ( 如 Fortran 和 Algol), 要 深 刻 理 解 其 结 构 ( 语 法 ) 和 含 义 ( 语 义 ) (2) 目 标 语 言 假 定 目 标 语 言 是 机 器 指 令, 那 么 就 必 须 搞 明 白 机 器 的 系 统 结 构 和 操 作 系 统 的 功 能 15

19 编 译 原 理 (3) 编 译 方 法 把 一 种 语 言 程 序 翻 译 成 另 一 种 语 言 程 序 的 方 法 很 多, 但 必 须 准 确 的 掌 握 一 种 或 几 种 在 着 手 构 造 一 个 具 体 的 编 译 程 序 的 时 候, 需 要 预 先 考 虑 种 种 具 体 的 因 素 ( 如 系 统 功 能 要 求 硬 件 设 备 软 件 工 具 等 等 ), 特 别 的, 必 须 估 量 这 些 因 素 对 编 译 程 序 构 造 所 造 成 的 影 响 这 也 是 构 造 编 译 程 序 的 一 个 必 要 步 骤 1.6 习 题 1. 什 么 是 编 译 程 序? 编 译 程 序 的 功 能 是 什 么? 2. 什 么 是 编 译 器? 编 译 器 的 功 能 是 什 么? 3. 与 编 译 器 有 关 的 程 序 有 哪 些? 它 们 的 功 能 是 什 么? 4. 编 译 器 的 翻 译 步 骤 有 哪 些? 5. 编 译 器 的 结 构 有 哪 几 种 不 同 的 分 法? 各 自 有 什 么 特 点? 6. 编 译 过 程 可 以 分 为 几 个 阶 段? 各 自 的 主 要 任 务 是 什 么? 7. 请 用 图 的 形 式 描 述 编 译 程 序 的 结 构 16

20 第 2 章 词 法 分 析 编 译 程 序 是 在 单 词 的 基 础 上 来 分 析 和 翻 译 源 程 序 的, 词 法 分 析 作 为 编 译 的 第 一 个 阶 段, 其 主 要 任 务 是 从 左 到 右 逐 个 字 符 的 对 源 程 序 进 行 扫 描, 产 生 一 个 个 的 单 词 符 号, 把 作 为 字 符 串 的 源 程 序 改 造 成 为 单 词 符 号 串 的 中 间 程 序 因 此, 词 法 分 析 是 编 译 的 基 础 执 行 词 法 分 析 的 程 序 称 为 词 法 分 析 器 或 扫 描 器 构 造 词 法 分 析 器 是 构 造 整 个 编 译 程 序 的 基 础 本 章 主 要 介 绍 词 法 分 析 程 序 的 基 本 理 论 和 构 造 方 法 2.1 扫 描 处 理 编 译 器 的 扫 描 或 词 法 分 析 (lexical analysis) 阶 段 可 将 源 程 序 读 作 字 符 文 件 并 将 其 分 为 若 干 个 记 号 记 号 与 自 然 语 言 中 的 单 词 类 似 : 每 一 个 记 号 都 是 表 示 源 程 序 中 信 息 单 元 的 字 符 序 列 典 型 的 有 : 关 键 字 (keyword), 例 如 if 和 while, 它 们 是 字 母 的 固 定 串 ; 标 识 符 (identifier) 是 由 用 户 定 义 的 串, 它 们 通 常 由 字 母 和 数 字 组 成 并 由 一 个 字 母 开 头 ; 特 殊 符 号 (special symbol ) 如 算 术 符 号 + 和 * 一 些 多 字 符 符 号, 如 >= 和 <> 在 各 种 情 况 中, 记 号 都 表 示 由 扫 描 程 序 从 剩 余 的 输 入 字 符 的 开 头 识 别 或 匹 配 的 某 种 字 符 格 式 扫 描 程 序 的 任 务 是 从 源 代 码 中 读 取 字 符 并 形 成 由 编 译 器 的 以 后 部 分 ( 通 常 是 分 析 程 序 ) 处 理 的 逻 辑 单 元 由 扫 描 程 序 生 成 的 逻 辑 单 元 称 作 记 号 (token), 将 字 符 组 合 成 记 号 与 在 一 个 英 语 句 子 中 将 字 母 构 成 单 词 并 确 定 单 词 的 含 义 很 相 像 此 时 它 的 任 务 很 像 拼 写 记 号 通 常 定 义 为 枚 举 类 型 的 逻 辑 项 例 如, 记 号 在 C 中 可 被 定 义 为 : typedef enum { IF, THEN, ELSE,PLUS, MINUS, NUM, ID,...} TokenType; 记 号 有 若 干 种 类 型, 这 其 中 包 括 了 保 留 字 (reserved word), 如 IF 和 THEN, 它 们 表 示 字 符 串 if 和 then ; 第 2 类 是 特 殊 符 号 (special symbol), 如 算 术 符 号 加 (PLUS) 和 减 (MINUS), 它 们 表 示 字 符 + 和 - 第 3 类 是 表 示 多 字 符 串 的 记 号, 如 NUM 和 ID, 它 们 分 别 表 示 数 字 和 标 识 符 作 为 逻 辑 项 的 记 号 必 须 与 它 们 所 表 示 的 字 符 串 完 全 区 分 开 来 例 如 : 保 留 字 记 号 IF 须 与 它 表 示 的 两 个 字 符 if 的 串 相 区 别 为 了 使 这 个 区 别 更 明 显, 由 记 号 表 示 的 字 符 串 有 时 称 作 它 的 串 值 (string value) 或 它 的 词 义 (lexeme) 某 些 记 号 只 有 一 个 词

21 编 译 原 理 义 : 保 留 字 就 具 有 这 个 特 性 但 记 号 还 可 能 表 示 无 限 多 个 语 义 例 如 标 识 符 全 由 单 个 记 号 ID 表 示, 然 而 标 识 符 有 许 多 不 同 的 串 值 来 表 示 它 们 的 单 个 名 字 因 为 编 译 器 必 须 掌 握 它 们 在 符 号 表 中 的 情 况, 所 以 不 能 忽 略 这 些 名 字 因 此, 扫 描 程 序 也 需 用 至 少 一 些 记 号 来 构 造 串 值 任 何 与 记 号 相 关 的 值 都 是 记 号 的 属 性 (attribute), 而 串 值 就 是 属 性 的 示 例 记 号 还 可 有 其 它 的 属 性 例 如,NUM 记 号 可 有 一 个 诸 如 的 串 值 属 性, 它 是 由 5 个 数 字 字 符 组 成, 但 它 还 会 有 一 个 由 其 值 计 算 所 得 的 真 实 值 组 成 的 数 字 值 属 性 在 诸 如 PLUS 这 样 的 特 殊 符 号 记 号 中, 不 仅 有 串 值 + 还 有 与 之 相 关 的 真 实 算 术 操 作 + 实 际 上, 记 号 符 号 本 身 就 可 看 作 是 简 单 的 其 它 属 性, 而 记 号 就 是 它 所 有 属 性 的 总 和 为 了 后 面 的 处 理, 扫 描 程 序 要 求 至 少 具 有 与 记 号 所 需 相 等 的 属 性 例 如 要 计 算 NUM 记 号 的 串 值, 但 由 于 从 它 的 串 值 就 可 计 算, 因 此 也 就 无 需 立 刻 计 算 它 的 数 字 值 了 另 一 方 面, 如 果 计 算 它 的 数 字 值, 就 会 丢 弃 掉 它 的 串 值 有 时 扫 描 程 序 本 身 会 完 成 在 恰 当 位 置 记 录 属 性 所 需 的 操 作, 或 直 接 将 属 性 传 到 编 译 器 后 面 的 阶 段 例 如, 扫 描 程 序 能 利 用 标 识 符 的 串 值 将 其 输 入 到 符 号 表 中, 或 在 后 面 传 送 它 由 于 扫 描 程 序 必 须 计 算 每 一 个 记 号 的 若 干 属 性, 所 以 将 所 有 的 属 性 收 集 到 一 个 单 独 构 造 的 数 据 类 型 中 是 很 有 用 的, 这 种 数 据 类 型 称 作 记 号 记 录 (token record) 可 在 C 中 将 这 样 的 记 录 说 明 为 : typedef struct { TokenType tokenval; char * stringval; int numval; } TokenRecord; 或 可 能 作 为 一 个 联 合 typedef struct { TokenType tokenval; union { char * stringval; int numval; } attribute; } TokenRecord; 以 上 假 设 只 有 标 识 符 需 要 串 值 属 性, 只 有 数 字 需 要 数 值 属 性 对 于 扫 描 程 序 一 个 更 普 通 的 安 排 是 只 返 回 记 号 值 并 将 变 量 的 其 它 属 性 放 在 编 译 器 的 其 它 部 分 访 问 得 到 的 地 方 尽 管 扫 描 程 序 的 任 务 是 将 整 个 源 程 序 转 换 为 记 号 序 列, 但 扫 描 程 序 却 很 少 一 次 性 地 完 成 它 实 际 上, 扫 描 程 序 是 在 分 析 程 序 的 控 制 下 进 18

22 第 2 章 词 法 分 析 行 操 作 的, 它 通 过 函 数 从 输 入 中 返 回 有 关 命 令 的 下 一 个 记 号, 该 函 数 有 与 C 说 明 相 似 的 说 明 : TokenType gettoken( void ); 这 个 方 式 中 声 明 的 gettoken 函 数 在 调 用 时 从 输 入 中 返 回 下 一 个 记 号, 并 计 算 诸 如 记 号 串 值 这 样 的 附 加 属 性 输 入 字 符 串 通 常 并 不 给 这 个 函 数 提 供 参 数, 但 参 数 却 被 保 存 在 缓 冲 区 中 或 由 系 统 输 入 设 备 提 供 请 考 虑 在 gettoken 的 操 作 示 例 中 以 下 的 C 源 代 码 行 : a [ index ] = 假 定 将 这 个 代 码 行 放 在 一 个 输 入 缓 冲 区 中, 它 的 下 一 个 输 入 字 符 由 箭 头 指 出, 如 下 所 示 : a [ i n d e x ] = 一 个 对 gettoken 的 调 用 现 在 需 要 跳 过 下 面 的 4 个 空 格, 识 别 由 单 个 字 符 a 组 成 的 串 a, 并 返 回 记 号 值 ID 作 为 下 个 记 号, 此 时 的 输 入 缓 冲 区 如 下 所 示 : a [ i n d e x ] = 因 此,getToken 随 后 的 调 用 将 再 次 从 左 括 号 字 符 开 始 识 别 过 程 2.2 词 法 分 析 器 的 要 求 词 法 分 析 程 序 的 输 出 词 法 分 析 程 序 的 功 能 是 读 入 源 程 序, 输 出 单 词 符 号 单 词 符 号 是 一 个 程 序 语 言 的 基 本 语 法 符 号 程 序 语 言 的 单 词 符 号 一 般 可 分 为 下 列 五 种 : (1) 基 本 字 如 FORTRAN 中 的 DIMENSION IF 和 DO 等 等 ; (2) 标 识 符 用 来 表 示 各 种 名 字, 如 变 量 名 数 组 名 过 程 名 等 ; (3) 常 数 各 种 类 型 的 常 数, 如 TRUE 等 ; (4) 运 算 符 如 + - / 等 ; (5) 算 符 如 逗 点 分 号 括 号 等 ; 一 个 程 序 语 言 的 基 本 字 运 算 符 和 界 符 都 是 确 定 的, 一 般 只 有 几 十 个 或 上 百 个 而 对 于 标 识 符 和 常 数 的 使 用 都 不 加 什 么 限 制 词 法 分 析 器 所 输 出 的 单 词 符 号 常 常 采 用 如 下 的 二 元 式 来 表 示 : 19

23 编 译 原 理 ( 单 词 种 别, 单 词 自 身 的 值 ) 单 词 种 别 是 语 法 分 析 需 要 的 信 息, 通 常 用 整 数 编 码 一 个 语 言 的 单 词 符 号 如 何 分 种, 分 成 几 种, 怎 样 编 码, 这 是 一 个 技 术 问 题, 主 要 取 决 于 处 理 上 的 方 便 如 标 识 符 一 般 统 归 为 一 种, 常 数 则 宜 按 类 型 ( 整 实 复 或 布 尔 ) 分 种 基 本 字 可 将 其 全 体 视 为 一 种, 也 可 以 一 字 一 种 等 等, 在 此 不 详 细 介 绍 如 果 一 个 种 别 只 含 一 个 单 词 符 号, 则 对 于 这 个 单 词 符 号, 种 别 编 码 就 完 全 代 表 它 自 身 了 倘 若 一 个 种 别 含 有 多 个 单 词 符 号, 则 对 于 每 一 个 单 词 符 号, 除 了 给 出 种 别 编 码 之 外, 还 应 给 出 自 身 的 值 单 词 自 身 的 值 是 编 译 其 它 阶 段 需 要 的 信 息 单 词 的 种 别 可 用 整 数 编 码 来 表 示, 假 如 标 识 符 编 码 为 1, 常 数 为 2, 保 留 字 为 3, 运 算 符 为 4, 界 符 为 5, 程 序 段 if i=5 then x:=y; 在 经 词 法 分 析 器 扫 描 后 输 出 的 单 词 符 号 和 它 们 的 表 示 如 下 : 保 留 字 if (3, if ) 标 识 符 i (2, 指 向 i 的 符 号 表 入 口 ) 等 号 = (4, = ) 常 数 5 (2, 5 ) 保 留 字 then (3, then ) 标 识 符 x (1, 指 向 x 的 符 号 表 的 入 口 ) 赋 值 号 := (4, := ) 标 识 符 y (1, 指 向 y 的 符 号 表 的 入 口 ) 分 号 ; (5, ; ) 词 法 分 析 程 序 与 语 法 分 析 程 序 的 连 接 词 法 分 析 程 序 完 成 的 是 编 译 第 一 阶 段 的 工 作 词 法 分 析 工 作 可 以 是 独 立 的 一 遍, 把 字 符 流 的 源 程 序 变 为 单 词 序 列, 输 出 在 一 个 中 间 文 件 上, 这 个 文 件 作 为 语 法 分 析 程 序 的 输 入 而 继 续 编 译 过 程 然 而, 更 一 般 的 情 况 是 将 词 法 分 析 程 序 作 为 一 个 独 立 的 子 程 序, 每 当 语 法 分 析 程 序 需 要 一 个 单 词 时, 就 调 用 该 程 序 词 法 分 析 程 序 每 得 到 一 次 调 用, 便 从 源 程 序 文 件 中 读 入 一 些 字 符, 直 到 识 别 出 一 个 单 词, 或 者 说 直 到 下 一 个 单 词 的 第 一 个 字 符 为 止 把 词 法 分 析 程 序 作 为 独 立 的 子 程 序 的 好 处, 首 先 它 可 以 使 整 个 编 译 程 序 的 结 构 更 简 洁 清 晰 和 条 理 化 词 法 分 析 比 语 法 分 析 要 简 单 的 多, 可 用 更 有 效 的 特 殊 方 法 和 工 具 进 行 处 理 ; 其 次, 它 可 以 改 进 编 译 程 序 的 效 率, 把 词 法 分 析 独 立 出 来, 采 用 专 门 的 读 字 符 和 分 离 单 词 的 技 术 可 以 大 大 的 加 快 编 译 的 速 度 ; 最 后, 它 可 以 增 强 编 译 程 序 的 可 移 植 性 此 外, 把 词 法 分 析 作 为 独 立 的 一 段 可 以 20

24 第 2 章 词 法 分 析 充 分 的 考 虑 一 些 细 节 问 题 但 是, 这 并 不 意 味 着 我 们 必 须 把 词 法 分 析 作 为 独 立 的 一 遍 当 然, 我 们 也 可 以 把 词 法 分 析 安 排 成 独 立 的 一 遍, 让 它 把 整 个 源 程 序 翻 译 成 一 连 串 的 单 词 符 号 ( 上 述 二 元 式 ) 存 放 于 外 存 中 待 语 法 分 析 程 序 进 入 工 作 时 再 对 从 外 存 中 输 进 的 这 些 单 词 符 号 进 行 分 析 2.3 状 态 转 换 图 与 词 法 分 析 器 设 计 下 面 我 们 按 照 词 法 分 析 器 的 要 求 和 任 务 来 学 习 词 法 分 析 器 的 设 计 输 入 和 预 处 理 词 法 分 析 工 作 的 第 一 步 是 输 入 源 程 序 文 本 输 入 通 常 是 一 行 一 行 的 进 行, 但 也 可 以 若 干 行 或 成 页 的 进 行 输 入 串 一 般 是 放 在 缓 冲 区 中, 这 个 缓 冲 区 称 为 输 入 缓 冲 区 词 法 分 析 器 的 工 作 可 直 接 在 这 个 缓 冲 区 中 进 行 但 在 一 般 情 况 下, 需 要 对 输 入 串 进 行 一 下 预 处 理 对 于 大 多 数 的 程 序 语 言 来 说, 空 白 符 跳 格 符 回 车 符 和 换 行 符 等 编 辑 性 字 符 除 了 出 现 在 文 字 常 数 中 外, 在 别 处 的 任 何 地 方 出 现 都 没 有 意 义, 而 注 释 部 分 则 出 现 在 程 序 的 任 何 部 分, 它 们 不 是 程 序 的 必 要 组 成 部 分, 它 们 的 存 在 仅 仅 是 改 善 程 序 的 易 读 性 和 易 理 解 性 因 此 在 预 处 理 的 时 候 应 该 把 它 们 都 去 掉 有 些 语 言 的 空 白 符 ( 一 个 或 多 个 连 在 一 起 ) 用 作 单 词 符 号 的 间 隔, 在 这 种 情 况 下, 在 预 处 理 的 时 候 可 以 把 若 干 个 空 白 符 撮 合 成 一 个 对 于 像 FORTRAN 这 种 受 书 写 格 式 限 制 的 语 言, 预 处 理 可 以 包 括 识 别 标 号 区, 区 分 语 句 标 号 ; 识 别 续 行 标 志, 把 相 继 行 接 在 一 起, 产 生 语 句 结 束 符 因 此, 预 处 理 的 工 作 包 括 : 剔 除 无 用 的 空 白 跳 格 回 车 和 换 行 等 编 辑 性 字 符 ; 对 于 像 FORTRAN 这 种 受 书 写 格 式 限 制 的 语 言 来 说, 还 可 以 包 括 : 区 分 标 号 区 捻 接 续 行 和 给 出 句 末 符 预 处 理 工 作 还 可 以 包 括 源 程 序 和 出 错 信 息 的 列 表 打 印 单 词 符 号 的 识 别 词 法 分 析 器 的 结 构 如 图 2-1 所 示 : 21

25 编 译 原 理 输 入 预 处 理 子 程 序 输 入 缓 冲 区 列 表 扫 描 缓 冲 区 扫 描 器 单 词 符 号 图 2-1 词 法 分 析 器 当 词 法 分 析 器 调 用 预 处 理 子 程 序 处 理 出 一 串 输 入 字 符 放 入 扫 描 缓 冲 区 后, 扫 描 器 就 从 此 缓 冲 区 中 值 逐 一 识 别 单 词 符 号 当 缓 冲 区 中 的 串 处 理 完 了 之 后, 它 又 调 用 预 处 理 子 程 序 装 入 新 串 单 词 符 号 的 识 别 方 法 很 多, 在 此 仅 介 绍 其 中 之 一 - 超 前 搜 索 1. 基 本 字 的 识 别 有 些 语 言 的 基 本 字 的 输 入 表 示 有 特 殊 标 志, 如 加 双 引 号 ( 如 BEGIN ) 或 加 底 线, 在 这 种 情 况 下, 基 本 字 的 识 别 是 很 直 接 的, 不 存 在 什 么 困 难 但 有 些 语 言 则 不 同 象 FORTRAN 这 样 的 语 言, 基 本 字 不 加 特 殊 保 护, 基 本 字 和 用 户 自 定 义 的 标 识 符 或 标 号 之 间 没 有 特 殊 的 界 符 作 间 隔 这 就 使 得 基 本 字 的 识 别 甚 为 麻 烦 举 例 如 下 : 1 DO99K=1,10 2 IF(5.EQ.M)GOTO55 3 DO99K= IF(5)=55 从 上 面 的 语 句 可 以 看 出, 语 句 1 和 2 分 别 是 DO 和 IF 语 句, 它 们 都 是 以 基 本 字 开 头 的 语 句 3 和 4 是 赋 值 语 句, 它 们 都 是 以 用 户 自 定 义 的 标 识 符 开 头 的 为 了 从 1 2 中 识 别 出 基 本 字 DO 和 IF, 必 须 要 能 够 区 分 语 句 1 3 和 语 句 2 4 语 句 1 3 的 区 别 在 于 等 号 之 后 的 第 一 个 界 符 : 一 个 为 逗 点, 另 一 个 为 句 末 符 语 句 2 4 的 主 要 区 别 在 于 右 括 号 后 的 第 一 个 字 符 : 一 个 为 字 母, 另 一 个 为 等 号 为 了 识 别 出 1 2 中 的 基 本 字, 我 们 必 须 超 前 扫 描 许 多 个 字 符, 超 前 到 能 够 肯 定 词 性 的 地 方 为 止 22

26 第 2 章 词 法 分 析 2. 标 识 符 的 识 别 多 数 语 言 的 标 识 符 是 字 母 开 头 的 字 母 / 数 字 串, 而 且 在 程 序 中 标 识 符 的 出 现 都 后 跟 着 算 符 或 界 符 因 此 标 识 符 的 识 别 大 多 没 有 困 难 3. 常 数 的 识 别 算 术 常 数 的 识 别 以 及 将 其 转 换 成 二 进 制 内 码 形 式 是 扫 描 器 比 较 费 时 的 一 部 分 工 作 多 数 语 言 的 常 数 的 识 别 是 很 直 接 的, 但 对 于 某 些 语 言 的 常 数 的 识 别 也 需 要 用 超 前 识 别 的 方 法 例 如 上 例 中 的 第 二 句 中 的 5.EQ.M 只 有 当 超 前 扫 描 到 字 母 Q 时 才 能 断 定 5 的 词 性 因 为 5.E08 和 5.EQ.M 的 头 三 个 字 符 完 全 一 样 4. 算 符 和 界 符 的 识 别 扫 描 器 应 把 那 些 由 多 个 字 符 复 合 成 的 界 符 和 算 符 拼 合 成 一 个 单 一 的 单 词 符 号 因 为 这 些 字 符 串 是 一 个 不 可 分 的 整 体, 若 分 划 开 来, 就 失 去 原 来 的 意 义, 在 这 里 同 样 需 超 前 搜 索 到 此 为 止, 如 果 了 解 某 一 种 语 言 的 词 法 规 则, 就 应 该 能 够 设 计 一 个 词 法 分 析 器 了 下 面 介 绍 一 种 状 态 转 换 图, 它 是 一 种 设 计 词 法 分 析 器 的 好 工 具 状 态 转 换 图 使 用 状 态 转 换 图 是 设 计 词 法 分 析 器 的 一 种 好 途 径 转 换 图 是 一 张 有 限 方 向 图 在 状 态 转 换 图 中, 结 点 代 表 状 态, 用 圆 圈 表 示 状 态 之 间 用 箭 弧 连 结 箭 弧 上 的 标 记 ( 字 符 ) 代 表 在 射 出 结 ( 即 箭 弧 始 结 ) 状 态 下 可 能 出 现 的 输 入 字 符 或 字 符 类 例 如, 图 2-2(a) 表 示, 在 状 态 1 下, 若 输 入 字 符 为 X, 则 读 进 X, 并 转 换 到 状 态 2 若 输 入 字 符 为 Y, 则 读 进 Y, 并 转 换 到 状 态 3 一 张 转 换 图 只 包 含 有 限 个 状 态 ( 即 有 限 个 结 点 ), 其 中 有 一 个 被 认 为 是 初 态, 而 且 实 际 上 至 少 要 有 一 个 终 态 ( 用 双 圈 表 示 ) 字 母 或 数 字 X 2 1 字 母 其 它 Y 图 2-2 状 态 转 换 图 (a) 图 2-2 状 态 转 换 图 (b) 一 个 状 态 转 换 图 可 用 于 识 别 ( 或 接 受 ) 一 定 的 字 符 串 例 如, 识 别 标 识 符 的 转 换 图 如 图 2-2(b) 所 示 其 中 0 为 初 态,2 为 终 态 这 个 转 换 图 的 工 作 过 程 是 : 23

27 编 译 原 理 从 初 态 0 开 始, 若 在 状 态 0 之 下 输 入 字 符 是 一 个 字 母, 则 读 进 它, 并 转 入 状 态 1 在 状 态 1 下, 若 下 一 个 输 入 的 字 符 是 字 母 或 数 字, 则 读 进 它, 并 重 新 进 入 状 态 1 一 直 重 复 这 个 过 程, 直 到 状 态 1 发 现 输 入 字 符 不 再 是 字 母 或 数 字 时 ( 这 个 字 符 也 已 被 读 进 ) 就 进 入 状 态 2 状 态 2 是 终 态, 意 味 着 到 此 已 经 识 别 出 一 个 标 识 符, 识 别 过 程 宣 告 结 束 一 种 程 序 语 言 的 所 有 单 词 符 号 的 识 别 有 时 也 可 以 用 若 干 张 状 态 转 换 图 来 表 示 虽 然 用 一 张 图 也 可 以, 但 是 用 若 干 张 图 有 助 于 概 念 的 清 晰 化 转 换 图 非 常 容 易 用 程 序 来 实 现 最 简 单 的 办 法 是 让 每 一 个 状 态 结 对 应 一 小 段 程 序 这 些 小 程 序 的 集 合 构 成 了 整 个 的 词 法 扫 描 程 序, 完 成 词 法 分 析 的 功 能 2.4 正 则 表 达 式 程 序 设 计 语 言 中 的 单 词 是 基 本 语 法 符 号 单 词 符 号 的 语 法 可 以 用 有 效 的 工 具 加 以 描 述, 并 且 基 于 这 种 描 述 工 具, 可 以 建 立 词 法 分 析 技 术, 进 而 可 以 建 立 词 法 分 析 程 序 的 自 动 构 造 方 法 正 则 表 达 式 表 示 字 符 串 的 格 式 正 则 表 达 式 r 完 全 由 它 所 匹 配 的 串 集 来 定 义 这 个 集 合 称 为 由 正 则 表 达 式 生 成 的 语 言 (language generated by the regular expression ), 写 作 L(r) 此 处 的 语 言 只 表 示 串 的 集 合, 它 与 程 序 设 计 语 言 并 无 特 殊 关 系 ( 至 少 在 此 处 是 这 样 的 ) 该 语 言 首 先 依 赖 于 适 用 的 字 符 集, 它 一 般 是 ASCII 字 符 的 集 合 或 它 的 某 个 子 集 有 时 该 集 比 ASCII 字 符 的 集 合 更 普 通 一 些, 此 处 集 合 的 元 素 称 作 符 号 (symbol) 这 个 正 规 符 号 的 集 合 称 作 字 母 表 (alphabet) 并 且 常 写 作 希 腊 符 号 (sigma) 正 则 表 达 式 r 还 包 括 字 母 表 中 的 字 符, 但 这 些 字 符 具 有 不 同 的 含 义 : 在 正 则 表 达 式 中, 所 有 的 符 号 指 的 都 是 模 式 在 本 章 中, 所 有 模 式 都 是 用 黑 斜 体 写 出 以 与 作 为 模 式 的 字 符 区 分 开 来 因 此,a 就 是 一 个 作 为 模 式 的 字 符 a 正 则 表 达 式 r 还 可 包 括 有 特 殊 含 义 的 字 符 这 样 的 字 符 称 作 元 字 符 (metacharacter) 或 元 符 号 (metasymbol) 它 们 并 不 是 字 母 表 中 的 正 规 字 符, 否 则 当 其 作 为 元 字 符 时 就 与 作 为 字 母 表 中 的 字 符 时 很 难 区 分 了 但 是 通 常 不 可 能 要 求 这 种 排 斥, 而 且 也 必 须 使 用 一 个 惯 例 来 区 分 元 字 符 的 这 两 种 用 途 在 很 多 情 况 下, 它 是 通 过 使 用 可 关 掉 元 字 符 的 特 殊 意 义 的 转 义 字 符 (escape character) 做 到 的 源 代 码 层 一 般 是 反 斜 杠 和 引 号 如 果 转 义 字 符 是 字 母 表 中 的 正 规 字 符, 则 请 注 意 它 们 本 身 也 就 是 元 字 符 了 正 规 表 达 式 也 称 为 正 规 式, 是 表 示 正 规 集 的 工 具, 也 是 我 们 用 以 描 述 单 词 符 号 的 方 便 的 工 具 24

28 第 2 章 词 法 分 析 现 在 通 过 讲 解 每 个 模 式 所 生 成 的 不 同 语 言 来 描 述 正 则 表 达 式 的 含 义 首 先 讲 一 下 基 本 正 则 表 达 式 的 集 合 ( 它 是 由 单 个 符 号 组 成 ), 之 后 再 描 述 从 已 有 的 正 则 表 达 式 生 成 一 个 新 的 正 则 表 达 式 的 运 算 它 同 构 造 算 术 表 达 式 的 方 法 类 似 : 基 本 的 算 术 表 达 式 是 由 数 字 组 成, 如 43 和 2.5 算 术 运 算 的 加 法 和 乘 法 等 可 用 来 从 已 有 的 表 达 式 中 产 生 新 的 表 达 式, 如 在 43 * 2.5 和 43* 中 从 它 们 只 包 括 了 最 基 本 的 运 算 和 元 符 号 这 一 方 面 而 言, 这 里 所 讲 到 的 一 组 正 则 表 达 式 都 是 最 小 的, 以 后 还 会 讲 得 更 深 一 些 1. 基 本 正 则 表 达 式 它 们 是 字 母 表 中 的 单 个 字 符 且 自 身 匹 配 假 设 a 是 字 母 表 中 的 任 一 字 符, 则 指 定 正 则 表 达 式 a 通 过 书 写 L(a)={a} 来 匹 配 a 字 符 而 特 殊 情 况 还 要 用 到 另 外 两 个 字 符 有 的 时 候 需 要 指 出 空 串 (empty string ) 的 匹 配, 空 串 就 是 不 包 含 任 何 字 符 的 串 空 串 用 ε( epsilon) 来 表 示, 元 符 号 ε( 黑 体 ε) 是 通 过 设 定 L(ε)={ε} 来 定 义 的 偶 尔 还 需 要 写 出 一 个 与 任 何 串 都 不 匹 配 的 符 号, 它 的 语 言 为 空 集 (empty set), 写 作 { } 我 们 用 符 号 ф 来 表 示, 并 写 作 L(ф) = { } 请 注 意 { } 和 {ε} 的 区 别 :{ } 集 不 包 括 任 何 串, 而 {ε} 则 包 含 一 个 没 有 任 何 字 符 的 串 2. 正 则 表 达 式 运 算 在 正 则 表 达 式 中 有 3 种 基 本 运 算 :1 从 各 选 择 对 象 中 选 择, 用 元 字 符 ( 竖 线 ) 表 示 2 连 结, 由 并 置 表 示 ( 不 用 元 字 符 ) 3 重 复 或 闭 包, 由 元 字 符 * 表 示 后 面 通 过 为 匹 配 了 的 串 的 语 言 提 供 相 应 的 集 合 结 构 依 次 讨 论 以 上 3 种 基 本 运 算 3. 从 各 选 择 对 象 中 选 择 如 果 r 和 s 是 正 则 表 达 式, 那 么 正 则 表 达 式 r s 可 匹 配 被 r 或 s 匹 配 的 任 意 串 从 语 言 方 面 来 看,r s 语 言 是 r 语 言 和 s 语 言 的 联 合 (union), 或 L (r s) = L(r) L(s) 以 下 是 一 个 简 单 例 子 : 正 则 表 达 式 a b 匹 配 了 a 或 b 中 的 任 一 字 符, 即 L (a b) = L (a) L (b) = {a} {b} = {a,b} 又 例 如 表 达 式 a ε 匹 配 单 个 字 符 a 或 空 串 ( 不 包 括 任 何 字 符 ), 也 就 是 L (a ε) = {a,ε} 还 可 在 多 个 选 择 对 象 中 选 择, 因 此 L (a b c d) = {a,b,c,d} 也 成 立 有 时 还 用 点 号 表 示 选 择 的 一 个 长 序 列, 如 a b... z, 它 表 示 匹 配 a~z 的 任 何 小 写 字 母 4. 连 结 正 则 表 达 式 r 和 正 则 表 达 式 s 的 连 结 可 写 作 rs, 它 匹 配 两 串 连 结 的 任 何 一 个 串, 其 中 第 1 个 匹 配 r, 第 2 个 匹 配 s 例 如 : 正 则 表 达 式 ab 只 匹 配 ab, 而 正 则 表 达 式 (a b)c 则 匹 配 串 ac 和 bc ( 下 面 将 简 要 介 绍 括 号 在 这 个 正 则 表 达 式 中 作 为 元 字 符 的 作 用 ) 可 以 通 过 由 定 义 串 的 两 个 集 合 的 连 结 所 生 成 的 语 言 来 讲 解 连 结 的 功 能 假 设 有 串 S 1 和 S 2 的 两 个 集 合, 串 S 1 S 2 的 连 结 集 合 是 将 串 S 2 完 全 附 加 到 串 S 1 上 的 25

29 编 译 原 理 集 合 上 例 如 若 S 1 = {aa,b}, S 2 = {a,bb}, 则 S 1 S 2 = {aaa,aabb,ba,bbb} 现 在 可 以 将 正 则 表 达 式 的 连 结 运 算 定 义 如 下 :L(rs)=L(r)L(s), 因 此 ( 利 用 前 面 的 示 例 ), L((a b)c) = L( a b)l (c) ={a,b}{c} = {ac,bc} 连 结 还 可 扩 展 到 两 个 以 上 的 正 则 表 达 式 :L(r 1 r 2... r n ) = L(r 1)L(r 2)...L(r n ) = 由 将 每 一 个 L(r 1 ),...,L(r n) 串 连 结 而 成 的 串 集 合 5. 重 复 正 则 表 达 式 的 重 复 有 时 称 为 Kleene 闭 包 ((Kleene) closure ), 写 作 r *, 其 中 r 是 一 个 正 则 表 达 式 正 则 表 达 式 r * 匹 配 串 的 任 意 有 穷 连 结, 每 个 连 结 均 匹 配 r 例 如 a * 匹 配 串 ε a aa aaa...( 它 与 ε 匹 配 是 因 为 ε 是 与 a 匹 配 的 非 串 连 结 ) 通 过 为 串 集 合 定 义 一 个 相 似 运 算 *, 就 可 用 生 成 的 语 言 定 义 重 复 运 算 了 假 设 有 一 个 串 的 集 合 S, 则 S* = {ε} S SS SSS... 这 是 一 个 无 穷 集 的 联 合, 但 是 其 中 的 每 一 个 元 素 都 是 S 中 串 的 有 穷 连 结 现 在 可 如 下 定 义 正 则 表 达 式 的 重 复 运 算 : L(r*) = L(r)* 例 如, 在 正 则 表 达 式 (a bb)* 中, 该 正 则 表 达 式 与 以 下 串 任 意 匹 配 :ε a bb aa abb bba bbbb aaa aabb 等 等 在 语 言 方 面,L ((a bb)*)= L (a bb)* = {a,bb}* ={ε,a,bb,aa,abb,bba,bbbb,aaa,aabb,abba,abbbb,bbaa,...} 6. 运 算 的 优 先 和 括 号 的 使 用 前 面 的 内 容 忽 略 了 选 择 连 结 和 重 复 运 算 的 优 先 问 题 例 如 对 于 正 则 表 达 式 a b*, 是 将 它 解 释 为 (a b)* 还 是 a (b*) 呢 ( 这 里 有 一 个 很 大 的 差 别, 因 为 L((a b)*) = {ε, a, b, aa, ab, ba, bb,...}, 但 L( a (b*)) = {ε,a,b,bb, bbb,...} )? 标 准 惯 例 是 重 复 的 优 先 权 较 高, 所 以 第 2 个 解 释 是 正 确 的 实 际 上, 在 这 3 个 运 算 中,* 优 先 权 最 高, 连 结 其 次, 最 末 因 此,a bc* 就 可 解 释 为 a (b(c*)), 而 ab c* d 却 解 释 为 (ab) ((c*)d) 当 需 指 出 与 上 述 不 同 的 优 先 顺 序 时, 就 必 须 使 用 括 号 这 就 是 为 什 么 用 (a b)c 能 表 示 选 择 比 连 结 有 更 高 的 优 先 权 的 原 因 而 a bc 则 被 解 释 为 与 a 或 bc 匹 配 类 似 地, 没 有 括 号 的 (a bb)* 应 解 释 为 a bb*, 它 匹 配 a b bb bbb... 此 处 括 号 的 用 法 与 其 在 算 术 中 类 似 :(3+4)*5 = 35, 而 3+4*5 = 23, 这 是 因 为 * 的 优 先 权 比 + 的 高 在 考 虑 用 一 些 例 子 来 详 细 描 述 正 则 表 达 式 的 定 义 之 前, 先 将 有 关 正 则 表 达 式 定 义 的 所 有 信 息 收 集 在 一 起 定 义 正 则 表 达 式 (regular expression ) 是 以 下 的 一 种 : (1) 基 本 (basic) 正 则 表 达 式 由 一 个 单 字 符 a ( 其 中 a 在 正 规 字 符 的 字 母 表 中 ), 以 及 元 字 符 ε 或 元 字 符 ф 组 成 在 第 1 种 情 况 下,L(a) = {a}; 在 第 2 种 情 况 下,L(ε) ={ε}; 在 第 3 种 情 况 下,L(ф) = {} (2) r s 格 式 的 表 达 式 : 其 中 r 和 s 均 是 正 则 表 达 式 在 这 种 情 况 下,L(r s) = L(r) 26

30 第 2 章 词 法 分 析 L(s) (3) rs 格 式 的 表 达 式 : 其 中 r 和 s 是 正 则 表 达 式 在 这 种 情 况 下,L(r s) = L(r) L(s) (4) r* 格 式 的 表 达 式 : 其 中 r 是 正 则 表 达 式 在 这 种 情 况 下,L(r*) = L(r)* (5) (r) 格 式 的 表 达 式 : 其 中 r 是 正 则 表 达 式 在 这 种 情 况 下,L((r)) = L(r), 因 此, 括 号 并 不 改 变 语 言, 它 们 只 调 整 运 算 的 优 先 权 我 们 注 意 到 在 上 面 这 个 定 义 中,(2) (3) 和 (4) 的 优 先 权 与 它 们 所 列 的 顺 序 相 反, 也 就 是 : 的 优 先 权 最 低, 连 结 次 之,* 则 最 高 另 外 还 注 意 到 在 这 个 定 义 中,6 个 符 号 ε ф * ( 和 ) 都 有 了 元 字 符 的 含 义 本 节 后 面 将 给 出 一 些 示 例 来 详 述 上 述 定 义, 但 它 们 并 不 经 常 作 为 记 号 描 述 在 程 序 设 计 语 言 中 出 现 在 下 面 的 示 例 中, 被 匹 配 的 串 通 常 是 英 语 描 述, 其 任 务 是 将 描 述 翻 译 为 正 则 表 达 式 还 有 另 一 种 情 况 是 将 正 则 表 达 式 翻 译 为 英 语 描 述, 参 见 下 面 的 练 习 例 2-1 在 仅 由 字 母 表 中 的 3 个 字 符 组 成 的 简 单 字 母 表 = {a,b,c } 中, 考 虑 在 这 个 字 母 表 上 的 仅 包 括 一 个 b 的 所 有 串 的 集 合, 这 个 集 合 由 正 则 表 达 式 (a c)*b(a c)* 产 生 尽 管 b 出 现 在 正 则 表 达 式 的 正 中 间, 但 字 母 b 却 无 需 位 于 被 匹 配 的 串 的 正 中 间 实 际 上, 在 b 之 前 或 之 后 的 a 或 c 的 重 复 会 发 生 不 同 的 次 数 因 此, 串 b abc abaca baaaac ccbaca 和 ccccccb 都 与 上 面 的 正 则 表 达 式 匹 配 例 2-2 在 与 上 面 相 同 的 字 母 表 中, 如 果 集 合 是 包 括 了 最 多 一 个 b 的 所 有 串, 则 这 个 集 合 的 正 则 表 达 式 可 通 过 将 上 例 的 解 作 为 一 个 解 ( 与 那 些 仅 为 一 个 b 的 串 匹 配 ), 而 正 则 表 达 式 (a c)* 则 作 为 另 一 个 解 ( 与 b 根 本 不 匹 配 ) 来 获 取 因 此 有 以 下 解 : (a c)* (a c)*b(a c)* 下 面 是 一 个 既 允 许 b 又 允 许 空 串 在 重 复 的 a 或 c 之 间 出 现 的 另 一 个 解 : (a c)*(b ε)(a c)* 例 2-3 在 字 母 表 = {a, b} 上 的 串 S 的 集 合 是 由 一 个 b 及 在 其 前 后 有 相 同 数 目 的 a 组 成 :S = {b, aba, aabaa, aaabaaa,...}={a n ba n n 0 } 正 则 表 达 式 并 不 能 描 述 这 个 集 合, 其 原 因 在 于 重 复 运 算 只 有 闭 包 运 算 * 一 种, 它 允 许 有 任 意 次 的 重 复 因 此 如 要 写 出 表 达 式 a*ba*( 尽 可 能 接 近 地 得 到 S 的 正 则 表 达 式 ), 就 不 能 保 证 在 b 前 后 的 a 的 数 量 是 否 相 等 了, 它 通 常 表 示 为 不 能 计 算 的 正 则 表 达 式 但 若 要 给 出 一 个 数 学 论 证, 则 需 使 用 有 关 正 则 表 达 式 的 称 作 Pumping 引 理 (Pumping lemma ) 的 著 名 定 理, 这 将 在 自 动 机 理 论 中 学 到, 现 在 就 不 谈 了 例 2-4 本 例 给 出 了 一 个 正 则 表 达 式, 要 求 用 英 语 简 要 地 描 述 它 生 成 的 27

31 编 译 原 理 语 言 若 有 字 母 表 = {a,b,c}, 则 正 则 表 达 式 : ((b c)*a(b c)*a)*(b c)* 生 成 了 所 有 包 括 偶 数 个 a 的 串 的 语 言 为 了 看 清 它, 可 考 虑 外 层 左 重 复 之 中 的 表 达 式 : (b c)*a(b c)*a 它 生 成 的 串 是 以 a 结 尾 且 包 含 了 两 个 a( 在 这 两 个 a 之 前 或 之 间 可 有 任 意 个 b 和 c) 重 复 这 些 串 则 得 到 所 有 以 a 结 尾 的 串, 且 a 的 个 数 是 2 的 倍 数 ( 即 偶 数 ) 在 最 后 附 加 重 复 (b c)* 则 得 到 所 需 结 果 这 个 正 则 表 达 式 还 可 写 作 : (not a* a nota* a)* not a* 2.5 有 穷 自 动 机 有 穷 自 动 机, 或 有 穷 状 态 的 机 器, 是 描 述 ( 或 机 器 ) 特 定 类 型 算 法 的 数 学 方 法 特 别 地, 有 穷 自 动 机 可 用 作 描 述 在 输 入 串 中 识 别 模 式 的 过 程, 因 此 也 能 用 作 构 造 扫 描 程 序 有 穷 自 动 机 ( 也 称 为 有 限 自 动 机 ) 作 为 一 种 识 别 装 置, 它 能 准 确 的 识 别 正 规 集, 即 识 别 正 规 文 法 所 定 义 的 语 言 和 正 规 式 所 表 示 的 集 合, 引 入 有 穷 自 动 机 这 个 理 论, 正 是 为 词 法 分 析 程 序 的 自 动 构 造 寻 找 特 殊 的 方 法 和 工 具 有 穷 自 动 机 分 为 两 类 : 确 定 的 有 穷 自 动 机 (Deterministic Finite Automata) 和 不 确 定 的 有 穷 自 动 机 (Nondeterministic Finite Automata) 下 面 我 们 分 别 介 绍 确 定 的 有 穷 自 动 机 (DFA) 和 不 确 定 的 有 穷 自 动 机 (NFA) 的 定 义 有 关 概 念 及 确 定 有 穷 自 动 机 的 化 简,NFA 到 DFA 的 转 换 等 等 确 定 的 有 穷 自 动 机 (DFA) 确 定 性 的 (deterministic) 有 穷 自 动 机, 即 : 下 一 个 状 态 由 当 前 状 态 和 当 前 输 入 字 符 唯 一 给 出 的 自 动 机 一 个 确 定 的 有 穷 自 动 机 (DFA)M 是 一 个 五 元 组 : M=(S,,f,s 0,Z) 其 中 (1) S 是 一 个 有 限 集, 它 的 每 一 个 元 素 称 为 一 个 状 态 ; (2) 是 一 个 有 穷 字 母 表, 它 的 每 一 个 元 素 称 为 一 个 输 入 字 符 ; (3) f 是 一 个 从 S 至 S 的 ( 单 值 ) 部 分 映 照 f (s,a)=s' 意 味 着 : 当 现 行 状 态 为 s, 输 入 字 符 为 a 时, 将 转 换 到 下 一 状 态 s' 我 们 把 s' 称 为 s 的 一 个 后 继 状 态 ; (4) s 0 S, 是 唯 一 的 一 个 初 态 ; (5) Z S, 是 一 个 终 态 集 ( 可 空 ) 28

32 第 2 章 词 法 分 析 一 个 DFA 可 以 用 一 个 矩 阵 来 表 示, 该 矩 阵 的 行 表 示 状 态, 列 表 示 输 入 字 符, 矩 阵 元 素 表 示 相 应 状 态 行 和 输 入 字 符 列 下 的 新 状 态, 即 k 行 a 列 为 f(k,a) 的 值 这 个 矩 阵 称 为 状 态 转 换 矩 阵 例 如, 有 DFA M=({0,1,2,3},{a,b},f,0,{3}) 其 中 f 为 : f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 所 对 应 的 状 态 转 换 矩 阵 如 表 2-1 所 示 : 表 2-1 状 态 转 换 矩 阵 字 符 a b a 1 a 状 态 b b 2 a a b 3 a,b 图 2-3 转 换 图 一 个 DFA 也 可 表 示 成 一 张 ( 确 定 的 ) 状 态 转 换 图 整 个 图 含 有 唯 一 的 一 个 初 态 结 和 若 干 个 ( 可 以 是 0 个 ) 终 态 结 上 例 中 的 状 态 转 换 图 如 图 2-3 所 示 对 于 中 的 任 何 字 α, 若 存 在 一 条 从 初 态 结 到 某 一 终 态 结 的 道 路, 且 这 条 路 上 所 有 弧 的 标 记 符 连 接 成 的 字 等 于 α, 则 称 α 可 为 DFA M 所 识 别 ( 读 出 或 接 受 ) 若 M 的 初 态 结 同 时 又 是 终 态 结, 则 空 字 ε 可 为 M 所 识 别 ( 或 接 受 ) DFA M 所 能 识 别 的 字 的 全 体 记 为 L(M) 结 论 : 上 的 一 个 字 符 串 集 V 是 正 规 的, 而 且 仅 当 存 在 一 个 上 的 确 定 的 有 穷 自 动 机 M, 使 得 V= L(M) DFA 的 确 定 性 表 现 在 映 照 f:s S 是 一 个 单 值 函 数 也 就 是 说, 对 任 何 状 态 s S 和 输 入 符 号 a, f(s,a) 唯 一 的 确 定 了 下 一 个 状 态 从 转 换 图 的 角 度 来 看, 假 定 字 母 表 含 有 n 个 输 入 字 符, 那 么, 任 何 一 个 状 态 结 顶 多 只 有 n 条 弧 射 出, 而 且 每 条 弧 以 一 个 不 同 的 输 入 字 符 标 记 例 2-5 串 中 仅 有 一 个 b 的 集 合 被 下 示 的 DFA 接 受 : 29

33 编 译 原 理 请 注 意, 在 这 里 并 未 标 出 状 态 当 无 需 用 名 字 来 指 出 状 态 时 就 忽 略 标 签 例 2-6 包 含 最 多 一 个 b 的 串 的 集 合 被 下 示 的 DFA 接 受 : 请 注 意 这 个 DFA 是 如 何 修 改 前 例 中 的 DFA, 它 将 初 始 状 态 变 成 另 一 个 的 接 受 状 态 例 2-7 科 学 表 示 法 中 数 字 常 量 的 正 则 表 达 式, 如 下 所 示 : nat = [0-9]+ signednat = (+ -)? nat number = signednat ("." nat)? (E signednat)? 我 们 想 为 由 这 些 定 义 匹 配 的 串 写 出 DFA, 但 是 先 如 下 重 写 它 会 更 为 有 用 : digit = [0-9] nat = digit+ signednat = (+ -)? nat number = signednat ("." nat)? (E signednat)? 如 下 为 nat 写 出 一 个 DFA 是 非 常 简 单 ( 请 记 住 a+ = aa* 对 任 意 的 a 均 成 立 ) 的 : 由 于 可 选 标 记,signedNat 要 略 难 一 些, 但 是 可 注 意 到 signednat 是 以 一 个 数 字 或 一 个 标 记 与 数 字 开 头, 并 写 作 以 下 的 DFA: 30

34 第 2 章 词 法 分 析 在 它 上 面 添 加 可 选 的 小 数 部 分 也 很 简 单, 如 下 所 示 : 请 注 意, 它 有 两 个 接 受 状 态, 它 们 表 示 小 数 部 分 是 可 选 的 最 后 需 要 添 加 可 选 的 指 数 部 分 要 做 到 它, 就 要 指 出 指 数 部 分 必 须 是 以 字 母 E 开 头, 且 只 能 发 生 在 前 面 的 某 个 接 受 状 态 之 后, 图 2-4 是 最 终 的 图 不 确 定 性 自 动 机 (NFA) 图 2-4 浮 点 数 的 有 穷 自 动 机 一 个 不 确 定 的 有 穷 自 动 机 (NFA)M 是 一 个 五 元 组 : M=(S,,f,s 0,Z) 其 中 (1) S 是 一 个 有 限 集, 它 的 每 一 个 元 素 称 为 一 个 状 态 ; (2) 是 一 个 有 穷 字 母 表, 它 的 每 一 个 元 素 称 为 一 个 输 入 字 符 ; (3) f 是 一 个 从 S 至 S 的 子 集 的 映 照, 即 f:s 2 S ; (4) s 0 S, 是 一 个 非 空 初 态 集 ; (5) Z S, 是 一 个 终 态 集 ( 可 空 ) 显 然, 一 个 含 有 m 个 状 态 和 n 个 输 入 字 符 的 NFA 可 表 示 成 如 下 的 一 张 状 态 转 换 图 : 这 张 图 含 有 m 个 状 态 结, 每 个 结 可 射 出 若 干 条 箭 弧 与 别 的 结 相 连 接, 每 条 弧 用 中 的 一 个 字 ( 不 一 定 要 不 同 的 字 而 且 可 以 是 空 字 ε) 作 标 记 ( 称 为 31

35 编 译 原 理 输 入 字 ), 整 个 图 至 少 含 有 一 个 初 态 结 以 及 若 干 个 ( 可 以 是 0 个 ) 终 态 结 某 些 结 既 可 以 是 初 态 结 也 可 以 是 终 态 结 对 于 中 的 任 何 字 α, 若 存 在 一 条 从 初 态 结 到 某 一 终 态 结 的 道 路, 且 这 条 路 上 所 有 弧 的 标 记 字 以 次 连 接 成 的 字 ( 不 理 睬 那 些 标 记 为 ε 的 弧 ) 等 于 α, 则 称 α 可 为 NFA M 所 识 别 ( 读 出 或 接 受 ) 若 M 的 某 些 结 既 是 初 态 结 又 是 终 态 结, 或 者 存 在 一 条 从 某 个 初 态 结 到 某 个 终 态 结 的 ε 道 路, 那 么, 空 字 ε 可 为 M 所 识 别 ( 或 接 受 ) 显 然,DFA 是 NFA 的 特 例 但 是, 对 于 每 一 个 NFA M 存 在 一 个 DFA M', 使 L(M)= L(M') 对 于 任 何 两 个 有 限 自 动 机 M 和 M', 如 果 L(M)=L(M'), 则 称 M 和 M' 是 等 价 的 自 动 机 理 论 中 有 一 个 重 要 的 结 论, 这 就 是, 判 定 任 何 两 个 有 限 自 动 机 等 价 性 的 算 法 是 存 在 的 下 面 介 绍 一 个 重 要 的 概 念 : ε- 转 换 (ε-transition) 是 无 需 考 虑 输 入 串 ( 且 无 需 消 耗 任 何 字 符 ) 就 有 可 能 发 生 的 转 换, 它 可 看 作 是 一 个 空 串 的 匹 配 空 串 在 前 面 已 讲 过 是 写 作 的 ε- 转 换 在 图 中 的 表 示 就 好 像 ε 是 一 个 真 正 的 字 符 : ε 例 2-8 考 虑 下 面 的 NFA 图 下 面 两 个 转 换 序 列 都 可 接 受 串 abb: 32 实 际 上,a 上 的 由 状 态 1 向 状 态 2 的 转 换 与 b 上 的 由 状 态 2 向 状 态 4 的 转 换 均 允 许 机 器 接 受 串 ab, 接 着 再 使 用 由 状 态 4 向 状 态 2 的 转 换, 所 有 的 串 与 正 则 表 达 式

36 第 2 章 词 法 分 析 ab+ 匹 配 类 似 地,a 上 的 由 状 态 1 向 状 态 3 的 转 换, 和 ε 上 的 由 状 态 3 向 状 态 4 的 ε- 转 换 也 允 许 接 受 与 ab* 匹 配 的 所 有 串 最 后, 由 状 态 1 向 状 态 4 的 ε- 转 换 可 接 受 与 b* 匹 配 的 所 有 串 因 此, 这 个 NFA 接 受 与 正 则 表 达 式 ab+ ab* b* 相 同 的 语 言 能 够 与 此 生 成 相 同 的 语 言 的 更 为 简 单 的 正 则 表 达 式 是 (a ε)b* 例 2-9 考 虑 下 面 的 NFA: 它 通 过 下 面 的 转 换 接 受 串 acab: 不 难 看 出, 这 个 NFA 接 受 的 语 言 实 际 上 与 由 正 则 表 达 式 (a c)*b 生 成 的 语 言 相 同 2.6 从 正 则 表 达 式 到 DFA 在 本 节 中, 我 们 将 学 到 将 正 则 表 达 式 翻 译 成 DFA 的 算 法 由 于 也 存 在 着 将 DFA 翻 译 成 正 则 表 达 式 的 算 法, 所 以 这 两 种 概 念 是 等 同 的 然 而 因 为 正 则 表 达 式 的 简 洁 性, 它 们 趋 向 于 将 DFA 当 作 记 号 来 描 述, 而 这 样 扫 描 程 序 的 生 成 就 通 常 是 从 正 则 表 达 式 开 始, 并 通 过 DFA 的 构 造 以 达 到 最 终 的 扫 描 程 序 正 是 因 为 这 一 点, 我 们 只 是 将 兴 趣 放 在 完 成 该 等 同 推 导 的 算 法 之 上 将 正 则 表 达 式 翻 译 成 DFA 的 最 简 单 算 法 是 通 过 中 间 构 造, 在 它 之 中, 正 则 表 达 式 派 生 出 一 个 NFA, 接 着 就 用 该 NFA 构 造 一 个 同 等 的 DFA 现 在 有 一 些 算 法 可 将 正 则 表 达 式 直 译 为 DFA, 但 是 它 们 很 复 杂, 且 对 中 间 构 造 也 有 些 影 响 因 此 我 们 只 关 心 两 个 算 法 : 一 个 是 将 正 则 表 达 式 翻 译 成 NFA, 另 一 个 是 将 NFA 翻 译 成 DFA 再 与 将 DFA 翻 译 成 程 序 的 一 个 算 法 合 并, 则 构 造 一 个 扫 描 程 序 的 自 动 过 程 可 分 为 3 步, 如 下 图 2-5 所 示 : 正 则 表 达 NFA DFA 程 序 图 2-5 构 造 扫 描 程 序 的 过 程 33

37 编 译 原 理 从 正 则 表 达 式 到 NFA 下 面 将 要 谈 到 的 结 构 是 Thompson 结 构 (Thompson construction ), 它 以 其 发 明 者 命 名 Thompson 结 构 利 用 - 转 换 将 正 则 表 达 式 的 机 器 片 段 粘 在 一 起 以 构 成 与 整 个 表 达 式 相 对 应 的 机 器 因 此 该 结 构 是 归 纳 的, 而 且 它 依 照 了 正 则 表 达 式 定 义 的 结 构 : 为 每 个 基 本 正 则 表 达 式 展 示 一 个 NFA, 接 着 再 显 示 如 何 通 过 连 接 子 表 达 式 的 NFA( 假 设 这 些 是 已 经 构 造 好 的 ) 得 到 每 个 正 则 表 达 式 运 算 1. 基 本 正 则 表 达 式 基 本 正 则 表 达 式 格 式 a ε 或 ф, 其 中 a 表 示 字 母 表 中 单 个 字 符 的 匹 配,ε 表 示 空 串 的 匹 配, 而 ф 则 表 示 根 本 不 是 串 的 匹 配 与 正 则 表 达 式 a 等 同 的 NFA ( 即 在 其 语 言 中 准 确 接 受 ) 的 是 : a 类 似 地, 与 ε 等 同 的 NFA 是 : ε 正 则 表 达 式 ф 的 情 况 在 实 际 的 编 译 器 中 是 不 可 能 发 生 2. 并 置 我 们 希 望 构 造 一 个 与 正 则 表 达 式 rs 等 同 的 NFA, 其 中 r 和 s 都 是 正 则 表 达 式 假 设 已 构 造 好 了 与 r 和 s 等 同 的 NFA, 并 用 NFA 对 应 r 且 与 s 类 似 来 写 出 它 : r 在 该 图 中, 圆 角 矩 形 的 左 边 圆 圈 表 示 初 始 状 态, 右 边 的 双 圆 表 示 接 受 状 态, 中 间 的 3 个 点 表 示 NFA 中 未 显 示 出 的 状 态 和 转 换 这 个 图 假 设 与 r 相 应 的 NFA 中 只 有 一 个 接 受 状 态 如 果 构 造 的 每 个 NFA 都 有 一 个 接 受 状 态, 那 么 这 个 假 设 就 要 调 整 一 下 对 于 基 本 正 则 表 达 式 的 NFA, 这 是 正 确 的 ; 且 对 于 下 面 每 个 结 构, 它 也 是 正 确 的 可 以 将 与 rs 对 应 的 NFA 构 造 如 下 : r ε s 34