(1.1.4)--Samuel's Ch1_2编译原理与实践英文版.ppt

《(1.1.4)--Samuel's Ch1_2编译原理与实践英文版.ppt》由会员分享，可在线阅读，更多相关《(1.1.4)--Samuel's Ch1_2编译原理与实践英文版.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 1 Chapter 1 Introduction Introduction Compilers are computer programs that translate one language to another.Very complex program from 10,000 to 1,000,000 lines of code.Its input is a program written in its source language.It produces an equivalent program written in its target language.Comp

2、ilerS2CompilersCompilersCompilerS3Translation ProcessTranslation ProcessThis is a book.Step 1:lexical analysisThis/is/a/book/.Step 2:syntax analysisThis subjectis predicatea quantifierbook object.endStep 3:semantic analysisThis pronoun 这is copula 是a numeral 一book noun 书.period 。Step 4:This is a book

3、.Step 5:这是一书。Step 6:这是一本书。CompilerS4Translation ProcessTranslation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeLiteral TableSymbol TableError Handler123456Target CodeCompilerS5Translation ProcessTranslation ProcessScannerParserSemantic Anal

4、yzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeLiteral TableSymbol TableError Handler1Reads the source program(stream of characters).Performs lexical analysis:collects sequences of characters into meaningful units called tokens.Example:aindex=4+2 a identifier left bracket ind

5、ex identifier right bracket =assignment 4 number +plus sign 2 numberCompilerS6The ScannerThe ScannerCompilerS7Translation ProcessTranslation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeTokensLiteral TableSymbol TableError Handler2Receives t

6、he source in form of tokens.Performs syntax analysis determines the structure of the program similar to performing grammatical analysis on a sentence in natural language.The result is represented as a parse tree or a syntax tree.CompilerS8The ParserThe ParserCompilerS9Parse TreeParse Tree expression

7、 assign-expression expression expression=subscript-expression additive-expression expression expression expression expression+identifieraidentifierindexnumber 4number 2aindex=4+2CompilerS10Abstract Syntax Tree Abstract Syntax Tree An abstract syntax tree is a condensation of the information containe

8、d in a parse tree.assign-expression subscript-expression additive-expressionidentifieraidentifierindexnumber 4number 2aindex=4+2CompilerS11Translation ProcessTranslation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeTokensSyntax TreeLiteral T

9、ableSymbol TableError Handler3The semantics of a program are its“meaning”.The semantics of a program determine its runtime behavior.Most programming languages have features(called static semantics)that can be determined prior to execution.Typical static semantics featuresDeclarationsType checkingThe

10、 extra information computed by the semantic analyzer are called attributes.They are added to the tree as annotations,or“decorations”CompilerS12The Semantic AnalyzerThe Semantic AnalyzerCompilerS13Abstract Syntax Tree Abstract Syntax Tree An abstract syntax tree is a condensation of the information c

11、ontained in a parse tree.assign-expression subscript-expression additive-expressionidentifieraidentifierindexnumber 4number 2aindex=4+2CompilerS14Abstract Syntax Tree Abstract Syntax Tree assign-expression subscript-expression additive-expressionidentifieraidentifierindexnumber 4number 2aindex=4+2Co

12、mpilerS15Annotated TreeAnnotated Tree assign-expression subscript-expression integer additive-expressioninteger identifieraarray of integeridentifierindexintegernumber 4integernumber 2integeraindex=4+2CompilerS16Translation ProcessTranslation ProcessScannerParserSemantic AnalyzerSource Code Optimize

13、rCode GeneratorTarget Code OptimizerSource CodeTokensSyntax TreeAnnotated TreeLiteral TableSymbol TableError Handler4The earliest point at which optimization steps can be performed is just after semantic analysis.There may be possibilities that depend only on the source code.Compilers exhibit a wide

14、 variation in the kind of optimization and its placement.The output of the source code optimizer is the intermediate representation(IR)or intermediate code.CompilerS17The Source Code OptimizerThe Source Code Optimizer 4+2 can be precomputed by the compiler.This optimization is known as constant fold

15、ing.This optimization can be performed on the annotated syntax tree by collapsing the right hand subtree to its constant value.CompilerS18Example Example assign-expression subscript-expression integer additive-expressioninteger identifieraarray of integeridentifierindexintegernumber 4integernumber 2

16、integer 4+2 can be precomputed by the compiler.This optimization is known as constant folding.This optimization can be performed on the annotated syntax tree by collapsing the right hand subtree to its constant value.CompilerS19Example Example assign-expression subscript-expression integer number6in

17、teger identifieraarray of integeridentifierindexintegerCompilerS20Translation ProcessTranslation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeTokensSyntax TreeAnnotated TreeIntermediate code Literal TableSymbol TableError Handler5The code ge

18、nerator takes the intermediate code or IR and generates code for the target machine.We will write target code in assembly language form.Most compilers generate object code directly.The properties of the target machine become important.Use instructions of the target machine.Data representations:how m

19、any bytes or words integer and floating-point data types occupy in memory.CompilerS21The Code GeneratorThe Code Generator&a is the address of a(the base address of the array)*R1 means indirect register addressing We assumed that the machine performs byte addressing.Integers occupy two bytes of memor

20、y.CompilerS22ExampleExampleMOV 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 R1aindex=4+2aindex=6CompilerS23Translation ProcessTranslation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode Generato

21、rTarget Code OptimizerSource CodeTokensSyntax TreeAnnotated TreeIntermediate code Target CodeLiteral TableSymbol TableError Handler6Improvements include Choosing addressing modes to improve performance.Replacing slow instructions by faster ones.Eliminating redundant or unnecessary operationsExample:

22、CompilerS24The Target Code OptimizerThe Target Code Optimizer MOV R0,index ;value of index-R0 SHL R0 ;double the value in R0 MOV&aR0,6 ;constant 6-address a+R0MOV 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 R

23、1aindex=6CompilerS25Translation ProcessTranslation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeTarget CodeTokensSyntax TreeAnnotated TreeIntermediate code Target CodeLiteral TableSymbol TableError HandlerCompilerS26DebuggersDebuggersEditors

24、EditorsPreprocessorsPreprocessorsLoadersLoadersLinkers Linkers AssemblersAssemblersInterpreters Interpreters Compiler Compiler An interpreter is a language translator like a compiler.The difference:the source program is executed immediately,not after translation is complete.Programming language can

25、be either interpreted or compiled.Interpreted languages:BASIC,LISP,JavaCompiled languages:FORTRAN,C,C+.Interpreters share many operations with compilers.CompilerS27Interpreters Interpreters An assembler is a translator for the assembly language of a particular computer.Assembly language is a symboli

26、c form of the machine language and it is easy to translate.Sometimes,a compiler will generate assembly language as its target language.Then assembler will finish the translation into object code.CompilerS28AssemblersAssemblersA linker collects code separately compiled or assembled in different objec

27、t files into final executable file.Also connects to the code for standard library functions and to resources supplied by OS(memory allocators,I/O devices)A linker was originally one of the principal activities of a compiler.CompilerS29Linkers Linkers In object code the primary memory references are

28、made relative to an undetermined starting location that can be anywhere in memory.Loader will resolve all relocateable addresses to a given starting address.Usually,the loading process is part of OS.CompilerS30LoadersLoadersA preprocessor is a separate program that is called by the compiler before t

29、he translation begins.Preprocessors canDelete commentsInclude other filesPerform macro substitutions A macro is a shorthand description of a repeated sequence of text CompilerS31PreprocessorsPreprocessorsSource programs are written using an editor that produces a standard file(ASCII).Recently,compil

30、ers have been bundled with editors and other programs into an interactive development environment(IDE).Such editors may be oriented towards the format of programming language.Programmer may be informed of errors as the program is written.The compiler can be called from within the editor.CompilerS32E

31、ditorsEditorsA debugger is a program that determines execution errors in a compiled program.It is also packaged in IDE.The debugger keeps track of the source code information such as line numbers,names of variables and procedures.It can halt execution at breakpoint and provide information on called functions and current values of variables.CompilerS33DebuggersDebuggers1.21.2 Given the C assignment ai+1=ai+2 draw a parse tree and a syntax tree for the expression,using the similar example as a guide.CompilerS34HomeworkHomework