Wednesday 5:00 - 7:00
Room 109, Warren Weaver Hall
Professor Edmond Schonberg
Instructor: Edmond Schonberg (firstname.lastname@example.org)
All students should register themselves with the class list, which is used for
all technical discussions concerning the course and the course project. To
register, send an e-mail message to email@example.com. The
contents of the message should be the single line:
you will be notified in return that you are a list participant. Please send
all your questions to this list (not to the instructor) so that everyone can
Aho, Sethi and Ullman: Compilers, principles, Techniques and tools
This is still the standard textbook, even though more than 10 years old. The
following suggested readings touch on more recent topics, but the Dragon
book still contains much information that every compiler writer should know.
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: cs.nyu.edu, directory
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
If Ada is new to you, you may want to start with this
ada summary .
Semester project: write a prototype compiler for a Pascal subset of Ada,
using the front-end of the GNAT compiler.
Various problem sets, and a take-home final examination.
Assignment 0: assembly language review (done).
automaton for numeric literals in Ada
Solutions to assignment 1 (Latex)
Solutions to assignment 3
Language translators: compilers and interpreters. The structure of a compiler:
lexical analysis, parsing, semantic analysis, intermediate code generation,
register allocation, global optimization. Bootstrapping a compiler.
Readings: ASU chap. 1 and 2.
A modern compiler : GNAT. The architecture of GNAT: phases, intermediate
representations, important data structures. How to build GNAT from sources.
How to build modified versions of GNAT, tree-walking routines that use the
intermediate representation of GNAT.
Readings: GNAT specifications for syntactic and entity information, the
driver routines, interface to the GCC code generator.
an example tree-walking routine
syntax specification for GNAT AST
semantic information for entities in GNAT AST
Lexical scanning: Token classes, fast keyword recognition, minimizing the
code-per-character cost of scanning, scanning numeric literals and string
literals. The interface between the scanner and the parser.
Hand-written vs. automatically generated scanners.
Readings: GNAT files
ASU sections 3.1 - 3.4 (rest of chapter optional)
Parsing. Abstract syntax vs. concrete syntax. Grammars and the formal
specification of certain aspects of programming languages. Top-down
parsing and recursive descent.
Readings: GNAT files
par.adb (the top level parsing routine),
and its subunits. such as
par-ch3.adb (parsing of declarations),
par-ch10.adb (compilation units),
and ASU sections 4.1-4.4
Automatic parser construction. FIRST and FOLLOW functions. LL(1) parsers.
LR parsers. Conflicts in LR grammars and how to resolve them.
Readings: ASU sec. 4.7-4.9
Semantic analysis: attributes and their computation, tree-traversals,
visibility and name resolution. Inherited attributes and symbol tables.
Name resolution in block-structured languages.
Readings: GNAT files sem_chX.ads/adb, X= 3 to 8
ASU sections 5.1 - 5.5,
Type checking. Type systems, varieties of strong typing, overload resolution,
polymorphism and dynamic dispatching.
Type-checking and type inference, unification.
Readings: GNAT files sem_res, sem_type, sem_disp.
ASU chapter 6.
Run-time organization: storage allocation, non-local references, parameter
passing, dynamic storage allocation. Exception handling, debugging information.
Readings: GNAT files sem_res, exp_ch4, exp_ch6, exp_ch11.
ASU chapter 7.
Intermediate code generation: control structures, assignments, aggregates.
Lowering the semantic abstraction of high-level constructs.
Readings: GNAT files exp_ch5, exp_aggr. ASU chapter 8.
Code generation: quadruples, assembly language, machine language. Simple
algorithms for register allocation. Formal specification of machine
Readings: GCC docs, ASU chapter 9
An excellent GCC tutorial can be found at www.gnat.com/gcctut/ppframe.htm.
Code generation for RISC machines: pipelines, delay slots,
Readings : Microprocessors, chap. ???
Peephole optimization. Case study: the REALIA Cobol compiler.
Global optimization: data flow analysis, monotonic frameworks, use-def chaining,constant folding, common subexpression elimination.
Readings: ASU chapter 10, lecture notes.