编译器介绍
分层
前端（frontend）
将源代码翻译为一个中间表示（intermediate representation, IR）。clang 是 LLVM 中 C 系语言的前端。
词法分析
词法分析是为了识别输入（源代码）中特定单词的准确含义，比如一个单词到底是语言的关键字还是程序员自定义的变量名？注释开始结束？这些分析结果将作为后续语法分析的输入。
词法分析器基本原理是正则表达式+action，即匹配到正则表达式时采取某个action。例如：匹配到 /*...*/ 时什么也不做，匹配到 int a 时识别到 int 是一个类型关键字，a 是标识符。最后将上述判断输出。
lex 是 Linux 上的语法分析工具，定制好词法（正则和 action）规则后即可产生词法分析程序。
语法分析
语法分析的原理就是检查给定的句式是否满足特定的语法。语法（Grammer）是描述语言语法结构的规则形式，在编译器中是树形的。比如，汉语言可以用下面的语法表示：
句子 : 子句子 宾语
子句子 : 主语 谓语
主语 : 你|我|他…
宾语 : 饭|水…
其中每一行称为一个产生式（production），粗体的是非终结符（nonterminal），细体的是终结符（terminal）。终结符是语法中最基本的元素，无法再分割，非终结符则可分解为n个终结符的组合。可以看到这种表示形式自上而下由根逐级分解，像一颗树，因此又被称之为语法树（syntax tree）或语法分析属（parse tree）。
检查给定的句式是否满足语法有两个思路：
- 推导（derivation）
推导是正向的，从语法的开始处（根产生式），逐级分解到非终结符，如果输出句式和目标句式一致表明句式正确。推导过程中，选择什么路径影响到效率（如果发生句式不匹配甚至要回溯），因此会有优化算法，比如递归算法和 LL(1) 算法
- 归约（reduction）
规约是反向思路，将目标句式从一个个终结符逐步向上替换成产生式，最终如果能归一到语法的根节点，说明目标句式语法正确。实现上可以使用栈：将目标句式的终结符逐步压入栈中，压入的过程中如果发现栈中内容能归约到某个产生式，则向上归约转换，否则继续压入目标句式的下一个终结符，直到能够继续归约。最终，如果目标句式语法正确，则一定能归约到语法的根节点。（有点儿像俄罗斯方块）。归约也存在路径选择问题，因此也有优化算法，比如 LR(1)
对于程序语言来说，主要使用归约法，和上述汉语言的归约过程别无二致，唯一的区别是语法树不同而已。也就是说，程序语言中，int **、+、-、(** … 等都是终结符，语法分析过程就是对它们进行归约分析。当然，最重要的工作显然是语法树的确立，这里不细说。
yacc 是 Linux 上的语法分析工具，它用 %token 标识终结符（大写字母），非终结符用小写。定制好语法树规则（以及辅助信息）后即可产生词法分析程序。
- 词法分析和语法分析如何合作？（lex 和 yacc ）
词法分析为语法分析提供输入，我们知道归约语法分析的输入是终结符，词法分析步骤即按语法分析器定义的终结符形式识别、分析出所有的终结符，最终输入给语法分析器。
比如源码中的 int 是终结符 INT 的关键字，那么 lex 会将其输出为一个 INT 的 token （终结符）。yacc 检查语法树，确定是否有语法错误。
语义分析
归约过程是自语法树自下而上的，一种主流的语义分析方法，语法制导转换（syntax directed translation，或语法制导翻译），即在归约到某个指定的产生式（production）时触发特定的动作（语义分析动作）。举例来说，declarartion : declarartion_specifiers ';' | declaration_specifers init_declarator_list ';' 是某个变量定义产生式，如果语法分析时归约到到 int* c 时，进入此产生式，表明源代码定义了一个变量，那么我们就分析出了变量定义这个行为，可以在对应的动作输出 “Find a new symbol” ，并将其记录到一个符号表结构体（链表）中，记录为 @int*_c，表明其类型和名称。
静态语义检查，在编译过程中对源代码进行语义检查，c/c++ 只采用静态语义检查
动态语义检查，在程序运行过程中的检查，比如数组越界等，java 等语言支持动态语义检查，为了实现动态检查，编译器要在目标程序中插入额外的检查代码
IR 生成
IR 生成可以在语义分析的action中触发（设置IR生成对应的 action），IR 的类型可以是单地址、二地址以及三地址形式。
- 一地址：指令的操作数和操作结果都存储在栈中。比如 Java 字节码
- 二地址：指令的操作结果会存储到操作数的存储空间里。类似于 Intel X86 汇报指令格式
- 三地址：操作数、操作结果都有自己的存储空间。比如 DEX 字节码，由于 ARM CPU 中寄存器很多，采用此类型的 IR，灵活度最高。
代码如何翻译成 IR ? 内容很复杂，概括来说包括语句（statement）和表达式（expression）的翻译，还涉及类型系统、对函数调用的抽象（包括如何在调用者和被调用者之间传递参数和返回值 ）
优化器（optimizer）
对 IR 进行分析，并将其翻译成一个更高效的形式（可以是与之前同一类 IR ，也可能是另外一种 IR）。opt 是 LLVM 的优化器工具。
优化器是基于 控制流（control flow）和数据流（data flow）来做的
- 控制流图
描述程序结构的相关信息。优化器用控制流图（Control Flow Graph）来表示它。控制流图包含两类基本元素：基本块（Basic Block）和边（edge）。基本块是代码中不包含分支语句的部分，而边则代表跳转关系（比如true、false时走到哪个基本块，用箭头表示），这样程序就可以完全用控制流图表示。实现一个控制流图提取器也比较简单，判断目标 IR 中的分支指令即可分割出各个基本块。有了 CFG ，就可以做一些优化了，比如循环优化、无用代码剔除等
+----------+
| x=z-2; |
| y=2*z; |(Basic Block)
| if(c) |
+--+-----+-+
True | | False
v v
+--------+-+ ++---------+
| x=x|1; | | x=x|1; |
| y=y+1; | | y=y-1; |
| | | |
+--------+-+ +-+--------+
| |(edge)
v v
+-+------++
| z=x+y; |
| |
+---------+
CFG 实例
（对于 ART 编译器来说，它仅包含优化器和后端而没有前端，它的优化器处理的是 dex 字节码 IR，控制流图也是从字节码中提取出来的，源代码 block_builder.cc）
- 数据流
后端（backend）
通过将 IR 映射为目标硬件的指令集生成机器码。llc 是 LLVM 的后端工具
compiler vs. interpreter
编译器：是一种计算机程序，将一个一种语言编写的源码转换为另一个计算机语言（即目标语言，包括可直接执行的机器码、不可直接执行的另一种计算机代码），编译成的目标语言文件可以直接被执行或需要再编译后执行或由解释器解释执行；
解释器
是一种计算机程序，直接执行由编程语言或脚本语言编写的代码，并不会把源代码预先地编译成机器码，有三类执行策略
- 解析源代码，并直接执行行动。（例如bash脚本语言，脚本文件一行一行直接被运行）
- 把源代码翻译成相对更加高效率的中间码，然后立即执行它。
- 内部包含一个编译器，先编译存储（例如缓存）好代码，然后执行。 （有编译器？那涉及 JIT 和 AOT！）
JIT vs. AOT
术语 Ahead-of-Time (AOT) 和 Just-in-Time (JIT) 指的是编译什么时候发生，其中的“-time”指的是术语“runtime”，也就是说 JIT 编译器是运行时编译，而 AOT 编译器是运行前编译。值得注意的是，这两个术语只适用于编译器，对于解释器，“运行时解释或运行前解释的解释器”是没有意义的，因为解释器总是在运行的时候解释 ：)