发布时间 : 星期五 文章编译原理期末考试试卷及答案更新完毕开始阅读
Goto L1
L2:
7． (6分) Give out the all basic blocks of the following program fragment and construct the relevant flow graph(DAG). read C
A=0 B=1
L4: A=A+B
if B>C goto L2
B=B+1
goto L4
L2: write A
8. (8分)Translate the assignment statement b[i]=b*c-b*d into (1) A syntax tree.
(2) Three address instructions. 答案：：
(1) 栈式动态存储分配 (2) 堆式动态存储分配 (3) 左 (4) 语法分析 (5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1
(10) 基本块
一、 选择题（每问2分，共20分） 1.C B 2.D 3.B 4.A 5.D 6.A,C
7.BCD,选对一个得1分且不超过满分，选错一个扣一分，扣完为止。 8.BCD，选对一个得1分且不超过满分，选错一个扣一分，扣完为止。 二、 解答题
1．（1）文法存在左递归，消除左递归后的文法为：
E→(E)E’|i E’（2分） E’→TEE’|ε （2分）
5 / 15
T→*|+ （1分）
（2）(5分)没考虑#扣0.5分，其它错或少写一个扣0.5分
FIRST(E)={(,i} FIRST(E’)={*,+, ε} FIRST(T)={*,+} FOLLOW(E)={),*,+,#} FOWLLOW(E’)= {),*,+,#} FOLLOW(T)={(,i}
（3）每错一个扣0.5分，全错或不写不得分，扣完为止，共5分 E E’ ( ) i E→iE’ * E’→TEE’ E’ →ε T T→* + E’→TEE’ E’ →ε T→+ # E’ →ε E→(E)E’ E’→ ε 2．（1）规范推导过程如下。写错推导符号扣0.5分,错写或少写一步推导扣0.5分，扣完为止，最左推导扣2分，共4分。
S?S(S)?S(?)?S(S)()?S(?)()?S(S)()()?S(S(S))()()?S(S(?))()()?S(S(S)())()()?S(S(?)())()()?S((?)())()()??(()())()()（1）中加下划线的部分是句柄，标识如（1）。每少写一个句柄扣0.5分，扣完为止，共4分。 （3）每少写步扣0.5分，扣完为止，共4分。
S ( S ) ε )
ε S ( S ) ) )
ε ε ．3（1）打印的字符串是：12020（错一个扣0.5分，共3分） （2）归约过程中错一步扣0.5分，扣完为止。（共5分） 4．（1）每少写一步扣0.5分，扣完为止，共5分。
S
while M1.q=100 E1.t=102 do M2.q=102 S1 6 / 15 E1.f=107
do S1.nl=103 S ( S ) ε
S ( S ) ) S ( S ) ε ) S
（2）
y z
c>d x E5.p=y + E6.p=z
(E3.t=102) ε L.p=x := E4.p=T1
（2）少写一个四元式扣0.5分，全错或不写不得分，回填错误扣0.5分，共5分。 四元式序列为：
100(j?,a,b,102)101(j,_,_,107)102(j?,c,d,104)103((j,_,_,106)104(?,y,z,T1)105(:?,T1,_,x)106(j,_,_,100)
5．（1）少写一个扣1分，全错或不写不得分，共5分。 FIRSTVT(S)={a,∧,(} FIRSTVT(T)={, a,∧,(} LASTVT(S)={ a,∧,)} LASTVT(T)={ a,∧,), ,}
(2)优先表如下。每错一个扣0.5分，全错或不写不得分，扣完为止，共3分
文法G[S]没有两个非终结符相邻的情况，且其优先表中任一对终结符之间最多满足?、?、 三种关系中的一种，因此是G[S]算符优先文法。（2分） 可以不考虑终结符“#”。 A ∧ ( ) , # a ? ? ? ∧ ? ? ? ( ? ? ? ) ? ? ? ?
7 / 15
, ? ? ? ? ? ? # ? ? ?
或者
（3）优先函数。可以不考虑终结符“#”。每错一个扣0.5分，全错或不写不得分，扣完为止，共5分。 f g 或者 f g a 4 5 ∧ 4 5 ( 2 5 ) 4 2 , 4 3 a 6 7 ∧ 6 7 ( 2 7 ) 6 2 , 6 5 # 2 2 三、 填空题（每空2分，共20分）
1目标程序 （target code） 语法分析（syntax analyzer） 代码优化器（code optimizer） 代码产生器（code generator） 符号表管理（symbol table manager）
2 继承属性（inherited attribute） 3 局部优化（local optimization） 4 四元式（quatriple）
5 E + * ( ) id
四、 单项选择题（每题2分，共10分） 1.B 2.D 3.B 4.D 5.C 五、 解答题（共70分）
1．（1） L(G)={01|M≥1} 共2分，≥写成＞扣1分
mm
（2） S=>0S1=>00S11=>000111，共3分， =>写成->扣1分 （3） 共3分，错处扣0.5分，扣完为止
2.（1）空白表格也可以填写“错误”字样,共4分，错一个扣0.5分，扣完为止 S A B a S→aBc A→aAb b S→bAB A→b B→b c B→ε $(#) B→ε （2）共6分，其中判断“baabbb是该文法句子”为2分，其他错一个扣0.5分，扣完为止 符号栈 $S $BAb $BA $BbAa $BbA $BbbAa 输入串 baabbb$ baabbb$ aabbb$ aabbb$ abbb$ abbb$
8 / 15
规则 S→bAB A→aAb A→aAb