答案：(1)消除左递，文法变为G’[S]：

S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε

此文法无左公共左因子。

(2)构造相应的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}， FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)} (3)构造预测分析表： a ^ ( S T T’ S→a T→ST’ S→^ T→ST’ S→(T)' T→ST’ ) T’→ε , T’→,ST’ # 2. (1) C→if E then

(1)

S→CS (2)

C→if E then {BACK(E.TC, NXQ); C.chain:=E.FC}

(1) (1)

S→CS{S.chain:=MERG(C.Chain, S. Chain)} 3. (1) FIRSTVT(S)={a, ( } FIRSTVT(T)={+, aa, (} LASTVT(S)={a, ) }

LASTVT(T)={+, a, )}

(2) a + ( a .> + <. .> <. ( <. <. <. ) .> .> (1)(2) 4. (1) F→for i:=E to E do (1)

S→FS

(1)(2)

(2) F→for i:=E to E do

(1)

{GEN(:=, E.place, _, entry(i)); F.place:=entry(i); LIMIT:=Newtemp;

(2)

GEN(:=, E.place, _, LIMIT); Q:=NXQ; F.QUAD:=q;

GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)}

(1)

S→FS

(1)

{BACKPATCH(S.chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain }

5. (1) (j<, a, ‘10’, (3))

第 9 页 共 11 页

) .> .> =. >. (2) (j, _, _, (12)) (3) (j>, c, ‘0’, (5)) (4) (j, _, _, (8)) (5) (+, a, ‘1’, T1)) (6) (:=, T1, _, a) (7) (j, _, _, (1)) (8) (*, a, ‘13’, T2) (9) (-, T2, ‘1’, T3) (10) (:=, T3, _, a) (11) (j, _, _, (1)) 6.优化后的四元序列

D:=A-C E:=A*C F:=D*E M:=F+20 7. 最左推导

S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 短语

((T,S),a) (T,S),a (T,S) T,S a

直接短语 T,S a 句柄 T,S 8.(1)

S→do M1 S1while M2 E M→ε (2)

M→ε {M.quad=nestquad;}

S→do M1 S1while M2 E {backpatch(s1.nextlist, M2.quad); backpatch(E.truelist, M1.quad); S.nextlist=E.falelist; }

9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde

(2) 短语: aAbcde, Ab, d 素短语: Ab, d 10.(1) S →(L) | aS’ S’→S |ε L→SL’

L’→,SL’ |ε

(2) FIRST(S)={a, (} FIRST(S’)={a, (, ε} FIRST(L)={a, (} FIRST(L’)={,, ε}

FOLLOW(S)={,, ), #} FOLLOW(S’)={,, ), #} FOLLOW(L)={ )} FOLLOW(L’)={ )}

第 10 页 共 11 页

(3)

( ) a , S S →(L) S → aS’ S’ S’→S S’→ε S’→S S’→ε L L→SL’ L→SL’ L’→,SL’ L’ L’→ε

11.(1) (j>, X, 0, (5))

(2) (j, _, _, (3)) (3) (j<, Y, 0, (5)) (4) (j, _, _, (11)) (5) (j>0, X, 0, (7)) (6) (j, _, _, (7)) (7) (*, A, 3, T1) (8) (:=, T1, _, N) (9) (j, _, _, (5)) (10) (j, _, _, (13)) (11) (+, B, 3, T2) (12) (:=, T2, _, Y)

12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T =>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T =>(i+i)*i+F=>(i+i)*i+i

(2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短语 i, E+T 最左素短语 E+T

13.(1) FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -} FIRSTVT(U)={i, -}

LASTVT(S)={∨, ∧, i, - }

LASTVT(T)={∧, i, -}

LASTVT(U)={i, -}

(2)

i ∨ ∧ - S .> .> ∨ <. .> <. <. ∧ <. .> .> <. - <. .> .> <.

# S’→ε 第 11 页 共 11 页