编译原理与实践第三章答案

TheexercisesofChapterThree3.2GiventhegrammarA→AA|(A)|Describethelanguageitgenerates;Showthatitisambiguous.[Solution]:Generatesastringofbalancedparenthesis,includingtheemptystring.parsetreesof():AAAA(A)(A)3.3Giventhegrammarexpexpaddopterm|termaddop+|-termtermmulopfactor|factormulop*factor(exp)|numberWritedownleftmostderivations,parsetrees,andabstractsyntaxtreesforthefollowingexpression:a.3+4*5-6b.3*(4-5+6)c.3-(4+5*6)[Solution]:a.Theleftmostderivationsfortheexpression3+4*5-6:Exp=>expaddopterm=>expaddoptermaddopterm=>termaddoptermaddopterm=>factoraddoptermaddopterm=>3addoptermaddopterm=>3+termaddopterm=>3+termmulopfactoraddopterm=>3+factormulopfactoraddopterm=>3+4mulopfactoraddopterm=>3+4*factoraddopterm=>3+4*5addopterm=>3+4*5-term=>3+4*5-factor=>3+4*5-63.5WriteagrammarforBooleanexpressionsthatincludestheconstantstrueandfalse,theoperatorsand,orandnot,andparentheses.Besuretogiveoralowerprecedencethanandandandalowerprecedencethatnotandtoallowrepeatednot’s,asintheBooleanexpressionnotnottrue.Alsobesreyourgrammarisnotambiguous.[solution]bexp→bexporA|AA→AandB|BB→notB|CC→(bexp)|true|falseEx:notnottrueboolExp→ABnotBnotnotBnotnotCnotnottrue3.8Giventhefollowinggrammarstatement→if-stmt|other|εif-stmt→if(exp)statementelse-partelse-part→elsestatement|εexp→0|1a.Drawaparsetreeforthestringif(0)if(1)otherelseelseotherb.whatisthepurposeofthetwoelse’s?Thetwoelse’sallowtheprogrammertoassociateanelseclausewiththeoutmostelse,whentwoifstatementsarenestedandthefirstdoesnothaveanelseclause.c.IssimilarcodepermissibleinC?Explain.ThegrammarinClookslike:if-stmt→if(exp)statement|if(exp)statementelsestatementthewaytooverride“danglingelse”problemistoenclosetheinnerifstatementin{}s.e.g.if(0){if(1)other}elseother.3.10a.Translatethegrammarofexercise3.6intoEBNF.b.DrawsyntaxdiagrammsfortheEBNFofpart(a).[Solution]a.Theoriginalgrammarlexp→atom|listatom→number|identifierlist→(lexp-seq)lexp-seq→lexp-seqlexp|lexpTheEBNFoftheabovegrammar:lexp→atom|listatom→number|identifierlist→(lexp-seq)lexp-seq→lexp{lexp}b.ThesyntaxdiagrammsfortheaboveEBNF:lexpatomlistatomNUMIDElist(lexp-seq)lexp-seqlexplexp3.12.UnaryminusescanbeaddedinseveralwaystothesimplearithmeticexpressiongrammarofExercise3.3.RevisetheBNFforeachofthecasesthatfollowsothatitsatisfiesthestatedrule.a.Atmostoneunaryminusisallowedineachexpression,anditmustcomeatthebeginningofanexpression,so-2-3islegal(andevaluatesto-5)and-2-(-3)islegal,but-2--3isnot.expexpaddopterm|termaddop+|-termtermmulopfactor|factormulop*factor(exp)|(-exp)|number|b.Atmostoneunaryminusareallowedbeforeanumberorleftparenthesis,so-2--3islegalbut--2and-2---3arenot.expexpaddopterm|termaddop+|-termtermmulopfactor|factormulop*factor(exp)|-(exp)|number|-numberc.Arbitrarilymanyunaryminusesareallowedbeforenumbersandleftparentheses,soeverythingaboveislegal.3.19Insomelanguages(Modula-2andAdaareexamples),aproceduredeclarationisexpectedtobeterminatedbysyntaxthatincludesthenameoftheprocedure.Forexample,inModular-2aprocedureisdeclaredasfollows:PROCEDUREP;BEGIN⋯⋯ENDP;NotetheuseoftheprocedurenamePaltertheclosingEND.Cansucharequirementbecheckedbyaparser?Explain.[Answer]Thisrequirementcannotbehandledaspartofthegrammarwithoutmakinganewruleforeachlegalvariablename,whichmakesitintractableforallpracticalpurposes,evenifvariablenamesarerestrictedtoaveryshortlength.Theparserwilljustcheckthestructure,thatanidentifierfollowsthekeywordPROCEDUREandanidentifieralsofollowsthekeywordEND,howevercheckingthatitisthesameidentifierisleftforsemanticanalysis.Seethediscussiononpages131-132ofyourtext.3.20a.Writearegularexpressionthatgeneratethesamelanguageasthefollowinggrammar:A→aA|B|εB→bB|Ab.Writeagrammarthatgeneratesthesamelanguageasthefollowingregularexpression:(a|c|ba|bc)*(b|ε)[Solution]a.Theregularexpression:(a|b)*b.Thegrammar:Step1:A→BCB→aB|cB|baB|bcB|εC→b|εStep2:A→Bb|BB→aB|cB|baB|bcB|ε