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 Wednesday 5-7 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_fa04
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
The course involves the construction of a compiler for a simple imperative
language. The compiler will produce assembly language for the machine of
your choice. This motivates Assignment 0 of the course.
The first step in the project 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: September 27.
Textbooks
required:
Aho, Sethi and Ullman: Compilers, principles, Techniques and tools
(Addison Wesley)
This is still a standard text, and even though more than 15 years old it
covers most of the topics we want to discuss in sufficient detail. A new
edition is to appear shortly.
Recommended:
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)
Good treatment of the machine-description techniques used among others by
the GCC family of compilers.
Muchnick: advanced compiler design and implementation (Morgan Kaufman, 1997)
Excellent treatment of code generation and optimization issues for a variety of processors.
Appel : modern compiler implementation in C : basic techniques
Also available in ML and Java versions.
Dewar & Smosna : Microprocessors, a programmer's perspective
(Mc-Graw Hill)
An excellent survey of what a software engineer needs to know about hardware.
Course outline
sample questions for final examination
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
Assignments
Assignment 1: lexical analysis
Assignment 2: Algorithms on grammars
Project
Lexical analyser
Parser for B-flat
Semantic analysis in the B-flat compiler
code generation for the B-flat compiler