Table of Contents:

github代码地址

开篇词 | 为什么你要学习编译原理？

编译原理不是只能用于炫耀的屠龙技。 别的不说，作为程序员，在实际工作中你经常会碰到需要编译技术的场景。

01 | 理解代码：编译器的前端技术

这里的“前端”指的是编译器对程序代码的分析和理解过程。
它通常只跟语言的语法有关，跟目标机器无关。而与之对应的“后端”则是生成目标代码的过程，跟目标机器有关。

词法分析

文章是由一个个的单词组成的。程序处理也一样，只不过这里不叫单词，而是叫做“词法记号”，英文叫 Token。词法分析是识别一个个的token，即分词程序。

分词是按照一定规则来写的。

这些规则可以通过手写程序来实现。事实上，很多编译器的词法分析器都是手写实现的，例如 GNU 的 C 语言编译器。
如果嫌手写麻烦，也可以偷点儿懒，用词法分析器的生 成工具来生成，比如 Lex（或其 GNU 版本，Flex）。这些工具是按照正则表达式来分词的。

语法分析

语法分析就是在词法分析的基础上识别出程序的语法结构。这个结构是一个树状结构，是计算机容易理解和执行的。

程序有定义良好的语法结构，它的语法分析过程，就是构造这么一棵树。一个程序就是一棵树，这棵树叫做抽象语法树（Abstract Syntax Tree，AST）。树的每个节点（子树）是一个语法单元，这个单元的构成规则就叫“语法”。每个节点还可以有下级节点。

语义分析

语义分析就是要让计算机理解我们的真实意图，把一些模棱两可的地方消除掉。
语义分析工作的某些成果，会作为属性标注在抽象语法树上，比如在 age 这个标识符节点和 45 这个字面量节点上，都会标识它的数据类型是 int 型的。
在这个树上还可以标记很多属性，有些属性是在之前的两个阶段就被标注上了，比如所处的源代码行号，这一行的第几个字符。这样，在编译程序报错的时候，就可以比较清楚地了解出错的位置。
做了这些属性标注以后，编译器在后面就可以依据这些信息生成目标代码了，我们在编译技术的后端部分会去讲。
语法阶段是上下文无关的，语义阶段则专门处理上下文。

课程小结

 词法分析是把程序分割成一个个 Token 的过程，可以通过构造有限自动机来实现。
 语法分析是把程序的结构识别出来，并形成一棵便于由计算机处理的抽象语法树。可以用递归下降的算法来实现。
* 语义分析是消除语义模糊，生成一些属性信息，让计算机能够依据这些信息生成目标代码。

02 | 正则文法和有限自动机：纯手工打造词法分析器

要实现一个词法分析器，首先需要写出每个词法的正则表达式，并画出有限自动机，
之后，只要用代码表示这种状态迁移过 程就可以了。

03 | 语法分析（一）：纯手工打造公式计算器

初步了解上下文无关文法，知道它能表达主流的计算机语言，以及与正则文法的区别。
理解递归下降算法中的“下降”和“递归”两个特点。它跟文法规则基本上是同构的，通
过文法一定能写出算法。
通过遍历 AST 对表达式求值，加深对计算机程序执行机制的理解

20 | 高效运行：编译器的后端技术

21 | 运行时机制：突破现象看本质，透过语法看运行时

22 | 生成汇编代码（一）：汇编语言其实不难学

23 | 生成汇编代码（二）：把脚本编译成可执行文件

24 | 中间代码：兼容不同的语言和硬件

25 | 后端技术的重用：LLVM不仅仅让你高效

26 | 生成IR：实现静态编译的语言

27 | 代码优化：为什么你的代码比他的更高效？

问题：
 代码优化的目标是什么？除了性能上的优化，还有什么优化？
 代码优化可以在多大的范围内执行？是在一个函数内，还是可以针对整个应用程序？
* 常见的代码优化场景有哪些？

了解代码优化的目标、对象、范围和策略

代码优化的目标： 

CPU利用率（主要）、代码大小、内存占用大小、磁盘访问次数、网络通讯次数等等

代码优化的对象：

大多数的代码优化都是在 IR 上做的，而不是在前一阶段的 AST 和后一阶段汇编代码上进行的
在 AST上抽象层次太高，含有的硬件架构信息太少。在汇编代码上进行优化会让算法跟机器相关，当换一个目标机器的时候，还要重新编写优化代码。

代码优化的范围

从优化的范围看，分为:
本地优化
针对基本块进行优化
全局优化
如果通过分析 CFG，我们发现 t 在其他地方没有被使用，就可以把第二行删掉。这种针对一个函数、基于 CFG 的优化，叫做全局优化（Global Optimization）
过程间优化
它能跨越函数的边界，对多个函数之间的关系进行优化，而不是仅针对一个函数做优化。

代码优化的策略

你不需要每次都把代码优化做彻底，因为做代码优化本身也需要消耗计算机的资源。
所以，你需要权衡代码优化带来的好处和优化本身的开支这两个方面，然后确定做多少优化。

一些优化的场景

代数优化（Algebraic Optimazation）
常数折叠（Constant Folding）
删除不可达的基本块
删除公共子表达式（Common Subexpression Elimination）
拷贝传播（Copy Propagation）和常数传播（Constant Propagation）
死代码删除（Ded code elimintation）
多次优化

一个优化可能导致另一个优化，比如，拷贝传播导致 y 不再被使用，我
们又可以进行死代码删除的优化。所以，一般进行多次优化、多次扫描。

28 | 数据流分析：你写的程序，它更懂

全局优化比本地优化能做的工作更多，分析算法也更复杂，因为 CFG 中可能存在多
条执行路径。不过，我们可以在上一节课提到的本地优化的算法思路上，解决掉多路径情况
下，V 值的计算问题。而这种基于 CFG 做优化分析的方法框架，就叫做数据流分析

29 | 目标代码的生成和优化（一）：如何适应各种硬件架构？