编译原理大家是怎么学习的？

[paranoiddemon]

非科班，最近在看 Enginnering a compiler 。看第二章 scanner 部分讲正则和自动机还勉强能理解。 第三章 parser 讲 CFG 引出了一堆符号和概念，感觉完全看不明白。

不知道大家是怎么学的，有没有更基础的视频课程推荐或者其他更入门的书推荐的？

[ipwx]

楼主觉得不明白，是因为楼主假设这里的定义是别人用过的，肯定有更详细的定义。但其实。。。

这里就是完整定义了啦！
====

读过论文的都知道，论文里面对于新符号的定义也就这么点篇幅。

[ipwx]

顺便这里其实定义了这些符号。。。

[ipwx]

不同文献的定义其实各有不同的，没有 universally consistent 的定义。读这种文献的一个重要技能就是快速适应新的符号系统 2333

[MeatIndustry]

B 站搜索斯坦福编译原理。
这个确实抽象的一批，如果能亲自做个根据 CFG 解析的 Parser，则好理解的多。

[zjsxwc]

额，以前我是看中文教程， 裘巍《编译器设计之路 》设计 pascal 的书， 当时龙书我也看得头疼。

[echo1937]

楼主是学生还是工作了，学习编译原理是爱好还是工作需要

我学了好几次了，都没坚持下去。

[Cola98]

如果只是为了做东西的话，就可以跳过这些定义，直接上手做就行了

[ch2]

根据我的学习经验，编译原理你学学 LL(1)就行了，LR 的资料非常少
github 上能按教科书级别把 LR 语法分析器代码实现的稍微像点样的项目一只手就数的过来
学别的至少你都有很好的参考，编译原理到实际用的时候通常都是离底层词法跟语法分析器很远的库直接调就行了
是我去解决能用到编译原理的问题，我肯定直接正则表达式+yacc 就一把梭了，LALR(1)的算法跟原理细节学了你也没多少机会复盘，不像别的课程可以常学常新

[paranoiddemon]

@echo1937 工作了。属于是爱好吧，比较好奇高级程序语言是怎么变成机器指令的。确实要学下去难度比较大

[paranoiddemon]

@MeatIndustry 好的，感谢。我周末找来看下

[paranoiddemon]

@ipwx 感谢回复，就是以前没看过看 CS 理论的文献。突然很多符号，有点适应不了

[Junzhou]

我毕业了之后就再也没有看过编译原理了。。。

[ch2]

顺带提一句，排行榜里排得上号的编程语言的编译
为了追求灵活性跟性能，基本上都是用非常特化的方法处理的，一门语言一个 case
你在教科书上学的通用编程语言语法分析器的设计，在实际中只是非常基础并非不能不用的那种
不像你学网络那就绕不开 socket 、epoll 这些，基本上可以说学了就是屠龙

[paranoiddemon]

@ch2 其实我还不太清楚 LR LL 是什么，不过你的建议我先记着

[paranoiddemon]

@ch2 好的，非常感谢你提供的信息，工作中目前确实甚少用上编译器相关的知识，主要还是因为个人兴趣。加上本来本科也没上过相关课程，还是希望知识体系稍微完整一些。

[misaka19000]

有一本书叫做《自己动手写虚拟机》？具体名字不记得了，日本人写的，个人觉得还不错，相关的内容也做过一些笔记：
https://www.nosuchfield.com/2017/07/16/Talk-about-compilation-principles-1/
https://www.nosuchfield.com/2017/07/30/Talk-about-compilation-principles-2/

此外我之前写过一个解析四则运算的小玩意儿，楼主有兴趣可以看看：
https://www.nosuchfield.com/2018/10/22/Implementing-four-arithmetic-operations-with-golang-compiler/

[misaka19000]

再给楼主贴一些资料

https://pandolia.net/tinyc/index.html

[paranoiddemon]

@misaka19000 看了下这个似乎没那么理论化。谢谢！

[Exin]

动手做一个最简单的，就学会了

[kuro1]

写个 PL/0 编译器

[Mistwave]

https://craftinginterpreters.com/
这本不错，最近看了一多半了，推荐一下，web 版免费看。
没那么理论，learn by doing
作者是大佬，以前写过游戏设计模式那本经典

[ch2]

@paranoiddemon #18 这个用的是递归下降，优点是代码量可以很小，缺点是语义耦合在了代码动作里。比如我要做计算器，只做加减乘除当然很简单，但是当我想要分阶段完成支持括号、阶乘、指数、对数......的时候，用标准的 LL 或者 LR 分析法，只需要改文法的产生式，然后再一条一条搞定语义子程序就好了。递归下降则是人力把各种 case 的处理的语义翻译成代码，除非你是对语义非常熟悉的老编译器要不然是很难 debug 的

[Martin9]

@misaka19000 #16 《 30 天自制操作系统》， 作者川合秀实

[DianQK]

支持一下楼上，可以考虑 自己动手实现 Lua + https://craftinginterpreters.com/ 一起看，有一些重叠内容，但也有不少补充内容。
自己动手实现 Lua 这本因为一些原因我只看到 17 章，后面会回来再看
正在看 craftinginterpreters，目前看到了 24 章

这两本非常值得一看，语法分析那里基本都用了递归下降的方法，这个相对其他算法似乎会容易一些（而且似乎现代的语言都优先使用递归下降，这个不知道，书里这么说的）。

截图的这个符号，楼主一定得突破，这是理解的关键，图片中的 Paren 和 Bracket 看起来会互相转换有点烧脑，但这里并非互相转换，**只是解析的语法内部可以再套这个结构而已**。就像这样 ([1+2]) 或者 [(1+2)] 都是合法的语法。

craftinginterpreters 里面会有 decl （声明变量） -> stmt （普通语句） -> block （代码块） 的转换。

block 里面也可以套 decl 嘛，所以会有类似图片那样的烧脑的结构，是个（递归）解析的规则。

> 另外之前看过虎书，说实话跪了。。不过现在再看可能会好一些。

我的部分书单供参考： https://trello.com/b/IkJcQ7cp/2021-study

[misaka19000]

@Martin9 是的，确实是这本，感谢提醒

[learningman]

我现在就在边哭边看龙书。。。

[misaka19000]

@Martin9 抱歉，弄插了。。。这个是自制操作系统的，楼主要的是自制编译器的😂

我又找了下，应该是这本《自制编译器》：
https://book.douban.com/subject/26806041/

[ctrlaltdeletel]

最近看了本 [自己动手实现 Lua]( https://book.douban.com/subject/30348061/) 还挺好看的。内容涉及 lua 解释器的前端和后端虚拟机。书里面代码从头实现出来，实践性很强。

[PythonYXY]

对于符号和概念理解有困难的话可以参考下《离散数学》以及《形式语言与自动机》

[aasdkl]

我编译原理是大学的时候选修的

虽然没有好好听课，都是后面做大作业的时候自己看龙书（中文的）……但是在讲例子的时候都有认真在听

所以我觉得在学习自动机分析器这些内容的时候，有个视频一步步带着，就像 debug 一样还是比较好理解的

[Rwing]

能把编译原理讲好的网课太少了

[zke1e]

Enginnering a compiler 写得已经很好了，这种经典书籍都是要读很多遍才能慢慢理解的

[ipwx]

现在的编程语言很少用递归下降的方法了。

更多的是类似于 PyParsing 那种自顶向下回溯搜索的方式。。

[ipwx]

现在的编程语言很少用递归下降的方法了。
=>
现在的编程语言很少用 LL LR 这类的方法了。

[pisc]

看不懂。。。就跳过呗。。。Parser 和后面的中后端没啥关系，拿到 AST 就行了

[pisc]

说实话，学习编译原理，私以为可以很简单，比如可以看看 SICP，先从小的东西写一遍，就对 PL 很多东西有点初步的认识了，之后再挑具体的兴趣点深入就行了，传统编译原理的书都比较工程、具体、复杂化，对新手非常不友好，导致很多新手学编译原理连 Parser 都走不过（看看楼上的评论），实际上，用 Scheme 这种半结构化语言，Parser 是不需要花什么精力的，也能更快迈入到中后端有意思的东西。

[Orlion]

网易云课堂有个视频： https://study.163.com/course/introduction/1002830012.htm ，可以跟着敲一遍代码应该就懂了，再回头看各种编译原理的理论就好懂了。by the way，前端学完了感觉就那么回事，无非就是一些算法，真正的星辰大海还是后端😄。

[Hconk]

看过自己动手实现 Lua 感觉还行，书上是用 go 实现的，可以自己用别的 C++或者别的语言实现一遍。

[secondwtq]

实际上大多数常用的语言实现前端用的都是手写递归下降。原因无非就是方便 hack，灵活。
不过也有例外，比如 OCaml 和 Haskell 貌似都是用的自家的 generator 。
自己玩可以用 parser combinator 。所以你把这块绕过去也无所谓，后面有的你看。

编译方面最牛逼的书私以为是 Optimizing Compilers for Modern Architectures，这书能让你了解最牛逼的那些编译器（传统意义上）都在做些什么。

[xbtu]

作为看过编译器源码的我说下自己的经验：
1：看两遍龙书，看懂大致的内容。
2：找一个简单的，功能齐全的编译器源码研究-比如上面提到过的 lua 源码(lua5.15 就好，再高了，基础不牢，太费劲）
经过这两布下来，你就基本上搞清楚了一个编译器的大致内容。shankusu.me 这个网站有 lua 编译器源码相关的内容，可以上来看看。

[levelworm]

还有一本书，game scripting mastery，手把手教你写一个脚本语言加虚拟机。

[swsh007]

浙大有出过一本讲 lemon 的
纯粹是从代码开始刷
我觉得比啃各种动物书要好理解多了

[pcslide]

很正常，编译原理前面的基础知识，如果做为计算理论的一部分在大学上，可能会讲 1 到 2 个月，但是在上编译原理的时候只花两周就带过了。。。。
建议参考 J. Glenn Brookshear 的 Theory of Computation，这本写得简单易懂
如果找不到上面这本书，找 Michael Sipser 的那本（有电子版）也不错.

当然有一个捷径，如果你数学有一定基础，就是直接去看 Donald Knuth 写的关于 LR parser 的原文 On the translation of languages from left to right，这文章基本是从头讲起，写得简洁易懂，从头到底看下来，弄懂 7 成，其他基本就不用看了。

[levelworm]

@DianQK 惭愧，我之前看 craftintepreter 也是卡在 CFG 那里了。他说什么要按照顺序来排我就一直没想明白这个。

[namelosw]

强烈推荐先看这本 Crafting Interpreters http://craftinginterpreters.com/ 写得很简单易懂。前半截是一个解释器，后半截 是一个 bytecode VM，而且该接触的都接触了，大部分东西都既手写又简单，很完整。

Engineering a compiler 我还没看，但是你 CFG 就卡住了后面应该很难看下去，先把 Crafting Interpreters 快速看完做一遍。

---

具体说 CFG，就是比正则稍微强力一点，可以递归引用规则的语法而已。不用特别纠结你发的这些 formal 定义到底懂不懂，接着往后走，直接看一些实际 BNF 的例子，能照猫画虎地翻译成 recursive descent parser，写一遍之后就懂了。

[namelosw]

@levelworm

> 惭愧，我之前看 craftintepreter 也是卡在 CFG 那里了。他说什么要按照顺序来排我就一直没想明白这个。

top down 和 bottom up ？不用太纠结这个，直接看他写的 recursive descent parser 代码就行了。

这个其实是个简单算法问题，recursive descent 本质上是用一个 N 叉树的 DFS 生成一个 AST，比如你看 binary expression 之类的解析，其实就是二叉树的后序遍历。

因为是递归，递归其实就是一个隐式的栈运算，所以看着有点上下反着的感觉，但是后序遍历比较适合生成树，因为可以接 children 的返回值。

从上到下递归调用，所以叶子节点优先级最高，但是人习惯的理解逻辑是从上到下，从整体到局部的。所以理解完代码，回头再看对应的 BNF 就很好理解了。

[levelworm]

@namelosw 多谢，我是这里没明白：
https://craftinginterpreters.com/parsing-expressions.html
（上面半页基本的 CFG 还是很简单的）

引用开始：
Each rule here only matches expressions at its precedence level or higher. For example, unary matches a unary expression like !negated or a primary expression like 1234. And term can match 1 + 2 but also 3 * 4 / 5. The final primary rule covers the highest-precedence forms—literals and parenthesized expressions.
引用结束

他说的 precedence rule 我明白，就是优先度的问题，比如说加减乘除，乘除高于加减。但是什么叫做 each rule here only matches expressions at its precedence level or higher?

这是他最后的结果，能够看到每一行实际上都引用了下一行的东西：

expression → equality ;
equality → comparison ( ( "!=" | "==" ) comparison )* ;
comparison → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term → factor ( ( "-" | "+" ) factor )* ;
factor → unary ( ( "/" | "*" ) unary )* ;
unary → ( "!" | "-" ) unary
| primary ;
primary → NUMBER | STRING | "true" | "false" | "nil"
| "(" expression ")" ;

我感觉他这里很巧妙的就把之前比较复杂的东西，比如说 expression 简化成 equality 了，但是对于我这个看的人来说，似乎就需要一个个调用下去，才能真正知道这行到底对应的是什么东西。

[levelworm]

接楼上。我现在又看了一下，是看懂了，但是你让我自己推出来这个，我就有些困难了，不是完全做不到，而是想不到这么做。

[ch2]

@levelworm #47 文法产生式，你直接拿来用就行了，设计的话需要你有经验才能设计的出来复杂语言的规则。你想自己搞的话可以先从 json 开始做一个解析器，标准 LL/LR 的好处是算法框架搭好了，切换到新语言只需要重新写产生式就行了

[levelworm]

@ch2 明白了，看来我硬着头皮看下去就行了。我之前看过另外一本书，好像就不是用这个办法，用的是状态机好像。

[namelosw]

@levelworm

> 但是什么叫做 each rule here only matches expressions at its precedence level or higher?

意思就是说优先级低的（也就是 BNF 靠上的、行数小的）可以兼容他自己那行和优先级更高的那行（也就是 BNF 靠下的，行数大的）。比如调用 factor，它不仅自己可以解析乘除，而且还可以递归解析 unary 和 primary，但是他不能解析 term 。

> 我感觉他这里很巧妙的就把之前比较复杂的东西，比如说 expression 简化成 equality 了，但是对于我这个看的人来说，似乎就需要一个个调用下去，才能真正知道这行到底对应的是什么东西。

这个就是 recursive descent 的特点，因为 CFG 是可以递归嵌套的（ expression 里面有 binary，binary 里还能有 binary ），我们用的编程语言的表达式是可以互相任意无限嵌套的，所以需求就是递归的，如果不这样一层层调用其他的方式其实看起来更复杂。如果 BNF 没有这层递归，那么就只能得到一个比 basic 还 basic 很多的语言了，写起来可能跟汇编一样。

至于实现 BNF，其实本质上就是照着 BNF 结构做一个 N 叉树 DFS，而且代码很像 BNF 本身很直观。

private Expr equality() {
Expr expr = comparison();

while (match(BANG_EQUAL, EQUAL_EQUAL)) {
Token operator = previous();
Expr right = comparison();
expr = new Expr.Binary(expr, operator, right);
}

return expr;
}

其实就和平常刷 LeetCode 差不多，只不过多了 match 判断到底该用几叉树和构建哪种 AST：

fn traverse(root) {
left = traverse(root.left)
right = traverse(root.right)
return AST(left, right)
}

如果也就是说，上面的 equality match 的结果为 true 时，这段代码的骨架等于二叉树后序遍历，就在原地建起来 Binary：

fn equality() {
left = comparison()
right = comparison()
return Binary(left, right)
}

如果 match 为 false 时，那就交给子规则去递归，有点像链表（一叉树）遍历但不干活，有点像 LeetCode 那种删除链表后 N 个节点那种题里，前面节点 length - N 个节点无操作只递归一样：

fn equality() {
exp = comparison()
return exp
}

可以尝试做一下二叉树的序列化和反序列化，还有根据前序中序 / 中序后序结果反推二叉树的题。然后把这几道题扩展一下变成多态，其实就能得到 recursive descent 了。

本质上就是序列化字符串或者源码本身是一个隐式树，你控制代码递归遍历这个隐式树来创建一个真树。如果你把 N 叉树的遍历搞熟了，假如你从来没听说过 recursive descent，有人给你讲明白 BNF 的需求，你很可能也会凭空发明出 recursive descent 。

[err1y]

我最近也在学，给你两个我看的资料
[自己动手写编译器]
https://pandolia.net/tinyc/
[编译原理（哈工大）-哔哩哔哩] https://b23.tv/ceo4sd

[zxCoder]

硬着头皮看肯定能看明白，但是如果不用的话，也没啥用，很快就忘了

[DianQK]

@levelworm 优秀，现在我也只是可以看懂，让我设计一个那只能设计出一个辣鸡。
后面的章节会不断增加这个语法规则（就更复杂了），不过本质上还是不变的，某个规则是可以向下（规则）解析的，（也可能向上，向上就是递归了，比如 primary 又回到 expression 这个）
PS. 11 13 17 22 23 24 几个章节看起来可能也蛮辛苦的，其中 17 的 Pratt parser 跟 BNF 差不多的绕 /带劲，层主加油

[loryyang]

先问问自己为啥要学。。。说实话，知识是很多的，具体学什么要好好选择一下
我工作快十年了，至少我觉得这个东西作用不大，学编译原理还不如去学 linux 的源码，有本书的，不记得名字了。里面写了各种系统里面的设计，包括缓存、分页，CPU 调度等设计原理，这个对你设计好一个系统真的帮助挺大的

[jones2000]

大学里面学的。计算机专业必修课， 上了 2 个学期。毕业以后再找些开源的编译器看下，一般没什么问题。

[weiwenhao]

@namelosw +1 我也是看了这本，照着做最后就是一个解释器+vm

[zouzou0208]

@misaka19000 感谢。

[whosesmile]

@Mistwave 我虽然也看英文文档，但是一般是基本概念已经有了的情况，再去看文档都是查细节或者深入了解下，通常不会再概念还不了解，大脑基本空白的状况下去读，那样理解太累，各种专业词汇和术语，这和读英文小说和诗歌不一样，我也读不下去，毕竟英文很一般。
所以借这个机会问一个一直以来的疑惑，你们的英文都怎么学的？是双语成长环境？还是留学有了氛围后天努力的？

[whosesmile]

@loryyang 有用的，比如我一直好奇 Mustach 基于字符串的模版引擎和 Vue 、React 这种基于数据结构的 DOM 引擎在程序上如何实现的，解析思路怎么设计出来的，模板语法怎么分析的，有什么差异；这些没有编译原理的功底，去理解这个代码太费力了，我不是计算机专业毕业的。

[loryyang]

@whosesmile #60 嗯，如果要了解这些，那编译原理很有用的

[dog82]

大学 72 课时的编译原理，只讲完了语法分析器，上课完全听不懂，我硬头皮啃书，因为如果挂科可能就没法毕业了。最后老师大放水给我打了 90 分。

[chenyu0532]

实话实说：我没看过 /学过编译原理，我是真的用不上啊，对我来说好深奥啊。
(感觉刷刷 lleetcode 挺好的)

[2i2Re2PLMaDnghL]

SICP 第五章我也没能仔细看下去（

[agagega]

通常编译器会分为前端、中端、后端三个部分，这种划分不是拍脑袋，而是因为三个阶段的目的有明确的不同：前端是把源代码字符串转换为结构化数据，中端是针对变形后的结构化数据反复做优化，后端是从优化后的数据生成真实的机器指令。

为什么你提到的定义这么复杂，是因为它是一种严格的数学表示。直观理解的话，这个文法就相当于一个树形结构，其中只有某些类型的节点可以作为根。不清楚楼主是否会写正则表达式，正则的本质是有限自动机，从上一个匹配到的字符到下一个，就是自动机状态的跳转，而* ? +这些特殊符号，表示的无非是这种跳转的方向不再是下一个而是自己。写一个最简单的正则匹配引擎可能也就一百行代码。正则表达式能够涵盖的文法被称作正则文法。

直观理解，上下文无关无法比正则文法复杂的本质在于，它支持递归，而正则文法不支持。所以在有限自动机之外，还需要一个栈，才能完整地保存当前解析的状态。一个最简单的例子：你有没有做过那道「检查字符串正反括号是否匹配」的编程练习题？这道题看起来不需要复杂的解析，是因为它的状态过于少，不需要用自动机表示。但如果把题目改成 [] () {}的任意嵌套，大概就可以领会这个语法解析的过程在干什么。

前面说了语法定义是一棵树，那按照树的结构从上往下自己写代码去逐个字符解析的过程，称为递归下降。在常见的语言中，函数的调用层次本身就暗含了栈，所以我们不再需要一个自定义栈去存储当前解析的层级状态。但由于代码是手写的，所以整个过程中我们可以夹带任意的数据结构，这也使得手写的解析器在实际应用中几乎能处理任何奇怪的语法。而书上提到的 LL/LR 这些理论，其实是为了将语法解析这件事通用化——给程序一套语法定义，程序就能按照你的定义去跑，最后返回结果。个中差别有些类似「写一段代码解析一个浮点数的字符串」和「写一个正则引擎，然后给它传一个浮点数的正则表达式，解析字符串」。在理论上，语法分析这块有很多经典的算法；而在实践上，也有很多实用的工具，从语法生成器到语法组合子，等等。

语法解析结束以后，我们必然想要一个表示源码内容的数据结构，而不仅仅是一个表示源码是否符合文法的布尔结果。拿到以后，编译器会做若干自定义的语义检查（比如类型是否匹配）和前端处理（比如在必要的地方插调试信息）。其实到这一步，通过对这颗语法树进行模式匹配，编译器已经可以生成出最后的指令了。但为了更高级的优化，编译器往往会引入一些新的中间表示形式。这些形式通常遵循某种特征（比如每个量只被赋值一次），以减少后续分析的复杂度。编译器的优化，其实更像是「写一段新的代码，比原来的代码更快，但功能保持一致」。很多抽象的优化发生在这个阶段：减少循环中的代码，把循环操作变成向量操作，重新调整分支的关系…

然后到了后端，就会依赖更多的平台信息了。这个阶段，会做很多可能每个硬件平台 /操作系统都不一样的事情：如果移位真的比乘法更快，那就把合适的乘法优化成移位；不同平台的 ABI 要求调用函数或者加载全局变量时有一些额外的指令，也是在这里加上；用一个复杂指令匹配一组复杂操作；更好的分配寄存器以减少寄存器复制和内存读写；重排指令以适配流水线等等。最后吐出的指令就是真的汇编了。

所以后端和中端的知识，理论上比前端更多。前端更大的成就感其实是自己写了一个解析器，拿到了这个语言的结构化表示，然后就可以做任何事情。而且后端和中端在简单情况下确实可以省略，比如你解析了一个 XML，想从它生成 JS 代码，那解析好以后直接遍历这棵树按照规则输出就好了。再往后面，其实就是玩各种新的算法，以及在实践上整新活。

[Mistwave]

@whosesmile 无他，就硬啃。啃三五本英文专业书之后，就会有质变了。
双语环境 /留学当然好，但是大多数人是没这个条件的😂

[joydee]

当代编译器最难啃的部分已经不是 scanner 和 parser 了，现在的难点都集中在后端的 Optimization 中了

[namelosw]

@whosesmile
> 所以借这个机会问一个一直以来的疑惑，你们的英文都怎么学的？是双语成长环境？还是留学有了氛围后天努力的？

你可以每个东西中文英文的资料都试着查一下，比较入门的知识可能网上到处都有，但是随着知识的深入你会发现英文虽然读起来稍微费力气，但是内容要好一些，经常深入浅出一语中的，所以坚持中英文混着搜索，就会发现英文越来越省时省力。

基本到后来很多词汇都是先知道的英文，根本不知道中文是啥，比如 tagless final 之类的。

> 基于字符串的模版引擎和 Vue 、React 这种基于数据结构的 DOM 引擎在程序上如何实现的

小小纠正一下，其实 React 没有模板，是靠 JSX 实现的，也就是一般用 babel 插件，除了很早期的原型之外早就没有自己的 transpiler 了（感觉 14 年就不咋用了）。也就是说 VDOM 和 「模板完全没有关系」，因为可以直接用 React.createElement 是完全一样的。

[Remode]

我当时是用 lex,yacc,c++,llvm 做了个 c 语言子集（自己定义）的编译器，算是基本用上了相关知识。。。收获还是不错的