东南大学编译原理期末复习

Review1.StructureofthecourseLexicalAnalysisSyntaxAnalysisGrammar&LanguageRG&DFATop-downLL(1)ParsingBottom-UpPrecedenceandLRLayeredAutomationSemanticAnalysisAttributeGrammarTypeCheckingIntermediateCodegenerationTACQuadruple(Backpatching)CodeOptimizationControl-flowAnalysisData-flowAnalysisRun-timeEnvironmentStackAllocationsReview2.ScopeofreviewingFromChapter2-Chapter9Review3.MethodsofreviewingUnderstandingbasicconcept,principlesdeeplyBeingabletodoexercisesUnderstandingtheprocessbydrawingthegraphortheflowRememberingafterunderstandingReview4.FormsofproblemsintheexaminationpaperSimilartotheexercisesfinishedbyyouWithoutanytheformofchoosinganswersorjudgment

Review5.FormofexaminationClosed(Cannotrefertoanyothermaterials)Review6.ImportantknowledgepointsChapter2ChomskyGrammarandrelatedAutomationConstructacontext-freegrammarwithout-productionfromalanguageAllstringsofa’sandb’swithanevennumberofa’sandanoddnumberofb’sStringsofa’sandb’swithanequalnumberofa’sandb’sEmbeddedgrammarCombinationofregulargrammarandembeddedgrammarPleaseconstructcontext-freegrammarswith-freeproductionforthefollowinglanguage.L={|(a,b,c,d)*andthenumbersofa’sandb’sandd’soccurredinareodd,and

startswitha,endswithb}Review6.ImportantknowledgepointsChapter3ConversionfromNFAtoDFASubsetMethodMinimizingofDFATop-downpartitionofequivalentclassConversionfromRegularexpressiontoNFAandinverseconversionConversionfromRegularGrammartoNFAandinverseconversionConstructaminimum-stateDFAforaregularexpressionPleaseconstructaDFA

withminimumstatesforthefollowingregularexpression.((ab*)(a|b)*)*(a|b)(a|b)*Review6.ImportantknowledgepointsChapter4Top-downParsingRecursivedescentparsingPredictiveparsingLL(1)LL(1)ParsingtableconstructionEliminationofleftrecursionFirstdirect,NextindirectrecursionFactoringFirst&FollowShowaCFGgrammariswhetheraLL(1)grammarbyconstructingtherelatedparsingtablePleaseeliminatetheleftrecursions(ifthereare)andextractmaximumcommonleftfactors(ifthereare)fromthefollowingcontextfreegrammar,andthendecidetheresultedgrammariswhetheraLL(1)grammarbyconstructingtherelatedLL(1)parsingtable.

SifEthenS|ifEthenSelseS|whileEdoS|aEEandF|FFForG|GG(E)|bReview6.ImportantknowledgepointsChapter4Bottom-upParsingLRparsingSLR(1)--FollowLR(1)–PredictivesymbolLALR–MergingstateswiththesamecoreShowaCFGgrammariswhetheraLRgrammarbyconstructingtherelatedparsingtableReview6.ImportantknowledgepointsChapter4AmbiguousGrammarparsingAdditionalconditionsAssociatedlawandprecedenceDanglerulesParsinganambiguousgrammarinLRparsingmethodwithadditionalconditions

PleaseconstructaLR(1)parsingtableforthefollowingambiguousgrammarwithyourowndefinedadditionalconditions(Youdeterminetherequiredadditionalconditionsbyyourself).EEandE|EorE|notE|(E)|bReview6.ImportantknowledgepointsChapter5AttributeAnnotatedparsingtreeConstructanannotatedparsingtreeforanexpression(S-attribute)Syntax-directeddefinitionS-attributeGrammarandevaluationofS-attributeConstructsemanticrulesforaS-attributegrammarPleaseconstructanannotatedparsetreefortheinputstring111.0111wherethesyntax-directeddefinitionisasfollowing:

ProductionsSemanticRulesSL1.L2{S.val=L1.val+L2.val/2L2.len}SL{S.val=L.val}LL1B{L.val=L1.val*2+B.val,L.len=L1.len+1}LB{L.val=B.val,L.len=1}B0{B.val=0}B1{B.val=1}Review6.ImportantknowledgepointsChapter6TypeTypeexpressionConstructatypeexpressionforadeclarationReview6.ImportantknowledgepointsChapter7Stack-basedstorageallocationActivationRecordFormClanguageprogramRecursivefunctionPascallanguageprogramDisplayConstructamaximumstackmapforaCrecursiveprogramWeassumethatthestorageorganizationandtheformofactivationrecordusedinClanguageprogramrun-timestackstorageallocationareasabove.Pleaseconstructtherun-timestackmapwhenitgetsthemaximumsizeforthefollowingCprogram.TheCprogramisasthefollowing:#include<stdio.h>intx,y,z;intmain(){x=35;y=40;z=f(x,y);}intf(intm,intn){if(n>m){intt;t=f(n,m);returnt}elseif(n==0)returnm;else{intt1,t2;t1=m%n;//remainderofm/nt2=f(n,t1);returnt2}}Notes:1)Hereweassumethatthecaller’sspofMainfunctionisthestartaddressofglobalvariabledataarea,andthereturnedaddressintheactivationrecordofafunction(includingMainfunction)isfilledbytheoperatingsystemautomatically,youmightnotcareit.2)TheinitialvalueofvariableXandYare35and40respectively,thestartaddressofstackusedintheprogramisK.Review6.ImportantknowledgepointsChapter8TACQuadrupleBottom-upSyntax-directedProgramTranslationAssignmentstatementwitharrayIfandWhilestatementTranslateaprogramfragmentintoTACorquadrupleusingbottom-upsyntax-directedprogramtranslationmethodPleasetranslatethefollowingprogramfragmentintothreeaddresscode(TAC)sequenceusingshortcircuitcodeandback-patchingtechniques.i=1;m=0;loop=0;while(loop==0&&i<=10){j=1;while(loop==0&&j<=i)if(a[i,j]<>a[j,i])//”<>”means“notequalto”{loop=1;m=1;}elsej=j+1;if(loop==0)i=i+1;}if(loop==1)e=1;elsee=0;Notes:HereweassumethatthedeclarationofarrayAisarray[1..20,1..20],eachdataelementofarrayAwouldonlyuse4storageunit,andthestartaddressofarrayA’sstorageareaisaddrA.Review6.ImportantknowledgepointsChapter9BlockDivisionConstructaflowgraphfromTACstatementssequenceOptimizationinaBlockConstantfoldingCommonsub-expressionCopy-propagationDAGCoderewritingOptimizeablockinDAGmethodandrewritethecodePleaseconstructtheDAGforthefollowingbasicblock,optimizetheblockandrewritetheblockinoptimizedcodeform.NotethatweassumeonlyVariableLwouldbeusedlater.A=B*CD=B/CE=A+DF=2*EG=B*CH=G*GF=H*GL=FM=LReview6.ImportantknowledgepointsChapter9LoopseekingBackedgeCodeMotionReductionofstrengthFindouttheloopinaflowgraphusingdominatorsandbackedgeDataflowanalysisWhyshouldweanalyzethedata-flowofaprogram?Howshouldweanalyzethedata-flowofaprogram?123465789Experiments1.LexicalAnalyzerDefinethesetofRegularExpressionsofthewordsC