Compiler Construction

G22.2130.01
Monday 7:00 - 8:50 pm
Room 1302, Warren Weaver Hall
Professor Edmond Schonberg

Instructor: Edmond Schonberg (schonber@cs.nyu.edu) Office hours: WWH410, Monday and Thursday 3-5 pm, and by appointment.

Teaching Assistants: TBD

Class list

All students should register themselves with the class list, which is used for all technical discussions concerning the course and the course project. To subscribe to this list visit the web page:

http://www.cs.nyu.edu/mailman/listinfo/g22_2130_001_fpa04

where you will find full directions.

Please send all your questions to this list (not only to the instructor) so that everyone can participate.

Assignments

Assignment 0 The final project for the course will involve writing a code generator for the target machine of your choice. The first step is to review the assembly language for that machine, so you know what your code generator is supposed to generate! For this zeroth assignment, you must write a small procedure in assembly language (for example, your favorite sorting algorithm, quicksort or heapsort prefered) as well as a test program in C (or the high-level language of your choice) that calls and tests your assembly routine. Hand in the source for the assembly program and for the driver, and the output of the program. Indicate the machine on which you are running and the assembler you used.

If you need to refresh your knowledge of assembly language, the following may prove useful:

Free Assembly Tutorial
direct download

On a Unix system you can run gcc with the -S switch to obtain the generated assembly code, which provides the quickest introduction to the conventions of the assembler on your machine.

Submission

Send listing of assembly program, driver program, and output, to me and to the graders.
Due date: February 5.
Assignment 1 Lexical scanning

Assignment 2 Context-free grammars

Assignment 3 Top-Down parsing

Textbooks

required:

Keith D. Cooper & Linda Torczon: Engineering a Compiler (Wiley)
This is a brand-new textbook, with an extensive coverage of code generation and optimization techniques, presented from a pragmatic point of view.

recommended:

Aho, Sethi and Ullman: Compilers, principles, Techniques and tools (Addison Wesley)

This is still a standard text, even though more than 15 years old. A new edition is to appear shortly.

Scott: Programming Language Pragmatics.
A nice balance of language issues and implementation issues, with substantial elementary information about compiler structures and organization.

Additional recommended readings:

Fraser and Hanson: a retargetable C compiler (Benjamin Cummings, 1996)
Muchnick: advanced compiler design and implementation (Morgan Kaufman, 1997)
Fisher & LeBlanc : Crafting a Compiler (Benjamin Cummings)
Appel : modern compiler implementation in C : basic techniques
Dewar & Smosna : Microprocessors, a programmer's perspective (Mc-Graw Hill)


Course outline
sample questions for final examination
  • Compiler Project

    GNAT Sources

    Throughout the course we will be referring to the sources of the GNAT compiler, which will also be the basis of the course project. The compact overview of GNAT provides a roadmap to its main components. You can download GNAT for your favorite machine, and get the full sources of the compiler, from the NYU ftp site: ftp cs.nyu.edu, directory pub/gnat. To build the compiler, you will need the sources for GCC 2.81.

    You may also find it useful to browse the GNAT sources here. To download the entire set, grab gnat-html.zip, unzip it on your local machine, and point your browser to index.htm.

    Bison Documentation

    On-line documentation for the Bison parser-generator can be found here