编译原理Compiler Theory一直被视为计算机专业的“硬核必修课”。很多人学完数据结构、操作系统却在编译原理面前犹豫了很久——它不像写 Web 接口那样能立刻看到效果也不像刷算法题那样有清晰的反馈。但在实际工程中无论是写业务代码时排查构建报错还是研究框架里的 AOP 和字节码甚至是用 ANTLR 定制一门 DSL背后都离不开编译原理的基础认知。斯坦福大学的 CS143 课程Compilers是国外公认最适合入门的编译器课程之一配套的 Cool 语言项目完整覆盖了词法分析、语法分析、语义分析、代码生成等核心环节。最近整理了一份带中文配音、去掉了静音空白的精讲版本资源配合课程讲义和参考编译器学习体验比纯英文视频顺畅不少。这篇文章就把我完整跟完课程后的学习路线、核心知识点、项目实操和排错经验整理出来希望对想入门编译原理的你有所帮助。1. 背景编译原理是什么为什么值得学1.1 从一个简单问题说起很多初学者会有这样的疑问我平时写代码根本用不到编译器为什么还要学编译原理如果把计算机世界比作一个大型工厂CPU 只认识机器指令而我们日常使用的高级语言比如 C、Java、Python都是给人阅读和编写用的。编译器就是连接这两者的“翻译官”。当你在 IDE 里按下 Run 按钮整个过程并不是一瞬间发生的。它内部要经历把高级语言拆成最小单元、按语法规则组装成结构、检查类型是否匹配、生成中间代码、优化、最后生成目标机器码等环节。这些环节正是编译原理课程要讲的内容。一个典型的例子是 IntelliJ IDEA 或 VS Code 的语法高亮和错误提示。IDE 之所以能在你还没运行代码的时候标出语法错误是因为它内部内置了一个“迷你编译器”不停地在后台做词法分析和语法分析。理解编译原理你对这些工具的认知就不再停留在“能用”的层面。1.2 编译器的整体工作流程编译器的工作可以分成前端、中端、后端三个大部分这也是斯坦福 CS143 课程的主线前端包含词法分析Lexical Analysis、语法分析Parsing、语义分析Semantic Analysis。它把源代码变成抽象语法树AST并做类型检查。中端包含中间代码生成Intermediate Code Generation和优化Optimization。它把 AST 转换成与机器无关的中间表示再进行常量折叠、死代码删除、循环优化等操作。后端包含指令选择、寄存器分配、指令调度等最终生成目标平台的机器码。最经典的一句话是编译器的前端解决“这个程序是否合法”后端解决“如何高效运行”。理解这个流水线后面学任何具体算法都会有定位感。1.3 斯坦福 CS143 课程特点CS143 是 Stanford 大学的经典课程课程主页公开了完整的 slides、assignments、reference compiler 和 exam。它有几个明显特点使用自行设计的教学语言 CoolClassroom Object-Oriented Language。这是一门精简的面向对象语言语法简洁但包含类、继承、方法调度、类型检查等真实语言的核心特性非常适合在一学期内实现完整编译器。课程强调“动手实现”。每个 Project 都对应编译器的一个阶段从词法分析器一直写到生成 MIPS 汇编。授课讲义质量很高尤其对正则表达式、有限自动机、LL(1)、LR(1) 等经典算法的讲解非常清楚。对于英语跟读有压力的同学中文字幕或中文配音版本可以大大降低理解门槛。这里提到的“中配·去静”资源就是把原视频中的停顿、静音片段做精简处理后的版本语速和信息密度更贴近国内同学的学习习惯。2. 学习环境与资源准备2.1 需要的软硬件环境斯坦福 CS143 的原版 Project 以 C 编写为主但很多同学在 Windows 上配置 C 环境会卡住。根据我的实验最稳妥的组合是项目推荐方案操作系统Windows 10/11、macOS、Ubuntu 均可虚拟机可选使用 VirtualBox 安装 Ubuntu方便编译 Cool 项目核心语言C 或 Python如果自选实现方式辅助工具flex、bison、g、make其他工具Git、VS Code、PlantUML画图用如果你是初学者我建议优先使用 Ubuntu 虚拟机避免在 Windows 原生环境里折腾 flex/bison 依赖。版本不需要刻意追求最新能正常运行 flex 和 g 即可。下面给出 Ubuntu 下安装依赖的命令sudo apt update sudo apt install -y g make flex bison git在 macOS 下可以使用 Homebrewbrew install flex bison2.2 课程资料与配套教材课程资料主要包含以下几个方面官方课程主页包含 slides、handout、assignment 说明、reference compiler 源码、测试用例这些几乎是唯一的权威资料。配套阅读教材可以选择《Compilers: Principles, Techniques, and Tools》经典龙书或《Modern Compiler Implementation in Java》虎书。斯坦福的课程和虎书的章节结构比较接近建议以虎书为主线遇到不懂的自动机细节再去查龙书。中文配音视频资源主要是方便理解英文授课逻辑不要把它当成全部内容。真正掌握知识还得靠自己动手。另外国内有许多配套资源可以参考哈尔滨工业大学陈鄞老师的编译原理网课对语法制导翻译和中间代码生成讲得非常细致适合中文母语学习者建立整体框架。国内经典教材《编译原理第 3 版》的习题答案和课件在很多高校课程网站可以找到用来巩固课后练习比较方便。注意不要只囤资料不实践。编译原理是一门“看十遍不如写一遍”的课。2.3 如何安排学习节奏以两个月为周期建议按下面节奏推进第 1 周看完课程第一、二讲理解“编译器是什么”掌握词法分析器的构造原理完成 Project 1词法分析。第 2-3 周学习上下文无关文法、自顶向下和自底向上语法分析完成 Project 2语法分析。第 4 周学习 AST 构建、符号表、类型检查完成 Project 3语义分析。第 5-6 周学习中间代码生成、栈帧、代码生成完成 Project 4-5代码生成与优化。第 7-8 周整合全部代码跑通一个完整的 Cool 程序并进行错误处理和优化。这个节奏并不是固定的你可以根据自己的时间调整但一定要保证有“完整跑通编译器”的经验这比只做完某几个作业重要得多。3. 核心知识点拆解3.1 词法分析让计算机读懂字符流词法分析的任务是把源代码字符流转换成 token 序列。比如下面的代码片段class Main { main(): Int { 1 2 * 3; }; };经过词法分析后会变成类似这样的 token 流CLASS(位置1) ID(Main) LBRACE ID(main) LPAREN RPAREN COLON INT LBRACE INT(1) PLUS INT(2) STAR INT(3) SEMICOLON RBRACE SEMICOLON RBRACE每个 token 通常包含三部分类型、语义值、行号列号。工科实现常借助正则表达式描述 token 规则再用有限自动机来识别。课程 Project 1 会让你实现一个类 flex 的词法分析器。如果你用 Python 实践可以先用re模块快速理解整个流程。词法分析的常见误区是试图用词法分析解决语法层面的问题比如括号匹配。括号是否成对属于语法分析范畴不应该在词法阶段处理。词法阶段只负责把字符串切成“单词”不负责判断结构。3.2 语法分析从线性序列到语法树语法分析是编译原理中最难也最核心的部分。它根据词法分析得到的 token 序列结合文法规则构建一棵抽象语法树AST。语法分析有两大派别自顶向下Top-Down从开始符号出发不断展开非终结符最典型的是递归下降分析Recursive Descent和 LL(1) 分析。自底向上Bottom-Up从输入串开始不断归约到开始符号最典型的是 LR(0)、SLR(1)、LR(1) 和 LALR(1) 分析。CS143 课程要求手写递归下降解析器和用 bison 完成 LALR 解析器的实验这对理解两种策略的差异非常有帮助。递归下降的写法比较直观适合手写# context-free grammar 示例 # expr : term ( term)* # term : factor (* factor)* # factor : NUMBER | ( expr )上面这种文法避免了左递归所以可以直接用递归下降实现。需要特别注意递归下降要求文法没有左递归否则程序会死循环。比如直接写成expr : expr term就会导致无限递归必须改写成右递归形式或使用循环结构。3.3 语义分析检查程序是否“说得通”语法分析能确认程序结构合法但还不能判断1 hello是否有意义。语义分析阶段需要构建符号表Symbol Table记录每个变量、函数、类的类型信息然后进行类型检查。以 Cool 语言为例一个合法程序需要满足类型匹配算术运算的操作数必须是整数或浮点数。作用域规则变量必须先声明后使用。继承关系子类方法重写时要保持参数和返回类型的兼容性。语义分析的核心数据结构是符号表通常采用栈式结构进入一个作用域时压入新表。退出作用域时弹出当前表。变量查找从栈顶向下逐层搜索。课程 Project 3 会让你实现一个完整的 Cool 类型检查器。这个过程稍微繁重但完成后你对面向对象语言的类型体系会有非常深刻的理解。3.4 中间代码生成与优化中间代码生成阶段不直接生成目标机器码而是先生成一种与具体机器无关的中间表示。常见的中间表示有三地址码Three-Address Code、静态单赋值形式SSA和虚拟机字节码。以三地址码为例a b c * d可能会被翻译成t1 c * d t2 b t1 a t2然后进入优化阶段。常见优化手段有常量折叠直接把2 * 3简化为6。死代码删除删除永远不会执行到的语句。公共子表达式消除重复计算的表达式只计算一次。循环不变代码外提把循环内不会改变的运算移到循环外。在课程里优化不是强制要求但如果你想拿高分可以参考课程给出的优化思路在局部做几项优化即可。4. 实战案例手写一个四则运算计算器纸上得来终觉浅下面用一个最小的“编译器”来串联前面讲的概念。我们要实现一个支持加、减、乘、除和括号的四则运算计算器输入一个表达式输出计算结果。这个案例体量小但词法分析、语法分析、AST 求值三步全都有非常适合作为第一个练手项目。4.1 需求与设计输入(2 3) * 4输出20整体结构分为三部分tokenizer把字符流转换成 token。parser根据文法构建 AST。evaluator对 AST 递归求值。为了简单直观这里使用 Python 3 实现。版本可自行调整核心逻辑与语言本身关系不大。4.2 词法分析器实现先写 tokenizer把(2 3) * 4拆成LPAREN、INTEGER、PLUS、RPAREN、STAR等 token。import re from dataclasses import dataclass dataclass class Token: kind: str # token 类型比如 INTEGER、PLUS value: str # 原始值 line: int col: int class Tokenizer: def __init__(self, text: str): self.text text self.pos 0 self.line 1 self.col 1 def error(self, msg: str): raise SyntaxError(f{msg} at line {self.line}, col {self.col}) def next_token(self): while self.pos len(self.text) and self.text[self.pos] in \t\n: if self.text[self.pos] \n: self.line 1 self.col 1 else: self.col 1 self.pos 1 if self.pos len(self.text): return None ch self.text[self.pos] if ch.isdigit(): start self.pos while self.pos len(self.text) and self.text[self.pos].isdigit(): self.pos 1 self.col 1 # 简单做一下边界保护 return Token(INTEGER, self.text[start:self.pos], self.line, self.col) if ch : self.pos 1 self.col 1 return Token(PLUS, , self.line, self.col) if ch -: self.pos 1 self.col 1 return Token(MINUS, -, self.line, self.col) if ch *: self.pos 1 self.col 1 return Token(STAR, *, self.line, self.col) if ch /: self.pos 1 self.col 1 return Token(SLASH, /, self.line, self.col) if ch (: self.pos 1 self.col 1 return Token(LPAREN, (, self.line, self.col) if ch ): self.pos 1 self.col 1 return Token(RPAREN, ), self.line, self.col) self.error(fUnexpected character {ch}) def tokenize(self): tokens [] while True: t self.next_token() if t is None: break tokens.append(t) return tokens这段代码的关键点统一通过next_token返回 token调用方不关心内部跳跃逻辑。记录行号和列号方便后续报错。空白字符直接跳过。对数字字符串一次性完整扫描。4.3 递归下降语法解析器实现接下来写 parser。它读取 token 列表使用递归下降算法构建 AST。这里定义三种节点类型分别表示数字、二元运算和括号结构。from dataclasses import dataclass from typing import List, Union dataclass class NumNode: value: int dataclass class BinOpNode: left: Node op: str right: Node Node Union[NumNode, BinOpNode] class Parser: def __init__(self, tokens: List[Token]): self.tokens tokens self.pos 0 def peek(self): if self.pos len(self.tokens): return self.tokens[self.pos] return None def advance(self): t self.peek() if t is not None: self.pos 1 return t def expect(self, kind: str): t self.advance() if t is None or t.kind ! kind: raise SyntaxError(fExpected {kind}, got {t.kind if t else EOF}) return t def parse(self): ast self.expr() if self.peek() is not None: raise SyntaxError(fUnexpected token {self.peek().kind}) return ast def expr(self): node self.term() while self.peek() and self.peek().kind in (PLUS, MINUS): op self.advance().kind right self.term() node BinOpNode(node, op, right) return node def term(self): node self.factor() while self.peek() and self.peek().kind in (STAR, SLASH): op self.advance().kind right self.factor() node BinOpNode(node, op, right) return node def factor(self): t self.peek() if t is None: raise SyntaxError(Unexpected end of input) if t.kind INTEGER: self.advance() return NumNode(int(t.value)) if t.kind LPAREN: self.advance() node self.expr() self.expect(RPAREN) return node raise SyntaxError(fUnexpected token {t.kind})文法对应的表达式expr: term ((PLUS | MINUS) term)*term: factor ((STAR | SLASH) factor)*factor: INTEGER | LPAREN expr RPAREN乘法优先于加法正是依赖expr调term、term调factor的层级关系实现的。4.4 AST 求值器实现最后一步对 AST 递归求值def evaluate(node: Node) - int: if isinstance(node, NumNode): return node.value if isinstance(node, BinOpNode): left evaluate(node.left) right evaluate(node.right) if node.op PLUS: return left right if node.op MINUS: return left - right if node.op STAR: return left * right if node.op SLASH: if right 0: raise ZeroDivisionError(division by zero) return left // right raise ValueError(fUnknown node: {node})至此三个部分已经齐了。把它们串起来def compile_and_run(source: str): tokenizer Tokenizer(source) tokens tokenizer.tokenize() parser Parser(tokens) ast parser.parse() result evaluate(ast) return result if __name__ __main__: test_cases [ (1 2 * 3, 7), ((1 2) * 3, 9), (2 * (3 4) - 5, 9), (10 / 2 6, 11), ] for src, expected in test_cases: got compile_and_run(src) status OK if got expected else FAIL print(f{src} {got} (expected {expected}) [{status}])运行结果1 2 * 3 7 (expected 7) [OK] (1 2) * 3 9 (expected 9) [OK] 2 * (3 4) - 5 9 (expected 9) [OK] 10 / 2 6 11 (expected 11) [OK]4.5 结果说明这个简单的例子说明了一个核心思想编译器本质上只是重复使用“分解 组合”的方式分析程序。词法分析把字符串切成词语法分析把词组合成树求值器递归处理树。斯坦福 CS143 里的 Cool 编译器无非是把NumNode换成了Class、Method、Dispatch等更复杂的节点把evaluate换成了类型检查、代码生成、汇编输出。如果你把上面的evaluate函数换成“输出三地址码”你就得到了一个最简单的中间代码生成器。继续把三地址码换成 MIPS 汇编再交给模拟器运行这就离完整编译器不远了。5. 常见问题与排查思路5.1 C 基础薄弱可以用 Java 或 Python 完成作业吗可以但要注意课程框架是基于 C 的。如果你选择用 Java 或 Python 另起炉灶需要自己处理数据结构的定义AST 节点、符号表、类型绑定。文件读写和错误输出格式。与课程提供测试脚本的对接。建议的折中方案是第一遍用 Python 完成一个简化版比如只支持部分语法第二遍再按课程要求用 C 完成完整版。这样既能快速验证算法逻辑又能最终贴合官方评分框架。5.2 课程里的 Cool 语言怎么运行不起来常见现象报错make: command not found。解决安装 build-essential。运行./coolc提示找不到文件。解决检查是否已经编译参考编译器并且是否在项目根目录下运行。英文路径下没问题中文路径下编译失败。解决尽量使用纯英文路径。make ./coolc test.cltest.cl是 Cool 语言源文件最简单的测试程序就是课程 handout 里的“hello world”。5.3 作业没思路只能抄参考编译器吗参考编译器reference compiler的作用是看输出格式不是用来照抄逻辑。正确用法先用自己的实现跑一个测试文件对照参考编译器的输出差异。调试时用--help或-p等参数查看 parse 树。输出格式不一致时逐字节比对参考编译器的结果。如果卡在某个阶段超过两天建议回头重看对应章节的 slides 和教学视频尤其是 lexing 和 parsing 部分往往是你忽略了一个边界条件。5.4 视频看不完、PPT 看不懂怎么办这是正常状态。编译原理的知识密度高一次吸收不掉很正常。我的方法是第一遍快速看视频建立全局观第二遍对着 PPT 自己画一张编译器流水线图第三遍边写作业边回来翻对应概念。“中配·去静”版资源的好处是去掉了老师等待学生回答问题的静默片段信息密度更高适合在通勤或睡前快速过一遍。但注意它不能替代精读教材和写代码。5.5 常用排错清单问题现象常见原因解决思路flex 报错找不到头文件未安装 flex 或版本过旧使用系统包管理器重装bison 语法冲突太多文法存在二义性检查优先级、结合性定义递归下降解析栈溢出文法带有左递归改写为右递归或循环结构输出格式与答案不一致漏处理行号列号看参考编译器输出逐项对比Python 版本不兼容使用了 f-string 或新语法统一 Python 3.8 以上版本类型检查的继承关系报错类型表构建顺序错误先处理父类再处理子类6. 最佳实践与工程建议6.1 学习顺序先整体后细节不要一开始就钻进自动机算法的深水区。先通过一门语言跑通“从源码到执行”的整体过程建立感性认识。之后再针对每个阶段深入算法细节。推荐顺序视频整体过一遍中文配音版适合此时使用 - 画出编译器总体流程图 - 精读每个阶段的课程讲义 - 动手做对应 Project。6.2 工具链建议手写代码时用 VS Code 配合插件做语法高亮和 Git 版本管理。画 AST 和状态转换图时用 PlantUML 或 draw.io比 PPT 方便得多。测试用例用课程提供的公共用例自己再补充边界用例空程序、非法字符、类型不匹配、除零等。6.3 国内教材和课程的配合使用斯坦福 CS143 是英文语境部分同学在自动机、语法制导翻译这些概念上可能需要中文资料对照。哈尔滨工业大学陈鄞老师的编译原理网课和国内经典教材《编译原理第 3 版》可以作为补充。使用方法是看 CS143 视频时遇到不懂的概念先去哈工大课程找对应章节。课后练习题方面可以结合国内教材的课后答案检验自己理解是否正确。这里要提醒一点答案只能用来核对结果不能代替思考过程。6.4 保持刷题与代码量编译原理的学习曲线陡峭但代码量并不是越大越好。它的核心在于“精准”和“结构”。建议每周保持 10 小时以上的投入其中至少一半时间在写代码或调试。可以参考以下几个方向重写一个简单计算器本文的案例。给计算器增加负数、小数、幂运算。尝试输出 AST 的 JSON 格式方便可视化。用 flex/bison 重新实现一遍词法分析和语法分析。每完成一个阶段记录一篇实践笔记写下踩过的坑和解决思路。很多面试题本质上就是在考察你能不能把一个大规模系统拆解成若干个可以独立实现的模块编译器本身就是最好的训练素材。6.5 结合 Java 生态与工具链如果你未来主要做 Java 后端编译原理的知识不会白学。Java 生态中的 Lombok 注解处理器、Spring 的字节码增强机制、GraalVM 的 Native Image甚至 Java Compiler API都需要理解语法树、符号表、类型检查和代码生成。ANTLR 和 JavaCC 都是基于编译原理设计的解析器生成器学会它们之后你完全可以在业务项目里快速构建配置解析、DSL 解析等能力。7. 总结与后续学习路线7.1 核心收获通过这篇文章你应该理解了编译器的整体工作流程词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成。词法分析基于正则表达式和有限自动机语法分析基于上下文无关文法。递归下降、LL(1)、LR(1) 是学习语法分析必须掌握的算法。AST 是前端分析的产物也是后端处理的输入。手写一个计算器是理解“用代码处理代码”的最小起步项目。斯坦福 CS143 的 Cool 语言项目是把这些理论应用到完整语言的最佳练习。7.2 下一步可以学什么学完 CS143 之后你有几个方向可以选择学习更深入的优化知识SSA 形式、活跃变量分析、寄存器分配、循环优化。阅读 LLVM 官方的 Kaleidoscope 教程用 LLVM 实现一门语言的后端。学习 ANTLR快速生成 JSON Parser、SQL Parser 或自定义 DSL。研究 RPython 或 PyPy 的 JIT 架构理解解释器与编译器的边界。如果你对底层的 Java 生态感兴趣可以从 Java Compiler Tree API 开始研究。7.3 一些鼓励的话编译原理不是一门靠记忆力就能通过的课它需要你在崩溃的边缘反复调试、修正、再调试。但当你第一次看到自己写的编译器把 Cool 源码变成汇编再通过模拟器运行起来的那一刻那种成就感是其他课程很难替代的。哪怕只完成一个“能跑通所有作业的编译器”你的收获也会远超预期。如果你手头正好有那份中文配音的精讲资源不妨从下一周开始按本文的节奏走一遍。