程序設(shè)計語言與編譯習(xí)題解答

1、4-5 解：上下文有關(guān)文法（1型文法），產(chǎn)生的語言L（G）=aibici | i1,i為整數(shù)4-6 解：3型文法，L（G）=ai | i1,i為奇數(shù)4-7 解：2型文法，L（G）=aibi | i1,i為整數(shù)4-8 解：1型文法，L（G）=aibici | i1,i為整數(shù)4-9 解：1. 最左推導(dǎo)最右推導(dǎo)S (A) (B) (SdB)S (A) (B) (SdB) (A)dB) (B)dB) (SdS) (Sda) (S)dB) (b)dB) (A)da (B)da) (b)dS) (b)da) (s)da (b)da)2. 語法樹4-10解：1. 因為存在推導(dǎo)S SbF SbP Sbc Fb

2、c FaPbc所以FaPbc是文法G (S) 的一個句型。2. 語法樹4-11解：因為串a(chǎn)aabaa可有下列兩棵不同的語法樹所以文法G (S)是二義文法。9-2解：（1）消除文法G的產(chǎn)生式直接左遞歸。ASeA | fA AdA | e （2）消除間接左遞歸：按S.A排序（按書上P116頁的算法i=2,j=1時）將S的產(chǎn)生式代入有AAaeA | AbeA | ceA | fA （3）消除的直接左遞歸有AceAA | fAA AaeAA | beAA | e （4）對S的產(chǎn)生式提公因子有SAB | c B| a | b （5）最后，文法G提取公因子，消除左遞歸后的產(chǎn)生式由, , , 和組成，無多余

3、的產(chǎn)生式。（6）若按A.S排序，得到的產(chǎn)生式組合是另外的形式，但它們是等價的文法，讀者可以試試。9-3解：消除左遞歸后，得文法G:S(L) | aLSLL, SL | e遞歸下降過程： Procedure match(t:token); begin if lookahead=t then lookahead=nexttoken else error end procedure S; begin if lookahead=a then match(a) else if lookahead=( then begin match(c); L; if lookahead=) then match()

4、else error end end procudure L; begin S; L; end procudure L; begin if lookahead=, then begin match(,) S; L end end9-6解：（1）G（S）：SAS SiAS | e ABA A+BAe BbS* | a （2）FIRST集和FOLLOW集FIRSTFOLLOWSb，a#，*Si，e#，*Ab，a#，*，iA+，e#，*，iBb，a#，*，i，+預(yù)測分析表ai+b*#SSASSASSSiASSeSeAABAABAAAeA+BAAeAeBBaBbS*（3）因為預(yù)測分析表無多重定義入口，

5、所以G是LL（1）文法。9-7解：對習(xí)題9-3的文法G消除左遞歸后，得文法G： S(L) | a LSL L,SL | e FIRST集和FOLLOW集FIRSTFOLLOWS(，a)，#L(，a)L，e)預(yù)測分析表（）a,#SS(L)SaLLSLLSLLL)L,SL因為預(yù)測分析表無多重定義入口，所以文法G是LL（1）文法。 10-1解：（1）規(guī)范規(guī)范推導(dǎo)（最右推導(dǎo)）最右推導(dǎo)SABASbAABbbBABb（2）語法樹（推導(dǎo)樹）（3）短語 bB, AB, ABb, bBABb 直接短語 bB, AB 句柄 bB 最左素短語 bB10-2解：（1）因為存在推導(dǎo)SSbFFbFFaPbFFaPbPFa

6、Pbc所以FaPbc是文法G的一個句型。（2）語法樹（3）短語 FaP, c, FaPbc 直接短語 FaP, c 句柄 FaP 最左素短語 FaP10-3解：拓廣文法0.SS1.SAS2.Sb3.ASA4.AaLR（0）項目集規(guī)范族I0=closureSS I1=GO(I0,S) I2=GO(I0,A) I3=GO(I0,b)I0:SS SS SAS SbSAS ASA SAS GO(I1,a)=I4Sb ASA Sb GO(I2,A)=I2ASA Aa ASA GO(I2,b)=I3Aa SAS Aa SbI4=GO(I0,a) I5=GO(I1,A) I6=GO(I1,S) I7=GO(

7、I2,S)Aa ASA ASA SAS SAS ASA ASA SAS Ab ASA Sb SAS Aa ASA Sb SAS Aa Sb GO(I1,b)=I3 GO(I2,a)=I4FOLLOW(S)=a, b, #FOLLOW(A)=a, b 狀態(tài)5在輸入a時有S4和r3的移進歸約矛盾。 狀態(tài)5在輸入b時有S3和r3的移進歸約矛盾。 狀態(tài)7在輸入a時有S4和r1的移進歸約矛盾。 狀態(tài)7在輸入b時有S3和r1的移進歸約矛盾。 文法G既不是LR（0）文法，也不是SLR（1）文法。10-4解：（1）最左推導(dǎo) S(T)(T,S)(S,S)(a,S)(a,(T) (a,T,S)(a,(S,S)=(

8、a,(a,S)(a,(a,a) 最右推導(dǎo) S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a) (T,(S,a)(T,(a,a)(S,(a,a)(a,(a,a) 最左推導(dǎo) S(T)(T,S)(S,S)(T),S)(S),S)(T,S),S) (T,S,S),S)(S,S,S),S)(T),S,S),S) (T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S) (a,a),S,S),S)(a,a),S),S)=(a,a),(T),S) (a,a),(S),S)(a,a),(a),S) =(a,a),(a),S)(a,a),(a),a)最右推導(dǎo)S(T)(T,S)(

9、T,a) (S,a)(T),a)(T,S),a) (T,(T),a)(T,(S),a)(T,(a),a)(T,S,(a),a) (T,(a),a)(S,(a),a)(T),(a),a) (T,S),(a),a)(T,a),(a),a)(S,a),(a),a) (a,a),(a),a)（2）對句子(a,(a,a)的移進歸約棧的變遷如下：其中，（3），（4），（8），（9），（12），（13），（15），（16），（18）共進行9次歸約，最右推導(dǎo)也是9次推導(dǎo)，正好是遞過程。歸約（3）的句柄是a，語法樹如圖（1）所示。歸約（4）的句柄是S，語法樹如圖（2）所示。歸約（8）的句柄是a，語法樹如圖（3）

10、所示。歸約（9）的句柄是S，語法樹如圖（4）所示。歸約（12）的句柄是S，語法樹如圖（5）所示。歸約（13）的句柄是T,S，語法樹如圖（6）所示。歸約（15）的柄是(T)，語法樹如圖（7）所示。歸約（16）的句柄是T,S，語法樹如圖（8）所示。歸約（18）的句柄是(T)，語法樹如圖（9）所示。圖（9）即是完整的語法樹。圖中的下標是為了區(qū)分歸約過程中同名文法符號和便于理解而添加的，實際是沒有的，對句子(a,a),(a),a)的規(guī)約棧變遷如圖(10)所示。圖(10)規(guī)范推導(dǎo)（最右推導(dǎo)）一共進行17步推導(dǎo)，歸約過程也進行了17次歸約，語法樹如圖(11)所示，其中的下標可表明其形成的先后。圖(11)1

11、0-7解：0.SSFOLLOW(S)=$1.SABFOLLOW(A)=b,c2.BcBdFOLLOW(B)=d,$3.Bcd4.AaAb5.AabI0=closureSSI0:SSI4=GO(I2,B)I9=GO(I5,d) SAB SAB Bcd AaAbI5=GO(I2,c)I10=GO(I6,b) Aab BcBd AaAbI1=GO(I0,S) BcBdI11=GO(I8,d) SS BcBd BcBdI2=GO(I0,A) Bcd SABI6=GO(I3,A) BcBd AaAb Bcd GO(I3,a)=I3I3=GO(I0,a)I7=GO(I3,b) AaAb Aab AabI8

12、=GO(I5,B) AaAb BcBd Aab GO(I5,c)=I5上述狀態(tài)集沒有移進歸約沖突，（a）是SLR文法，分析表如下：abcd$SAB0S3121acc2S543S3S764r15S5S986S107r5r58S119r3r310r4r411r2r210-10解：（1）FIRSTVT(P)=A,(LASTVT(P)=a,) FIRSTVT(F)=aLASTVT(F)=a（2）優(yōu)先關(guān)系表：習(xí)題1111-1解：11-3解： 推導(dǎo)樹如下：（1）EiEVAL=B設(shè)四元式初始編號ip=100（2）EiEVAL= C（3）E-EEVAL=T1(101)(,c,-,T1)（4）EiEVAL=D（

13、5）EE+EEVAL=T2(101)(+,T1,D,T2)（6）EE*EEVAL=T3(103)(*,B,T2,T3)（7）Si:=E(104)(:=,T3,-,A)11-4解：結(jié)果為333645211。11-5解：（1）E1CDE1F=101(100)(BE2F=103(102)(,A,B,104)（4）E1E*EE1VAL=T1(103)(j,-,-,0)（5）E2E+EE2VAL=T2(104)(*,2,z.T1)（6）Ai:=E2Achain=0(105)(+,y,T1,T2)（7）SAS1chain=0(106)(:=,T2,-,x)（8）SWS1S1chain=103(107)(j

14、,-,-,102)（9）Sif E1 thenS1Schain=101習(xí)題12回邊749110712-1解：（a）基本塊程序流圖B1 (1)(3)B2 (4)B3 (5)B4 (6)B5 (7)(8)B6 (9)B7 (10)(11)B8 (12)(13)B9 (14)(15)B10 (16)(17)（b）必經(jīng)結(jié)點D(1)=1D(2)=1,2D(3)=1,3D(4)=1,3,4D(5)=1,3,4,5D(6)=1,3,4,6D(7)=1,3,4,7D(8)=1,3,4,7,8D(9)=1,3,4,7,8,9D(10)=1,3,4,7,8,10由回邊74組成的循環(huán)7,4,5,6,8,10。（3）

15、優(yōu)化結(jié)果(3) B:=10(4) A:=A+8(5) if B100 then goto (8)(6) B:=B+10(7) goto (4)(8) write A12-2解：（1）基本塊（2）程序流圖 B1 (1)(3) B2 (4)(5) B3 (6)(7) B4 (8)12-7解：MOVbR0ADDR0cMOVaR1SVBR1R0MOVR0t1MOVdR0ADDR01MOVR1t2MOVeR1MVLR1fADDR0R1MOVt2R1DIVR1R012-8解：abcdefB1122211B212111B312212B422211B5111122698637分配給b, c, f，執(zhí)行代價最省

16、。13-2解：當運行到C調(diào)用B時，活動記錄棧的狀態(tài)如下圖。13-4解：靜態(tài)作用域規(guī)則下輸出 0.250 0.250 0.250 0.250動態(tài)作用域規(guī)則下輸出 0.250 0.125 0.250 0.1257-6解：設(shè)x, y, z對應(yīng)的形式單元為J1（和J1），J2（和J2），J3（和J3）。1. 引用調(diào)用A:=2B:=3T:=A+B（T的值為5）J1:=T的地址J2:=A的地址J3:=A的地址J2:=J2+1（A的值為3）J3:=J3+J1（A的值為3+5=8）打印A的值為8。2. 傳值A(chǔ):=2B:=3T:=A+B（T的值為5）J1:=T（J1的值為5）J2:=A（J2的值為2）J3:=A（J3的值為2）J2:=J2+1（J2的值為3）J3:=J3+J1（J3的值為7）打印A的值為2。3. 結(jié)果調(diào)用形式單元J1, J2, J3無初始化值，計算是不確