由上可见：

I1 ,I2 ,I9 存在移进—归约冲突. 分析FOLLOW集： 因为： 对I1 FOLLOW(S’)={ # }∩{ + }= ф

对I2 FOLLOW(E)={ +, #, ) }∩{* }= ф 对I9 FOLLOW(E)={ +, #, ) }∩{* }= ф

所以是SLR(1)文法。 （2）： STEP 1 2 3 4 5 6 7 8 S 0 04 045 043 042 048 0486 04864 X # # ( # (i # (F # (T # (E # (E+ # (E+ ( ( i + ( * i ) # ( i + ( * i ) # i + ( * i ) # + ( * i ) # + ( * i ) # + ( * i ) # + ( * i ) # ( * i ) # * i ) # action S4 S5 r6 r4 r2 S6 S4 error goto 3 2 8

4、(一) 给出语句 if a+b > b+c*d then while x*y>3 do x:=x-a*b else while b+c*d>10 do b:=b-(x*y+5) 相应的三地址代码.

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) t1=a+b t2=c*d t3=b+t2 if t1>t3 goto (6) goto (14) t4=x*y if t4>3 goto (9) goto (13) t5=a*b t6=x-t5 x=t6 (12) (13) (14) (15) (16) (17) (18) (19) (20) (21) (22) (23) goto (6) goto (23) t7=c*d t8=b+t7 if t8>10 goto (18) goto (23) t9=x*y t10=t9+5 t11=b-t10 b=t11 goto (14)

(二) While a＞0 ∨ b＜0 do Begin

X：＝X＋1；

if a＞0 then a：＝a－1 else b：＝b＋1 End；

翻译成四元式序列. (10分) ? 解：

(1) (j＞，a，0，5) (2) (j，＿，＿，3) (3) (j＜，b，0，5） (4) (j，＿，＿，15) (5) (＋，x，1，T1) (6) (:= ，T1，＿，x) (7) (j＞，a，0，9) (8) (j，＿，＿，12) (9) (－，a，1，T2) (10) (:= ，T2，＿，a) (11) (j，＿，＿，1) (12) (＋，b，1， T3) (13) (:= ，T3，＿，b) (14) (j，＿，＿，1) (15)

5、(一)设有基本块(10分) T1：＝2

T2：＝10∕T1 T3：＝S－R T4：＝S＋R

A：＝T2 * T4 B：＝A T5：＝S＋R T6：＝T3 * T5 B：＝T6

(1) 画出DAG图；

(2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。

5(一)、解：(1)DAG：

(2) 优化后的四元式 T3：＝S－R T4：＝S＋R A：＝5*T4

B：＝T3＋T4

(二) P255-257 DAG图

例 试构造以下基本块G的DAG

(1) T0：＝3.14 (2) T1：＝2* T0 (3) T2：＝R+r (4) A：＝T1 * T2 (5) B：＝A (6) T3：＝2* T0 (7) T4：＝R+r

(8) T5：＝T3 * T4 (9) T6：＝R-r (10) B：＝T5 *T6 (11)if B<=10 goto (1) (1) 画出DAG图；

(2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。解：（1）DAG图如下：

分)

(3

（2） 四元序列如下： 1 T：＝R+r ○

2

2 T：＝R-r ○

6

3 A：＝6.28* T○4 B：＝A*T ○

6

2

四、 ? 1.1

先给出NFA图：

画状态转换表:

A B C' D' E' I A B BC BD CBE 0 B BD B BD 1 B BC BC BCE BC 得DFA如下图：