Day3.编译器运作流程介绍

编译器做了什麽 ?

我们知道使用机器指令撰写程序码是非常麻烦的事情，也会使开发程序的效率不高，编译器就是将来源码（source code）翻译成机器语言（object code）的一种工具。

Source Code 到 Object Code 中间发生了什麽事情

Complier 会分三个阶段

1.Front-end: 将程序码切成一个一个的字，然後照该语言的逻辑变成一个抽象语法树(AST)
2.Middle-end: 将AST转换成中间语言(IR),并优化这个IR
3.Back-end:将IR 转换成目标码并且优化

词汇分析(Lexical analysis)

首先将 来源码 (Source Code) 输入到 扫描器(Scanner)，扫描器只是简单地进行语法分析，使用一种类似於有限状态机(Finite State Machine) 的算法将 Source Code 的字符序列分割成一系列的 Token。

unsigned background(unsigned foreground) {
    if ((foreground >> 16) > 0x80) {
        return 0;
    } else {
        return 0xffffff;
    }
}

有一个叫做lex 的程序可以实现词法扫描，他会按照描述好的词汇规则将输入字符分割成一个个的Token，编译器的开法者就无需对每个编译器开发一个独立的扫描器，而是根据需要改变语法规则就可以了

语法分析 (Parser)

Parser 读取 token，然後对照语法规则来判断 token 属於哪个语法的哪个部分，遇到不合法的 token 就会丢出 Parse error，最後产生语法树(Synta Tree)

那麽语法规则该怎麽表示呢?
BNF(Backus-Naur Form)
是一种用来表示上下文无关文法的语言，原理非常复杂，因此不赘述，定义了语法之後，我们就可以拿这个文法来实作真的parser 程序码，Parser 使用 LL 或 LR 两种方式转换语法树，而通常在现代 parser generator 的技术都很成熟了，只要把 CFG 定义好丢给 parser generator 就可以产生 parser 了。

语意分析 (Semantic analysis)

语意分析是根据语言规则和上下文，检查 parse tree 里的语意是否有问题。

var a:bool = 1 + ture

假设一个数字跟一个布林值相加，很明显是错误的，Semantic analysis 要做的就是把这个问题抽出来，可能不只这些语意上错误，不同语言也可能有不同的规则，而编译器所能分析的语意是静态语意，所谓的静态语意是指在编译期间可以确定的语意，与之对应的动态语意就是只有在运行期间才可以确定的语意。

中间语言生成

编译器可能有中间语言，称作中间表达式 Intermedia Representation（简称 IR），以便进行後续的优化以及对应多机器平台的机器码。

为什麽需要先转为 IR 优化後才转为 Object Code？

1.如果没有 IR，直接从 Front-end 编译到各个机器平台的话，因为对应平台的机器目的码都不同，这样会有太多种的组合，以实作来说就是一个悲剧。而 IR 通常都是不相依於机器的，因此这样更易於重用，提高开发弹性。
2.直接在语法树上做优化较其困难，所以将 Source Code 优化器往往讲整个语法树转换成 IR ，它是语法树的顺序表示。

程序码生成（Code Generation）

程序码生成器将IR转换成机器码，这个过程十分依赖於目标机器，因为不同机器有着不同的CPU架构而有不同的指令集，另外也有一种虚拟机 (VM, Virtual Machine)，主要是建立跨平台的执行环境，让相同的目标码在任何机器上执行，像是 JVM 它的目标码就是 bytecode 。
最後目标码优化器对上述机器码进行优化，这边属於跟机器平台有关的优化，往往利用硬体平台的特性来帮助优化，IR的优化属於与机器无关的优化。

参考资料

实现一个编译器需要实现哪些流程？
人人都能读懂的编译器原理
一点都不深入的了解 Compiler、 Interpreter 和 VM