Unformatted text preview:

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

U of M CS 5641 - Lecture notes

Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?