English | MP4 | AVC 960×540 | AAC 44KHz 2ch | 19h 10m | 1.04 GB
eLearning | Skill level: Advanced | by Alex Aiken

part 1
part 2

This course will discuss the major ideas used today in the implementation of programming language compilers, including lexical analysis, parsing, syntax-directed translation, abstract syntax trees, types and type checking, intermediate languages, dataflow analysis, program optimization, code generation, and runtime systems. As a result, you will learn how a program written in a high-level language designed for humans is systematically translated into a program written in low-level assembly more suited to machines. Along the way we will also touch on how programming languages are designed, programming language semantics, and why there are so many different kinds of programming languages.

The course lectures will be presented in short videos. To help you master the material, there will be in-lecture questions to answer, quizzes, and two exams: a midterm and a final. There will also be homework in the form of exercises that ask you to show a sequence of logical steps needed to derive a specific result, such as the sequence of steps a type checker would perform to type check a piece of code, or the sequence of steps a parser would perform to parse an input string. This checking technology is the result of ongoing research at Stanford into developing innovative tools for education, and we’re excited to be the first course ever to make it available to students.

An optional course project is to write a complete compiler for COOL, the Classroom Object Oriented Language. COOL has the essential features of a realistic programming language, but is small and simple enough that it can be implemented in a few thousand lines of code. Students who choose to do the project can implement it in either C++ or Java.


Table of Contents

1. Introduction
Structure of a Compiler
The Economy of Programming Languages

2. The Cool Programming Language
Cool Overview
Cool Example II
Cool Example III

3. Lexical Analysis
Lexical Analysis
Lexical Analysis Examples
Regular Languages
Formal Languages
Lexical Specifications
DeduceIt Demo

4. Finite Automata
Lexical Specification
Finite Automata
Regular Expressions into NFAs
Implementing Finite Automata

5. Parsing
Introduction to Parsing
Context Free Grammars

6. Top-Down Parsing
Error Handling
Abstract Syntax Trees
Recursive Descent Parsing
Recursive Descent Algorithm
Left Recursion

7. Bottom-Up Parsing I
Predictive Parsing
First Sets
Follow Sets
LL1 Parsing Tables
Bottom-Up Parsing
Shift-Reduce Parsing

8. Bottom-Up Parsing II
Recognizing Handles
Recognizing Viable Prefixes
Valid Items
SLR Parsing
SLR Parsing Example
SLR Improvements
SLR Examples

9. Semantic Analysis and Type Checking
Introduction to Semantic Analysis
Symbol Tables
Type Checking
Type Environments
Typing Methods
Implementing Type Checking

10. Cool Type Checking
Static vs. Dynamic Typing
Self Type
Self Type Operations
Self Type Usage
Self Type Checking
Error Recovery

11. Runtime Organization
Runtime Organization
Activation Records
Globals and Heap
Stack Machines

12. Code Generation
Introduction to Code Generation
Code Generation I
Code Generation II
Code Generation Example
Object Layout

13. Operational Semantics
Semantics Overview
Operational Semantics
Cool Semantics I
Cool Semantics II

14. Local Optimization
Intermediate Code
Optimization Overview
Local Optimization
Peephole Optimization

15. Global Optimization
Dataflow Analysis
Constant Propagation
Analysis of Loops
Liveness Analysis

16. Register Allocation
Register Allocation
Graph Coloring
Managing Caches

17. Garbage Collection
Automatic Memory Management
Mark and Sweep
Stop and Copy
Conservative Collection
Reference Counting

18. Java
Java Arrays
Java Exceptions
Java Interfaces
Java Coercions
Java Threads
Other Topics