开篇词 | 在真实世界的编译器中游历

作者回复: 恭喜你的成绩！ 你说的血缘分析，是Lineage Analysis吗？我以前搞元数据的时候接触过，看上去很亲切:-)

作者回复: 你问的问题很好，我都有点想针对这个问题展开，写一篇加餐了:) 计算机科学中所用到的数学知识，基本上都体现在离散数学中了。当然，每本离散数学课本的内容不一样，有的多一些，有的少一些。 离散数学其实涉及了好几个数学分支。但这些内容由于不是我们从中学开始学习的那些“经典”的数学内容，所以会显得有点另类。不过，离散数学确实是实实在在的数学，是解决现实问题所需要的数学工具，很多内容还很值得琢磨，在我看来是一些很“高级”的话题。 不过，我们有时会对这些知识的应用场景不清楚，从而学起来有点抽象。而编译原理就为这些数学知识提供了很多的运用场景，我来给你梳理一下： 1.自动机理论 自动机理论是计算机科学的根基。这部分内容很有意思，因为它可能会触发你对一些“终极”问题的理解。首先，是对“什么是计算”的理解。我们成天都用Computer，但计算（compute）的实质到底是什么呢？小学和初中时，我们做算术题，那是计算，这个你能理解；而现在的计算机程序，也声称是在做计算，这就有点难以理解了。你明明只是在用Word做字处理，或者只是在浏览网页呀？为什么说程序在做计算？这个问题再挖下去，你会了解为什么CPU一定会发热，哪怕未来用的工艺再好也没用。会涉及到信息的熵和热力学熵的关系。很有趣。 第二个问题是可计算性问题。图灵设计出图灵机来以后，加上哥德尔，一下子解决了希尔伯特提出来的好几个数学问题。从这里，你能看到数学和计算机科学的关联。计算机一开始就是用来解决数学问题的，比如命题的可证明性问题。 在编译原理中，我们发现词法分析和语法分析过程，等价于某些简化的图灵机的运算过程。比如词法分析，就等价于某个NFA或DFA，所以只要构造出这么一台自动机就行了。 2.形式语言 接着说形式语言。这块也跟数学有很大的关系。因为数学就是一个形式系统。命题用形式系统来做表达，而推理和证明的过程，就是根据一定的规则来对这些形式进行变换的过程。定理的自动证明，一直是计算机科学的一个分枝。还有一个分枝，是自动证明你的程序是否正确。这两个都是用符号、形式做计算。在Matalab和Mathematics里，都有把用符号表达的公式进行推演、化简的能力，很有趣。用这个功能，就可以把你很多中学数学作业给干掉，你想想多好玩。 正则文法、上下文无关文法等，都是形式语言中的文法规则。 学会对符号进行处理，实际上是一种很强的计算机思维。有些计算机语言，如Lisp，擅长做符号处理。这也是Lisp家族的语言特别擅长做元编程的根本原因。因为你的程序就是一堆符号，一些形式。而Lisp语言又可以很方便地处理这些符号和形式。再进一步，对符号、形式的处理能力，也是学习编译原理对你的最重要的赋能之一。当你用正则表达式工具处理一个字符串的时候，你其实就能感觉到这种强大。 3.格理论（Lattice） 在优化算法中，有一个知识点是数据流分析框架。这里会涉及到格理论，而格理论又涉及偏序集、上界、下界等概念。不过不用怕，好消息是，其实你不懂这些数学理论，从直观上也能学会数据流分析框架。 不过格理论确实比较有用，除了数据流分析外，在很多其他地方也会用得到。比如，现代语言的类型系统都比较复杂，而对类型进行运算，也会用到格理论。如果你阅读Julia编译器的代码，在类型处理有关的代码里就可以看到格的痕迹。 4.图论 在中端处理中（主要是基于IR做各种优化），我们经常会用到图这种数据结构，例如CFG等。所以，与图有关的理论就可以发挥作用了。 5.计算复杂性理论 也就是大O有关的理论，要知道什么是NP完全、NP难等概念。在编译中的很多算法是NP级的（比如寄存器分配、指令重排序等），所以寻找合适的启发式算法就很重要，可以降低计算量。 6.一些运筹学知识 在有些算法中，我们会用到动态规划这样的知识。还有的同学问过，寄存器分配是否可以用约束求解的方法来实现。这都是运筹学封面的知识点。 7.Lambda演算等 为了更好的理解函数式编程等概念，你还可能需要用到Lambda演算的一些知识。可以看邱齐（也就是图灵的老师）的一些成果。 再进一步延伸，你可能还要看《范畴论》这样的东西。不过这都是想在这个领域深钻的人的要求，可以写博士论文的那种。硕士论文都不需要钻这么深。 好了，总结起来，编译原理中用到的数学，基本上不是传统意义上的数学，但这些数学也很厉害、很有意思。对离散问题的处理，有时候更复杂。就像运筹学里面，整数规划比线性规划要更难。写到这里，我真的可能扩展一下，写一篇加餐了。你注意课程更新信息:)

作者回复: 两门课都是围绕编译原理，但讲述方式和侧重点不同。 《编译原理之美》是通过手工实现一款编译器的方式，带你了解这个过程中的知识点，循序渐进地讲解，最后才去介绍难度比较高的那几个算法。对编译器前端工具ANTLR的使用也比较多。如果你想学会如何快速实现一个编译器，可以先从这门课入手。 《编译原理实践课》总体的目标，是带你“行万里路”，扩大你的视野和见识。它讲述的方式是先做一些基础知识的概述（概述部分也会注意扩展你的知识面）、然后是研究多个编译器的实现，最后是总结这些编译器的实现，并探讨现代语言的设计。如果你比较想了解真实世界的编译器的情况，可以先从这门课入手。 你的专业是二进制安全，涉及后端的内容会更多，所以我觉得了解真实世界的编译器的情况会有很大的帮助。 因为编译原理的知识点比较多，所以用不同的课程体现不同的侧面。在我的出书计划中，也发现其实仅用一卷书是不能说完的。比如，有的作者用“编译器DIY”的方式就可以写一本书，但对原理和算法体现得就不够；写算法比较深入的书呢，又没有体现当前真实编译器中所采用的技术。

作者回复: 你这个专业，肯定要多了解真实语言的实现。二进制漏洞问题本来就是实现编译器时要考虑的一个因素。比如，在使用内存的时候，要让返回的内存地址没有明显的规律，避免出现漏洞。

作者回复: 又见到sugar！

作者回复: 谢谢你分享自己的使用场景。非常好。我对你的名字有印象:-) 如果有可能，你也可以把自己的设计思路描述一下，我们可以多做一些探讨！ 有具体需求推动，学习会更有动力。

作者回复: 不需要。这两们课是并行关系，可以互相补充。

作者回复: 以前，像Lisp等好几种语言都是编译成c语言，再用c语言的编译器来编译成目标代码。 现在网上也有一些开源的编译器（名字不太记得了），能编译成c代码，你可以搜索一下，作为参考。

作者回复: 我个人认为，中国的软件工程师们是适合做编译技术的。主要原因是，编译技术总体的变化所读没有那么快，所以我们消化存量技术还是没啥问题的。在足够多的工程师能够掌握存量的技术之后，自然就会在某些前沿做出自己的突破。 如果技术没有问题，那就是需要生态的支持了。不管是有意还是无意（比如美国的技术封锁），中国都开始形成自己的IT技术生态，编译器自然是其中不可缺少的一环。

作者回复: 用QT写工具，不错。 既然叫做工具，肯定要具备各种自定义能力，使工具具有普适性。这个地方可能就要用到编译技术。