编译作业答案.doc

7-2给定文法G：SAa|Ab|cAAd|Se|f请消除文法的左递归，并提取公共左因子。解：（1）消除文法G的产生式直接左递归。ASeA | fA AdA | e （2）消除间接左递归：按S.A排序（按算法i=2,j=1时）将S的产生式代入有AAaeA | AbeA | ceA | fA （3）消除的直接左递归有AceAA | fAA AaeAA | beAA | e （4）对S的产生式提公因子有SAB | c B| a | b （5）最后，文法G提取公因子，消除左递归后的产生式由, , , 和组成，无多余的产生式。（6）若按A.S排序，得到的产生式组合是另外的形式，但它们是等价的文法。7-3给定文法G：S(L)|aLL，S|S消除文法G的左递归，并写出递归下降分析的相应递归过程。解：消除左递归后，得文法G:S(L) | aLSLL, SL | e递归下降过程：procedure advance( )begin sym =getchar( )end procedure S; begin if sym =a then advance( ) else if sym =( then begin advance( ) L( ); if sym =) then advance( ) else error() end else error() end procudure L; begin S; L; end procudure L; begin if sym =, then begin advance( ) S; L end end7-5解：（1）G（S）：SAS S:AS | e ABA A+BA|e BbS* | a （2）FIRST集和FOLLOW集FIRSTFOLLOWSb，a#，*S:，e#，*Ab，a#，*，:A+，e#，*，:Bb，a#，*，:，+预测分析表a:+b*#SSASSASSS:ASSeSeAABAABAAAeA+BAAeAeBBaBbS*（3）因为预测分析表无多重定义入口，所以G是LL（1）文法。7-6解：对习题7-3的文法G消除左递归后，得文法G： S(L) | a LSL L,SL | e FIRST集和FOLLOW集FIRSTFOLLOWS(，a)，#L(，a)L，e)预测分析表（）a,#SS(L)SaLLSLLSLLL)L,SL因为预测分析表无多重定义入口，所以文法G是LL（1）文法。8-1已知文法G：SABAAb|bBBa|Sb（1）写出bBABb的规范推导。（2）画出bBABb的语法树。（3）求bBABb的短语、直接短语、句柄和最左素短语。解：（1）规范规范推导（最右推导）最右推导SABASbAABbbBABb（2）语法树（推导树）（3）短语 bB, AB, ABb, bBABb 直接短语 bB, AB 句柄 bB 最左素短语 bB8-2已知文法G：SSbF|FFFaP|PPc（1）试证明FaPbc是文法G的一个句型。（2）画出FaPbc的语法树。（3）求出FaPbc的短语、直接短语、句柄和最左素短语。解：（1）因为存在推导SSbFFbFFaPbFFaPbPFaPbc所以FaPbc是文法G的一个句型。（2）语法树（3）短语 FaP, c, FaPbc 直接短语 FaP, c 句柄 FaP 最左素短语 FaP8-3已知文法G：SAS|bASA|a（1）列出G的LR（0）项目集规范族。（2）这个文法是LR（0）文法吗？是SLR（1）文法吗？若是，请构造出相应的分析表。解：拓广文法0.SS1.SAS2.Sb3.ASA4.AaLR（0）项目集规范族I0=closureSS I1=GO(I0,S) I2=GO(I0,A) I3=GO(I0,b)I0:SS SS SAS SbSAS ASA SAS Sb ASA Sb ASA Aa ASA Aa SAS Aa SbI4=GO(I0,a) I5=GO(I1,A) I6=GO(I1,S) I7=GO(I2,S)Aa ASA ASA SAS SAS ASA ASA SAS Ab ASA Sb SAS Aa ASA Sb SAS Aa S GO(I1,b)=I3 GO(I2,a)=I4 GO(I1,a)=I4 GO(I2,A)=I2 GO(I2,b)=I3 FOLLOW(S)=a, b, #FOLLOW(A)=a, b 状态5在输入a时有S4和r3的移进归约矛盾。 状态5在输入b时有S3和r3的移进归约矛盾。 状态7在输入a时有S4和r1的移进归约矛盾。 状态7在输入b时有S3和r1的移进归约矛盾。 文法G既不是LR（0）文法，也不是SLR（1）文法。8-7设有文法G：SABBcBd|cdAaAb|ab它是否为SLR（1）文法？若是，请构造相应的SLR（1）分析表。解：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=GO(I5,B) AaAb BcBd Aab GO(I5,c)=I5上述状态集没有移进归约冲突，（a）是SLR文法，分析表如下：abcd$SAB0S3121acc2S543S3S764r15S5S986S107r5r58S119r3r310r4r411r2r28-9设有文法G：PP（F）|FFabFda|a（1）试求每个非终结符的FIRSTVT集和LASTVT集。（2）试构造文法G的优先关系表。解：（1）FIRSTVT(P)=a,(LASTVT(P)=a,) FIRSTVT(F)=aLASTVT(F)=a（2）优先关系表：9-4对下列翻译方案：SPSprint “1”SPQprint “2”Pa print “3”QbR print “4”QdQ print “5”Rc print “6”当输入串为“aaadb”时，翻译结果是什么？解：结果为333645211。9-5试写出语句if CB do x:=y+2*z 的翻译过程。解：（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）SA S1chain=0(106)(:=,T2,-,x)（8）SWS1S1chain=103(107)(j,-,-,102)（9）Sif E1 thenS1 Schain=1019-69-7 试写出语句for i:=1 to N do S1的语义子程序。其语义为 i:=1;again : if iN then begin S1; i:=i+1; goto again end原文法 Sfor i:=1 to N do S1改写为 Ffor i:=1 to N do SF S1Ffor i:=1 to N do F.place := entry(i);emit(:=,1,- F.place); F.again:=ip; /F+1 emit(j,entry(i),N,F.again+2); F.CHAIN:=ip; /F+2 emit(j,-,-,0) SF S1 backpatch(S1.CHAIN,ip); emit (+,F.place,1,F.place); emit(j,-,-,F.again); S.CHAIN:=F.CHAIN 9-8 试写出repeat语句的语义子程序。其语义为again : S1;. B.T: if B goto 0 B.F: goto again 原文法 Srepeat S1 until B改写为 SR BRP S1 until Prepeat翻译方案： PrepeatP.CODE:=ipRP S1 until backpatch(S1.CHAIN,ip);R.CODE:= P.CODE SR B backpatch(B.F, R.CODE);S1.CHAIN:=B.T 回边749110710-1有如下三地址代码序列：（1）read x （10）B:=y+j（2）read y （11）if A=B goto（6）（3）if xB goto（16）（5）read j （14）write B（6）if ij goto（9） （15）goto （9）（7）A:=i+1 （16）A:=x*j（8）goto（10） （17）goto （10）（9）A:=x*j（a）请划分基本块，构造程序流图。 （b）根据必经结点找出回边及由回边组成的循环。解：（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）必经结点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组成的循环7,4,5,6,8,10。10-2试将下面的程序段划分为基本块，构造其程序流图，并进行优化。（1）C:=100（2）A:=0（3）B:=10（4）A:=A+B（5）if BC then goto（8）（6）B:=B+10（7）goto（4）（3）优化结果(3) B:=10(4) A:=A+8(5) if B100 then goto (8)(6) B:=B+10(7) goto (4)(8) write A（8）write A解：（1）基本块（2）程序流图 B1