编译原理-概述

Chapter1IntroductionInstructorJianhuiYueSoftwareCollege@SCUOffice:JC-B321Outline1Conceptions2CompilerProcessesOverview3SuggestionsonhowtostudythiscourseCompilersCompilersarecomputerprogramsthattranslateonelanguagetoanother.Verycomplexprogramfrom10,000to1,000,000linesofcode.Itsinputisaprogramwritteninitssourcelanguage.Usually,thesourcelanguageisahigh-levellanguage(C,C++,etc).Itproducesanequivalentprogramwritteninitstargetlanguage.Thetargetlanguageisobjectcode

(machinecode)forthetargetmachine.MachineLanguageInitially,theprogramswerewritteninmachinelanguage–numericcodesthatrepresentedtheactualmachineoperationstobeperformed.C70600000002movesnumber2tothelocation0000.Writingsuchcodesistimeconsumingandtedious.AssemblyLanguageInassemblylanguageinstructionsandmemorylocationsaregivensymbolicforms.MOVX,2Anassemblertranslatesthesymboliccodesandmemorylocationsintocorrespondingnumericcodes.Advantages:Greatimprovementinspeedandaccuracyofwritingprograms.stillusedtoday.Disadvantages:Stillnoteasytowriteanddifficulttoreadandunderstand.Machinedependent.High-levelLanguagesNearlyresemblesmathematicalnotationornaturallanguage.Independentonanyparticularmachine.CapableofbeingtranslatedintoexecutablecodeX=2Needaprogramthatperformstranslation.Isitpossible?Isgeneratedobjectcodeefficient?TheoreticalFoundationsNoamChomsky’sstudyofthestructureofnaturallanguages.Classificationoflanguagesaccordingtothecomplexityoftheirgrammarsandthealgorithmstorecognizethem.Context-freegrammarsarethemostusefulforprogramminglanguagesStudyoftheparsingproblem,whichbecomeastandardpartofcompilertheory.Studyoffiniteautomataandregularexpressions.LedtosymbolicmethodsforexpressingthestructureofwordsofaprogramminglanguageOptimizationtechniques

(codeimprovementtechniques).InterpretersAninterpreterisalanguagetranslatorlikeacompiler.Thedifference:thesourceprograminexecutedimmediately,notaftertranslationiscomplete.Programminglanguagecanbeeitherinterpretedorcompiled.Interpretedlanguages:BASIC,LISP,JavaCompiledlanguages:FORTRAN,C,C++.Interpreterssharemanyoperationswithcompilers.AssemblersAnassemblerisatranslatorfortheassemblylanguageofaparticularcomputer.Assemblylanguageisasymbolicformofthemachinelanguageanditiseasytotranslate.Sometimes,acompilerwillgenerateassemblylanguageasitstargetlanguage.Thenassemblerwillfinishthetranslationintoobjectcode.LinkersAlinkercollectscodeseparatelycompiledorassembledindifferentobjectfilesintofinalexecutablefile.AlsoconnectstothecodeforstandardlibraryfunctionsandtoresourcessuppliedbyOS(memoryallocators,I/Odevices)Alinkerwasoriginallyoneoftheprincipalactivitiesofacompiler.LoadersInobjectcodetheprimarymemoryreferencesaremaderelativetoanundeterminedstartinglocationthatcanbeanywhereinmemory.Loaderwillresolveallrelocateableaddressestoagivenstartingaddress.Usually,theloadingprocessispartofOS.PreprocessorsApreprocessorisaseparateprogramthatiscalledbythecompilerbeforethetranslationbegins.PreprocessorscanDeletecommentsIncludeotherfilesPerformmacrosubstitutionsAmacroisashorthanddescriptionofarepeatedsequenceoftextEditorsSourceprogramsarewrittenusinganeditorthatproducesastandardfile(ASCII).Recently,compilershavebeenbundledwitheditorsandotherprogramsintoaninteractivedevelopmentenvironment(IDE).Sucheditorsmaybeorientedtowardstheformatofprogramminglanguage.Programmermaybeinformedoferrorsastheprogramiswritten.Thecompilercanbecalledfromwithintheeditor.DebuggersAdebuggerisaprogramthatdeterminesexecutionerrorsinacompiledprogram.ItisalsopackagedinIDE.Thedebuggerkeepstrackofthesourcecodeinformationsuchaslinenumbers,namesofvariablesandprocedures.Itcanhaltexecutionatbreakpointandprovideinformationoncalledfunctionsandcurrentvaluesofvariables.ItsRoleintheComputerSystemHardwareOSCompilerHighLevelLanguageOtherFacilitiesTranslationProcessScannerParserSemanticAnalyzerSourceCodeOptimizerCodeGeneratorTargetCodeOptimizerSourceCodeTargetCodeTokensSyntaxTreeAnnotatedTreeIntermediatecodeTargetCodeLiteralTableSymbolTableErrorHandlerWhytoStudyit?1ObtaintheKnowledgeaboutCompiler2Writegoodqualityprogramcode3ObtaintheKnowledgeaboutsystemsoftwareconstructiontoimproveprogrammingskills4Learnhowtoapplythetheoriesintosoftwareconstruction(DataStructure,DiscreteMath,FormalLanguageandAutomata,etc)5Layasolidbaseforfutureresearchworkonthecomputerscience(Doseitreallydead?)ItsApplicationCases1EmbeddedSQL2ExtensionstoExistedLanguages3DevelopaDedicatedUsageLanguages(DisplayCardDriverGenerationLanguage,GamedevelopmentLanguage,AILanguage)4ConstructCASEtools(OrientedtoSEresearch)(checksoftwarebug…)5Toreducethegapsbetweenthesoftwareandhardware(OrientedtoCSresearch)TheScannerReadsthesourceprogram(streamofcharacters).Performslexicalanalysis:collectssequencesofcharactersintomeaningfulunitscalledtokens.Example:a[index]=4+2;aidentifier[leftbracket

indexidentifier]rightbracket

=assignment4number

+plussign2numberTheParserReceivesthesourceinformoftokens.Performssyntaxanalysisdeterminesthestructureoftheprogramsimilartoperforminggrammaticalanalysisonasentenceinnaturallanguage.Theresultisrepresentedasaparsetreeorasyntaxtree.ParseTree

expressionassign-expression

expression

expression=

subscript-expression

additive-expression

expression

expression

expression

expression[]+identifieraidentifierindexnumber4number2AbstractSyntaxTreeAnabstractsyntaxtreeisacondensationoftheinformationcontainedinaparsetree.assign-expression

subscript-expression

additive-expressionidentifieraidentifierindexnumber4number2TheSemanticAnalyzerThesemanticsofaprogramareits“meaning〞.Thesemanticsofaprogramdetermineitsruntimebehavior.Mostprogramminglanguageshavefeatures(calledstaticsemantics)thatcanbedeterminedpriortoexecution.TypicalstaticsemanticsfeaturesDeclarationsTypecheckingTheextrainformationcomputedbythesemanticanalyzerarecalledattributes.Theyareaddedtothetreeasannotations,or“decorations〞AnnotatedTreeassign-expression

subscript-expressioninteger

additive-expressionintegeridentifieraarrayofintegeridentifierindexintegernumber4integernumber2integerTheSourceCodeOptimizerTheearliestpointatwhichoptimizationstepscanbeperformedisjustaftersemanticanalysis.Theremaybepossibilitiesthatdependonlyonthesourcecode.Compilersexhibitawidevariationinthekindofoptimizationanditsplacement.Theoutputofthesourcecodeoptimizeristheintermediaterepresentation

(IR)orintermediatecode.Example

4+2canbeprecomputedbythecompiler.Thisoptimizationisknownasconstantfolding.Thisoptimizationcanbeperformedontheannotatedsyntaxtreebycollapsingtherighthandsubtreetoitsconstantvalue.assign-expression

subscript-expressioninteger

number6integeridentifieraarrayofintegeridentifierindexintegerTheCodeGeneratorThecodegeneratortakestheintermediatecodeorIRandgeneratescodeforthetargetmachine.Wewillwritetargetcodeinassemblylanguageform.Mostcompilersgenerateobjectcodedirectly.Thepropertiesofthetargetmachinebecomeimportant.Useinstructionsofthetargetmachine.Datarepresentations:howmanybytesorwordsintegerandfloating-pointdatatypesoccupyinmemory.Example&aistheaddressofa(thebaseaddressofthearray)*R1meansindirectregisteraddressingWeassumedthatthemachineperformsbyteaddressing.Integersoccupytwobytesofmemory.MOVR0,index;;valueofindex->R0MULR0,2;;doublevalueinR0MOVR1,&a;;addressofa->R1ADDR1,R0;;addR0toR1MOV*R1,6;;constant6->addressinR1TheTargetCodeOptimizerImprovementsincludeChoosingaddressingmodestoimproveperformance.Replacingslowinstructionsbyfasterones.EliminatingredundantorunnecessaryoperationsExample:

MOVR0,index;;valueofindex->R0SHLR0;;doublethevalueinR0MOV&a[R0],6;;constant6->addressa+R0MajorDataStructuresinCompilerThereisastronginteractionbetweenthealgorithmsusedbythephasesofacompilerandthedatastructuresthatsupportthesephases.Algorithmsneedtobeimplementedinefficientmanner.ThechoiceofdatastructuresisimportantTokensWhenascannercollectscharactersintoatoken,itrepresentsthetokensymbolicallyasavalueofanenumerateddatatyperepresentingasetoftokensofthesourcelanguageSometimes,itisnecessarytopreservethecharacterstringitselforotherinformationderivedfromitThenameassociatedwithanidentifiertokenThevalueofanumbertokenInmostlanguagesthescannerneedstogenerateonetokenatatime(singlesymbollookahead)Asingleglobalvariablecanbeusedtoholdthetokeninformation.TheSyntaxTreeThesyntaxtreeisconstructedasastandardpointer-basedstructurethatisdynamicallyallocatedasparsingproceeds.Thetreecanbekeptasasinglevariablepointingtotherootnode.Eachnodeisarecord.Itsfieldsrepresenttheinformationcollectedbytheparserandthesemanticanalyzer.SometimesthesefieldsaredynamicallyallocatedTheSymbolTableThisdatastructurekeepsinformationassociatedwithidentifiers:functions,variables,constants,anddatatypes.Thesymboltableinteractswithalmosteveryphaseofthecompiler.Theinsertion,deletionaccessoperationsneedtobeefficient.Astandarddatatypeforthispurposeisthehashtable.TheLiteralTableStoresconstantsandstringsusedintheprogram.Quickinsertionandlookupareessential.Neednotallowdeletions.IntermediateCodeDependingonthekindofintermediatecode,itmaybekeptasAnarrayoftextstringsAtemporarytextfileLinkedlistofstructuresTemporaryFilesComputersdidnotpossessenoughmemoryforanentireprogramtobekeptinmemoryduringcompilation.Thiswassolvedbyusingtemporaryfilestoholdtheproductsofintermediatesteps.Memoryconstrainsarenowmuchsmallerproblem.Occasionally,compilersgenerateintermediatefilesduringsomeofthesteps.PassesAcompileroftenprocessedtheentiresourceprogramseveraltimesbeforegeneratingcode.Theserepetitionsarereferredaspasses.Passesmayormaynotcorrespondtophases.Dependingonthelanguage,acompilermaybeonepass.Efficientcompilation,butnotefficienttargetcode.Examples:PascalandC.Mostcompilerswithoptimizationsusemorethanonepass:ScanningandparsingSemanticanalysisandsource-leveloptimizationCodegenerationandtargetcodeoptimizationLanguageDefinitionThedescriptionofthelexical,syntactic,andsemanticsofaprogramminglanguageiscollectedinalanguagereferencemanual,orlanguagedefinition.Withanewlanguage,alanguagedefinitionandcompilerareoftendevelopedtogether.Morecommonsituationiswhenacompileriswrittenforwell-knownlanguagewhichhasanexitinglanguagedefinition.ErrorHandlingOneofthemostimportantfunctionsofacompiler.Errorscanbedetectedduringalmosteveryphaseofcompilation.Errorreportedbyacompilerarestatic

(orcompile-time)errors.Itisimportanttogeneratemeaningfulerrormessages.ErrorhandlercontainsdifferentoperationsforaspecificcompilerphaseandsituationCompilerLanguageTheimplementation(orhost)languagehastobemachinelanguage.Thiswashowthefirstcompilerswerewritten.Anotherapproachistowritethecompilerinanotherlanguageforwhichacompileralreadyexists.Weneedonlytocompilethenewcompilerusingtheexistingcompilertogetarunningprogram.Whatiftheexistingcompilerrunsonamachinedifferentfromthetargetmachine?Compilationproducesacrosscompiler–acompilerthatgeneratestargetcodeforadifferentmachine.T-DiagramAcompilerwritteninlanguageH(hostlanguage)thattranslateslanguageS(sourcelanguage)intolanguageT(targetlanguage)isdrawnasthefollowingT-diagram:Thisisequivalenttosayingthatthecompilerrunson“machine〞H.Typically,weexpectH=T.thecompilerproducescodeforthesamemachineastheoneonwhichitruns.STHCase1TherearetwocompilersthatrunonthesamemachineH.OnetranslatesfromlanguageAtolanguageB.TheothertranslatesfromlanguageBtolanguageC.Wecancombinethembylettingtheoutputofthefirsttobetheinputtothesecond.TheresultisacompilerfromAtoConmachineH.ABHBCHACH=>Case2WecanuseacompilerMfrom“machine〞Hto“machine〞Ktotranslatetheimplementationlanguageofanothe