编译原理-第七章习题

1．给出下面表达式的逆波兰表示（后缀式）：a*(-b+c)a+b*(c+d/e)notAornot(CornotD)(AandB)or(notCorD)后缀式分别为：ab-c+*abcde/+*+AnotCDnotornotorABandCnotDoror3.请将表达式-（a+b）*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。三元式：(0)（+，a,b）(1)(-,(0),_)(2)(+,c,d)(3)(*,(1),(2))(4)（+，a,b）(5)(+,(4),c)(6)(-,(3),(5))间接三元式：(1)（+，a,b）(2)(-,(1),_)(3)(+,c,d)(4)(*,(2),(3))(5)(+,(1),c)(6)(-,(4),(5))间接代码：（1）（2）（3）（4）（1）（5）（6）四元式：（0）（+，a,b,T1）（1）（-，T1,_,T2）（2）（+，c,d,T3）（3）（*,T2,T3,T4）（4）（+，a,b,T5）（5）（+，T5,c,T6）（6）（-，T4,T6,T7）7.用7.5.1节的方法，把下面语句翻译成四元式序列：WhileACandBDdoIfA=1thenC:=C+1ElsewhileA≤DdoA:=A+2;100（j,A,C,102）101（j,_,_,115）102（j,B,D,104）103（j,_,_,115）104（j=,A,1,106）105（j,_,_,109）106（+,C,1,T1）107（:=,T1,_,C）108（j,_,_,114）109（j≤,A,D,111）110（j,_,_,115）111（+,A,2,T2）112（:=,T2,_,A）113（j,_,_,109）114（j,_,_,100）115第十章3.试对以下基本块B1和B2：B1：A:=B*CD:=B/CF:=2*EG:=B*CH:=G*GF:=H*GL:=FM:=LB2：B:=3D:=A+CE:=A*CG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：（1）假设只有G,L,M在基本块后面还要被引用；（2）假设只有L在基本块后面还要被引用。解：B1：F,L,M*EH2+*A,GD/*BCB1优化后：A:=B*C(1)G:=B*C(2)G:=B*CD:=B/CH:=G*GH:=G*GE:=A+DL:=G*HL:=G*HG:=AM:=LH:=G*GF:=H*GL:=FM:=LB2：L,M+J+E,ID,HG+**KBn11n21n31n441n81n51n91n61n81n51n4n71n31n91n61n2n1n10F315ACB2优化后：B:=3(1)G:=3*F(2)H:=A+CD:=A+CH:=A+CI:=A*CE:=A*CI:=A*CJ:=H+IG:=B*FJ:=H+IL:=15+JH:=DL:=15+JI:=EM:=LJ:=H+IK:=15L:=K+JM:=L5.以下程序是某程序的最内循环，试对它进行循环优化A:=0I:=1L1：B:=J+1C:=B+IA:=C+AIfI=100GOTOL2I:=I+1GOTOL1L2：解：代码外提：B:=J+1删除归纳变量I：由C:=B+I可知I和C成线性关系所以I=100和C=B+100等价，即替换为：R:=100+BIFC=BGOTOL2同理I:=I+1可替换成C:=C+1综上所述代码优化后为：A:=0B:=J+1C:=B+1R:=100+BL1：A:=C+AIfC=RGOTOL2C:=C+1GOTOL1L2：第五章5．文法S-AS|bA-SA|a(1)列出所有LR(0)项目(2)构造LR(0)项目集规范族及识别活前缀的DFA(3)该文法是SLR的么？若是构造它的SLR分析表。解：扩展文法：S’-SSS-AS|bA-SA|abAaSAaSbAbbSaaSAbAaaSbA(3)FollowFirstS’#a,bS#,a,ba,bAa,ba,b冲突项目I１中：有接受项目和移进冲突，可解决.＃a,bI5,I7存在移进，归约冲突，不可解决．∵Follow(S)∩a∩b≠○所以，该文法不是SLR的８.证明下面的文法S-AaAb|BbBaA-εB-ε是LL(1)文法。①不含左递归；②First(α1)∩First(α2)∩…=○③First(A)∩Follow(A)=○∴该文法是LL(1)文法I0:S’-·SS-·ASS-·bA-·SAA-·aI1:S’-S·A-S·AA-·aS-·ASS-·bI2:S-A·SS-·ASS-·bA-·SAA-·aI3:S-b·I4:A-a·I6:A-S·AA-SA·A-·aS-·ASS-·bI5:A-SA·S-A·SS-·ASS-·bA-·SAA-·aI7:S-AS·A-S·AA-·SAA-·aS-·ASS-·bPartIWriting(30minutes)Directions：Forthispart,youareallowed30minutestowriteashortessayentitledHowShouldParentsHelpChildrentoBeIndependent?Youshouldwriteatleast150wordsfollowingtheoutlinegivenbelow.1.目前不少父母为孩子包办一切2.为了让孩子独立,父母应该……HowShouldParentsHelpChildrentoBeIndependent?..PartIIReadingComprehension(SkimmingandScanning)(15minutes)Directions:Inthispart,youwillhave15minutestogooverthepassagequicklyandanswerthequestionsonAnswerSheet1.Forquestions1-7,choosethebestanswerfromthefourchoicesmarked[A],[B],[C]and[D].Forquestions8-10,completethesentenceswiththeinformationgiveninthepassage.AGrassrootsRemedyMostofusspendourlivesseekingthenaturalworld.Tothisend,wewalkthedog,playgolf,gofishing,sitinthegarden,drinkoutsideratherthaninsidethepub,haveapicnic,liveinthesuburbs,gototheseaside,buyaweekendplaceinthecountry.ThemostpopularleisureactivityinBritainisgoingforawalk.Andwhenjoggers(慢跑者)jog,theydon’trunthestreets.Everyoneoftheminstinctivelyheadstotheparkortheriver.Itismyprofoundbeliefthatnotonlydoweallneednature,butweallseeknature,whetherweknowwearedoingsoornot.Butdespitethis,ourchildrenaregrowingupnature-deprived(丧失).IspentmyboyhoodclimbingtreesonStreathamCommon,SouthLondon.Thesedays,childrenarerobbedoftheseancientfreedoms,duetoproblemslikecrime,traffic,thelossoftheopenspacesandoddnewperceptionsaboutwhatisbestforchildren,thatistosay,thingsthatcanbebought,ratherthanthingsthatcanbefound.Thetruthistobefoundelsewhere.AstudyintheUS:familieshadmovedtobetterhousingandthechildrenwereassessedforADHD—attentiondeficithyperactivitydisorder(多动症).Thosewhoseaccommodationhadmorenaturalviewsshowedanimprovementof19%;thosewhohadthesameimprovementinmaterialsurroundingsbutnoniceviewimprovedjust4%.AstudyinSwedenindicatedthatkindergartenchildrenwhocouldplayinanaturalenvironmenthadlessillnessandgreaterphysicalabilitythanchildrenusedonlytoanormalplayground.AUSstudysuggestedthatwhenaschoolgavechildrenaccesstoanaturalenvironment,academiclevelswereraisedacrosstheentireschool.Anotherstudyfoundthatchildrenplaydifferentlyinanaturalenvironment.Inplaygrounds,childrencreateahierarchy(等级)basedonphysicalabilities,withthetoughonestakingthelead.Butwhenagrassyareawasplantedwithbushes,thechildrengotmuchmoreintofantasyplay,andthesocialhierarchywasnowbasedonimaginationandcreativity.Mostbullying(恃强凌弱)isfoundinschoolswherethereisatarmac(柏油碎石)playground;theleastbullyingisinanaturalareathatthechildrenareencouragedtoexplore.ThisremindsmeunpleasantlyofSunnyhillSchoolinStreatham,withitsharshtarmac,whereIusedtohangaboutincornersfantasisingaboutwildlife.Butchildrenarefrequentlydiscouragedfrominvolvementwithnaturalspaces,forhealthandsafetyreasons,forfearthattheymightgetdirtyorthattheymightcausedamage.So,instead,thedamageisdonetothechildrenthemselves:nottotheirbodiesbuttotheirsouls.OneofthegreatproblemsofmodernchildhoodisADHD,nowincreasinglyandexpensivelytreatedwithdrugs.Yetonestudyafteranotherindicatesthatcontactw