Course Outline

Lecture 1

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.

Reading: Cooper & Torczon, ch. 1

Lecture 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.
slides (powerpoint)

Lecture 3

Lexical scanning: Token classes, 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.

Reading: Cooper & Torczon, ch. 2
slides (powerpoint)

Lecture 4

Parsing. Abstract syntax vs. concrete syntax. Grammars and the formal specification of certain aspects of programming languages. Top-down parsing and recursive descent.

Reading: Cooper & Torczon, ch.3.1 - 3.3
slides (powerpoint)

Lecture 5

Automatic parser construction. FIRST and FOLLOW functions. LL(1) parsers. LR parsers. Conflicts in LR grammars and how to resolve them.

Reading: Cooper & Torczon, ch. 3.4 - 3.6
slides (powerpoint)

Lecture 6

Semantic analysis: attributes and their computation, tree-traversals, visibility and name resolution. Inherited attributes and symbol tables. Name resolution in block-structured languages.

Reading: Cooper & Torczon, ch. 4
slides (powerpoint)

Lecture 7

Type checking. Type systems, varieties of strong typing, overload resolution, polymorphism and dynamic dispatching. Type-checking and type inference, unification.

Reading: Some programming language text (e.g. Sethi). Chapter 6 of Aho, Sethi and Ullman, section 4.2 of Cooper & Torczon.
slides (powerpoint)

Lecture 8

Run-time organization: storage allocation, non-local references, parameter passing, dynamic storage allocation. Exception handling, debugging information.

Reading: Cooper & Torczon, ch. 5.6, 6
slides (powerpoint)

Lecture 9

Intermediate code generation: control structures, expressions, simple register allocation. Aggregates and other high-level constructs.

Reading: Cooper & Torczon, ch. 5
slides (powerpoint)

Lecture 10

Code generation over basic blocks. Using dags. Global register allocation and graph coloring.
Reading: Cooper & Torczon, ch.7
slides (powerpoint)

Lecture 11

Global optimization: data flow analysis, Single-Assignment form.
Reading: Cooper & Torczon ch.9
slides (powerpoint)

Lecture 12

Code generation for RISC machines: delay slots, instruction scheduling, inlining, loop unrolling.
Reading: Cooper & Torczon, ch. 10 and 12

slides (powerpoint)

Lecture 13

Peephole optimization.
Reading: Cooper & Torczon, ch. 11

slides (powerpoint)