1、 共 4 页 第 页12012-2013 学年 第 1 学期2010 级编译原理期末考试试题(A 卷)考试时间：2013 年 1 月 7 日班级 学号 姓名 请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰； 请 在 答 题 纸 和 试 题 纸 上 都 写 上 你 的 班 级 ， 学 号 和 姓 名 ， 交 卷 时 请 将 试 题 纸 、答 题 纸 和 草 纸一 并 交 上 来 。 一 、 填 空 题 （ 4 小 题 ， 共 20 分 ， 每 题 5 分 ）1. 判 断 布 尔 表 达 式 文 法 GB符 号 间 的 优 先 关 系 ( 、 、 或 表 示 无 关 系 的 )。 GB:
2、B-BoT|TT-TaF|FF-nF|(B)|t|f则 下 列 符 号 之 间 的 优 先 关 系 为 B_#, o_B, n_n, t_a, (_(.2. 设 有 一 个 文 法 GS:S-VV-T|ViTT-F|T+FF-V*|句 型 F+Fi的 短 语 ， 简 单 短 语 和 句 柄 分 别 为 _,_,_。3. 设 语 义 分 析 中 当 前 层 数 为 L， 偏 移 量 为 off， 试 写 出 以 下 程 序 点 的 层 数 和 偏 移 变 化 情 况 。注 意 ： 约 定 基 本 类 型 bool,char,int,float,指 针 型 分 别 分 配 1， 2， 4， 8，
3、2 个 存 储 单 元 。const int N = 10;typedef struct studentchar* name;intN2 mark;student a,b;bool ave(student* s, int n, float x)bool successful;int sum;void main()共 4 页 第 页24. 设 一 个 文 法 GS： S-SS-BBB-aBB-b其 LR(1)活 前 缀 状 态 机 如 下 ， 请 填 写 I3 和 I6 状 态 。 依 据 此 状 态 机 构 造 的 LR(1)分 析 表 当 中 ，相 应 位 置 的 内 容 为 ACTIONI
4、1,#=_， ACTIONI3,b=_， GOTOI6,B=_。二 、 计 算 题 （ 4 小 题 ， 每 小 题 5 分 ， 共 20 分 ）1. 求 与 = a,b 的 正 则 表 达 式 (a|b)* (aa*|b*b)(ab)*a 等 价 的 最 简 DFA。2. 将以下文法等价变换为不含空产生式的文法。GS:S-aAbBcA-a|B-AA|b3. 将如下文法转换为等价的自动机。GS:S-aAS-bBA-aBcB-bAcSI0：S-.S,#S-.BB,#B-.aB,a/bB-.b,a/bI1：S-S.,#I4：B-b.,a/bI5：S-BB.I7：B-b.,#I2：S-B.B,#B-.
5、aB,#B-.b,#I3：I9：B-aB.,#I8：B-aB.,a/bSbBabbBbBI6：Baaa共 4 页 第 页34. 求 与 下 面 NFA 等 价 的 DFA。1a,bbb243 5aa ab ba,b三 、 简 答 题 （ 4 小 题 ， 每 小 题 5 分 ， 共 20 分 ）1. 设 计 一 个 文 法 G 描 述 语 言 aibjcjdiek|i=0,j=1,k=2。2. 请 用 正 则 表 达 式 描 述 下 面 自 动 机 所 接 受 的 语 言 。1b23aabb4b3. 分 析 LR 族 四 种 典 型 分 析 方 法 的 异 同 。4. 请 给 出 运 行 时 动
6、 态 空 间 的 内 存 存 储 区 划 分 和 典 型 过 程 活 动 记 录 内容 。四 、 问 答 题 （ 2 小 题 ， 每 小 题 5 分 ， 共 10 分 ）设 高 级 程 序 设 计 语 言 中 有 Repeat 语 句 的 文 法 如 下 ：GS:S-RepeatMUntil(E)M-S;M|文 法 的 语 义 如 右 图 的 流 程 图 所 示 。1. 请 给 出 Repeat 语 句 的 四 元 式 表 示 。2. 采 用 语 法 制 导 的 方 式 设 计 语 义 函 数 ， 构 造 Repeat 语 句 的 中 间 代执行 M判断 E真假共 4 页 第 页4码 生 成
7、方 法 。五 、 问 答 题 （ 2 小 题 ， 每 小 题 5 分 ， 共 10 分 ）1. 以 驻 留 法 构 造 以 下 程 序 段 的 全 局 符 号 表 （ 包 括 类 型 表 、 标 识 符 表 以 及 表 之 间 的 指 针 ） 。2. 比 较 说 明 单 表 结 构 下 的 驻 留 法 管 理 和 多 表 结 构 下 的 scope 栈 辅 助 管 理 方 法 的 异 同 。#include const float E=2.718;typedef struct Lnfloat base; float antilog;void main()float x;Ln X;printf(
8、“Please input the value of x: ”);scanf(X.base=E;X.antilog=power(E,x);printf(“The antilog of the logarithms is : %f”, X.antilog);六 、 问 答 题 （ 2 小 题 ， 每 小 题 5 分 ， 共 10 分 ）1. 通 过 文 法 等 价 变 换 消 除 以 下 文 法 GS的 左 递 归 ；2. 判 断 变 换 后 的 文 法 是 否 为 LL(1)文 法 。GS:S-Aa|bA-SBB-ab七 、 问 答 题 （ 2 小 题 ， 每 小 题 5 分 ， 共 10 分 ）1. 构 造 如 下 文 法 的 NFA。GA：A-B0B-B0|A1|02. 产 生 式 形 为 A-a 或 A-Ba， A、 B Vn， a Vt 的 文 法 是 正 则 文 法 ， 称 为 左 线 性 文 法 。 设 计构 造 与 左 线 性 文 法 等 价 的 NFA 算 法 。
