Compiler Construction - Northwestern University

Compiler Construction - Northwestern University

Compiler Construction Vana Doufexi [email protected] office #317 @ CS dept 1 Administrative info class webpage http://www.cs.northwestern.edu/academics/courses/ 322 contains: news staff information lecture notes & other handouts

homeworks & manuals policies, grades newsgroup portal useful links 2 What is a compiler A program that reads a program written in some language and translates it into a program written in some other language Modula-2 to C Java to bytecodes COOL to MIPS code

3 Why study compilers? Application of a wide range of theoretical techniques Good SW engineering experience Better understand languages 4 Features of compilers Correctness preserve the meaning of the code Speed of target code

vs. speed of compilation? Good use of resources (size, power) Good error reporting/handling 5 Compiler structure source code Front End IR

Back End target code Use intermediate representation Why? 6 Compiler Structure Front end Recognize legal/illegal programs report/handle errors

Generate IR The process can be automated Back end Translate IR into target code instruction selection register allocation instruction scheduling lots of NPC problems -- use approximations 7

Compiler Structure Optimization: Middle stage goals improve running time of generated code improve space, power consumption, etc. how? perform a number of transformations on the IR multiple passes important: preserve meaning of code 8

The Front End Scanning (a.k.a. lexical analysis) recognize "words" Parsing (a.k.a. syntax analysis) check syntax Semantic analysis examine meaning (e.g. type checking) Other issues: symbol table (to keep track of identifiers) error detection/reporting/recovery 9

The Scanner Its job: given a character stream, recognize words (tokens) e.g. x = 1 becomes IDENTIFIER EQUAL INTEGER collect identifier information e.g. IDENTIFIER corresponds to a lexeme (the actual word x) and its type (acquired from the declaration of x). ignore white space and comments report errors Good news the process can be automated

10 The Parser Its job: Check and verify syntax based on specified syntax rules e.g. IDENTIFIER LPAREN RPAREN make up an EXPRESSION. Coming soon: how context-free grammars specify syntax Report errors Build IR often a syntax tree

Good news the process can be automated 11 Semantic analysis Its job: Check the meaning of the program e.g. In x=y, is y defined before being used? Are x and y declared? e.g. In x=y, are the types of x and y such that you can assign one to the other? Meaning may depend on context Report errors

12 IRs Graphical e.g. parse tree, DAG Linear e.g. three-address code Hybrid e.g. linear for blocks of straight-line code, a graph to connect blocks Low-level or high-level

13 The scanning process Main goal: recognize words How? by recognizing patterns e.g. an identifier is a sequence of letters or digits that starts with a letter. Lexical patterns form a regular language Regular languages are described using regular expressions (REs) Can we create an automatic RE recognizer? Yes! (Hold that thought) 14

The scanning process Definition: Regular expressions (over alphabet ) is an RE denoting {} If , then is an RE denoting {} If r and s are REs, then (r) is an RE denoting L(r) r|s is an RE denoting L(r)L(s) rs is an RE denoting L(r)L(s)

r* is an RE denoting the Kleene closure of L(r) Property: REs are closed under many operations This allows us to build complex REs. 15 The scanning process Definition: Deterministic Finite Automaton a five-tuple (, S, , s0, F) where is the alphabet S is the set of states is the transition function (SS) s0 is the starting state F is the set of final states (F S)

Notation: Use a transition diagram to describe a DFA DFAs are equivalent to REs Hey! We just came up with a recognizer! 16 The scanning process Goal: automate the process Idea: Start with an RE Build a DFA How? We can build a non-deterministic finite automaton (Thompson's construction)

Convert that to a deterministic one (Subset construction) Minimize the DFA (Hopcroft's algorithm) Implement it Existing scanner generator: flex 17

Recently Viewed Presentations

  • Charter Review Commission 2007-2008 Meeting 4  Issues Gathering

    Charter Review Commission 2007-2008 Meeting 4 Issues Gathering

    48261a communication serv-e911. 35220a false alarm civil penalty. 35741a drug enforcemt forft-fed. 35742a drug enfrcemt forft-state. 36928a sale unclaimed property. 36979 junk/salvage. 47608a patient participatn reimb. 47967a drug rebates. dept field. finance - cx (0150) 0150 business relations & economic...
  • Death

    Death

    AKA Black Putrefaction. Days 10-20. Body has very strong odor. Flesh is black colored and skin has ruptured- seeping fluids and gases. Creates a . cadaver of decomposition island (CDI) Most of the body mass disappears due to insect activity-...
  • Firmung 2005 Dekanat Axams - dibk.at

    Firmung 2005 Dekanat Axams - dibk.at

    Versöhnungsfeier DEICHKIND Es tut mir Leid doch ich muss leider gestehen es gibt Dinge auf der Welt die sind Auto's machen Dreck, Umwelt geht kaputt doch 'ne fette neue Karre is' Ich knabber' an nem' Buntstift, Mama sagt 'Lass das!'...
  • American Physical Society (APS) awards:UR Faculty and Alumni

    American Physical Society (APS) awards:UR Faculty and Alumni

    American Physical Society (APS) awards:UR Faculty and Alumni Physics& Astronomy, LLE & Institute of Optics Nobel Prize 2001 Masatoshi Koshiba University of Tokyo. UR Physics PhD 55 (Also Wolf Prize Israel 2001) Nobel Prize 97 Steve Chu - Stanford UR...
  • Taxonomy - BETSY SANFORD'S WEBSITE

    Taxonomy - BETSY SANFORD'S WEBSITE

    Made of cells (smallest building block of life) Have DNA (complex chemicals that control cell activities) Have basic needs (use energy from food and water, need habitat) Can reproduce (sexually/2 parents or asexually/1 parent) Grow and develop (have a life...
  • Digital Logic Design Lecture 19 Announcements  Homework 6

    Digital Logic Design Lecture 19 Announcements Homework 6

    Consider two n-bit binary numbers: ?=??−1⋯????−1⋯?1?0. ?=??−1⋯????−1⋯?1?0. Assume ??, ?? are entering the subnetwork and that the binary numbers are analyzed from right to left. Subnetwork is called a 1-bit comparator.
  • Third Edition - pearsoncmg.com

    Third Edition - pearsoncmg.com

    Many economists believe that market-based solutions are the best approach to improving the health care system. Your Turn: Test your understanding by doing related problems 3.13 and 3.14 at the end of this chapter. ... Spending on Health Care around...
  • PLDC PLDC COUNSELING PLDC L204-RC/JUN 94/VGT-8 L204-RC PLDC

    PLDC PLDC COUNSELING PLDC L204-RC/JUN 94/VGT-8 L204-RC PLDC

    Times New Roman Arial Calibri Office Theme 1_Office Theme 2_Office Theme Microsoft Word Document PowerPoint Presentation PLDC MILITARY APPROACHES TO COUNSELING REASONS FOR COUNSELING NCOERs DESIGNED TO: RULES OF NCOER COUNSELING NCOER COUNSELING PHASES PREPARATION FOR COUNSELING THE COUNSELING SESSION...