A→a {print “3”}
B→Aa) {print “4”}
（3） 当输入序列为 b(((aa)a)a)b 时，打印的字符串是什么？（4） 写出移入-规约分析过程。
5． （12 分）翻译循环语句 while (x>y) do if (a=b) then x:=2*y+a 。要求：给出加注释的分析树、三地址码序列及相应的四元式序列。
参考以下部分翻译模式：
(1) S→if E then M S1 {backpatch(E.truelist,M.quad);
S.nextlist:=merge(E.falselist,S1 .nextlist)}
(2) S→while M1 E do M2 S1 {backpatch(S1.nextlist,M1,.quad);
backpatch(E.truelist,M2,.quad); S.nextlist:=E.falselist emit (‘j,-,-,’M1 .quad)} {S.nextlist:=makelist()} {L.nextlist:=S.nextlist} {M.quad:=nextquad}
{E.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1);
(3) S→A (4) L→S (5) M→ε
(6) E→id1 relop id2
emit(‘j’relop.op,‘,’id1.place ‘,’id2.place‘,’‘0’);
emit(‘j,-,-,0’)}
(7) S→L:=E
{emit(:=,E.place,-,L.place)}
(8) E→E1+E2{E.place:=newtemp;
emit(+,E1.place,E2.place,E.place,)}
6. (8 分) Generate assembly code for the following sequence assuming that x,y and z are in
memory locations(noticing only two registers R1 and R2).
S=0
I=0
L1: if x>y goto L2
Z=s+a[i]
I=i+1 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 分） 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 分 ( ) i * + # E E→(E)E’ E→iE’ E’→TEE’ E’ →ε E’ E’→ ε E’→TEE’ E’ →ε E’ →ε T T→* T→+
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((? )())()() ? ? (()())()()
（2）（1）中加下划线的部分是句柄，标识如（1）。每少写一个句柄扣 0.5 分，扣完为止，共 4 分。 （3）每少写步扣 0.5 分，扣完为止，共 4 分。
S
S ( S )
S
( S ) ε
S
( S ) ε
ε 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 E1.f=107
do M2.q=102 S1
ε
a
E2.f=103
S2
ε if E2.t=102 then M3.q=104
ε L.p=x :=
(E3.t=102) (E3.f=103)
E4.p=T1
x
E5.p=y + E6.p=z
c>d
（2）少写一个四元式扣 0.5 分，全错或不写不
y
z
四元式序列为：
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 分