编译原理
Compiler Principles
📖这门课到底讲什么
编译原理研究如何把源程序翻译成目标代码，主线是前端与后端两段：词法分析（有限自动机与正则表达式）、语法分析（上下文无关文法、LL 与 LR 分析、自顶向下与自底向上）、语义分析（符号表、类型检查）、中间代码生成与三地址码、代码优化与目标代码生成。它把形式语言与自动机理论落到工程实现上，是理论与实践结合最紧的课程之一。学完你应能手写词法分析器与递归下降语法分析器、用 LR 方法构造分析表、生成中间代码并实现常量传播与死代码消除，最终完成一个能编译小型语言子集的编译器。
🎯为什么必须学好
编译器涉及的状态机、语法树、符号表、优化，在工程中无处不在：JSON/正则解析、DSL 与配置语言、SQL 解析器、模板引擎、IDE 的语法高亮与自动补全都是它的应用。面试中被问正则表达式原理与回溯、AST 的作用、语法糖如何被展开，都是这门课的直接考点。考研 408 中它是独立的四十五分科目之一。此外与编程语言设计与类型系统的关系密切，想读研做 PL 或系统方向必须扎实。
📌核心知识清单
- 编译流程与前端后端划分：词法、语法、语义分析，中间代码与优化，目标代码生成
- 词法分析：正则表达式与有限自动机（NFA 到 DFA、DFA 最小化）、手工构造词法分析器与 lex 工具
- 语法分析基础：上下文无关文法、推导与语法树、二义性与消除、左递归消除与提取左公因子
- 自顶向下分析：LL(1) 文法、FIRST 与 FOLLOW 集合、预测分析表的构造、递归下降实现
- 自底向上分析：LR(0)、SLR(1)、LR(1) 与 LALR(1) 项目集构造、移进归约冲突的解决、yacc/bison 的使用
- 语义分析：属性文法与语法制导翻译、符号表组织、类型检查与作用域处理
- 中间代码与运行时环境：三地址码、四元式、控制流语句的翻译、运行时存储分配（活动记录、静态链与访问链）
- 代码优化与生成：基本块与流图、数据流分析（到达定值、活跃变量）、常量传播、公共子表达式消除、寄存器分配与指令选择
✍️怎么学（可执行步骤）
- 以《编译原理》（龙书）为主线，重点第2至6章与第8、9章，同时用陈火旺版或《编译原理实践》补齐国内考试风格
- 作业不要用现成生成器糊过去：先手写一个支持算术表达式与 if/while 的词法加语法分析器，再学 bison/flex 对比效率与可维护性
- 用 Python 或 Java 从零实现一个能编译玩具语言（含变量声明、赋值、if、while、函数、打印）到三地址码的编译器，这是本课唯一真正有效的检验方式
- 读一本工程实现书：《自制编译器》或《两周自制脚本语言》，跟着写出可运行的编译器，把抽象表格变成能调试的代码
📚推荐教材与书籍
领域圣经，词法、语法与语义分析部分讲解最权威，中后段的优化与数据流分析可逐步精读
国内教材，与考研 408 题型接近，重点词法、语法分析与语法制导翻译章节
虎书，实践导向，直接从工程实现讲起，适合配合做编译器项目
用少量代码实现完整解释器，成就感强，适合作为动手入门第一站
🎬视频课程 / 公开课
🌐网站与文档
观察真实编译器对优化选项的响应，把课堂上讲的优化与你写的代码对应起来
工业级语法分析生成器，写 DSL 或解析配置时的实用工具
🐙GitHub 开源资料
主流语法分析器生成器，文档与示例丰富，适合写课程项目时借用其设计思路
工业级编译基础设施，读它的 IR 设计与优化 Pass 能理解现代编译器的架构
GCC 镜像，可查阅前端与优化实现，适合进阶研读
🧪动手实践任务
实践 1
用 Python 实现一个小型词法分析器与递归下降语法分析器，能解析含加减乘除与括号的表达式并计算求值，输出语法树
实践 2
为一个玩具语言实现完整的前端：变量声明、赋值、if-else、while、函数定义与调用，生成三地址码并输出到文件
实践 3
在中间代码上实现两个优化：常量折叠与死代码消除，用同一段测试程序对比优化前后的指令条数
实践 4
用 flex 与 bison 重写上述词法与语法分析部分，比较手工实现与生成器方案在代码量与可维护性上的差异
🧾考试与面试
💼 面试会怎么考
高频：正则表达式的实现原理（NFA 与 DFA、为什么某些正则会指数级回溯）、如何自己写一个表达式解析器；词法分析与语法分析的分工、为什么语法分析用上下文无关文法而不是正则；三地址码与 AST 的作用、语法糖在编译器内部如何处理；数据流分析能解决什么问题、常量传播与死代码消除怎么做。工程岗位里手写解析器是常见考题，DSL 与配置解析也常被追问。
📝 期末与考研怎么过
期末重点：正则到 NFA、NFA 到 DFA、DFA 最小化、消除左递归、求 FIRST/FOLLOW、构造 LR 分析表、语法制导翻译生成三地址码，题量与推导步骤都很大。备考策略：把每类构造题都做成手算模板限时训练，考前把这些题型完整做十套以上。目标八十分以上；这是最需要动笔练习而非背诵的一门课。
⚠️ 常见坑
- 把编译原理当纯理论背概念，不动手写编译器，结果 LR 分析表会填却写不出一百行可运行的解析代码
- 构造 LR 项目集时移进归约冲突处理不当，不理解 LALR 合并项目集带来的冲突风险
- 忽略语义分析与符号表，以为语法正确程序就对，遇到类型检查与作用域问题完全没准备
- 实验依赖 bison 等生成器自动完成，不理解生成的代码逻辑，面试被追问原理即露馅