About the web course
This course in compiler construction has been given many times by Martin Steffen. In 2021, the lectures were pre-recorded and published (due to the pandemic). This year, we will follow the progression of the course as it was given in 2021. The videos relevant for each week are outlined below.
The videos are accompanied by a script, that follows the lectures in written form (or perhaps it is the other way around).
It should be possible to complete the course with these resources available. Still, we strongly encourage you to attend the physical lectures. The physical lectures will not be recorded.
Note that the plan below is ambitious, covering quite a lot of material in certain weeks. This gives a lot of time at the end of the semester. If we need more time to cover the topic for a week, we will simply postpone.
Week 1
Script: Chapter 1 and Section 2.1
Week 2
Script: Section 2.2 – 2.8
- Scanning: Regular Expressions and Languages (0:53:34)
- Scanning: Finite State Automata (DFA/NFA) (0:31:58)
- Scanning: Implementation of DFAs (0:12:07)
- Scanning: Thompson’s Construction (0:25:38)
- Scanning: Determinization (0:17:01)
- Scanning: DFA Minimization (0:19:09)
Week 3
Script: Section 3.1 – 3.4
- Grammars: Introduction to Formal Languages (0:19:19)
- Grammars: Context-Free Grammars (0:48:02)
- Grammars: Ambiguity (0:54:01)
Week 4
Script: Section 4.1 – 4.2
Week 5
Script: Section 4.3–4.4
Week 6
Script: Section 4.5–4.7.2
Week 7
Script: Section 4.7.3–4.7.8 and Chapter 5
- Parsing: SLR Parsing (0:34:47)
- Parsing: Ambiguity in LR Parsers (0:28:59)
- Semantic Analysis: Introduction (0:17:23)
- Semantic Analysis: Attribute Grammars (1:02:05)
Week 8
Script: Chapter 6–7
- Symbol Tables: Design and Implementation (0:59:42)
- Symbol Tables: Scoping, Binding, and Name-Spaces (0:33:02)
- Symbol Tables: By Attribute Grammars (0:32:27)
- Type Checking: Part 1 (1:04:16)
- Type Checking: Part 2 (0:36:21)
- Type Checking: Equality of Types and Type Checking (1:05:35)
Week 9
Script: Section 8.1–8.2
- Run-Time Environments: Introduction (0:18:12)
- Run-Time Environments: Static Layout (0:11:23)
- Run-Time Environments: Stack-Based (0:49:25)
- Run-Time Environments: Nested Procedures (0:23:50)
- Run-Time Environments: Procedures as Arguments (0:34:47)
Week 10
Script: Section 8.3 – 8.5 and Section 9.1 – 9.3
- Run-Time Environments: Parameter Passing (0:53:03)
- Run-Time Environments: Virtual Methods in OO (0:39:02)
- Run-Time Environments: Garbage Collection (0:28:43)
- Intermediate Code Generation: Introduction (0:16:02)
- Intermediate Code Generation: Intermediate Code (0:11:51)
- Intermediate Code Generation: Three-Address Code (3AIC) (0:29:07)
Week 11
Script: Section 9.4–9.9
- Intermediate Code Generation: P-Code (0:16:14)
- Intermediate Code Generation: Generating P-Code (0:32:24)
- Intermediate Code Generation: Generating 3A-Code (0:20:33)
- Intermediate Code Generation: Converting Between P-Code and 3A-Code (0:18:26)
- Intermediate Code Generation: Complex Data (0:38:17)
- Intermediate Code Generation: Control Statements and Locical Expressions (0:47:26)
Week 12
Script: Section 10.1 – 10.10.4
- Code Generation: Introduction (0:17:38)
- Code Generation: 2AC and Instruction Costs Part 1 (0:28:33)
- Code Generation: 2AC and Instruction Costs Part 2 (0:20:32)
- Code Generation: Control-Flow Graphs (0:38:49)
- Code Generation: Liveness Analysis (0:19:11)
- Code Generation: Local Liveness (0:21:41)
Week 13
Script: Section 10.5 – 10.8
- Code Generation: More on Local Liveness (0:34:38)
- Code Generation: Global Liveness Analysis (0:57:05)
- Code Generation: Code Generation Algorithm (0:42:19)