Scribd Logo
Upload

Welcome to Scribd!

  • 92 views

    Compiler Construction: Mohamed Zahran (Aka Z) Mzahran@cs - Nyu.edu

    Uploaded by

    Helal Ismail
    This document provides an overview of a compiler construction course. It outlines the formal goals of understanding compilers, their interaction with hardware and programming languages, and the different phases of a compiler. It also lists the informal goals of learning compilers and enjoying the material. The grading breakdown and course web page are described. An introduction to compilers and their importance is provided at a high level.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Compiler Construction: Mohamed Zahran (Aka Z) Mzahran@cs - Nyu.edu

    Uploaded by

    Helal Ismail
    92 views37 pages
    This document provides an overview of a compiler construction course. It outlines the formal goals of understanding compilers, their interaction with hardware and programming languages, and the different phases of a compiler. It also lists the informal goals of learning compilers and enjoying the material. The grading breakdown and course web page are described. An introduction to compilers and their importance is provided at a high level.

    Original Title

    Lecture 1

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an overview of a compiler construction course. It outlines the formal goals of understanding compilers, their interaction with hardware and programming languages, and the different phases of a compiler. It also lists the informal goals of learning compilers and enjoying the material. The grading breakdown and course web page are described. An introduction to compilers and their importance is provided at a high level.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    92 views37 pages

    Compiler Construction: Mohamed Zahran (Aka Z) Mzahran@cs - Nyu.edu

    Uploaded by

    Helal Ismail
    This document provides an overview of a compiler construction course. It outlines the formal goals of understanding compilers, their interaction with hardware and programming languages, and the different phases of a compiler. It also lists the informal goals of learning compilers and enjoying the material. The grading breakdown and course web page are described. An introduction to compilers and their importance is provided at a high level.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 37

    G22.

    2130-001

    Compiler Construction
    Mohamed Zahran (aka Z)
    [email protected]
    Who Am I?
    • Mohamed Zahran (aka Z)
    • Computer architecture/OS/Compilers
    Interaction
    • http://www.mzahran.com
    • Office hours: Thursdays 5:00-7:00 pm
    • Room: CIWW 328
    • Course web page:
    http://www.cs.nyu.edu/courses/spring11/G22.2130-001/
    Formal Goals of This Course
    • What exactly is this thing called
    compiler?
    • How does the compiler interact with the
    hardware and programming languages?
    • Different phases of a compiler
    • Develop a simple compiler
    Informal Goals of This Course
    • To get more than an A
    • To learn compilers and enjoy it
    • To use what you have learned in MANY
    different contexts
    Grading
    • The project (labs): 60%
    – Due several lectures later
    – Several parts
    – Mostly programming and dealing with tools
    – Can do on your own machine or NYU machines
    – Must be sure that they work on NYU machines
    – Getting help: office hours, mailing list, and FAQ

    • Final exam: 40%


    The Course Web Page
    • Lecture slides
    • Info about mailing list, labs, … .
    • FAQ
    • Useful links (manuals, tools, book
    errata, … ).
    • Interesting links (geeky stuff!)
    The Book
    • The classic definitive
    compiler technology
    text
    • It is known as the
    Dragon Book
    • A knight and a dragon in
    battle, a metaphor for
    conquering complexity
    • We will cover mostly
    chapters 1 - 8
    What Is A Compiler?
    • Programming languages
    are notations for
    describing computations
    to people and to machines
    • Machines do not
    understand programming
    languages
    • So a software system is
    needed to do the
    translation
    • This is the compiler
    Machine Architecture Programming Languages

    Compiler writers
    Compiler writers have to track
    must take advantage
    new language features
    of new hardware features
    Compilers

    Language Theory Software Engineering

    •Optimizing compilers are hard to build


    •Excellent software engineering case study
    •Theory meets practice
    Why Compilers Are So
    Important?
    • Compiler writers have influence over all
    programs that their compilers compile
    • Compiler study trains good developers
    • We learn not only how to build compilers but
    the general methodology of solving complex and
    open-ended problems
    • Compilation technology can be applied in many
    different areas
    – Binary translation
    – Hardware synthesis
    – DB query interpreters
    – Compiled simulation
    So What Is An Interpreter?

    + Better error diagnostics than compiler


    -Slower than machine language code directly executed on the
    machine
    Compilation

    Interpretation
    Problem  Algorithm Development  Programmer

    High Level Language

    Compiler (translator)

    Assembly Language

    Assembler (translator)

    Machine Language

    Control Unit (Interpreter)

    Microarchitecture

    Microsequencer (Interpreter)

    Logic Level

    Device Level  Semiconductors  Quantum


    Compiler Is Not
    A One-Man-Show!

    Why not letting the compiler


    generate machine code directly?
    Let’s Have A Closer Look:
    Phases of A Compiler

    Front-end
    (Analysis Phase)

    Back-End
    (Synthesis Phase)
    Lexical Analysis
    • Reads stream of characters: your program
    • Groups the characters into meaningful
    sequences: lexemes
    • For each lexeme, it produces a token
    <token-name, attribute value>
    • Blanks are just separators and are
    discarded
    • Filters comments
    • Recognizes: keywords, identifier,
    numbers, …
    Token stream

    token name Entry into the symbol table


    Syntax Analysis (Parsing)
    • Uses tokens to build a tree
    • The tree shows the grammatical
    structure of the token stream
    • A node is usually an operation
    • Node’s children are arguments
    This is usually called a syntax tree
    Semantic Analysis
    • Uses the syntax tree and symbol tables
    • Gathers type information
    • Checks for semantic consistency errors
    Intermediate Code Generation
    • Code for an abstract machine
    • Must have two properties
    – Easy to produce
    – Easy to translate to target language
    •Called three address code
    •One operation per instruction at most
    •Compiler must generate temporary names
    to hold values
    Intermediate Code Optimization
    (Optional)
    • Machine independent
    • optimization so that better target code
    will result
    t1 = inttofloat (60) t1 = id3 * 60.0 t1 = id3 * 60.0
    t2 = id3 * t1 t2 = id2 + t1 id1 = id2 + t1
    t3 = id2 + t2 id1 = t2
    id1 = t3

    Instead of inttofloat Do we really need t2?


    we can use 60.0 directly
    Code Generation
    • Input: the intermediate representation
    • Output: target language
    • This is the backend, or synthesis phase
    • Machine dependent
    Qualities of a Good Compiler
    • Correct: the meaning of sentences must be preserved
    • Robust: wrong input is the common case
    – compilers and interpreters can’t just crash on wrong input
    – they need to diagnose all kinds of errors safely and reliably
    • Efficient: resource usage should be minimal in two
    ways
    – the process of compilation or interpretation itself is
    efficient
    – the generated code is efficient when interpreted
    • Usable: integrate with environment, accurate
    feedback
    – work well with other tools (editors, linkers, debuggers, . . . )
    – descriptive error messages, relating accurately to source
    Compilers Optimize Code For:
    • Performance/Speed
    • Code Size
    • Power Consumption
    • Fast/Efficient Compilation
    • Security/Reliability
    • Debugging
    Compiler Construction Tools
    • Parser generators: automatically
    produce syntax analyzer
    • Scanner generators: produce lexical
    analyzer
    • Syntax-directed translation engines:
    collection of routines for walking a
    parse tree and generate intermediate
    code
    • and many more …
    A Little Bit of History

    Eckert and Mauchly

    • 1st working electronic


    computer (1946)
    • 18,000 Vacuum tubes
    • 1,800 instructions/sec
    • 3,000 ft3
    A Little Bit of History
    • Maurice Wilkes

    1st stored program


    computer
    EDSAC 1 (1949) 650 instructions/sec
    http://www.cl.cam.ac.uk/UoCCL/misc/EDSAC99/ 1,400 ft3
    A Little Bit of History
    • 1954 IBM developed
    704
    • All programming
    done in assembly
    • Software costs
    exceed hardware
    costs!
    A Little Bit of History
    • Fortran I (project
    1954-57)
    • The main idea is to
    translate high level
    language to assembly
    • Many thought this was
    impossible!
    • In 1958 more than
    50% of software in
    assembly!
    • Development time John Backus
    halved! (December 3, 1924 – March 17, 2007)
    A Glimpse At Programming
    Language Basics
    • Static/Dynamic distinction
    • Environments and states
    – Environment: mapping names to locations
    – States: mapping from locations to values

    • Procedures vs Functions
    • Scope
    Roadmap
    • Today we have mostly discussed chap 1
    • Chapter 2 gives an overview of the
    different phases of a compiler by
    building the front-end of a simple
    compiler
    • Chapters 3-8 fill the gaps

    You might also like