Post

编译器做了什么

编译器的作用

为什么会需要编译器? 使用机器语言或汇编语言效率低下,移植性差,而高级语言使得人们可以关注程序的逻辑本身,尽量少考虑计算机本身的限制.

compile process

从上图可以看到,编译过程一般分为六步:

  • 词法分析(扫描)
  • 语法分析
  • 语义分析以
  • 源代码优化
  • 代码生成
  • 目标代码优化

词法分析

首先源代码会被输入到扫描器,扫描器的任务就是进行词法分析。 运用一种类似于 有限状态机 的算法可以将源代码的字符序列分割成一系列的 Token。 词法分析产生的记号一般可以分为如下几类:

  • 关键字
  • 标识符
  • 字面量
  • 特殊符号

在标记记号的同时,扫描器也完成了其他工作,比如将标识符放到符号表,字面量放到文字表

Linux 下有 lex(lexical analyzer generator)/flex 程序可以进行词法扫描。

语法分析

语法分析器将对扫描器产生的记号进行语法分析,从而生成语法树。整个分析过程采用了 上下文无关语法下推自动机。 语法树是以表达式为节点的树。C 语言的一个语句就是一个表达式,而复杂语句就是很多表达式的组合。

array[index] = (index + 4) * (2 + 6)

比如上面这行代码生成的语法树就如图所示: ast

同词法分析一样,语法分析也有现成的工具可以使用 yacc(Yet Another compiler compiler)/bison. 可以理解为编译器的编译器. 它可以根据给定的语法规则对输入的序号序列进行解析,从而构建一颗语法树。

语义分析

语法分析只是对表达式语法层面的分析,但是它并不了解这个语句是否真的有意义。编译器能通过语义分析器(Semantic Analyzer)进行静态语义分析。(动态语义分析只能在运行期才能确定。) 静态语义通常包含声明和类型的匹配,类型的转换。 经过语义分析之后,整个语法树的表达式都被标识了类型。如果某些类型需要做隐式转换,语义分析程序会在语法树中插入对应的转换节点。

ast semantic

中间语言生成

现代的编译器有很多层次的优化,往往源代码级别就有一个。源码级优化器(Source Code Optimizer) 会在源代码级别进行优化。而直接在语法树上进行优化是比较困难的,所以一般会将语法树转换成中间代码,常见的中间代码形式有 三地址码P-Code.上面的语法树会被翻译成类似这样的中间代码

t1 = 2 + 6
t2 = index + 4
t3 = t2 * t1
array[index] = t3

优化后:

t2 = index + 4
t2 = t2 * 8
array[index] = t2

中间代码使得编译器可以分为前端和后端。前端负责生成机器无关的中间代码,后端负责将中间代码转换成目标机器代码。

目标代码生成与优化

编译器后端主要包含代码生成器目标代码优化器代码生成器负责将中间代码转换成目标机器代码,这个过程强依赖于目标机器,因为不同机器有不同的字长、寄存器、整数数据类型等。 目标代码优化器 对生成的目标代码进行优化,比如选择合适的寻址方式,位移代替乘法,删除多余的指令等。

经过上述一些列步骤,源代码终于被编译成目标代码,但是还有一个问题,indexarray 的地址还没有确定。 如果我们要把目标代码使用汇编器编译成真正能够执行的指令,indexarray 的地址从哪里获得呢,尤其是当它们不在我们当前的源代码文件中的时候。 事实上,定义在其他模块的全局变量和函数在最终运行时的绝对地址都要在最终链接的时候才能确定。

TODO lex 与 yacc

TODO 常见的编译器优化有哪些

  • RVO
This post is licensed under CC BY 4.0 by the author.