状态 0 1 2 3 4 5 a S1 S1 S1 ACTION b S2 S2 S2 # r3 acc r1 r2 GOTO S 3 4 5
该文法是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
*
n9 T4
+ n3 T1,T4,N
n8 T3 + －
n7n1 n2 n4 T2 n5 M n6
7
A B 5 20 C 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
试卷编号： 1-A 第 6 页 共 8 页
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 结点，也是出口结点。 (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
B2，且B2DOMB3，所以，有一个循环{B2, B3}，B2是循环入口
L1：A=C+A if C=R goto L2 C=C+1 GOTO L1 L2： B4 B3 B2
试卷编号： 1-A 第 7 页 共 8 页
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分） PP_TOP →
DISPLAY表 PP_SP ex_SP 形式参数x 参数个数：1 全局DISPLAY地址 返回地址
PP_SP → ex_SP ex_TOP →
局部变量：a DISPLAY表 ex_SP 参数个数：0 全局DISPLAY地址
返回地址 ex_SP →
ex_SP 试卷编号： 1-A 第 8 页 共 8 页
PP的活动记录 PP（a）之后）
ex的活动记录 PP（a）之前）（调用 （调用