編譯作業(yè)答案

1、7-2給定文法G：S?Aa|Ab|cA?Ad|Se|f請消除文法的左遞歸，并提取公共左因子。解：（ 1 ）消除文法G 的產(chǎn)生式直接左遞歸。2 SeA' | fA'AdA'| ?（2）消除間接左遞歸：按 S.A排序（按算法i=2,j=1時）將S的產(chǎn)生式代入有2 AaeA' | AbeA' | ceA' | fA'（3）消除的直接左遞歸有2 ceA'A" | fA'A"A aeA'A” | beA'A" | ?（ 4 ）對S 的產(chǎn)生式提公因子有Sf AB|cBf | a | b(5

2、)最后，文法G提取公因子，消除左遞歸后的產(chǎn)生式由，和組成，無多余的產(chǎn)生式。(6)若按A.S排序，得到的產(chǎn)生式組合是另外的形式，但它們是等價的文法。7-3 給定文法G：S?(L)|aL?L， S|S消除文法 G 的左遞歸，并寫出遞歸下降分析的相應(yīng)遞歸過程。解：消除左遞歸后，得文法G':>(L) | aLf SL'L' f, SL' |遞歸下降過程：procedure advance( ) beginsym =getchar( ) endprocedure S;beginif sym ='a' then advance( )else if sy

3、m ='(' thenbeginadvance( )ifL( );sym =')' then advance( ) else error()endelseerror()endprocudure L;begin S;L'endprocudure L'beginif sym =',' then beginadvance( )S;L'endend7-5 解：(1) G' (S): S AS'S' f :AS' |Af BA'A' f+BA'|?Bf bS* | a(2) F

4、IRST集和 FOLLOWFIRST FOLLOWS'A'b, ab, ab, a#, *#, *#, *#, *#, *預測分析表a:+b*#SSf AS'Sf AS'S'S'fAS'S' f ?S' f ?A2 BA'A BA'A2 ?2 +BA'A ?2 ?BB aBf bS*(3)因為預測分析表無多重定義入口，所以 G是LL (1)文法7-6 解：對習題7-3的文法G消除左遞歸后，得文法 G':S "(L) | aL f SL'L' f,SL'| ?

5、FIRST 集和 FOLLOW!FIRSTFOLLOWS(,a),',#L(,a)L'?)預測分析表()a,#SS" (L)S” aLLf SL'Lf SL'L'L'fL' f ,SL'因為預測分析表無多重定義入口，所以文法 G是LL (1)文法已知文法G:8-1S?ABA?Ab|bBB?a|Sb（1）寫出bBABb的規(guī)范推導。（2）畫出bBABb的語法樹。（3）求bBABb的短語、直接短語、句柄和最左素短語。解：（ 1 ）規(guī)范規(guī)范推導（最右推導）最右推導S?AB?ASb?AABb?bBABb（ 2 ）語法樹（推導樹）（

6、 3 ）短語bB, AB, ABb, bBABb直接短語bB, AB句柄 bB最左素短語 bBS?SbF|FF?FaP|PP?c（1）試證明FaPbc是文法G的一個句型。（ 2）畫出FaPbc 的語法樹。（ 3）求出FaPbc 的短語、直接短語、句柄和最左素短語。解：（ 1 ）因為存在推導S?SbF?FbF?FaPbF?FaPbP?FaPbc所以FaPbc是文法G的一個句型。（ 2 ）語法樹（ 3 ）短語FaP, c, FaPbc直接短語 FaP, c句柄 FaP最左素短語 FaP8-4G：S?AS|bA?SA|a(1)列出G的LR (0)項目集規(guī)范族。( 2)這個文法是LR( 0)文法嗎？是

7、SLR( 1 )文法嗎？若是，請構(gòu)造出相應(yīng)的分析表。解：拓廣文法0s f S1.Sf AS2.Sf b3 .Af SA4 .A aLR( 0)項目集規(guī)范族10=closureS' 7 S I i=GO(Io,S) I 2=GO(Io,A)S' S-I 3=GO(I0,b)S A- SSf ASSf b2 SA2 a aAf SAA7 aS ASSf bAf SAI4=GO(I0,a)I5=GO(I1,A)I6=GO(I1,S)Af S AI7=GO(I2,S)A fSA- AS- AS f AS-SA- SS ASSf bAf SAA7 aGO(I1,b)=I3GO(I2,a)

8、=I4 GO(I1,a)=I4 GO(I2,A)=I2 GO(I2,b)=I3FOLLOW(S)=a, b, #FOLLOW(A)=a, b狀態(tài)5在輸入a時有S和r 3的移進歸約矛盾狀態(tài)5在輸入b時有$和n的移進歸約矛盾狀態(tài)7在輸入a時有0和ri的移進歸約矛盾。狀態(tài) 7 在輸入 b 時有S3 和 r 1 的移進歸約矛盾。文法G既不是LR (0)文法，也不是 SLR (1)文法。8-7設(shè)有文法G：S?ABB?cBd|cdA?aAb|ab它是否為 SLR( 1)文法？若是，請構(gòu)造相應(yīng)的 SLR( 1)分析表。解：0s SFOLLOW(S)=$1.Sf ABFOLLOW(A)=b,c2.Bf cBd

9、FOLLOW(B)=d,$3.B” cd4.A aAb5.A abI 0=closureS10s . SS f ABA f aAbA f abI 1=GO(I0,S)S' SI 2=GO(I0,A)S -A BB f cBdB f cdI 3=GO(I0,a)A a AbA a bA f aAbSI 4=GO(I2,B)S f ABI 5=GO(I2,c)IB fc BdB f cBdB f cBdB f c dI 6=GO(I3,A)A f aA bGO(I 3,a)=I 3I 7=GO(I3,b)A ab I 8=GO(I5,B)I 9=GO(I5,d)B f cd 10=GO(I

10、6,b)A f aAb I 11=GO(I8,d)B fcBd-B f cB dGO(I 5,C)= I 5上述狀態(tài)集沒有移進一歸約沖突，（a）是SLR文法，分析表如下:SABaccS5S。S5S）10S131128-9設(shè)有文法G:P?P (F) |FF?abFda|a(1)試求每個非終結(jié)符的FIRSTVT集和LASTVTBo(2)試構(gòu)造文法G的優(yōu)先關(guān)系表。解:(1) FIRSTVT(P尸a,(LASTVT(P尸a,)FIRSTVT(F尸aLASTVT(F尸a(2)優(yōu)先關(guān)系表:9-4對下列翻譯方案：S?PSprint“1”S?PQprint“ 2”P?a print“ 3”Q?bR print

11、“ 4”Q?dQ print“ 5”R?c print“ 6”當輸入串為“ aaadb”時，翻譯結(jié)果是什么？解：結(jié)果為 333645211。9-5試寫出語句if C<D then while A>B do x:=y+2*z 的翻譯過程。解：(1) ElC<DE1 F=101(100)(<,C,D,102)W code=102E2 F=103Ei VAL=TE2 VAL=T2A - chain=0S 1 chain=0S chain=103S chain=101 Wwhile(3)巳fA>B(4) EiE*E(5)巳fE+E(6) Af i:=E 2(7) Sf A

12、(8) Sf WS(9) Sf if E i thenSi9-69-7 試寫出語句(101)(j,-,-,103)(102)(>,A,B,104)(103)(j,-,-,0)(104)(*,2,z.T1)(105)(+,y,T1,T2)(106)(:=,T2,-,x)(107)(j,-,-,102)for i:=1 to N do S1的語義子程序。其語義為i:=1;again : if i?N then beginS 1;i:=i+1;goto againend原文法S for i:=1 to N do S 1改寫為F for i:=1 to N doSf F SiF for i:=1

13、 to N do F.place := entry(i);emit(:=, 1 , - F.place);F.again:=ip;/F+1emit(j?,entry(i),N,F.again+2);F.CHAIN:=ip;/F+2emit(j,-,-,0) Sf F Si backpatch(S 1.CHAIN,ip);emit (+,F.place, i ,F.place);emit(j,-,-,F.again);S.CHAIN:=F.CHAIN 9-8 試寫出 repeat 語句的語義子程序。其語義為again : S 1;.B.T: if B goto 0B.F: goto again原

14、文法S repeat S1 until B改寫為S f R BRf P S1 untilP f repeat翻譯方案：P f repeatP.CODE:=ipRf P S1 until backpatch(S1.CHAIN,ip); R.CODEk P.CODE Sf R B backpatch(B.F, R.CODE); S1.CHAIN:=B.T 10-1(1) read x(10)(2) read y(11)(3) if x<y goto(5)(12)(4) read i(13)(5) read j(14)(6) if i>j goto(9)(15)回邊B:=y+jif A=

15、B goto (6)B:=y+iif A>B goto (16)write Bgoto (9)有如下三地址代碼序列：A:=i+1(16)A:=x*j(8) goto (10)(17) goto (10)B。(16)(17)(9) A:=x*j(a)請劃分基本塊，構(gòu)造程序流圖。(b)根據(jù)必經(jīng)結(jié)點找出回邊及由回邊組成的循環(huán)解：(a)基本塊程序流圖Bi(3)R (4)B (5)R (6)B5(8)B6 (9)B (10)(11)B (12)(13)B9 (14)(15)(b)必經(jīng)結(jié)點D(1)=1D(4)=1,3,4D(7)=1,3,4,7D(2)=1,2D(5)=1,3,4,5D(8)=1,3,4,7,8D(3)=1,3D(6)=1,3,4,6D(9)=1,3,4,7,8,9D(10)=1,3,4,7,8,10由回邊774組成的循環(huán)7,4,5,6,8,1010-2試將下面的程序段劃分為基本塊，構(gòu)造其程序流圖，并進行優(yōu)化。(1) C:=100 A:=0(3) B:=10(4) A:=A+B(5) if B C then goto( 8)(6) B:=B+10(7) goto (4)(8) write A(3)優(yōu)化結(jié)果(3) B:=10解:(1)基本塊(2)程序流圖B