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）之前）