编译原理习题及答案

编译原理考试试题及答案（汇总）一 、 是 非 题 （ 请 在 括 号 内 ， 正 确 的 划 ， 错 误 的 划 ） （ 每 个 2分 ， 共 20分 ）1 编 译 程 序 是 对 高 级 语 言 程 序 的 解 释 执 行 。 ()2 一 个 有 限 状 态 自 动 机 中 ， 有 且 仅 有 一 个 唯 一 的 终 态 。 ()3 一 个 算 符 优 先 文 法 可 能 不 存 在 算 符 优 先 函 数 与 之 对 应 。 ()4 语 法 分 析 时 必 须 先 消 除 文 法 中 的 左 递 归 。 ()5 LR分 析 法 在 自 左 至 右 扫 描 输 入 串 时 就 能 发 现 错 误 ， 但 不 能 准 确 地 指 出 出 错 地 点 。 ()6 逆 波 兰 表 示 法 表 示 表 达 式 时 无 须 使 用 括 号 。 ()7 静 态 数 组 的 存 储 空 间 可 以 在 编 译 时 确 定 。 ()8 进 行 代 码 优 化 时 应 着 重 考 虑 循 环 的 代 码 优 化 ， 这 对 提 高 目 标 代 码 的 效 率 将 起 更 大 作 用 。 ()9 两 个 正 规 集 相 等 的 必 要 条 件 是 他 们 对 应 的 正 规 式 等 价 。 ()10 一 个 语 义 子 程 序 描 述 了 一 个 文 法 所 对 应 的 翻 译 工 作 。 ()二 、 选 择 题 (请 在 前 括 号 内 选 择 最 确 切 的 一 项 作 为 答 案 划 一 个 勾 ， 多 划 按 错 论 )(每 个 4分 ， 共 40分 )1 词 法 分 析 器 的 输 出 结 果 是 _。A () 单 词 的 种 别 编 码 B () 单 词 在 符 号 表 中 的 位 置C () 单 词 的 种 别 编 码 和 自 身 值 D () 单 词 自 身 值2 正 规 式 M1 和 M2 等 价 是 指 _。A ()M1 和 M2 的 状 态 数 相 等 B ()M1和 M2 的 有 向 边 条 数 相 等C ()M1 和 M2 所 识 别 的 语 言 集 相 等 D ()M1和 M2状 态 数 和 有 向 边 条 数 相 等3 文 法 G： SxSx|y 所 识 别 的 语 言 是 _。A ()xyx B ()(xyx)*C ()xnyxn(n0) D ()x*yx*4 如 果 文 法 G是 无 二 义 的 ， 则 它 的 任 何 句 子 _。A ()最 左 推 导 和 最 右 推 导 对 应 的 语 法 树 必 定 相 同B () 最 左 推 导 和 最 右 推 导 对 应 的 语 法 树 可 能 不 同C () 最 左 推 导 和 最 右 推 导 必 定 相 同D ()可 能 存 在 两 个 不 同 的 最 左 推 导 ， 但 它 们 对 应 的 语 法 树 相 同5 构 造 编 译 程 序 应 掌 握 _。A ()源 程 序 B () 目 标 语 言C () 编 译 方 法 D () 以 上 三 项 都 是6 四 元 式 之 间 的 联 系 是 通 过 _实 现 的 。A () 指 示 器 B () 临 时 变 量C () 符 号 表 D () 程 序 变 量7 表 达 式 (A B) (C D)的 逆 波 兰 表 示 为 _。A.()AB CD B ()AB CD C ()AB CD D ()AB CD8. 优 化 可 生 成 _的 目 标 代 码 。A () 运 行 时 间 较 短 B () 占 用 存 储 空 间 较 小C () 运 行 时 间 短 但 占 用 内 存 空 间 大 D () 运 行 时 间 短 且 占 用 存 储 空 间 小9 下 列 _优 化 方 法 不 是 针 对 循 环 优 化 进 行 的 。A.() 强 度 削 弱 B () 删 除 归 纳 变 量C () 删 除 多 余 运 算 D () 代 码 外 提10 编 译 程 序 使 用 _区 别 标 识 符 的 作 用 域 。A.() 说 明 标 识 符 的 过 程 或 函 数 名B () 说 明 标 识 符 的 过 程 或 函 数 的 静 态 层 次C () 说 明 标 识 符 的 过 程 或 函 数 的 动 态 层 次D.() 标 识 符 的 行 号三 、 填 空 题 (每 空 1分 ， 共 10分 )1 计 算 机 执 行 用 高 级 语 言 编 写 的 程 序 主 要 有 两 种 途 径 ： _解 释 _和 _编 译 _。2 扫 描 器 是 _词 法 分 析 器 _， 它 接 受 输 入 的 _源 程 序 _， 对 源 程 序 进 行 _词 法 分 析 _并 识 别 出 一 个 个单 词 符 号 ， 其 输 出 结 果 是 单 词 符 号 ， 供 语 法 分 析 器 使 用 。3 自 上 而 下 分 析 法 采 用 _移 进 _、 归 约 、 错 误 处 理 、 _接 受 _等 四 种 操 作 。4 一 个 LR分 析 器 包 括 两 部 分 ： 一 个 总 控 程 序 和 _一 张 分 析 表 _。5 后 缀 式 abc-/所 代 表 的 表 达 式 是 _a/(b-c)_。6 局 部 优 化 是 在 _基 本 块 _范 围 内 进 行 的 一 种 优 化 。四 、 简 答 题 （ 20分 ）1. 简 要 说 明 语 义 分 析 的 基 本 功 能 。答 ： 语 义 分 析 的 基 本 功 能 包 括 : 确 定 类 型 、 类 型 检 查 、 语 义 处 理 和 某 些 静 态 语 义 检 查 。2. 考 虑 文 法 GS:S(T)|a+S|aTT,S|S消 除 文 法 的 左 递 归 及 提 取 公 共 左 因 子 。解 ： 消 除 文 法 GS的 左 递 归 ：S(T)|a+S|aTSTT,ST|提 取 公 共 左 因 子 ：S(T)|aSS+S|TSTT,ST|3. 试 为 表 达 式 w+(a+b)*(c+d/(e-10)+8) 写 出 相 应 的 逆 波 兰 表 示 。解 ： wab+cde10-/+8+*+4. 按 照 三 种 基 本 控 制 结 构 文 法 将 下 面 的 语 句 翻 译 成 四 元 式 序 列 ：while(AaAd|aAb|判 断 该 文 法 是 否 是 SLR(1) 文 法 ， 若 是 构 造 相 应 分 析 表 ， 并 对 输 入 串 ab# 给 出 分 析 过 程 。解 ： 增 加 一 个 非 终 结 符 S/后 ， 产 生 原 文 法 的 增 广 文 法 有 ：S-AA-aAd|aAb|下 面 构 造 它 的 LR(0) 项 目 集 规 范 族 为 ：从 上 表 可 看 出 ,状 态 I0 和 I2 存 在 移 进 -归 约 冲 突 ， 该 文 法 不 是 LR(0)文 法 。 对 于 I0 来 说 有 ：FOLLOW(A)a=b,d,#a=， 所 以 在 I0状 态 下 面 临 输 入 符 号 为 a 时 移 进 ， 为 b,d,#时 归 约 ， 为 其 他 时报 错 。 对 于 I2来 说 有 也 有 与 I0完 全 相 同 的 结 论 。 这 就 是 说 ， 以 上 的 移 进 -归 约 冲 突 是 可 以 解 决 的 ， 因 此 该文 法 是 SLR(1)文 法 。其 SLR(1)分 析 表 为 ：对 输 入 串 ab#给 出 分 析 过 程 为 ：一 、 是 非 题 ：1.一 个 上 下 文 无 关 文 法 的 开 始 符 ， 可 以 是 终 结 符 或 非 终 结 符 。 ( )2.一 个 句 型 的 直 接 短 语 是 唯 一 的 。 （ ）3.已 经 证 明 文 法 的 二 义 性 是 可 判 定 的 。 （ ）4.每 个 基 本 块 可 用 一 个 DAG表 示 。 （ ）5.每 个 过 程 的 活 动 记 录 的 体 积 在 编 译 时 可 静 态 确 定 。 （ ）6.2型 文 法 一 定 是 3 型 文 法 。 （ ）7.一 个 句 型 一 定 句 子 。 ( )8.算 符 优 先 分 析 法 每 次 都 是 对 句 柄 进 行 归 约 。 X ( )9.采 用 三 元 式 实 现 三 地 址 代 码 时 ， 不 利 于 对 中 间 代 码 进 行 优 化 。 （ ）10.编 译 过 程 中 ， 语 法 分 析 器 的 任 务 是 分 析 单 词 是 怎 样 构 成 的 。 ( )11.一 个 优 先 表 一 定 存 在 相 应 的 优 先 函 数 。 X ( )12.目 标 代 码 生 成 时 ， 应 考 虑 如 何 充 分 利 用 计 算 机 的 寄 存 器 的 问 题 。 ( )13.递 归 下 降 分 析 法 是 一 种 自 下 而 上 分 析 法 。 ( )14.并 不 是 每 个 文 法 都 能 改 写 成 LL(1)文 法 。 ( )15.每 个 基 本 块 只 有 一 个 入 口 和 一 个 出 口 。 ( )16.一 个 LL(1)文 法 一 定 是 无 二 义 的 。 ( )17.逆 波 兰 法 表 示 的 表 达 试 亦 称 前 缀 式 。 ( )18.目 标 代 码 生 成 时 ， 应 考 虑 如 何 充 分 利 用 计 算 机 的 寄 存 器 的 问 题 。 ( )19.正 规 文 法 产 生 的 语 言 都 可 以 用 上 下 文 无 关 文 法 来 描 述 。 ( )20.一 个 优 先 表 一 定 存 在 相 应 的 优 先 函 数 。 ( )21.3型 文 法 一 定 是 2 型 文 法 。 ( )22.如 果 一 个 文 法 存 在 某 个 句 子 对 应 两 棵 不 同 的 语 法 树 ， 则 文 法 是 二 义 性 的 。 ( )答 案 ： 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.二 、 填 空 题 ：2.编 译 过 程 可 分 为 （ 词 法 分 析 ） ， （ 语 法 分 析 ） ， （ 语 义 分 析 与 中 间 代 码 生 成 ） ， （ 优 化 ） 和 （ 目 标代 码 生 成 ） 五 个 阶 段 。3.如 果 一 个 文 法 存 在 某 个 句 子 对 应 两 棵 不 同 的 语 法 树 ， 则 称 这 个 文 法 是 （ 二 义 性 的 ） 。4.从 功 能 上 说 ， 程 序 语 言 的 语 句 大 体 可 分 为 （ 执 行 性 ） 语 句 和 （ 说 明 性 ） 语 句 两 大 类 。5.语 法 分 析 器 的 输 入 是 （ 单 词 符 号 ） ， 其 输 出 是 （ 语 法 单 位 ） 。6.扫 描 器 的 任 务 是 从 （ 源 程 序 中 ） 中 识 别 出 一 个 个 （ 单 词 符 号 ） 。7.符 号 表 中 的 信 息 栏 中 登 记 了 每 个 名 字 的 有 关 的 性 质 ， 如 (类 型 、 种 属 、 所 占 单 元 大 小 、 地 址 ） 等 等 。8.一 个 过 程 相 应 的 DISPLAY表 的 内 容 为 (现 行 活 动 记 录 地 址 和 所 有 外 层 最 新 活 动 记 录 的 地 址 )10.常 用 的 两 种 动 态 存 贮 分 配 办 法 是 （ 栈 式 ） 动 态 分 配 和 （ 堆 式 ） 动 态 分 配 。11.一 个 名 字 的 属 性 包 括 ( 类 型 )和 (作 用 域 )。12.常 用 的 参 数 传 递 方 式 有 (传 地 址 ） ， （ 传 值 ） ， （ 传 名 ）13.根 据 优 化 所 涉 及 的 程 序 范 围 ， 可 将 优 化 分 成 为 (局 部 优 化 ） ， （ 循 环 优 化 ） ， （ 全 局 优 化 ） 三 个 级 别 。14.语 法 分 析 的 方 法 大 致 可 分 为 两 类 ， 一 类 是 （ 自 上 而 下 ） 分 析 法 ， 另 一 类 是 （ 自 下 而 上 ）分 析 法 。15.预 测 分 析 程 序 是 使 用 一 张 （ 分 析 表 ） 和 一 个 （ 符 号 栈 ） 进 行 联 合 控 制 的 。17.一 张 转 换 图 只 包 含 有 限 个 状 态 ,其 中 有 一 个 被 认 为 是 （ 初 ） 态 ;而 且 实 际 上 至 少 要 有 一 个 （ 终 ） 态 。19.语 法 分 析 是 依 据 语 言 的 （ 语 法 ） 规 则 进 行 。 中 间 代 码 产 生 是 依 据 语 言 的 （ 语 义 ） 规 则 进 行 的 。21.一 个 文 法 G， 若 它 的 预 测 分 析 表 M不 含 多 重 定 义 ， 则 该 文 法 是 （ LL(1) 文 法 ） 文 法 。22.对 于 数 据 空 间 的 存 贮 分 配 ， FORTRAN采 用 ( 静 态 策 略 ， PASCAL 采 用 ( 动 态 )策 略 。24.最 右 推 导 亦 称 为 （ 规 范 推 导 ） ， 由 此 得 到 的 句 型 称 为 （ 规 范 ） 句 型 。26.对 于 文 法 G， 仅 含 终 结 符 号 的 句 型 称 为 ( 句 子 )。27.所 谓 自 上 而 下 分 析 法 是 指 (从 开 始 符 号 出 发 ， 向 下 推 导 ， 推 出 句 子 ）29.局 限 于 基 本 块 范 围 的 优 化 称 （ 局 部 优 化 ） 。31.2型 文 法 又 称 为 （ 上 下 文 无 关 ） 文 法 ； 3 型 文 法 又 称 为 （ 正 则 ） 文 法 。32.每 条 指 令 的 执 行 代 价 定 义 为 (指 令 访 问 主 存 次 数 加 1）33.算 符 优 先 分 析 法 每 次 都 是 对 (最 左 素 短 语 ） 进 行 归 约 。三 、 名 词 解 释 题 ：1.局 部 优 化 -局 限 于 基 本 块 范 围 的 优 化 称 。2.二 义 性 文 法 -如 果 一 个 文 法 存 在 某 个 句 子 对 应 两 棵 不 同 的 语 法 树 ， 则 称 这 个 文 法 是 二 义 性 文 法 。3.DISPLAY 表 -过 程 的 嵌 套 层 次 显 示 表 ， 记 录 该 过 程 的 各 外 层 过 程 的 最 新 活 动 记 录 的 起 始 地 址 。5.最 左 推 导 -任 何 一 步 = 都 是 对 中 的 最 右 非 终 结 符 替 换 。6.语 法 -一 组 规 则 ， 用 它 可 形 成 和 产 生 一 组 合 式 的 程 序 。7.文 法 -描 述 语 言 的 语 法 结 构 的 形 式 规 则 。8.基 本 块 -指 程 序 中 一 顺 序 执 行 的 语 句 序 列 ， 其 中 只 有 一 个 入 口 和 一 个 出 口 ， 入 口 就 是 其 中 的 第 一 个语 句 ， 出 口 就 是 其 中 的 最 后 一 个 语 句 。9.语 法 制 导 翻 译 -在 语 法 分 析 过 程 中 ， 根 据 每 个 产 生 式 所 对 应 的 语 义 子 程 序 进 行 翻 译 的 办 法 叫 做 语 法制 导 翻 译 。10.短 语 -令 G 是 一 个 文 法 ， S 划 文 法 的 开 始 符 号 ， 假 定 是 文 法 G 的 一 个 句 型 ， 如 果 有 S A 且 A ， 则 称 是 句 型 相 对 非 终 结 符 A的 短 语 。11.待 用 信 息 -如 果 在 一 个 基 本 块 中 ， 四 元 式 i 对 A 定 值 ， 四 元 式 j 要 引 用 A 值 ， 而 从 i 到 j 之 间 没有 A的 其 它 定 值 ， 则 称 j 是 四 元 式 i的 变 量 A的 待 用 信 息 。12.规 范 句 型 -由 规 范 推 导 所 得 到 的 句 型 。13.扫 描 器 -执 行 词 法 分 析 的 程 序 。14.超 前 搜 索 -在 词 法 分 析 过 程 中 ， 有 时 为 了 确 定 词 性 ， 需 超 前 扫 描 若 干 个 字 符 。15.句 柄 -一 个 句 型 的 最 左 直 接 短 语 。16.语 法 制 导 翻 译 -在 语 法 分 析 过 程 中 ， 根 据 每 个 产 生 式 所 对 应 的 语 义 程 序 进 行 翻 译 的 方 法 叫 做 语法 制 导 翻 译 。17.规 范 句 型 -由 规 范 推 导 所 得 到 的 句 型 。18.素 短 语 -素 短 语 是 指 这 样 一 个 短 语 ， 至 少 含 有 一 个 终 结 符 ， 并 且 ， 除 它 自 身 外 不 再 含 任 何 更 小 的素 短 语 。19.语 法 -是 组 规 则 ， 用 它 可 形 成 和 产 生 一 个 合 式 的 程 序 。20.待 用 信 息 -如 果 在 一 个 基 本 块 中 ， 四 元 式 i 对 A 定 值 ， 四 元 式 j 要 引 用 A 值 ， 而 从 i 到 j 之 间 没有 A的 其 它 定 值 ， 则 称 j 是 四 元 式 i的 变 量 A的 待 用 信 息 。21.语 义 -定 义 程 序 的 意 义 的 一 组 规 则 。四 、 简 答 题 ：1.写 一 个 文 法 G, 使 其 语 言 为 不 以 0开 头 的 偶 数 集 。2.已 知 文 法 G(S)及 相 应 翻 译 方 案S aAb print “ 1” S a print “ 2” A AS print “ 3” A c print “ 4” 输 入 acab, 输 出 是 什 么 ？3. 已 知 文 法 G(S)S bAaA (B | aB Aa)写 出 句 子 b(aa)b的 规 范 归 约 过 程 。4. 考 虑 下 面 的 程 序 ：procedure p(x, y, z)；beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A, A, B);Print A, Bend.试 问 ， 若 参 数 传 递 的 方 式 分 别 采 用 传 地 址 和 传 值 时 ， 程 序 执 行 后 输 出 A, B 的 值 是 什 么 ?5 文 法 G(S)S dABA aA| aB Bb| 描 述 的 语 言 是 什 么 ？6. 证 明 文 法 G(S)S SaS| 是 二 义 性 的 。7. 已 知 文 法 G(S)S BAA BS| dB aA| bS | c的 预 测 分 析 表 如 下 a b c d #S S BA S BA S BAA A BS A BS A BS A dB B aA B bS B c给 出 句 子 adccd 的 分 析 过 程 。8. 写 一 个 文 法 G, 使 其 语 言 为 L(G)=albmclanbn| l=0, m=1, n=29. 已 知 文 法 G(S):S a| (T)T T,S|S的 优 先 关 系 表 如 下 ： 关 系 a ( ) ,a - - . .( ., .请 计 算 出 该 优 先 关 系 表 所 对 应 的 优 先 函 数 表 。10. 何 谓 优 化 ？ 按 所 涉 及 的 程 序 范 围 可 分 为 哪 几 级 优 化 ？11. 目 标 代 码 有 哪 几 种 形 式 ？ 生 成 目 标 代 码 时 通 常 应 考 虑 哪 几 个 问 题 ？12. 一 字 母 表 =a, b， 试 写 出 上 所 有 以 a 为 首 的 字 组 成 的 正 规 集 相 对 应 的 正 规 式 。13. 基 本 的 优 化 方 法 有 哪 几 种 ？14. 写 一 个 文 法 G, 使 其 语 言 为 L(G)=abncn| n 015. 考 虑 下 面 的 程 序 ：procedure p(x, y, z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b, b, a);print aend.试 问 ， 若 参 数 传 递 的 方 式 分 别 采 用 传 地 址 和 传 值 时 ， 程 序 执 行 后 输 出 a 的 值 是 什 么 ?16.写 出 表 达 式 a b*(c-d)/e 的 逆 波 兰 式 和 三 元 序 列 。17.证 明 文 法 G(A)A AA | (A)| 是 二 义 性 的 。18.令 =a,b，