编译技术--实验指导书

《编译技术--实验指导书》由会员分享，可在线阅读，更多相关《编译技术--实验指导书（12页珍藏版）》请在金锄头文库上搜索。

1、1编译技术实验指导书湘潭大学信息工程学院计算机工程系 何春梅2015-09-012实 验 课 时 说 明 编 译 技 术 课 总 课 时 为 32/8 学 时 ， 其 中 实 验课 时 为 8 学 时 ， 课 时 分 配 为 ： 前 三 个 实 验 是 必 做 实验 ： 其 中 DFA 的 模 拟 程 序 2 学 时 、 DFA 的 化 简 2 学时 、 LL(1)文 法 判 断 程 序 4 学 时 。 后 面 3 个 实 验 为 学生 根 据 自 己 安 排 选 做 实 验 。3目 录实 验 1 DFA 模 拟 程 序 1实 验 2 DFA 化 简 2实 验 3 LL(1)文 法 判 断 程

2、 序 4实 验 4 基 于 预 测 分 析 表 法 的 语 法 分 析 程 序 (1) 5实 验 5 基 于 预 测 分 析 表 法 的 语 法 分 析 程 序 (2) 6实 验 6 中 间 代 码 生 成 ： 逆 波 兰 式 的 产 生 与 计 算 84实 验 1 词 法 程 序 设 计 DFA 模 拟 程 序一 、 实 验 目 的 通 过 实 验 教 学 ， 加 深 学 生 对 所 学 的 关 于 编 译 的 理 论 知 识 的 理 解 ， 增 强 学生 对 所 学 知 识 的 综 合 应 用 能 力 ， 并 通 过 实 践 达 到 对 所 学 的 知 识 进 行 验 证 。 通 过对 D

3、FA 模 拟 程 序 实 验 ， 使 学 生 掌 握 词 法 分 析 的 实 现 技 术 ， 及 具 体 实 现 方 法 。通 过 本 实 验 加 深 对 词 法 分 析 程 序 的 功 能 及 实 现 方 法 的 理 解 。二 、 实 验 环 境 供 Windows 系 统 的 PC 机 ， 可 用 C+/C#/Java 等 编 程 工 具 编 写三 、 实 验 内 容 1、 定 义 一 个 右 线 性 正 规 文 法 ， 示 例 如 (仅 供 参 考 ) GS： S aU|bV U bV|aQ V aU|bQ Q aQ|bQ|实 验 前 要 考 虑 清 楚 用 哪 种 数 据 结 构 存

4、储 上 述 文 法 。2、 构 造 其 有 穷 确 定 自 动 机 ， 如3、 利 用 有 穷 确 定 自 动 机 M=(K, ,f, S,Z） 行 为 模 拟 程 序 算 法 ， 来 对 于 任 意给 定 的 串 ， 若 属 于 该 语 言 时 ， 该 过 程 经 有 限 次 计 算 后 就 会 停 止 并 回 答 “是 ”，若 不 属 于 ， 要 么 能 停 止 并 回 答 “不 是 ”。K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes)else return (no)四

5、、 实 验 方 式 与 要 求1、 每 位 同 学 定 义 的 语 言 或 文 法 不 同 ， 上 机 编 程 实 现2、 实 验 报 告 格 式 要 求 书 写 要 点 ： 概 要 设 计 （ 总 体 设 计 思 想 ） ； 详 细 设 计 （ 程序 主 流 程 、 自 动 机 的 存 储 格 式 、 关 键 函 数 的 流 程 图 ） ； 结 果 分 析 （ 输 入 与 输 出结 果 、 存 在 问 题 及 有 待 改 进 善 的 地 方 、 实 验 心 得 ） 。5实 验 2 DFA（ 确 定 的 有 穷 自 动 机 ） 的 化 简一 、 实 验 目 的 与 要 求通 过 设 计 、 编

6、 写 和 调 试 将 确 定 的 有 穷 自 动 机 的 状 态 数 变 为 最 少 的 C 程 序 ，使 得 学 生 掌 握 化 简 为 有 穷 自 动 机 的 过 程 中 的 相 关 概 念 和 方 法 。 DFA 的 表 现 形式 可 以 为 表 格 或 图 形 。二 、 问 题 描 述每 一 个 正 规 集 都 可 以 由 一 个 状 态 数 最 少 的 DFA 所 识 别 ， 这 个 DFA 是 唯一 的 （ 不 考 虑 同 构 的 情 况 ） 。 任 意 给 定 的 一 个 DFA， 根 据 以 下 算 法 设 计 一 个C 程 序 ， 将 该 DFA 化 简 为 与 之 等 价

7、的 最 简 DFA。三 、 算 法（ 1） 构 造 具 有 两 个 组 的 状 态 集 合 的 初 始 划 分 I： 接 受 状 态 组 F 和 非 接受 状 态 组 Non-F。（ 2） 对 I 采 用 下 面 所 述 的 过 程 来 构 造 新 的 划 分 I-new.For I 中 每 个 组 G doBegin当 且 仅 当 对 任 意 输 入 符 号 a,状 态 s 和 读 入 a 后 转 换 到 I 的 同一 组 中 ； /*最 坏 情 况 下 ， 一 个 状 态 就 可 能 成 为 一 个 组 */用 所 有 新 形 成 的 小 组 集 代 替 I-new 中 的 G;end（

8、3） 如 果 I-new=I， 令 I-final=I,再 执 行 第 （ 4） 步 ， 否 则 令 I=I=new,重 复步 骤 （ 2） 。（ 4） 在 划 分 I-final 的 每 个 状 态 组 中 选 一 个 状 态 作 为 该 组 的 代 表 。 这 些 代表 构 成 了 化 简 后 的 DFA M 状 态 。 令 s 是 一 个 代 表 状 态 ， 而 且 假 设 ： 在DFA M 中 ， 输 入 为 a 时 有 从 s 到 t 转 换 。 令 t 所 在 组 的 代 表 是 r,那 么 在 M中 有 一 个 从 s 到 r 的 转 换 ， 标 记 为 a。 令 包 含 s0

9、的 状 态 组 的 代 表 是 M的 开 始状 态 ， 并 令 M的 接 受 状 态 是 那 些 属 于 F 的 状 态 所 在 组 的 代 表 。 注 意 ,I-final的 每 个 组 或 者 仅 含 F 中 的 状 态 ， 或 者 不 含 F 中 的 状 态 。（ 5） 如 果 M含 有 死 状 态 （ 即 一 个 对 所 有 输 入 符 号 都 有 刀 自 身 的 转 换 的 非接 受 状 态 d） ,则 从 M中 去 掉 它 ； 删 除 从 开 始 状 态 不 可 到 达 的 状 态 ； 取 消 从 任何 其 他 状 态 到 死 状 态 的 转 换 。四 、 基 本 要 求1、 输

10、入 一 个 DFA M,输 出 一 个 与 之 等 价 的 最 小 化 的 DFA M， 上 机 编 程 实 现 。2、 实 验 报 告 格 式 要 求 书 写 要 点 ：概 要 设 计 （ 总 体 设 计 思 想 ） ；详 细 设 计 ： 程 序 主 流 程 、 DFA 的 存 储 格 式 （ 即 数 据 结 构 ） 、 关 键 函 数 的 流程 图 ；结 果 分 析 （ 输 入 与 输 出 结 果 、 存 在 问 题 及 有 待 改 进 善 的 地 方 、 实 验 心 得 ）6五 、 测 试 数 据输 入 下 图 的 DFA M,得 到 其 最 简 的 DFA M。 DFA M六 、 实

11、现 提 示 ：（ 1） 可 将 输 入 的 DFA 存 放 在 外 部 文 本 文 件 中 ， 也 可 以 直 接 从 NFA 转 换 得到 。 对 DFA 的 最 小 化 分 两 部 分 进 行 化 简 ， 即 分 别 对 状 态 （ 结 点 ） 和 路径 （ 弧 ） 进 行 最 小 化 ， 最 后 输 出 最 小 化 的 DFA。（ 2） 实 现 的 数 据 结 构 ：用 链 表 实 现 DFA 的 构 造 ： 由 结 点 链 表 和 转 换 弧 链 表 组 成 ：struct node /结 点 的 定 义int pos;/结 点 在 哪 个 组 中int num； /结 点 的 序 号

12、int accept; /结 点 是 否 为 接 受 状 态struct node *next; NODE;struct arc/弧 的 定 义int start; /开 始 的 顶 点 位 置char input; /弧 上 所 接 受 的 输 入 字 符int end; /结 束 的 顶 点 位 置struct arc *next;ARC;Struct groups /分 组 后 各 结 点 所 在 组 的 位 置int n; /属 于 哪 个 组int i;/在 组 中 的 位 置GROUPs;（ 3） 实 现 方 法 ：根 据 accept 的 值 为 0 还 是 1 进 行 初 次

13、划 分 I， 将 accept 为 0 的 所 有 结 点构 建 成 一 个 链 表 ， 将 accept 为 1 的 所 有 结 点 构 建 一 个 链 表 。 然 后 执 行 最 小 化函 数 ， 对 每 一 个 输 入 字 符 遍 历 以 上 个 链 表 ， 对 每 个 结 点 .num=弧 .start 的 情 况 ，查 看 该 弧 .end 的 组 号 是 否 相 等 ， 相 等 则 不 划 分 ； 若 不 相 等 ， 则 需 进 一 步 划 分 ，构 建 新 的 链 表 等 。7划 分 完 成 后 选 头 结 点 为 代 表 ， 删 除 结 点 链 表 上 其 他 结 点 ， 并

14、将 弧 线 链 表 上需 被 删 的 弧 .start 或 弧 .end 该 为 头 结 点 。实 验 3 LL(1)文 法 判 断 程 序一 、 实 验 目 的 首 先 能 让 用 户 输 入 一 个 文 法 ， 然 后 让 计 算 机 自 动 判 断 是 否 是 一 个 LL(1)文法 ， 通 过 实 验 教 学 ， 加 深 学 生 对 所 学 的 关 于 编 译 的 理 论 知 识 的 理 解 ， 增 强 学 生对 所 学 知 识 的 综 合 应 用 能 力 ， 并 通 过 实 践 达 到 对 所 学 的 知 识 进 行 验 证 。 。二 、 实 验 环 境 供 Windows 系 统

15、的 PC 机 ， 可 用 C+/C#/Java 等 编 程 工 具 编 写三 、 实 验 步 骤 1、 让 计 算 机 接 受 一 个 文 法 ， 示 例 如 (仅 供 参 考 )：GS 为 :S AB S bCA A bB B aDC AD C bD aS D c1. 2、 编 程 实 现 对 上 述 文 法 是 否 是 LL(1)文 法 的 判 断 ， 是 则 给 出 肯 定 回 答 ，否 则 给 出 否 定 回 答 。2. 判 别 是 否 是 LL(1)文 法实 验 流 程 图 如 下 ：以 链 表 或 数 组 等 数据 结 构 保 存 文 法 .求 出 能 推 出 的 非终 结 符 .计 算 FIRST 集 ,FOLLOW 集 和 SELECT集SELECT(A )SELECT(A )= ?输 出 肯 定回 答是输 出 否 定 回 答否8实 验 4-5 基 于 预 测 分 析 表 法 的 语 法 分 析 程 序一 、 实 验 目 的 通 过 对 基 于 LL(1)文 法 的 预 测 分 析 表 法