S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q
K:=G*5 L:=K+J M:=L
假设基本块出口时只有M还被引用，请写出优化后的四元序列。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S
(1) 给出句子(a,(a,a))的最左推导；
(2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于 C 语言do S while E语句
(1)改写文法，使之适合语法制导翻译； (2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d
(1)给出句子abbcde的最左推导及画出语法树； (2)给出句型aAbcde的短语、素短语。 10.设文法G(S):
S→(T) | aS | a T→T,S | S
⑴消除左递归和提公共左因子；
⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表。 11.把语句
if X>0 ∨ Y<0
then while X>0 do X:=A*3 else Y:=B+3;
翻译成四元式序列。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i
(1) 给出句型 (i+i)*i+i的最左推导及画出语法树；
(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。 13.设文法G（S）： S→T | S∨T T→U |T∧U U→i |-U
（1）计算FIRSTVT 和LASTVT； （2）构造优先关系表。
第13页共6页
答案：(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))
第14页共6页
) .> .> =. >. (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’)={ )}
第15页共6页
(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’→ε 第16页共6页