中山大学软件学院10级编译原理期末试卷B中山大学软件学院10级编译原理期末试卷B.pdf

中 山 大 学 软 件 学 院 2 0 1 0 级 软 件 工 程 专 业 (2012 学年秋季学期) 《SE-3 03 编 译 原 理 》 期 末 试 题 (B 卷答案卷) ( 考 试 形 式 ： 闭 卷 考 试 时 间 : 2 小 时) Part one: Answer the following questions (15 points. 5 points for each item.) 1. What is local optimization? 【参考答案】 局部优化是局限在基本块内的优化。 【评分标准】 本小题 5 分。 2. When shall we do code optimization in a compiler? 【参考答案】 编译的代码优化可在中间代码生成阶段之后，目标代码生成阶段之前进行独立于机器 代码优化；还可以在目标代码生成阶段进行依赖于机器的代码优化。 【评分标准】 本小题 5 分。 中间代码生成阶段之后（2 分），目标代码生成阶段之前（1 分）进行独立于机器 代码优化（1 分）；还可以在目标代码生成阶段进行依赖于机器的代码优化（1 分）。 3. Give a regular expression for the language over the alphabet {a, b}: L = {anbm | (n + m) is even} 【参考答案】 (aa)*(bb)*| a(aa)*b(bb)* 【评分标准】 本小题 5 分。 Part two: Compute and answer the following questions （85 points ） 4. (15 points) Given a regular expression as following: (a | b)*(a | b) a (1) Based on the Thompson Algorithm, construct the NFA from the above regular expression. (2) Convert the above NFA to a DFA and a minimum-state DFA. （1） 【参考答案】 根据 Thompson Algorithm，对(a|b)*(a|b)a 绘制NFA 如下图4-1 所示： Page 1 of 8 图4-1 【评分标准】 本小题 6 分。 如图 4-1 所示：(a|b)*对应的 NFA 构造正确得 3 分；(a|b)对应的 NFA 构造正确得 2 分； a 对应的 NFA 构造正确得 1 分。 如果未按 Thompson Algorithm 算法绘制，可酌情给分。 （2 ） 【参考答案】 对图 4-1 的NFA 先转换为 DFA 如下图 4-2 所示： 图4-2 将图 4-2 的DFA 进行最小化优化，优化后的 DFA 如图 4-3 所示 图4-3 【评分标准】 本小题 9 分。 如图 4-3 所示：优化后的 DFA 正确，但状态数多于 3 或转换关系不完全正确，得 5 分； DFA 正确，状态数等于 3 且状态转换关系正确，得 9 分。 Page 2 of 8 5. (10 points) Which of the following language is a regular language, a context-free language or a context-sensitive language? For the regular language, write its re