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: Aho-Sethi-Ullman , ch. 1

Lecture 2

A modern compiler : GNAT. The architecture of GNAT: phases, intermediate representations, important data structures.
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.
Formalism: regular grammars, regular languages, FSA, non-deterministic FSA, automatic generation of lexical scanners.

Reading: Aho-Sethi-Ullman, ch. 3
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: Aho-Sethi-Ullman , ch. 4.1-4.4
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: Aho-Sethi-Ullman, ch. 4.7-4.9
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: Aho-Sethi-Ullman ch. 5
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. Scott). Chapter 6 of Aho-Sethi-Ullman.
slides (powerpoint)

Lecture 8

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

Reading: Aho-Sethi-Ullman ch. 7
slides (powerpoint)

Lecture 9

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

Reading: Aho-Sethi-Ullman Ch.8
slides (powerpoint)

Lecture 10

Code generation over basic blocks. Using dags. Global register allocation and graph coloring.
Reading: Aho-Sethi-Ullman chap. 9.1-9.6
slides (powerpoint)

Lecture 11

Global optimization: data flow analysis, Single-Assignment form.
Reading: Aho-Sethi-Ullman ch.10
slides (powerpoint)

Lecture 12

Code generation for RISC machines: delay slots, instruction scheduling, inlining, loop unrolling.

slides (powerpoint)

Lecture 13

Peephole optimization.


slides (powerpoint)

Lecture 14

Instruction selection by tree matching
slides (pdf)