1CS 5641 Compiler DesignRich [email protected] Heller HallAcknowledgements Notes derived from: Susan Horwitz (UW-Madison) Ras Bodik (UW-Madison) Alex Aiken (Berkeley) George Necula (Berkeley)2Readings Chapter 1 Chapter 2 (optional) – may want to review this chapter periodicallyLevels of Programming Languages Machine language Assembly language High-level languages C, C++, LISP, Pascal, Prolog, Scheme Natural language English3Programming Paradigms Imperative languages Computation as a series of actions Object-oriented programming Computation organized around objects and functions that can be applied to objects Functional programming Language as a set of (extendable) functions Logic programming Programs as defining what a solution look like, letting the machine find a solutionTools for Programming Interpreter Commands in a high level language are translated to machine terms as they are encountered Compiler Program translated in its entirety at one time to a corresponding machine language program Hybrids4Parts of a CompilerParserScannerSemanticAnalyzerIntermediateCode GeneratorOptimizerCode GeneratorSource CodeObject CodeScanner Translates an input sequence of characters into a sequence of tokens Tokens in English: word (junk), capitalized word (Program), period (.) Sample input: Dogs like chocolate. Tokens: capitalized word (Dogs)word (like)word (chocolate)period Scanners can note illegal characters Some scanners also do limit checks on integers5Program Tokens Sample input:int main () {int a = 0;cout << a << endl;return 1;} Tokens:Identifier (int)Identifier (main)Left parenthesisRight parenthesisLeft curly braceIdentifier (int)EqualsInteger (0)Semi-colonIdentifier (cout)Double left angle bracketIdentifier (a)Double left angle bracketIdentifier (endl)Semi-colonReserved word (return)Integer (1)Semi-colonRight curly braceParser Groups tokens together to form grammatical phrases Builds a structure to capture the program (abstract syntax tree) Interior nodes – operators Children - operands Example: a = a * 5;=aa*56Parser Errors Parsers generally understand programs as a series of statements (think sentences) Errors generated when it cannot understand your sentence Example: a = * 5;Something missing!Semantic Analyzer Checks for non-syntactic errors Example: type errors May change or annotate the abstract syntax tree For example, many arithmetic operators apply only to operands of one type, if two compatible types are mixed semantic analyzer may convert Example: a = 3.0 * 5;=a3.0*5=a3.0*int_to_double57Intermediate Code Generator Translates from syntax tree to some intermediate code One possibility – 3-address code, statements with at most 3 operands Example: a = initial + rate * 60; Translation:Temp1 = int_to_double(60)Temp2 = rate * Temp1Temp3 = initial + Temp2a = Temp3Optimizer Improves code generated by intermediate code generator Usually for speed, sometimes for size Example (from previous) InitialTemp1 = int_to_double(60)Temp2 = rate * Temp1Temp3 = initial + Temp2a = Temp3 ImprovedTemp2 = rate * 60.0a = initial + Temp2Convert at compile timeNo need to store, copy Temp38Code Generator Generates the object code Intermediate instructions are translated into a sequence of target code instructions Example:LOADF rate, R1MULF #60.0, R1LOADF initial, R2ADDF R2, R1STOREF R1,
View Full Document