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-Lam-Sethi-Ullman , ch. 1
slides (lecture1.ps) ,   lecture1.pdf,   lecture1_h4.ps ,   lecture1_h4.pdf

Lecture 2

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-Lam-Sethi-Ullman, ch. 3
slides (lecture2.ps) ,   lecture2.pdf,   lecture2_h4.ps ,   lecture2_h4.pdf ,  

Lecture 3

Parsing. Abstract syntax vs. concrete syntax. Grammars and the formal specification of certain aspects of programming languages. Top-down parsing and recursive descent. Automatic parser construction. FIRST and FOLLOW functions. LL(1) parsers.

Reading: Aho-Lam-Sethi-Ullman , ch. 4.1-4.4
slides (lecture3.ps) ,   lecture3.pdf,   lecture3_h4.ps ,   lecture3_h4.pdf ,  

Lecture 4

Bottom-up parsing through LR parsers. Conflicts in LR grammars and how to resolve them. SLR, LR(k), and LALR parsers.

Reading: Aho-Lam-Sethi-Ullman, ch. 4.7-4.9
slides (lecture4.ps) ,   lecture4.pdf,   lecture4_h4.ps ,   lecture4_h4.pdf ,   Updated 10.4.07

Lecture 5

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-Lam-Sethi-Ullman ch. 5
slides (lecture5.ps) ,   lecture5.pdf,   lecture5_h4.ps ,   lecture5_h4.pdf ,   Updated 10.30.07

Lecture 6

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-Lam-Sethi-Ullman.
slides (lecture6.ps) ,   lecture6.pdf,   lecture6_h4.ps ,   lecture6_h4.pdf ,   Updated 11.6.07

Lecture 7

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

Reading: Aho-Lam-Sethi-Ullman ch. 7
slides (lecture7.ps) ,   lecture7.pdf,   lecture7_h4.ps ,   lecture7_h4.pdf ,   Updated 11.13.07

Lecture 8

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

Reading: Aho-Lam-Sethi-Ullman Ch.8
slides (lecture8.ps) ,   lecture8.pdf,   lecture8_h4.ps ,   lecture8_h4.pdf ,   Updated 11.19.07

Lecture 9

Code generation over basic blocks. Using dags. Global register allocation and graph coloring.
Reading: Aho-Lam-Sethi-Ullman chap. 9.1-9.6
slides (lecture9.ps) ,   lecture9.pdf,   lecture9_h4.ps ,   lecture9_h4.pdf ,   Updated 11.26.07

Lecture 10

Global optimization: data flow analysis, Single-Assignment form.
Reading: Aho-Lam-Sethi-Ullman ch.10
slides (lecture10.ps) ,   lecture10.pdf,   lecture10_h4.ps ,   lecture10_h4.pdf ,   Updated 12.10.07

Lecture 11

Code generation for RISC machines: delay slots, instruction scheduling, inlining, loop unrolling.
slides (lecture11.ps) ,   lecture11.pdf,   lecture11_h4.ps ,   lecture11_h4.pdf ,   Updated 12.13.07

Lecture 12

Peephole optimization.

slides (lecture12.ps) ,   lecture12.pdf,   lecture12_h4.ps ,   lecture12_h4.pdf ,   Updated 12.13.07

Lecture 13

Instruction selection by tree matching
Reading: Aho-Lam-Sethi-Ullman ch. 8.9--8.13
slides (lecture13.ps) ,   lecture13.pdf,   lecture13_h4.ps ,   lecture13_h4.pdf ,  

Lecture 14

VLIW/EPIC Architectures, Software Pipelining.
Reading: Aho-Lam-Sethi-Ullman ch. 10.5
slides (lecture14.ps) ,   lecture14.pdf,   lecture14_h4.ps ,   lecture14_h4.pdf ,   powerpoint slides (Experimental) ,  

Lecture 15

Examples of assembly programs.
Reading: Manuals provided at this web page (see assignment).
slides (lecture15.ps) ,   lecture15.pdf,   lecture15_h4.ps ,   lecture15_h4.pdf ,  

Lecture 16

Optimizing for parallelism and locality. Affine programs. Analysis for data reuse. Integer Linear Programming.
Reading: Aho-Lam-Sethi-Ullman ch. 11.1-6
slides (lecture16.ps) ,   lecture16.pdf,   lecture16_h4.ps ,   lecture16_h4.pdf ,