编译原理第三章语法分析

《编译原理第三章语法分析》由会员分享，可在线阅读，更多相关《编译原理第三章语法分析（41页珍藏版）》请在装配图网上搜索。

1、1 第 三 章 语 法 分 析 词 法 分 析 ： 字 母 是 元 素 ， 组 成 字 符 串 ， 记 号 的 集 合 ， 线 性 结 构语 法 分 析 ： 记 号 是 元 素 ， 组 成 句 子 ， 句 子 的 集 合 ， 树 结 构语 法 的 双 重 含 意 ：1. 语 法 规 则 ： 上 下 文 无 关 文 法 （ 子 集 LL文 法 或 LR文 法 ）2. 语 法 分 析 ： 下 推 自 动 机 （ LL或 LR分 析 器 ） ， 自 上 而 下 和 自下 而 上 分 析 本 章 主 要 内 容 ：1. 与 语 法 分 析 有 关 的 基 本 概 念 和 相 关 问 题2. 上 下 文

2、 无 关 文 法3. 自 上 而 下 分 析4. 自 下 而 上 分 析5. 上 机 作 业 第 二 部 分 ： 函 数 绘 图 语 言 的 语 法 分 析 器 2 3.1 语 法 分 析 的 若 干 问 题 3.1.1 语 法 分 析 器 的 作 用 语 法 分 析 器 是 编 译 器 前 端 的 重 要 组 成 部 分 ， 许 多 编 译 器 ，特 别 是 由 自 动 生 成 工 具 构 造 的 编 译 器 ， 往 往 其 前 端 的 中 心 部件 就 是 语 法 分 析 器 。 语 法 分 析 器 在 编 译 器 中 的 位 置 和 作 用 ： 3 3.1.1 语 法 分 析 器 的 作

3、 用 （ 续 ）1. 根 据 词 法 分 析 器 提 供 的 记 号 流 ， 为 语 法 正 确 的 输 入 构 造分 析 树 （ 或 语 法 树 ） ， 这 是 本 章 的 重 点 ， 在 以 后 各 节 中详 细 讨 论 ；2. 检 查 输 入 中 的 语 法 （ 可 能 包 括 词 法 ） 错 误 ， 并 调 用 出 错处 理 器 进 行 适 当 处 理 ， 下 边 简 单 介 绍 语 法 错 误 处 理 的 基本 原 则 ， 而 在 以 后 的 讨 论 中 忽 略 此 问 题 。 语 法 分 析 器 的 两 个 重 要 作 用 ： 4 3.1.2 语 法 错 误 的 处 理 原 则 1

4、. 词 法 错 误 如 非 法 字 符 或 拼 写 错 关 键 字 、 标 识 符 等 intege 20times2. 语 法 错 误 是 指 语 法 结 构 出 错 ， 如 少 分 号 、 begin/end不 配 对 等begin x:=a+b y:=x;3. 静 态 语 义 错 误 ： 如 类 型 不 一 致 、 参 数 不 匹 配 等a,b:integer; x:array1.10 of integer;x:=a+b;4. 动 态 语 义 错 误 (逻 辑 错 误 )： 如 死 循 环 、 变 量 为 零 时 作 除 数 等while (t) .; a:=a/b; 源 程 序 中 可

5、 能 出 现 的 错 误 两 类 ： 语 法 （ 包 括 词 法 ） 错 误 和 语 义 错 误 5 3.1.2 语 法 错 误 的 处 理 原 则 （ 续 1） 大 多 数 错 误 的 诊 断 和 恢 复 集 中 在 语 法 分 析 阶 段 。 一 个 原因 是 大 多 数 错 误 是 语 法 错 误 ， 另 一 个 原 因 是 语 法 分 析 方 法 的准 确 性 ， 它 们 能 以 非 常 有 效 的 方 法 诊 断 语 法 错 误 。 编 译 时 想 要 准 确 诊 断 语 义 或 逻 辑 错 误 有 时 是 很 困 难 的 。 对 语 法 错 误 的 处 理 ， 一 般 希 望 达

6、到 以 下 基 本 目 标 ：1. 清 楚 而 准 确 地 报 告 错 误 的 出 现 ， 地 点 正 确 、 不 漏 报 、不 错 报 也 不 多 报 ；2. 迅 速 从 每 个 错 误 中 恢 复 过 来 （ 以 便 分 析 继 续 进 行 ） ；3. 不 应 使 对 语 法 正 确 源 程 序 的 分 析 速 度 降 低 太 多 。 语 法 错 误 处 理 的 目 标 6 3.1.2 语 法 错 误 的 处 理 原 则 （ 续 2）1. 紧 急 方 式 恢 复 ： 抛 弃 若 干 输 入 ， 直 到 遇 到 同 步 记 号 。2. 短 语 级 恢 复 ： 采 用 串 替 换 的 方 式

7、对 剩 余 输 入 进 行 局 部纠 正 （ 抛 弃 插 入 ） 。3. 出 错 产 生 式 ： 用 出 错 产 生 式 捕 捉 错 误 （ 预 测 错 误 ） 。预 置 型 的 短 语 级 恢 复 方 式 。4. 全 局 纠 正 ： 对 错 误 输 入 序 列 x， 找 相 近 序 列 y， 使 得 x变 换 成 y所 需 的 修 改 、 插 入 、 删 除 次 数 最 少 。 语 法 错 误 的 基 本 恢 复 策 略 7 3.1.2 语 法 错 误 的 处 理 原 则 （ 续 3）1. 紧 急 方 式 ： x := a + b + d; - 丢 弃 b后 若 干 记 号 ， 直 到 遇

8、到 +2. 短 语 级 恢 复 ： x := a + b; - 加 入 分 号 ， 使 之 成 为 一 个 赋 值 句 y := c + d; 例 3.1 下 述 两 条 是 有 语 法 错 误 的 语 句 ， 其 中 第 一 条 赋 值 句 结束 时 忘 记 加 分 号 ， 采 用 紧 急 恢 复 方 式 和 短 语 级 恢 复 方 式 的 可能 结 果 分 别 如 下 所 示 。x := a + by := c + d; 8 3.2 上 下 文 无 关 文 法 (Context Free Grammar,CFG)3.2.1 CFG的 定 义 与 表 示 定 义 3.1 CFG是 一 个 四

9、 元 组 G =（ N， T， P， S） ， 其 中（ 1） N是 非 终 结 符 （ Nonterminals） 的 有 限 集 合 ；（ 2） T是 终 结 符 （ Terminals） 的 有 限 集 合 ， 且 N T= ；（ 3） P是 产 生 式 （ Productions） 的 有 限 集 合 ， A ， 其 中 A N（ 左 部 ） ， (N T)*（ 右 部 ） ， 若 = ， 则 称 A 为 空 产 生 式 （ 也 可 以 记 为 A ） ；（ 4） S是 非 终 结 符 ， 称 为 文 法 的 开 始 符 号 （ Start symbol）。 9 3.2.1 CFG的

10、定 义 与 表 示 （ 续 1）N = E T = +， *， (， )， -， id S = EP: E E + E （ 1） E E * E （ 2） E （ E） （ 3） (G3.1) E -E （ 4） E id （ 5） 例 3.2 简 单 算 术 表 达 式 的 上 下 文 无 关 文 法 可 表 示 如 下 ： 产 生 式 的 一 般 读 法 可 以 将 产 生 式 中 的 记 号 读 作 “ 定 义 为 ” 或 者 “ 可 导 出” 。 更 一 般 的 ， “ E E + E” 可 用 自 然 语 言 表 述 为 “ 算 术表 达 式 定 义 为 两 个 算 术 表 达 式

11、相 加 ” 。 或 者 “ 一 个 算 术 表 达 式 加 上 另 一 个 算 术 表 达 式 ， 仍 然 是一 个 算 术 表 达 式 ” 。 10 3.2.1 CFG的 定 义 与 表 示 （ 续 2）前 提 ： 若 文 法 正 确 ， 第 一 个 产 生 式 的 左 部 是 文 法 开 始 符 号 S则 ： N是 可 以 出 现 在 产 生 式 左 边 符 号 的 集 合 ， T是 绝 不 出 现 在 产 生 式 左 边 符 号 的 集 合 （ 记 号 ）P: E E + E （ 1） E E * E （ 2） E （ E） （ 3） E -E （ 4） E id （ 5） S=EN=E

12、T=+， *， (， )， -， id 由 产 生 式 集 表 示 CFG 11 3.2.1 CFG的 定 义 与 表 示 （ 续 3）(a) 用 大 小 写 区 分 ： E id(b) 用 区 分 ： E id E E + E(c) 用 区 分 ： + 约 定 ： 大 写 英 文 字 母 A、 B、 C表 示 非 终 结 符 ； 小 写 英 文 字 母 a、 b、 c表 示 终 结 符 ； 小 写 希 腊 字 母 、 、 表 示 任 意 文 法 符 号 序 列 。 终 结 符 与 非 终 结 符 书 写 上 的 区 分 12 3.2.1 CFG的 定 义 与 表 示 （ 续 4） 当 若 干

13、 个 产 生 式 具 有 相 同 的 左 部 非 终 结 符 时 ， 可 以 将 它 们合 并 为 一 个 产 生 式 。 该 产 生 式 的 左 部 是 此 非 终 结 符 ， 右 部 是 所 有 原 来 右 部 的 或 运 算 （ 并 集 合 ） ， 产 生 式 以 该 非 终 结 符 命 名 。 例 3.3 G3.1可 以 重 写 为 如 下 形 式 ： E E + E （ 1） | E * E （ 2） |（ E） （ 3） (G3.2) | -E （ 4） | id （ 5） P: E E + E （ 1） E E * E （ 2） E （ E） （ 3） E -E （ 4） E i

14、d （ 5） 产 生 式 的 缩 写 形 式称 其 为 E产 生 式 。用 “ |” 连 接 的 每 个 右 部 称 为 一 个 候 选 项 ， 具 有 平 等 的 权 利 。 即 id是 一 个 表 达 式 ， -E也 是 一 个 表 达 式 。 13 3.2.2 CFG产 生 语 言 的 基 本 方 法 推 导 CFG（ 产 生 式 ） 通 过 推 导 的 方 法 产 生 语 言 。 通 俗 地 讲 ， 产 生 式 产 生 语 言 的 过 程 是 从 开 始 符 号 S开 始 ，对 产 生 式 左 部 的 非 终 结 符 反 复 地 使 用 产 生 式 ： 将 产 生 式 左 部 的 非

15、终 结 符 替 换 为 右 部 的 文 法 符 号 序 列 (展开 产 生 式 ， 用 标 记 =表 示 )， 直 到 得 到 一 个 终 结 符 序 列 。 E = -E by(4) = -(E) by(3) = -(E+E) by(1) = -(id+E) by(5) = -(id+id) by(5)E E + E （ 1） | E * E （ 2） |（ E） （ 3） (G3.2) | -E （ 4） | id （ 5）例 3.4 用 (G3.2)产 生 终 结 符 序 列 -(id+id)可 如 下 ： 14 3.2.2 CFG产 生 语 言 的 基 本 方 法 推 导 （ 续 1）

16、 若 对 于 任 意 文 法 符 号 序 列 1， 2， . n， 均 有 1= 2=.= n， 则 称 此 过 程 为 零 步 或 多 步 推 导 ， 记 为 ： 1=* n， 其 中 1= n的 情 况 为 零 步 推 导 。 若 1 n， 即 推 导 过 程 中 至 少 使 用 一 次 产 生 式 ， 则 称 此过 程 为 至 少 一 步 推 导 ， 记 为 ： 1= + n。 定 义 3.2强 调 了 两 点 ： ， 有 =* ， 即 推 导 具 有 自 反 性 ； 若 =* ， =* ， 则 =* ， 即 推 导 具 有 传 递 性 。定 义 3.2 利 用 产 生 式 产 生 句

17、子 的 过 程 中 ， 将 产 生 式 A 的 右部 代 替 文 法 符 号 序 列 A 中 的 A得 到 的 过 程 ， 称 A直 接 推 导 出 ， 记 作 ： A = 。 15 3.2.2 CFG产 生 语 言 的 基 本 方 法 推 导 （ 续 2）定 义 3.3 由 CFG G所 产 生 的 语 言 L(G)被 定 义 为 : L(G) = S=+ and T* ， L(G)称 为 上 下 文 无 关 语 言 (Context Free Language, CFL)， 称 为 句 子 。 若 S=* ， (N T)*， 则 称 为 G的 一 个 句 型 。 定 义 3.4 在 推 导

18、 过 程 中 ， 若 每 次 直 接 推 导 均 替 换 句 型 中 最 左边 的 非 终 结 符 ， 则 称 为 最 左 推 导 ， 由 最 左 推 导 产 生 的 句 型 被称 为 左 句 型 。 类 似 的 可 以 定 义 最 右 推 导 与 右 句 型 ， 最 右 推 导 也 被 称 为规 范 推 导 。 16 3.2.2 CFG产 生 语 言 的 基 本 方 法 推 导 （ 续 3） E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 1 2 3 4 5 6E E + E （ 1） | E * E （ 2） |（ E） （ 3） (G3.2) |

19、-E （ 4） | id （ 5）再 考 察 -(id+id)的 推 导 过 程 （ 这 是 一 个 最 左 推 导 ） ： 其 中 ， 1是 文 法 开 始 符 号 ， 6是 句 子 ， 其 他 i (i=2、 3、 4、 5)均 是 句 型 。 句 型 是 一 个 相 当 广 泛 的 概 念 ， 根 据 定 义 3.3可 知 ， 1和 6同 样 也 是 句 型 。 17 3.2.3 推 导 、 分 析 树 与 语 法 树 对 于 推 导 ： E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 它 产 生 句 子 的 方 式 很 不 直 观 ， 看 起 来

20、 十 分 困 难 。 分 析 树 是 推 导 的 图 形 表 示 ， 它 的 表 示 很 直 观 ， 并 且 同 时反 映 语 言 结 构 的 实 质 和 推 导 过 程 。 定 义 3.5 对 CFG G的 句 型 ， 分 析 树 被 定 义 为 具 有 下 述 性 质 的 一棵 树 。 （ 1） 根 由 开 始 符 号 所 标 记 ； （ 2） 每 个 叶 子 由 一 个 终 结 符 、 非 终 结 符 、 或 标 记 ； （ 3） 每 个 内 部 结 点 由 一 个 非 终 结 符 标 记 ； （ 4） 若 A是 某 内 部 节 点 的 标 记 ， 且 X1， X2， .， Xn是 该

21、节点 从 左 到 右 所 有 孩 子 的 标 记 ， 则 A X1X2.Xn是 一 个 产 生 式。 若 A ， 则 标 记 为 A的 结 点 可 以 仅 有 一 个 标 记 为 的 孩 子 。 18 3.2.3 推 导 、 分 析 树 与 语 法 树 （ 续 1）1. 每 一 直 接 推 导 (每 个 产 生 式 )， 对 应 一 棵 仅 有 父 子 关 系 的子 树 ， 即 产 生 式 左 部 非 终 结 符 “ 长 出 ” 右 部 的 孩 子 ；2. 分 析 树 的 叶 子 ， 从 左 到 右 构 成 G的 一 个 句 型 。 若 叶 子 仅由 终 结 符 标 记 ， 则 构 成 一 个

22、 句 子 。分 析 树 与 语 言 和 文 法 的 关 系 ： 19 3.2.3 推 导 、 分 析 树 与 语 法 树 （ 续 2） E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 用 分 析 树 的 方 式 如 下 ：1. 最 左 推 导 和 最 右 推 导 的 中 间 过 程 对 应 的 分 析 树 可 能 不 同 ， 因为 句 型 不 同 ： -(id+E) 或 -(E+id) 2. 但 是 最 终 的 分 析 树 相 同 ， 因 为 最 终 是 同 一 个 句 子 ： -(id+id) 例 3.5 再 考 察 -(id+id)的 推 导 过 程

23、 。 分 析 树 既 反 映 了 产 生句 型 的 推 导 过 程 ， 又 反 映了 句 型 的 结 构 。 20 3.2.3 推 导 、 分 析 树 与 语 法 树 （ 续 3）更 多 的 情 况 下 ， 仅 关 注 句 型 结 构 ， 而 忽 略 推 导 过 程 。 定 义 3.6 对 CFG G的 句 型 ， 表 达 式 的 语 法 树 被 定 义 为 具 有 下述 性 质 的 一 棵 树 : （ 1） 根 与 内 部 节 点 由 表 达 式 中 的 操 作 符 标 记 ； （ 2） 叶 子 由 表 达 式 中 的 操 作 数 标 记 ； （ 3） 用 于 改 变 运 算 优 先 级 和

24、 结 合 性 的 括 弧 ， 被 隐 含 在 语法 树 的 结 构 中 。 实 质 上 ， 语 法 树 与 分 析 树 的 最 根 本 区 别 在 于 它 们 的 内部 节 点 （ 包 括 根 节 点 ） ： 分 析 树 的 内 部 节 点 是 非 终 结 符 ； 语 法 树 的 内 部 节 点 是 操 作 符 （ 运 算 符 ） ； 或 者 说 语 法 树 中 省 略 了 反 映 分 析 过 程 的 非 终 结 符 。 21 3.2.3 推 导 、 分 析 树 与 语 法 树 （ 续 4）例 3.6 句 子 -(id+id)和 句 型 if C then s1 else s2 ： idid分

25、 析 树 ： 左 部 非 终 结 符 “ 产 生 出 ” 右 部 文 法 符 号 序 列 ；语 法 树 ： 操 作 符 （ 运 算 ） “ 作 用 于 ” 操 作 数 （ 运 算 对 象 ） ；习 惯 上 ： 它 们 分 别 被 称 为 具 体 语 法 树 和 抽 象 语 法 树 。 22结 束 （ 第 七 次 课 ） 定 义 3.1 CFG定 义 3.2 直 接 推 导 、 零 或 多 步 推 导 、 至 少 一 步 推 导定 义 3.3 CFL、 句 子 、 句 型定 义 3.4 最 左 推 导 、 左 句 型 （ 最 右 推 导 、 右 句 型 ）定 义 3.5 分 析 树定 义 3.6

26、 语 法 树今 天 的 重 要 概 念 23 上 次 课 程 内 容 回 顾1. 语 法 分 析 的 基 本 概 念 、 语 法 错 误 处 理 简 介2. 上 下 文 无 关 文 法 （ CFG） 文 法 的 定 义 文 法 的 表 示 （ 产 生 式 、 终 结 符 与 非 终 结 符 的 区 分 ）3. CFG产 生 语 言 的 基 本 方 法 推 导 推 导 的 基 本 概 念 用 推 导 的 方 法 产 生 的 语 言 （ CFL， 句 子 与 句 型 ） 推 导 的 直 观 表 示 分 析 树4. 分 析 树 与 语 法 树 二 者 的 特 点 与 区 别 24 3.2.4 二 义

27、 性 与 二 义 性 的 消 除3.2.4.1 二 义 性 （ 歧 义 ， Ambiguity） 问 题 ： 一 个 句 子 可 能 对 应 多 于 一 棵 分 析 树例 3.7 句 子 id+id*id和 id+id+id可 能 的 分 析 树 ：E E+E | E*E |（ E） | -E | id (G3.2) *优 先 级 高 +优 先 级 高 +左 结 合 +右 结 合 25 3.2.4.1 二 义 性 （ 续 1）原 因 ： 在 产 生 句 子 的 过 程 中 某 些 直 接 推 导 有 多 于 一 种 选 择注 意 ：1. 一 个 句 子 有 多 于 一 棵 分 析 树 ， 仅

28、与 文 法 和 句 子 有 关 ，与 采 用 的 推 导 方 法 无 关 ；2. 文 法 中 缺 少 对 文 法 符 号 优 先 级 和 结 合 性 的 规 定 。 定 义 3.7 若 文 法 G对 同 一 句 子 产 生 不 止 一 棵 分 析 树 ， 则 称 G是二 义 的 。 26 3.2.4.1 二 义 性 （ 续 2）S if C then S (1) | if C then S else S (2) | id := E (3) (G3.3)C E = E | E E (4).(6)E E + E | - E | id | n (7).(10)例 3.8 条 件 语 句 if x0

29、then x:=5 else x:=-5 if x0 then x:=5 else x:=-5“ 悬 空 （ dangling） else” 问 题 else与 离 它 远 的 then匹 配 27 3.2.4.1 二 义 性 （ 续 3）if x0 then x:=5 else x:=-5例 3.8 条 件 语 句 if x0 then x:=5 else x:=-5 else与 离 它 近 的 then匹 配 28 3.2.4.2 二 义 性 的 消 除 文 法 二 义 不 能 说 明 程 序 设 计 语 言是 二 义 。 程 序 设 计 语 言 不 能 二 义 。消 除 文 法 二 义

30、的 两 种 方 法 ： 改 写 二 义 文 法 为 非 二 义 文 法 ； 规 定 二 义 文 法 中 符 号 的 优 先 级 和结 合 性 ， 使 仅 产 生 一 棵 分 析 树 。 改 写 二 义 文 法 为 非 二 义 文 法 再 分 析 id+id*id和 id+id+id：例 3.9 与 G3.2等 价 的 非 二 义 文 法 : E E + T | T T T * F | F (G3.4) F （ E） | -F | id问 题 ： 如 何 将 二 义 文 法 改 写 为 非 二 义 文 法 ？ E E+E | E*E |（ E） (G3.2) | -E | id 29 改 写 二

31、 义 文 法 为 非 二 义 文 法 （ 续 1）1. 新 引 入 的 非 终 结 符 ， 限 制 了 每 一 步 直 接 推 导 均 有 唯 一 选 择 ；2. 最 终 分 析 树 的 形 状 ， 仅 与 文 法 有 关 ， 而 与 推 导 方 法 无 关 ；3. 非 终 结 符 的 引 入 ， 增 加 了 推 导 步 骤 （ 分 析 树 增 高 ） ；4. 越 接 近 S的 文 法 符 号 的 优 先 级 越 低 。 （ 如 E E+T） 。5. 对 于 A A ， 若 A在 终 结 符 左 边 出 现 （ 即 终 结 符 在 中 ） ，则 A产 生 式 具 有 左 结 合 性 质 。 改

32、 写 二 义 文 法 的 关 键 步 骤 ：1. 引 入 一 个 新 的 非 终 结 符 ， 增 加 一 个 子结 构 并 提 高 一 级 优 先 级 ；2. 递 归 非 终 结 符 在 终 结 符 左 边 ， 运 算 具有 左 结 合 性 ， 否 则 具 有 右 结 合 性 。 可 以 看 出 ： 30 例 3.10 改 写 二 义 文 法 G3.2为 G3.4 1. 优 先 级 ： + * ( ), -, id2. 结 合 性 ： 左 结 合 +, *右 结 合 -无 结 合 id3. 非 终 结 符 与 运 算 ：E:+ （ E产 生 式 ， 左 递 归 ）T:*， （ T产 生 式 ，

33、 左 递 归 ）F:-,( ),id （ F产 生 式 ， 右 递 归 ）E E + T | TT T * F | F F (E) | -F | id1. 引 入 一 个 新 的 非 终 结 符 ， 增 加 一 个 子 结 构 并 提 高 一级 优 先 级 ；2. 递 归 非 终 结 符 在 终 结 符 左 边 ， 运 算 具 有 左 结 合 性 ，否 则 具 有 右 结 合 性 。 E E + E | E * E |（ E ） (G3.2) | - E | id 31 改 写 二 义 文 法 为 非 二 义 文 法 （ 续 2） if-then-else和 if-then： 在 一 个 复

34、合 if语 句 中 ， 可 能then多 于 else， 使 得 else不 知 与 哪 个 then结 合 。 一 般 原 则 是 右 结 合 ， 即 else与 其 左 边 最 靠 近 的 then结 合 。 改 写 文 法 的 根 据 是 将 S分 为 完 全 匹 配 （ MS） 和 不 完 全 匹 配（ UMS） 两 类 ， 并 且 在 UMS中 规 定 else右 结 合 。 S if C then S | if C then S else S | i d : = E (G3.3)C E=E | EEE E+E | -E | id | nS MS (1) | UMS (2)MS if

35、 C then MS else MS (3) | id := E (4)UMS if C then S (5) | if C then MS else UMS (6) (G3.5)再 讨 论 “ 悬 空 else” 问 题E E + T | T (10).(11) T (E) | -T | id | n (12).(15)C E = E | E E (7).(9) 32 改 写 二 义 文 法 为 非 二 义 文 法 （ 续 3）if x0 then x:=5 else x:=-5S MS (1) | UMS (2)MS if C then MS else MS (3) | id := E (

36、4)UMS if C then S (5) (G3.5) | if C then MS else UMS (6)C E = E | E E (7).(9)E E + T | T (10).(11) T （ E） | -T | id | n (12).(15) 33 改 写 二 义 文 法 为 非 二 义 文 法 （ 续 4）S MS (1) | UMS (2)MS if C then MS else MS (3) | id := E (4)UMS if C then S (5) (G3.5) | if C then MS else UMS (6)if x0 then x:=5 else x:=

37、-5 不 可 能 ！不 可 能 ！不 可 能 ！ 34 为 文 法 符 号 规 定 优 先 级 和 结 合 性二 义 文 法 的 优 点 ： 比 非 二 义 文 法 容 易 理 解 ； 分 析 效 率 高 （ 分 析 树 低 ， 直 接 推 导 步 骤 少 ） 。对 于 ： id+id*id 为 二 义 文 法 规 定 优 先 级 和 结 合 性 （ YACC的 方 法 ） ： E : E + E | E * E | - E | ( E ) | idE E + E | E * E | - E | ( E ) | id E E+T|TT T*F|FF (E)|-F|id%left +%left

38、*%right - 35 修 改 语 言 的 语 法 （ 表 现 形 式 被 改 变 ）if x0then x:=5;end if;else x:=-5;end if; 给 表 达 式 加 括 号 ， 如 Pascal中 逻 辑 和 算 术 运 算 ：(a+b)(c*d) 明 确 给 出 结 束 标 志 ， 如 Ada中 用 end if， 于 是 有 ：if x0then x:=5;else x:=-5;end if;end if;if x0 then x:=5; end if; else x:=-5; end if;if x0 then x:=5; else x:=-5; end if;

39、end if; 36 3.3 语 言 与 文 法 简 介 文 法 的 重 要 作 用 ：1. 给 出 精 确 、 易 于 理 解 的 语 言 结 构 说 明 ；2. 以 文 法 为 基 础 的 语 言 ， 便 于 加 入 新 的 、 或 修 改 、 删 除旧 的 语 言 结 构 ；3. 有 些 类 别 的 文 法 ， 可 以 自 动 生 成 高 效 的 分 析 器 。 本 节 从 理 论 的 角 度 对 文 法 进 行 简 单 地 讨 论 。 讨 论 建 立 在形 式 语 言 与 自 动 机 的 理 论 之 上 ， 且 仅 引 用 结 论 而 忽 略 数 学 的证 明 ， 有 兴 趣 的 同

40、学 可 以 参 阅 相 关 文 献 。 希 望 通 过 本 节 的 讨 论 ， 对 文 法 的 分 类 和 它 们 在 编 译 器 构造 中 的 作 用 有 一 定 的 了 解 。 37 3.3.1 正 规 式 与 上 下 文 无 关 文 法 正 规 式 到 CFG的 转 换推 论 3.1 正 规 式 所 描 述 的 语 言 结 构 均 可 用 CFG描 述 ， 反 之 不 一 定 。 从 正 规 式 到 CFG的 对 应 关 系 ： 1. 构 造 正 规 式 的 NFA；2. 若 0为 初 态 ， 则 A0为 开 始 符 号 ；3. 对 于 move(i,a)=j， 引 入 产 生 式 Ai

41、 aAj；4. 对 于 move(i, )=j， 引 入 产 生 式 Ai Aj；5. 若 i是 终 态 ， 则 引 入 产 生 式 Ai 。例 3.11 从 正 规 式 r=(a|b) *abb的 NFA构 造 CFG： A0 aA0|bA0|aA1A1 bA2A2 bA3A3 经 验 的 方 法 ：A HTH | Ha | HbT abb 产 生 abb的 分 析 树 ： 38 为 什 么 用 正 规 式 而 不 用 CFG描 述 词 法 1. 词 法 规 则 简 单 ， 用 正 规 式 描 述 已 足 够 ；2. 正 规 式 的 表 示 比 CFG更 直 观 、 简 洁 、 易 于 理

42、解 ；3. 有 限 自 动 机 的 构 造 比 下 推 自 动 机 简 单 ， 且 分 析 效 率 高 ；4. 区 分 词 法 和 语 法 ， 为 编 译 器 前 端 的 模 块 划 分 提 供 方 便 。 贯 穿 词 法 分 析 和 语 法 分 析 始 终 的 思 想 ：1. 语 言 的 描 述 和 语 言 的 识 别 是 表 示 一 个 语 言 的 两 个 不 同 侧面 ， 二 者 缺 一 不 可 ； （ 语 言 、 文 法 、 自 动 机 ）2. 用 正 规 式 和 CFG描 述 的 语 言 ， 对 应 的 识 别 方 法 （ 自 动 机 ）不 同 ；3. 一 般 情 况 下 ， 正 规

43、 式 适 合 描 述 线 性 结 构 ， 如 标 识 符 、 关键 字 、 注 释 等 ；4. CFG适 合 描 述 具 有 嵌 套 （ 层 次 ） 性 质 的 非 线 性 结 构 ， 如 不 同 结 构 的 句 子 if-then-else、 while-do等 。 39 3.3.2 上 下 文 有 关 语 言（ Context Sensitive Language, CSL） 程 序 设 计 语 言 中 除 了 CFG可 以 描 述 的 结 构 之 外 ， 还 有 一 些是 CFG无 法 描 述 的 所 谓 上 下 文 有 关 的 结 构 。 典 型 的 这 类 语 言 结 构 包 括 ：

44、 变 量 的 声 明 与 引 用 、 过 程 调 用时 形 参 与 实 参 的 一 致 性 检 查 等 。 描 述 它 们 的 文 法 被 称 为 上 下 文 有 关 文 法 （ Context Sensitive Grammar, CSG） 。 40 3.3.2 上 下 文 有 关 语 言 （ 续 ）L1= c | (a|b)* (标 识 符 声 明 与 引 用 一 致 性 的 抽 象 )L2=anbmcndm|n 1和 m 1 (形 参 与 实 参 一 致 性 的 抽 象 )L3=anbncn|n 1 (计 数 问 题 的 抽 象 )相 近 的 CFL：L1= c r| (a|b)*L2=

45、anbmcmdn|n 1, m 1L2=a nbncmdm|n 1, m 1L3=ambmcn|m, n 1 （ S aSa|bSb|c）（ S aSd|aAd A bAc|bc）（ S AB A aAb|ab B cBd|cd）（ A AC A aAb|ab C cC|c）例 3.12 不 能 用 CFG描 述 的 语 言 ： 41 计 数 问 题L3=anbncn|n 1 CSLL3=ambmcn|m,n 1 CFLL3=akbmcn|k， m， n 1正 规 集命 题 ： L3不 是 正 规 集 ， 因 为 构 造 不 出 可 以 识 别 L3的 DFA。 证 明 ： （ 反 证 ） 假 设 L3是 正 规 集 ， 则 可 构 造 n个 状 态 的 DFA D， 它 接 受 L3； 考 察 D读 完 ， a， aa， .， an， 分 别 到 达 S0， S1， .， Sn，共 有 n+1个 状 态 。 根 据 鸽 巢 原 理 ， 序 列 中 至 少 有 两 个 状 态 相 同 ， 设 Si=Sj（ ji） ， 因 为 a ibick L3所 以 存 在 路 径 aibick。但 是 D中 也 有 路 径 ajbick， 矛 盾 。 故 L3不 是 正 规 集 。 A AC A aAb|ab C cC|ca+b+c+结 束 （ 第 八 次 课 ）