天津理工大学考试试卷 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 1C 0

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) C．a (c | d)| b (c | d)

*

*

*

*

*

B．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. 四元式之间的联系是通过（ ）实现的。

试卷编号： 1-A 第 1 页 共 9 页

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．32224441 B. 34242421 C．12424243 D. 34442212

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分）

X ? 0 1 1 ? 2 0 3 0 4 *

（2）用子集法将NFA确定化（2分） I I0 I1 {x,1,2} {1,2,3} {1,2} {1,2,3,4 } {1,2,3} {1,2,3,4} {1,2,3} {1,2,3,4} {1,2} {1,2} {1,2 } {1,2 } 试卷编号： 1-A 第 2 页 共 9 页

将所有子集重命名，得到转换矩阵： S 0 0 1 2 3 1 3 1 3 1 2 2 2 2

（3）化简，并画出DFA M（1分）

划分为状态：{0,2} {1 } {3} 将这三个状态命名为0，1，2三个状态

S 0 1 2 0 1 2 2 1 0 1 0 2 0 1 1 0 0 0

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 T * a

（2）写出该句型中所有的短语、直接短语、句柄和最左素短语。（3分） 短语：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 / + =

试卷编号： 1-A 第 3 页 共 9 页

(2) 三元式（1分） ① (+,b, c) ② (*,①,e) ③ (+,b, c) ④ (/,③,f) ⑤ (+,②, ④) ⑥ (=,a, ⑤)

(3) 间接三元式（1分） ① (+, b, c) ② (*, ①, e) ③ (/,①,f) ④ (+, ②, ③) ⑤ (=, a, ④)

间接码表：①②①③④⑤

(4) 四元式（2分） ① (+, b, c, T1) ② (*, T1, e,T2) ③ (+, b, c, T3) ④ (/, T3, f, T4) ⑤ (+, T2, T4, T5) ⑥ (=, T5,－, a)

四、综合题（共60分） 得分 1.已知文法G(S)：（共15分） S? * A A? 0A1 | *

(1)求文法G的各非终结符号的FIRSTVT和LASTVT集合。（5分） FIRSTVT(S)={ * } LASTVT(S)={ 1, *}

FIRSTVT(A)={ 0, * } LASTVT(S)={ 1, *}

(2)构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法。（5分）

* 0 1 < < > * < < = 0 > 1 文法G中的任何终结符对至多只存在一种优先关系，所以文法G是一个算符优先文法。

(3)分析句子*0*1，并写出分析过程。（5分）

试卷编号： 1-A 第 4 页 共 9 页

0 1 2 3 4 5 6 7 # #* #*0 #*0* #*0A #*0A1 #*A #S *0*1# 0*1# *1# 1# 1# # # # 分析正确 步骤 符号栈 输入串

2.已知文法G(S)：（共15分）

S? aS | bS | a

(1)构造该文法的拓广文法。（1分） (0)S’→S

(1) S→aS

(2)A→bS (3)A→a

(2) 构造其LR(0)项目集规范族，并给出识别活前缀的DFA。（7分）

a I1 : S→a.S

S→.aS S I4 : S→aS.

S→.bS S→.a S→a. 试卷编号： 1-A 第 5 页 共 9 页

输出

b I0 : S’→.S S→.aS S→.bS S→.a a S I3 : S’→S. b I2 : S→b.S S→.aS S→.bS S→.a a S I5 : S→bS. b (3)构造其SLR分析表，并判断该文法是否是SLR(1)文法。（7分） 状态I1移进－规约冲突，计算S的Follow集合：Follow(S)＝{#}，可以采用SLR冲突消解法，得到如下SLR分析表：

ACTION GOTO 状态 a b # S 0 S1 S2 3 1 S1 S2 r3 4 2 S1 S2 5 3 acc 4 r1 5 r2

该文法是SLR（1）文法。

3.设有如下基本块：（共10分） T1 = A + B

T2 = 5 M = T2 * 4 T3 = C - D T4 = M + T3 L = T1 * T3 T4 = A + B N = T4 (1)画出该基本块的DAG图。（5分） n10 L

*

试卷编号： 1-A 第 6 T4 页 共 9 页

n3 T1,T4,N + n9

T3

20 D

(2)假设变量L，M，N在基本块出口之后是活跃的，给出优化后的四元式序列。（5分） N＝A＋B M=20 T3=C-D L=N*T3

4.以下程序段是最内循环（共13分）

A = 0 I = 1 L1: B = J + 1 C = B + I A = C + A if I = 100 GOTO L2 I = I + 1 GOTO L1 L2:

(1)画出程序流图，并找出回边与循环。（3分）

A=0 I=1 B1 L1：B=J+1 C=B+I A=C+A if I=100 goto L2 B2 I=I+1 GOTO L1 B3 L2： B4 流图中有一条回边B3 结点，也是出口结点。

B2，且B2DOMB3，所以，有一个循环{B2, B3}，B2是循环入口

试卷编号： 1-A 第 7 页 共 9 页

(2)对循环优化（8分）

1. 代码外提：对于B2中的赋值四元式B=J+1，由于循环中没有对J的定值操作，所有对J的定值都在循环外，所以，它是循环中的不变运算，可以进行代码外提。

2. 删除归纳变量：循环中I是基本归纳变量，C是与I同族的归纳变量，两者有如下线性关系：C=B+I，则I=100可以用C=B+100替代，相应的I=I+1可用C=C+1替代，再将新的不变运算提到循环外。

(3)画出优化后的程序流图（2分）

A=0 I=1 B=J+1 C=B+I R=B+100 B1 L1：A=C+A if C=R goto L2 C=C+1 GOTO L1 L2： B4 B3 B2 5. 有一程序如下： program ex; a: integer; procedure PP(x: integer); begin: x:=5; x:=a+1 end; begin a:=2; PP(a); write(a) end

试用图表示ex调用PP(a)前后活动记录的过程。（共7分）

试卷编号： 1-A 第 8 页 共 9 页

PP_TOP →

PP_SP → ex_TOP →

DISPLAY表 PP_SP ex_SP 形式参数x 参数个数：1 全局DISPLAY地址 返回地址 ex_SP 局部变量：a PP的活动记录 （调用PP（a）之后）

试卷编号： ex_SP → 1-A DISPLAY表 ex_SP 参数个数：0 全局DISPLAY地址 返回地址 ex_SP 第 9 页 共 9 页

ex的活动记录 （调用PP（a）之前）