编译原理
这门课学什么
课程讲词法分析、语法分析、语义分析与类型检查、运行时组织、代码生成、优化和垃圾回收。可选项目是为教学语言 COOL 写一个完整编译器。
内容摘要
这门课讲高级语言程序怎样一步步翻译成汇编代码。edX 版是自定进度课程，建议进度共 10 周，讲师是 Alex Aiken。课程用短视频讲授，视频中穿插随堂小题。
课程沿编译器的流水线展开。第 1–4 周讲前端：先介绍课程项目语言 COOL，再讲词法分析和有限自动机，然后讲自顶向下和自底向上两类语法分析。第 5–6 周讲语义分析和类型检查，以 COOL 的类型规则为例。第 5 周安排期中考试。
第 6–7 周讲后端：运行时内存组织、代码生成和操作语义。第 8–9 周讲优化和高级主题：局部优化、全局优化、寄存器分配和垃圾回收。第 10 周用 Java 语言回顾全课概念，然后是期末考试。
评分由 4 部分组成：每周测验占 20%，期中占 15%，期末占 25%，编程作业占 40%。编程项目分 4 个作业，合起来是一个完整的 COOL 编译器，可以用 C++ 或 Java 写。每个作业都可以借用参考实现的其他阶段单独测试。学完后，你能说清编译器每个阶段的原理，也能自己写一个小型语言的编译器。
为什么值得学
少有的免费课程能带你从头写出一个可运行的编译器。
课程信息
- 学校
- 斯坦福（Stanford）
- 课程号
- SOE.YCSCS1
- 讲师
- Alex Aiken
- 学期
- self-paced
- 平台
- edX
- 费用
- 免费旁听
- 难度
- 高级
- 学时
- 每周 5–10 小时（edX 标注）
- 先修
- 需要数据结构、汇编基础，项目需要 C++ 或 Java。
- 材料
- 视频、作业、考试、代码
- 许可证
- 未注明
课程大纲 · 共 18 节
大纲依据：edX 课程 Syllabus 页的 10 周建议进度表（18 个视频单元）（查看原始页面 ↗）
- 1课程概览Course Overview
介绍编译器的整体结构和主要阶段。讨论为什么会有这么多种编程语言。
- 2COOL：课程项目语言Cool: The Course Project
介绍教学语言 COOL 的特性和示例程序。说明编程项目怎样逐步搭出一个编译器。
- 3词法分析Lexical Analysis
讲词法分析器的任务：把字符流切分成记号（token）。用正则表达式描述词法规则。
- 4有限自动机Finite Automata
讲 NFA 和 DFA。讲从正则表达式到 NFA、从 NFA 到 DFA 的转换，以及表驱动的实现。
- 5语法分析Parsing
讲上下文无关文法、推导和语法树。讨论二义性和语法错误处理。
- 6自顶向下分析Top-Down Parsing
讲递归下降分析和消除左递归。讲预测分析和 LL(1) 分析表的构造。
- 7自底向上分析（上）Bottom-Up Parsing I
讲移进-归约分析和句柄。讲怎样识别可归约的位置。
- 8自底向上分析（下）Bottom-Up Parsing II
讲 SLR 分析表的构造和分析过程。用例子演示自底向上分析器的运行。
- 9语义分析与类型检查Semantic Analysis and Type Checking
讲作用域和符号表。讲类型系统、类型规则和类型检查的实现。
- 10COOL 的类型检查Cool Type Checking
讲静态类型与动态类型的关系，以及 COOL 的 SELF_TYPE。讲类型检查中的错误恢复。
- 11运行时组织Runtime Organization
讲程序运行时的内存布局：活动记录、全局变量和堆。讲对齐和栈机器模型。
- 12代码生成Code Generation
讲把表达式翻译成汇编代码的方法。讲临时变量和对象在内存中的布局。
- 13操作语义Operational Semantics
讲用操作语义精确定义程序的含义。给出 COOL 表达式的求值规则。
- 14局部优化Local Optimization
讲中间代码和基本块。讲基本块内的优化和窥孔优化。
- 15全局优化Global Optimization
讲数据流分析。用常量传播和活跃变量分析两个例子说明全局优化。
- 16寄存器分配Register Allocation
讲干涉图和图着色寄存器分配。讲溢出（spilling）的处理和缓存的利用。
- 17垃圾回收Garbage Collection
讲自动内存管理的原理。比较标记-清除、停止-复制和引用计数 3 种方法。
- 18Java 语言专题Java
用 Java 回顾课程中的概念。讲 COOL 没有的语言特性，例如异常、接口和线程。