天津理工大学考试试卷 2009～2010学年度第二学期 《编译原理》 期末考试试卷
课程代码： 0660116 试卷编号： 1-A 命题日期： 2010 年 6 月 15 日 答题时限： 120 分钟 考试形式：闭卷笔试 得分统计表： 大题号 总分 一 二 三 四 一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共20分） 得分 注意：须将本题答案写在下面的表格中，写在其它地方无效
1 D 2 C 3 B 4 D 5 D 6 B 7 C 8 B 9 D 10 C 1. 编译程序是对（ ） A. 汇编程序的翻译 B. 高级语言程序的解释执行 C. 机器语言的执行 D. 高级语言的翻译 2. 词法分析器的输出结果是（ ）
A．单词的种别编码 B．单词在符号表中的位置 C．单词的种别编码和自身值 D．单词自身值 3. 在规范规约中，用（ ）来刻画可规约串。
A．直接短语 B．句柄 C．最左素短语 D．素短语 4. 与正规式(a| b) (c | d)等价的正规式是（ ）
A．a (c | d) | b(c | d)
*
*
*
*
*
B．a (c | d) | b(c | d)
*
*
* * *
C．a (c | d)| b (c | d) D．(a | b) c| (a | b) d 5. 若项目集IK含有A??·，则在状态K时，仅当面临输入符号a?FOLLOW(A)时，才采取A??·动作的一定是（ ）
A．LALR文法 B．LR(0) 文法 C．LR(1)文法 D．SLR(1)文法 6. 四元式之间的联系是通过（ ）实现的。
A. 指示器 B. 临时变量 C. 符号表 D. 程序变量 7．文法G：S ? x Sx | y所识别的语言是（ ） A．xyx B．(xyx) C．xnyxn(n≥0) D．xyx 8. 有一语法制导翻译如下所示： S ? b Ab {print “1”}
*
*
*
A?(B {print “2”} A?a {print “3”} B?Aa) {print “4”}
若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为（ ）
A． B. C． D.
9．关于必经结点的二元关系，下列叙述不正确的是（ ）
A．满足自反性 B．满足传递性 C．满足反对称型 D．满足对称性 10．错误的局部化是指（ ）。
A．把错误理解成局部的错误 B．对错误在局部范围内进行纠正 C．当发现错误时，跳过错误所在的语法单位继续分析下去
D．当发现错误时立即停止编译，待用户改正错误后再继续编译
二、判断题（每小题1分，共5分）
得分 1. 文法G的一个句子对应于多个推导，则G是二义性的。（× ）
2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√ ） 3. 算符优先文法采用“移进－规约”技术，其规约过程是规范的。（ × ） 4. 删除归纳变量是在强度削弱以后进行。（ √ ） 5. 在目标代码生成阶段，符号表用于目标代码生成。（ × ）
三、简答题（每小题5分，共15分）
得分 1. 构造正规式(0∣1)00相应的正规式并化简。（共5分） （1）根据正规式，画出相应的NFA M（2分）
*
0 X ? 1 ? 2 0 3 0 4 （2）用子集法将NFA确定化（2分） 1 I I0 I1 {x,1,2} {1,2,3} {1,2,3} {1,2,3,4} {1,2} {1,2,3} {1,2,3,4 } {1,2,3,4} {1,2} {1,2} {1,2 } {1,2 } 将所有子集重命名，得到转换矩阵：
S 0 1 0 1 2 3 1 3 1 3 2 2 2 2 （3）化简，并画出DFA M（1分）
划分为状态：{0,2} {1 } {3} 将这三个状态命名为0，1，2三个状态
S 0 1 0 1 2
1 1 2 2 0 0 0 1 0 0 1 0 2 1 0
2. 设文法G[S]: （共5分） S →S + aT | aT | +aT T →*aT | *a
（1）写出句型 aT + a *a *a的最右推导并画出语法树（2分） S?S＋aT?S＋a*aT?S+a*a*a?aT+a*a*a S
S ＋ a T
a T
* a
（2）写出该句型中所有的短语、直接短语、句柄和最左素短语。（3分） * a 短语：aT、*a*a、*a、aT+a*a*a 直接短语：aT、*a 句柄：aT 最左素短语：aT
3. 将下列语句翻译为逆波兰表示，三元式、间接三元式和四元式表示：（共5分） a = (b + c) * e + (b + c) / f (1) 逆波兰表示（1分）
abc + e * bc + f / + =
(2) 三元式（1分） ① (+,b, c) ② (*,①,e) ③ (+,b, c) ④ (/,③,f) ⑤ (+,②, ④) ⑥ (=,a, ⑤)
(3) 间接三元式（1分） ① (+, b, c) ② (*, ①, e) ③ (/,①,f) ④ (+, ②, ③) ⑤ (=, a, ④)
间接码表：①②①③④⑤ (4) 四元式（2分）