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 Grune, 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 Grune, ch. 2.1
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 Grune, ch. 2.2
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 Grune, ch. 2.2
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 Grune, ch. 3
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 6.1 of Grune et al.
slides (powerpoint)

Lecture 8

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

slides (powerpoint)

Lecture 9

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

Reading Grune, ch. 4
slides (powerpoint)

Lecture 10

Code generation over basic blocks. Using dags.Global register allocation and graph coloring.
Reading Aho, Sethi and Ullman, ch. 9, Grune et al. Section 4.2.
slides (powerpoint)

Lecture 11

Global optimization: data flow analysis, use-def chaining,constant folding, common subexpression elimination.
Reading Aho, Sethi and Ullman, ch. 10.
slides (powerpoint)

Lecture 12

Code generation for RISC machines: delay slots, instruction scheduling, inlining, loop unrolling.
Reading: Muchnick, chap. 9 and 17.

slides (powerpoint)

Lecture 13

Code generation for VLIW Architectures (guest lecturer: Ben Goldberg).

slides (powerpoint)

Lecture 14

Peephole optimization.
slides (powerpoint)