編譯原理英文版課件：Chapter1 INTRODUCTION

1、ContentINTRODUCTIONSCANNINGCONTEXT-FREE GRMMARS AND PARSINGTOP-DOWN PARSINGBOTTOM-UP PARSINGSEMANTIC ANALYSISRUNTIME ENVIRONMENTCODE GENERATION1. INTRODUCTIONWhat is a compiler?Compiler is a computer program translates one language to anotherSource language: the input of a compiler, usually high-lev

2、el language (such as C, C+)Target language: the output of a compiler, usually object code for the target machine (such as machine instruction or assembly code) CompilerSourceProgramTargetProgramWhat is a compiler?A compiler is a complex programFrom 10,000 to 1,000,000 lines of codesCompilers are use

3、d in many forms of computinge.g. Command interpretersMain Topics 1.1 Why Compilers? A Brief History Open1.2 Programs Related to Compilers Open1.3 The Translation Process Open1.4 Major Data Structures in a Compiler Open1.5 Other Issues in Compiler Structure Open1.1 Why? A Brief HistoryWhy CompilerThe

4、 development of programming languageMachine languageAssembly languageHigh-level languageWhy CompilerWriting machine language-numeric codes is time consuming and tediousC706 0000 0002Assembly language greatly improves the speed and accuracyMov x, 2 The assembly language has a number of defectsNot eas

5、y to writeDependent on the particular machaineWhy CompilerHigh-level languagex=2a concise form more resembling mathematical notation or natural languageindependent of any particular machineWhy CompilerComputer can only execute the code written in the machine instructions of the computer. For high-le

6、vel programs to be used, there must have a program to translate high-level programs to machine codesBrief History of CompilerThe first compiler was developed between 1954 and 1957The FORTRAN language and its compiler by a team at IBM led by John BackusThe structure of natural language was studied at

7、 about the same time by Noam ChomskyBrief History of CompilerThe related theories and algorithms in the 1960s and 1970sChomsky hierarchyThe classification of language according to the complexity of their grammargrammar: the rules specifying the structure of languagesThe parsing problem was pursued a

8、nd led to fairly complete solution: parsing problem: determine the structure of langagesContext-free language, parsing algorithmsBrief History of CompilerThe related theories and algorithms in the 1960s and 1970sThe symbolic methods for expressing the structure of the words of a programming language

9、: Finite automata, Regular expressionsMethods have been developed for generating efficient object code: Optimization techniques or code improvement techniquesBrief History of CompilerPrograms were developed to automate the complier development for parsingParser generators,such as Yacc by Steve Johns

10、on in 1975 for the Unix systemScanner generators, such as Lex by Mike Lesk for Unix system about same time Brief History of CompilerProjects focused on automating the generation of other parts of a compilerCode generation was undertaken during the late 1970s and early 1980sLess successful due to the

11、 complex nature of the operations and our less than perfect understanding of themBrief History of CompilerRecent advances in compiler designMore sophisticated algorithms for inferring and/or simplifying the information contained in programWindow-based Interactive Development Environment, IDE, that i

12、ncludes editors, linkers, debuggers, and project managers.However, the basic of compiler design have not changed much in the last 20 years.BACK1.2 Programs related to CompilerInterpretersInterpreter and CompilerThe same point: They are both language implementing systemDifferences:Interpreter execute

13、s the source program during translationCompiler generates object code that is executed after translation completesInterpretersExecute the source program immediately rather than generating object codeinterpreterInterpreter and CompilercompilerSource languageSource languagedataresultObject languageInt

14、erpretersAn interpreter may be preferred to a compiler depending on the language in use and the situation under which translation occursExamples: BASIC, LISP are interpreted Speed of execution is slower than compiled code by a factor of 10 or moreShare many of their operations with compilersSource p

15、rogram preprocessorSource programcompilerAssembly language programassemblerRelocatable machine codeloader/linkerAbsolute machine codeRelocatable object filesThe complete process of high-level programming languagePreprocessorsDelete comments, include other files, and perform macro substitutionsRequir

16、ed by a language (as in C) or can be later add-ons that provide additional facilitiesAssemblersA translator for the assembly language of a particular computerAssembly language is a symbolic form of one machine languageA compiler may generate assembly language as its target language and an assembler

17、finished the translation into object codeLoadersRelocatable code: memory references are relative to an undetermined starting location that can be anywhere in memory.Resolve all re-locatable address relative to a given baseMake executable code more flexibleLinkersCollect separate object files into a

18、directly executable fileConnect an object program to the code for standard library functions and to resource supplied by OSBACK1.3 The Translation ProcessThe phases of a compilerSix phasesScannerParserSemantic AnalyzerSource code optimizerCode generatorTarget Code OptimizerThree auxiliary components

19、Literal tableSymbol tableError HandlerA compiler consists of a number of phases, each performs distinct logical operationsThe Phases of a CompilerScannerParserSemantics AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerLiteralTableSymbolTableErrorHandlerSource codeSyntax TreeAnnotated

20、TreeIntermediate codeTarget codeTarget codeTokensThe ScannerScanner performs lexical analysis (the structure of the words)The Task of scanner:it reads the source program as a file of characters and collects sequences of characters into meaningful units called tokensInput: source program which is a s

21、tream of charactersOutput: tokensThe ScannerTokenEach token is a sequence of characters that represents a unit of information in the source program.Exampleaindex=4+2aindex=4+2Source program in fileToken stream after lexical analysis a identifierleft bracketindex identifierright bracket=assignment4nu

22、mber+plus sign2numberQuestionWrite down the tokens recognized from the following source program: const int x=4;Answer:const: keyword; int: keyword; x: identifier; =: equal;4: number;: semicolon;The ScannerOther operations: it may enter literals into the literal table, literals includeNumeric constan

23、ts (3.14)Quoted string of text (“hello”)RETURNThe ParserParser performs syntax analysisTask of parserThe parser receives the source code in the form of tokens from the scanner and performs the syntax analysis, which determines the structure of the programInput: stream of tokensOutput: parse tree or

24、syntax treeThe Parse TreeParse tree is a useful aid to visualizing the syntax of a program or program elementInternal nodes are labeled by the names of the structures they representLeaves represent the sequence of tokens from the inputThe Parse Tree for aindex=4+2The Syntax TreeA condensation of the

25、 information contained in the parse treeAlso called abstract syntax trees, since they represent a further abstraction from parse treesThe Syntax Tree for aindex=4+2 a index 4 2identifier identifier number number subscript-expression additive-expressionAssign-expressionRETURNQuestionDraw the abstract

26、 syntax tree for ai+1=ai+2Example: a index 4 2identifier identifier number number subscript-expression additive-expressionAssign-expressionSolutionDraw the abstract syntax tree for ai+1=ai+2The Semantic AnalyzerThe semantics of a program are its “meaning”, as opposed to its syntax, or structure, tha

27、t includes: Static semantic: properties of a program that can be determined prior to executionDynamic semantic: properties of a program that can only be determined by executionThe Semantic AnalyzerTask of Semantic Analyzer Analyze static semanticDetermines some of its running time behaviors prior to

28、 executionStatic semantics: declarations and type checkingThe Semantic AnalyzerSemantic Analysis for expression aindex=4+2 includes:Whether identifiers a and “index” have been declared?Whether the type of a is an array？ Whether the type of “index” is an integer?Whether the left and right side of ass

29、ignment have the same type?Whether the two operands of additive operation have the same type?The Semantic AnalyzerAttributes: The extra pieces of information computed by semantic analyzerSemantic analyzer will produce an annotated tree. Attributes are added to the tree as annotationsAn example: aind

30、ex=4+2The syntax tree annotated with attributesThe Annotated Syntax Tree a index 4 2identifier identifier number number subscript-expression additive-expression integer integerAssign-expressionarray of integer integer integer integerRETURNThe Source Code OptimizerThe earliest point of most optimizat

31、ion steps is just after semantic analysisThe code improvement depends only on the source code, and as a separate phaseSome optimizations can be performed directly on the syntax treeIt is easier to optimize using Intermediate CodeIndividual compilers exhibit a wide variation in optimization kinds as

32、well as placementThe Source Code OptimizerAn example: aindex=4+2Constant folding performed directly on annotated treeUsing intermediate code: three-address code, p-codeOptimizations on Annotated Tree a index 4 2identifier identifier number number subscript-expression additive-expression integer inte

33、gerAssign-expressionarray of integer integer integer integerOptimizations on Annotated Tree a index 6identifier identifier number subscript-expression integer Assign-expression array of integer integer integerOptimization on Intermediate CodeIntermediate CodeA form of code representation intermediat

34、e between source code and object codeIntermediate codes have the following properties: structure is simple, meaning is clear, and it is easy to translate them to object code For exampleThree-address code: it contains the addresses of three locations in memoryOptimization on Intermediate Codet = 4 +

35、2aindex=tt = 6aindex=taindex=6RETURNThree-address code for aindex=4+2three-address code after optimizationThe Code GeneratorIt takes the intermediate code or IR and generates code for target machineIR (Intermediate Representation)Any internal representation for the source code used by the compiler i

36、s called IRThe syntax tree and intermediate code are all IRThe Code GeneratorThe properties of the target machine become the major factor: Instructions exsit on the target machinerepresentation of data: how many beytes integer data type occupies in memoryThe number of registersAddressing modeAn exam

37、ple: aindex=4+2Code sequence in a hypothetical assembly languageA possible code sequenceaindex=6MOV R0, indexMUL R0,2MOV R1,&aADD R1,R0MOV *R1,6RETURNConventions on the target machine:An integer occupies two bytes of memory&a is the address of a*R means indirect register addressingThe Target Code Op

38、timizerIt improves the target code generated by the code generator, saving execution time and memory space.This Optimization includes:Change addressing mode to improve performance Instructions replacing Redundant eliminatingThe Target Code OptimizerMOV R0,indexMUL R0,2MOV R1,&aADD R1,R0MOV *R1,6BACK

39、MOV R0,indexSHL R0MOV &aR0,6Using a shift instruction to replace the multiplicationUsing indexed addressing to perform the array store1.4 Major Data Structure in a CompilerAuxiliary Components of Compiler PhasesThe Literal TableStores constants and strings used in a programReducing size of program i

40、n memory by allowing the reuse of constants and stringsQuick insertion and lookup are essentialAuxiliary Components of Compiler PhasesThe Symbol TableKeeps information associated with identifiers: function, variable, constants, and data typesInteracts with almost every phase of compilerScanner, pars

41、er or semantic analyzer may enter identifiers and information into the tableThe optimization and code generation will use the information provided by the symbol tableAuxiliary Components of Compiler PhasesError handlerStatic (or compile-time) errors must be reported by a compilerGenerate meaningful error messages and resume compilation after each errorEach phase of a compiler needs different kind of error handingBACK1.5 Other Issues in Compiler StructureThe Structure of CompilerMultiple views from different anglesLogical StructurePhysical StructureSequencing of the operationsA major im