Compilers

Course Description

In this course, you will learn principles and practices for design and implementation of compilers and interpreters. Topics covered include: lexical analysis; parsing theory; symbol tables; type systems; scope; semantic analysis; intermediate representations; runtime environments; code generation; and basic program analysis and optimization. Students will construct a compiler for a simple object-oriented language during the course's programming projects.

To understand the concepts in this course, you should be familiar with regular expressions, context-free grammars, graphs, sets, and formal languages. Well-developed programming skills and debugging ability will also be important for the programming assignments. An understanding of simple code generation and function calling conventions, as well as some exposure to different language paradigms would also be helpful. If you are unsure about some of these topics, be prepared to brush up on your own to fill in the gaps as you encounter them.

While a textbook is not required to complete the course, Compilers: Principles, Techniques, and Tools (2nd Edition) by Aho, Sethi, Lam, and Ullman (a.k.a. the "purple dragon" book) can be a useful reference. This is a new edition of the classic compiler text and is a very thorough and solid treatment of the material. Some students may find it helpful as a reference or supplemental source.

This course is a work in progress. Not all of the videos, assignments, and materials for this course have been uploaded (or even filmed/written, for that matter). Please be patient as we work to finish the course.

I. INTRODUCTION

•  Introduction (8 min)
•  Structure of a Compiler (13 min)
•  The Economy of Programming Languages (19 min)

II. THE COOL PROGRAMMING LANGUAGE

•  Cool Overview (19 min)
•  Cool Example II (15 min)
•  Cool Example III (18 min)
•  Programming Assignment 1

III. LEXICAL ANALYSIS

•  Lexical Analysis (12 min)
•  Lexical Analysis Examples (13 min)
•  Regular Languages (12 min)
•  Formal Languages (13 min)
•  Lexical Specifications (16 min)
•  Programming Assignment 2

IV. FINITE AUTOMATA

•  Lexical Specification (14 min)
•  Finite Automata (23 min)
•  Regular Expressions to NFAs (9 min)
•  NFA to DFA (15 min)
•  Implementing Finite Automata (11 min)

V. PARSING

•  Introduction to Parsing (5 min)
•  Context-Free Grammars (14 min)
•  Derivations (7 min)
•  Ambiguity (17 min)

VI. TOP-DOWN PARSING

•  Error Handling (13 min)
•  Abstract Syntax Trees (3 min)
•  Recursive Descent Parsing (6 min)
•  Recursive Descent Algorithm (13 min)
•  Left Recursion (9 min)
•  Programming Assignment 3

VII. BOTTOM-UP PARSING I

•  Predictive Parsing (19 min)
•  First Sets (14 min)
•  Follow Sets (17 min)
•  LL(1) Parsing Tables (14 min)
•  Bottom-Up Parsing (7 min)
•  Shift-Reduce Parsing (7 min)

VIII. BOTTOM-UP PARSING II

•  Handles (6 min)
•  Recognizing Handles (13 min)
•  Recognizing Viable Prefixes (14 min)
•  Valid Items (3 min)
•  SLR Parsing (14 min)
•  SLR Parsing Example (6 min)
•  SLR Improvements (11 min)
•  SLR Examples (12 min)

IX. SEMANTIC ANALYSIS AND TYPE CHECKING

•  Introduction to Semantic Analysis (3 min)
•  Scope (8 min)
•  Symbol Tables (11 min)
•  Types (11 min)
•  Type Checking (8 min)
•  Type Environments (11 min)
•  Subtyping (11 min)
•  Typing Methods (8 min)
•  Implementing Type Checking (6 min)
•  Programming Assignment 4

X. COOL TYPE CHECKING

•  Static vs. Dynamic Typing (7 min)
•  Self Type (7 min)
•  Self Type Operations (12 min)
•  Self Type Usage (6 min)
•  Self Type Checking (10 min)
•  Error Recovery (7 min)

XI. RUNTIME ORGANIZATION

•  Runtime Organization (6 min)
•  Activations (13 min)
•  Activation Records (13 min)
•  Globals & Heap (6 min)
•  Alignment (6 min)
•  Stack Machines (16 min)

XII. CODE GENERATION

•  Introduction to Code Generation (7 min)
•  Code Generation I (17 min)
•  Code Generation II (18 min)
•  Code Generation Example (13 min)
•  Temporaries (16 min)
•  Object Layout (23 min)

XIII. OPERATIONAL SEMANTICS

•  Semantics Overview (7 min)
•  Operational Semantics (12 min)
•  Cool Semantics I (21 min)
•  Cool Semantics II (26 min)
•  Programming Assignment 5
•  Optimizer (Optional Assignment)

XIV. LOCAL OPTIMIZATION

•  Intermediate Code (9 min)
•  Optimization Overview (13 min)
•  Local Optimization (25 min)
•  Peephole Optimization (4 min)

XV. GLOBAL OPTIMIZATION

•  Dataflow Analysis (8 min)
•  Constant Propagation (21 min)
•  Analysis of Loops (7 min)
•  Orderings (6 min)
•  Liveness Analysis (13 min)

XVI. REGISTER ALLOCATION

•  Register Allocation (9 min)
•  Graph Coloring (12 min)
•  Spilling (14 min)
•  Managing Caches (10 min)

XVII. GARBAGE COLLECTION

•  Automatic Memory Management (14 min)
•  Mark and Sweep (13 min)
•  Stop and Copy (19 min)
•  Conservative Collection (3 min)
•  Reference Counting (15 min)

XVIII. JAVA

•  Java (7 min)
•  Java Arrays (8 min)
•  Java Exceptions (14 min)
•  Java Interfaces (8 min)
•  Java Coercions (7 min)
•  Java Threads (18 min)
•  Other Topics (14 min)