B138编译程序概论课件.ppt

1、 1 1.1 1.2 1.3 1.4 (syntax)(semantics)(),COBOLCOmmon Business Oriented Language1960,(CODASYL)1968 1974 ANSI COBOL FORTRANFORmula TRANslation1960,J.Backus 1977 FORTRAN77 ALGOLALGOrithmic LanguageALGOL68-1968 IFIP WG2.1 Pascal1970,N.Wirth -,C1974 D.Ritchie UNIX 1988 ANSI C C+Ada1980 :reliability,simpl

2、icity,modularity,efficiency:package,generic features,multi-taskingreal-time application C+1983 B.Stroustrup OOPL:class,inheritance,polymorphismJava1996 Sun MicroSystems James Gosling OOPL,Exception processing()&Multithread Internet&Distributed Environment 5th :Independent Platform of OS&H/WC#2000 Mi

3、crosoft John Gough.NET Platform OOPL(Object-Oriented Prog.Lang.).NET Framework,JIT(Just In-Time Compilation)high Expressiveness&Simplicity C+VB,JAVA VB user interface,C+,JAVA component S/W Compiler A compiler is a computer program which translates programs written in a particular high-level programm

4、ing language into executable code for a specific target computerSource programSource programObjectprogramObjectprogramError messageLinkageEditorExecutableprogramExecutableprogramCompilerLibrarySource programwith macroSource programRelocatable machine codeAbsolute machine codeLibraryPreprocessorCompi

5、lerassemblerLinkage EditorObject program(as assembly code)(Cross-Compiler)(PreProcessor)(Assembler)(Interpreter)(Compiler)Cross-Compiler C program in WorkstationObject Code for PC CompileCrossCompile-:assembler ,Compiler :Operational System Interpreter:Developing or Educational System InterpreterInt

6、erpreterSource Program Macro substitution#define PI 3.141592Conditional compilation-#IF SUB100.Inclusion of files-#include PreprocessorPreprocessorPreprocessorTranslatorSource ProgramTarget Programs SourceProgramFront-EndFront-EndobjectProgramBack-EndBack-EndFront-End language dependent partBack-End

7、 machine dependent partI.C.:Intermediate CodeO.C.:Optimized Code Lexical AnalyzerSyntax AnalyzerSemantic AnalyzerImmediate Code GenerationCode OptimizationCode GenerationSymbolTableErrorHandlerSource ProgramObject ProgramFrontEndBackEnd1.Lexical Analyzer(Scanner).ex)if(a 10).Token :if (a 10 ).Token

8、Number:32 7 4 25 5 8 2.Syntax Analyzer(Parser):Syntax checking,syntax Tree generation.:incorrect-error message correct -program structure(tree)ex)if(a 10)a=1;if =a 10 a 13.Intermediate Code Generator ex)if(a 10)a=1.0;/a semantic error!ex)a=b+1;Tree:=a +b 1 Ucode:lod R1 b ldc R1 add store R1 a 4.Code

9、 OptimizerOptional phase()code code .Meaning of optimizationmajor part:improve running timeminor part:reduce code size ex)LDC R1,1 LDC R1,1 (x)Criteria for optimizationpreserve the program meaningsspeed up on averagebe worth the effortLocal optimizationlocal inspection inefficient code efficient cod

10、e .1.Constant folding 2.Eliminating redundant load,store instructions 3.Algebraic simplification 4.Strength reductionGlobal optimizationflow analysis technique 1.Common subexpression 2.Moving loop invariants 3.Removing unreachable codes5.Target Code Generator machine instruction.Code generator tasks

11、1.instruction selection&generation2.register management3.storage allocation4.code optimization(Machine-dependent optimization)6.Error Recovery Error recovery -error Error repair -error Error HandlingError detectionError recoveryError reportingError repairErrorSyntax ErrorSemantic ErrorRun-time Error

12、 “?”.()().:Analysis()vs.Synthesis()Analysis q ()q (Syntax tree)q :w=x+y*10w=+xy*10 q q MS Office q comment q q :()No Operationq Type check:()Undefined Symbol,type mismatching q()type checking q -(Lexical Analysis)-Symbol,-token stream :)x=y+10;q -(Syntax analysis)-token -q -Type check v Scanning :sc

13、an token v :.,1):-,2):-,v White space:blank,tab,new line v :position=initial+rate*60 /v :v token v :.v :)exp id|num|exp op exp Stmt id=exp if(exp)then Stmt if(exp)then Stmt else Stmt .op +|-|*|/|.v (),()()(),begin-end Syntax 的=position+initial*rate60Semantic 的=position+initial*rate60inttoreal v v ty

14、pe Parse tree v Key Focus:Type Checking 1),Symbol Table 2)Type Checking ):5+4.5v Compiler :identifier v identifier 1),type,(,),Scope 2)/type,/type/passing,v Symbol Table 1)field record 2)Hashing 3)type binding Scope RuleLife Timev -.v :)-:-:()-:/Syntax AnalyzerImmediate CodeGenerationCode Generation

15、Lexical Analyzer=id1+id2*id360Semantic Analyzerid1=id2+id3*60=id1+id2*id360Inttorealtemp1=inttoreal(60)temp2=id3*temp1 temp3=id2+temp2 id1 =temp3Code Optimizationtemp1=id3*60.0 id1 =id2+temp1 Mov ax,id3Mul ax,60.0Mov bx,id2Add ax,bxMov id1,axv ,.v -Object code v (control flow),.v :smaller&faster v :

16、Pre-code vs.Post-codev :Local Optimization vs.Global Optimization,-Local :(),/,-Global :Flow analysis .,Loop Unreachable code v Peep-hole:,control flow Algebraic,RISC v Relocatable Machine Code Assembly Code -)add ax,k 10001010 v :,:vs.push dx mov wordptrbx+di,1234h mov ax,2 mov bx,5678h mov ax,bx .

17、0000 52 0001 C741021234 0006 B80002 0009 BB5678 000C 8BC3 .v :binary code op-code,register,symbol,Etc.symbol )MOV a,R1 ADD 2,R1 MOV R1,b v Two-Pass Assembly 1)1st Pass:()Symbol Table 2)2nd Pass:Symbol :a0b40001 01 00 00000000 *0011 01 10 00000010 0010 01 00 00000100 *Loader&Link Editorv Loader:(,Lin

18、king loader,Linking editor)-:v Link Editor -+()v front-end vs.Back-end -dependent on source program&independent on machine -,symbol table,error handling,()-dependent on machine&immediate code -independent on source program -,symbol table,error handlingv Pass -:,-token ()v Pass -token.-.-Goto forward

19、 jump jump address -forward jump :Back-patching Goto there /there there:mov x,R1 /there there back-patch.Abstract Syntax Tree forposition=initial+rate*60Assignment statementidposition=expression+expressioninitialidexpression*expressionrateidexpression60numCompiler Generating Tools(=Compiler-Compiler

20、,Translator Writing System)Language machine compiler.:.N language M N*M .ex)2 language:C,Ada 3 Machine :IBM,SPARC,Pentium C-to-IBM,C-to-SPARC,C-to-Pentium Java-to-IBM,Java-to-SPARC,Java-to-PentiumCompiler-compiler ModelLanguage description grammar theory ,Machine description .HDL:Hardware Descriptio

21、n Language Computer Architecture design .Machine architecture programming language automatic compiler generation.1.Lexical Analyzer GeneratorLEX:1975 M.E.Lesk .2.Parser Generator(PGS:Parser Generating System)(1)Stanford PGSJohn Hennessy :5000 lines:AST .Output:Abstract Syntax Tree(AST).(2)Wisconsin

22、PGSC.N.Fisher .:10000 lines:error recovery (3)YACC(Yet Another Compiler Compiler)UNIX.C language .3.Automatic Code Generation Three aspects1.Machine Description:ISP,ISPS,HDL2.Intermediate language3.Code generating algorithmCGAPattern matching code generationTable driven code generation4.Compiler Com

23、piler System (1)PQCC(Production Quality Compiler Compiler System)W.A.Wulf(Carnegie-Mellon University)input language description target machine description PQC(Production Quality Compiler)table output.tree TCOL.Pattern Matching Code Generation code.(2)ACK(Amsterdam Compiler Kit)Vrije Andrew S.Tanenbaum Compiler Back-End .UNCOL .EM Abstract Machine Code .Portable Compiler .