编译原理期末考试试卷及答案

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))

(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’

第 13 页 共 14 页

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’)={ )} (3)

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

, S’→ε L’→,SL’ # S’→ε 第 14 页 共 14 页