《《编译系统》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编译系统》PPT课件.ppt（55页珍藏版）》请在三一办公上搜索。
1、1,Compiler Construction編譯系統,朱治平成功大學資訊工程系,A compiler is an executable program that can read a program in one high-level language and translate it into an equivalent executable program in machine language.,Compiler,program in high-level language,output,Executable programin machine language,executable
2、program in machine language,input,Definition,3,Textbook:Compiler Construction Principle and Practice-authored by Kenneth C.Louden Reference book:Lex&yacc-by John R.Levine,Tony Mason&Doug Brown OReilly&Associates,Inc.,4,Web Site,資工系 軟體發展實驗室網頁,5,Grading,Homework(25%)-Programming(lex,yacc,semantic acti
3、ons)-Hand-written Assignments(3)Midterm Exam(25%)Final Exam(25%)Final Project(25%),6,Prerequisites,Data StructuresDiscrete MathematicsProgramming LanguagesComputer ArchitecturesAssembly LanguagesFinite Automata(helpful),7,Chapter 1,Introduction,8,Compiler,Source program,Target program,9,The progress
4、ion of programming languages:,Machine language c7 06 0000 0002Assembly language mov x 2High-level language x=2*The first compiler was developed by the team at IBM led by John Backus between 1954 and 1957.,10,Why do we need to learn compilers?,(1)for new platforms(2)for new languages-language extensi
5、ons&improvement-specification languages-4th generation languages(3)foundation of parallelizing compilers&related tools,11,(4)theories learned are applicable to other fieldse.g.,silicon compiler,prototyping tools,database languages,text formatter,FSM(Finite State Machine)translator,query interpreter,
6、command interpreter,interface programs,etc.(5)for improving capabilities of existing compiler/interpreter,12,Silicon compiler,Source language:conventional programming languageVariables Represents not the location but logical signals(0 or 1)or groups of signals in a switching circuit.Output:circuit d
7、esign in an appropriate language,Programs Related to Compilers,Interpreters AssemblersLinkersLoadersPreprocessorsEditorsDebuggersProfilersProject Managers,preprocessor,compiler,assembler,linker/loader,source program,modified source program,target assembly program,relocatable machine code,target mach
8、ine code,Libraryfiles,14,Definitions of Languages,-Source language-Target language-Implementation language,15,Translator,A program,written in the implementation language,that takes sentences(strings)in the source language and outputs equivalent sentences(strings)in the target language.e.g.-preproces
9、sor,pretty printer,fortran2c,pascal2c(high to high)assembler(low to lower)disassembler(lower to low)-compiler(high to low),16,1.Self-compiling Compiler Source and implementation languages are the same.2.Self-resident Compiler Implementation and object languages are the same.3.Cross compiler A compil
10、er that runs on one machine and produces object code for another machine.,Category of compilers,17,Interpreter,-Def.An interpreter performs the operations implied by the source program.-Interpretation system lowest level low middle high,Interpreter,Sourceprogram,input,output,18,A hybrid compiler,Sou
11、rce program,Translator,Intermediate program,Input,VirtualMachine,Output,19,What are the differences between Interpreter and compiler”?,portabilityexecution speedwith/without object codewith/without optimizationdebugging capability,20,The Analysis-Synthesis Model of Compilation,There are two parts to
12、 compilation:analysis&synthesis.During analysis,the operations implied by the source program are determined and recorded in a hierarchical structure called a tree.During synthesis,the operations involved in producing translated code.,21,The Front-end and Back-end Model of Compilation,Source Intermed
13、iate Target Code Code Code,Front End,Back End,Compiling Process&Compiler Structure,Source code(Stream of chars),preprocessor,scanner,parser,Code optimizer/intermediate code generator,Advanced code optimizer,code generator,peephole optimizer,semantic analyzer,Target Code,23,Compiler Structure(continu
14、ed),Literal Table,Error Handler,Symbol Table,COMPILER,24,Preprocessor(or Character handler),throw away the commentscompress multiple blank charactersinclude files(include nested files)perform macro expansions(nested macro expansion)-a macro facility is a text replacement capability(two aspects:defin
15、ition&use).-a macro statement will be expanded into a set of programming language statements or other piler option(conditional compilation)(These jobs may be conducted by lexical analyzer.),25,Scanner(Lexical Analyzer),To identify lexical(語彙)structureInput:a stream of chars;Output:a stream of tokens
16、.A scanner may also enter identifiers into the symbol table and enter literals into literal table.(literals include numeric constants such as 3.1415926535 and quoted strings such as“Hello,world!”).,26,An Example:aindex=4+2;,(1)Output of the Scanner:a=identifier=left bracketindex=identifier=right bra
17、cket=assignment=number+=plus sign=number;=semicolon,27,How tokens(string of chars)are formed from underlying character set?,Usually specified(described)by sequence of regular expression.Lexical structures are analyzed via finite state automata.But it has the look-ahead requirement.(To recognize a to
18、ken the scanner may need to look more characters ahead of the token.),Parser(Syntax Analyzer),To identify syntax structure Input:a stream of tokens Output:On a logical level,some representation of a parse tree.Determine how do the tokens fit together to make up the various syntax entity of a program
19、.*Most compilers do not generate a parse tree explicitly but rather go to intermediate code directly as syntax analysis takes place.Usually specified via context free grammar.Syntax structures are analyzed by DPDA(Deterministic Push Down Automata),(2)Output of the parser parse tree(logical level),st
20、ructure names,tokens,30,Predefined context-free grammar,expression assign-expression|subscript-expression|additive-expression|identifier|numberassign-expression expression=expressionsubscript-expression expression expression additive-expression expression+expression,(2)Output of the parser Abstract
21、Syntax Tree(condensed parse tree),=,+,32,Semantic Analyzer,=Semantic Structure-What is the program supposed to do?-Semantics analysis can be done during syntax analysis phase or intermediate code generator phase or the final code generator.-typical static semantic features include declarations and t
22、ype checking.-information(attributes)gathered can be either added to the tree as annotations or entered into the symbol table.,(3)Output of the semantic analyzer annotated AST,with subscripts from a range,(3)Output of the semantic analyzer(contd)-finds the consistence of data type among a,index,and
23、2+4,or-declares a type dismatch error if not.,35,The time ratio for scanning,parsing,and semantic processing is 30:25:45.,36,Source Code Optimizer,(4)Output of the Source Code Optimizer,with subscripts from a range,38,Intermediate Code Generator,Transform the parse tree(logical level)into an interme
24、diate language representation,e.g.,three address code:A=B op C(op is a binary operator)Difference between intermediate code and assembly code-Specify the registers to be used for each operation in assembly codeActually intermediate code can be represented as any internal representation such as the s
25、yntax tree.,(4)Output of the intermediate code generator:intermediate code(three address code,two address code,P-code,etc.),Three address code temp=6 a index=6 a index=temp Quadruple:(in implementation),=,=,a,index,temp,temp,6,operator,8,12,33,15,#6,27,33,(logical),(reality),12,15,27,#6,a,index,temp
26、,15,.,.,27,.,.,33,(symbol table),location1,location2,location3,40,Advanced Code Optimizer,Detection of undefined variablesDetection of loop invariant computationConstant foldingRemoval of induction variablesElimination of common expression,Induction Variable Elimination,-When there are two or more i
27、nduction variables in a loop we have opportunity to get rid of all but one.I=1 T=0Repeat Repeat T=4*I=T=T+4 X=Y T X=Y T Prod=Prod+X Prod=Prod+X I=I+1 Until T 76Until I 20,Remove I,*Suppose I is not needed after the loop terminates,42,Elimination of common expression,A=B+C+DE=B+C+Fmight be T=B+C A=T+
28、D E=T+F,43,Code Generator,44,(5)Output of the code generator,Mov R0,index/value of index-R0Mul R0,2/double value in R0Mov R1,&a/address of a-R1Add R1,R0/add R0 to R1Mov*R1,6/constant 6-address in R1,45,(Machine-dependent)Peephole Optimizer,A simple but effective technique for locally improving the t
29、arget code.Examine a short sequence of target instruction(called peephole)and replacing these instruction by a shorter or faster sequence whenever possible.e.g.redundant instruction elimination flow-of-control optimization algebraic simplification use of machine idioms,46,(6)Output of the peephole o
30、ptimizer,Mov R0,index/value of index-R0Shl R0/double value in R0Mov&aR0,6/constant 6-address a+R0,47,Error Handling(Detection&Reporting),An important function of the compiler.Errors can be encountered by all of the phases of a compiler.The error messages should be reported to allow the programmer to
31、 determine where the errors have occurred.Once the error has been noted the compiler must modify the input to allow the latter phases can continue processing.,Phase ExampleLexical Analyzer A token is misspelled.Syntax Analyzer A syntax entity is unable to be inferred.Semantic analyzer An operator wh
32、ose operands have incompatible/Intermediate Code types.GeneratorCode Optimizer Certain statements can never be reached.Code Generator A compiler-created constant is too large to fit in a word of the target machineSymbol Table An identifier that has been multiply declared Management with contradictor
33、y attribute.,49,Major Data Structures in a Compiler,Token=a valueThe Syntax Tree=pointer-based structureThe Symbol Table=hash table/an array of struct/The Literal Table=an array of struct Intermediate Code=Quadruple(an array of struct)Temporary Files,Developing the first compiler,Suppose that we hav
34、e a self-compiling C compiler for Sun Sparc 2.Suppose we also have an inefficient self-resident C compiler for Sun Sparc 2.How can we get an efficient self-resident C compiler for Sun Sparc 2?C Sun C Sun C Sun C Sun Sun dirty inefficient C Sun C Sun C Sun C Sun Sun inefficient efficient,Porting a co
35、mpiler for a new machine,Suppose that you have a self-compiling C compiler for Sun Sparc 2.Suppose you also have a self-resident C compiler for IBM AS400.How can we get a self-resident C compiler for Sun Sparc 2?C Sun C As C Sun C As As cross compiler C Sun C Sun C Sun C As Sun cross compiler,Extend
36、ing a language and developing its corresponding compiler,Suppose you have both self-compiling and self-resident C compilers for Sun Sparc 2.If you want to extend the C language to become C+with some new features.How do you get the self-compiling and self-resident C+compilers for Sun Sparc 2?C+Sun C
37、Sun C+Sun C Sun Sun C+Sun C+Sun C+Sun C+Sun Sun,Improving an existing compiler,Suppose you have a good self-resident C compiler for IBM AS400.Now you want to develop a enhanced version of C compiler with excellent optimizing capabilities for IBM AS400.How do you do it?C As C As C As C As As C As C As C As C As As,55,
