Tuesday 5:00 - 7:00
Room 109, Warren Weaver Hall
Professor Robert Dewar
Instructor: Robert Dewar (email@example.com)
additional lectures: Ed 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
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
Frazer and Hanson: a retargetable C compiler (Benjamin Cummings, 1996)
Fisher & LeBlanc : Crafting a Compiler (Benjamin Cummings)
Dewar & Smosna : Microprocessors, a programmer's perspective
If Ada is new to you, you may want to start with this
ada summary .
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
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 scans.ads, scn.ads, scn-nlit.adb, scn-slit.adb,
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 sinfo.ads, par.adb and its subunits.
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
Code generation for RISC machines: pipelines, delay slots,
Readings : Microprocessors, chap. ???
Peephole optimization. Case study: the REALIA Cobol compiler.
Global optimization: data flow analysis, monotomic frameworks, use-def chaining,constant folding, common subexpression elimination.
Readings: ASU chapter 10, lecture notes.