Table of Contents:

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

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

 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 | 目标代码的生成和优化(一):如何适应各种硬件架构?