(1.1.1)--1Overview.pdf

Compilers TechniquesIntroductionThe position of compilation principle course in computer science and technology:ProgramminglanguageDiscreteMathematicsDatastructureCompilationprinciplesOperatingsystemInformationsystemsE-commerceSystemsoftwareApplicationsoftwareSoftwareengineeringIntroductionGeneral principles and basic implementation methods of compiler construction are introducedTheoretical knowledge:formal language and automata theory,Syntax-directed definition and attribute grammar,typology and type system,principle of program analysis,etcEmphasis on formal description technologyEmphasis on macro understanding of compilation principles and techniques,no distraction from branch algorithms,no bias towards a source language or target machineCourse ContentSignificance of LearningHave a deep understanding of the implementation and design of programming language,understand the theory related to programming language,which plays a foundation role in the macro grasp of programming languageFrom the view of software engineering,compiler is a good example.The concepts and techniques introduced can be applied to general software designApplication and development of compiler technology.Advanced language design,computer architecture optimization(parallel,memory stratification),new computer architecture design,program translation,Tools for improving software development efficiency,highly trusted softwareCourse ContentIntroductionThe compiler can logically be divided into several stagesEach stage transforms the source program from one representation to anotherThis chapter introduces the topic of compiling by describing the various stages of the compilerLexical analyzerSyntax analyzerSemantic analyzerSource programIntermediate-code generatorMachine-independent code optimizerCode generatorMachine-dependent code optimizerTarget-machine codeSymbol tableCompilerOverviewCompilerOverviewSymbol tablepositioninitialrate.123 token flowscharacter streamlexical analysis:source program lexical token stringLexical analyzer id,1 =id,2 +id,3 60 position=initial+rate 60Syntax features of expressionsAny identifier is an expressionAny number is an expressionIf e1 and e2 are all expressions,then e1+e2 e1*e2(e1)are all expressionsExpressionExpressionExpressionIdentifierExpressionExpression(initial)Identifier(rate)Digit(60)*+Parse tree of initial+rate*60 Syntax analysis:lexical token flow syntax phrasesCompilerOverview Syntax tree token flowsSymbol tablepositioninitialrate.123CompilerOverviewSyntax analyzerid,1=id,2+id,3 60=+60id,1id,2id,3Symbol table position initial rate.123 Syntax tree Syntax tree Semantic analysis:checking the semantic correctness of a program,such as type checking CompilerOverviewSemantic analyzer=+60id,1id,2id,3=+inttofloatid,1id,2id,360 grammar treeSymbol tablepositioninitialrate.123 Three-address intermediate codeCompilerOverviewIntermediate-code generatort1=inttofloat(60)t2=id3 t1t3=id2+t2id1=t3=+inttofloatid,1id,2id,360Three-address intermediate codeSymbol tablepositioninitialrate.123Three-address intermediate codeCompilerOverviewCode optimizert1=inttofloat(60)t2=id3 t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t1 Assembly codeThree-address intermediate codeSymbol tablepositioninitialrate.123CompilerOverviewCode generatorMOVF id3,R2MULF#60.0,R2MOVF id2,R1ADDF R2,R1MOVF R1,id1t1=id3*60.0id1=id2+t1Lexical analyzerSyntax analyzerSemantic analyzerSource programIntermediate-code generatorMachine-independent code optimizerCode generatorMachine-dependent code optimizerTarget-machine codeSymbol tableCompilerOverviewDifference between an interpreter and a compilerInstead of generating the target code,the interpreter directly performs operations specified by the source program.The interpreter also needs lexical,syntax,and semantic analysis of the source program,and intermediate-code generationBASIC era interpreterFunction:It translates the source program of a high-level language into an intermediate language program and then interprets and executes it.At that time,the functions of compiling and interpreting were combined in a program called the interpreterJava era interpreterThe above two functions of the interpreter are divided into two programsThe former is called a compiler,which translates the source program into an intermediate language prmgram called bytecodeThe latter is called the interpreter,which interprets bytecode programsCompilerOverviewLexical analyzerSyntax analyzerSemantic analyzerSource programIntermediate-code generatorMachine-independent code optimizerCode generatorMachine-dependent code optimizerTarget-machine codeCompilerOverviewPhase groupingFront endBack endFront end:dependent on the source language,independent of the target machine.Back end:dependent on the target machine,independent of the source language.Front end andBack endThe compilation process is divided into front-end and back-end.Front end:dependent on source only,independent of target machine(generating intermediate code)Take the front end of a compiler and rewrite its back end to produce the compiler of same source language on another machineDifferent front ends use the same back end to get several compilers on one machine(using the same intermediate language)Backend:Dependent on the target machine,independent of the source program,only related to the intermediate language(Generate target code from intermediate code)Benefits:Increased efficiency in developing compilersIntroductionSource program Target Machine 1Target Machine 2Target Machine 3Target machine nCompilerCompiler that do not distinguish between front end and back end Source program Target Machine 1Target Machine 2Target Machine 3Compilers front endCompilers back end Compilers that distinguish between front end and back end Target machine nIntroductionLexical analyzerSyntax analyzerSemantic analyzerSource programIntermediate-code generatorMachine-independent code optimizerCode generatorMachine-dependent code optimizerTarget-machine codePhase grouping PassA pass scan is commonly used in several stages of compilation.A scan includes reading an input file and writing an output file.IntroductionPass:One pass:refers to the whole process that the compiler scans the source program or the equivalent of the source program(intermediate program)from the beginning to the end at the time of compilation and converts it into another adjacent equivalentSingle pass scan and multi pass scan:each scan can complete one or more of the above stages.The input of each pass is the output of the previous one,the input of the first pass is the text of the source program,and output of the last pass is object code.Comparison of single and multiple pass:More passes:compiler structure is clear,but time efficiency is not highFewer passes:fast compilation,but high memory requirements for machinesNumber of passes determination:the main factor is the source program and machine(target machine)characteristics.IntroductionTools for improving the efficiency of software developmentType checking:Type checking is a mature and effective technique to capture inconsistencies in programs.Boundary check:Data flow analysis technology can be used to locate buffer overflow.Memory management:Automatic memory management deletion,memory leakage and other memory management errors.Program analysis derived from code optimization techniques in compilers has been improving software development efficiency.Application of Compiler TechnologySyntax-directed structured editor Program formatting toolsSoftware testing toolsProgram understanding toolsTranslation tools for high-level languagesetc.Application of Compiler TechnologyCompilers TechniquesIntroduction