随想录（编译器是怎么工作的）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    编译器一直是我比较喜欢的话题。编译器是个比较神奇的工具，它可以把原来毫无意义的字符数据转变成一行一行可以执行的代码。作为每一个科班出身的同学来说，编译原理都是专业学习中必须经历的一个部分。只是在后来的工作中，真正从事编译器开发的同学少之又少，但是如果你懂得了编译原理的相关机理，会给你的工作带来很大的帮助。关于编译原理的书很多，网上可以搜一下有阿霍版本的《编译原理》，有陈火旺院士的《编译原理》，张素琴版本的《编译原理》，三本书我都觉得不错。另外，现在关于编译原理也有很多的开发工具，比如说lex&yacc，只要你会编写基本的语法范式，设计自己的编译器也不是什么难事。

    其实，现在的编译器早已经突破了原来的概念。比如说，编译器最终的代码不一定在实际机器上运行，可能是虚拟机；编译器编译语言时不一定需要生成可执行文件，能解释就行；编译器最好并行编译；编译器不一定很大，可能十几个文件就可以，比如说lua等等。不过，我们今天说的编译器还是比较传统的c编译器，有兴趣的同学可以看看编译器是怎么帮助我们生成可执行文件的。我们按照词法、语法、语义、优化的顺序逐一展开。现在假设有这样一段代码，

#include <stdio.h>

#define MAX_VALUE 7
int test(int value)
{
    return MAX_VALUE + 1 + value * 4;
}

int main(int argc, char* argv)
{
    int p;
    p = test(3);
    printf("p = %d", p);
    return 1;
}

   

    （1）词法分析

    词法分析是整个文件编译最基本的环节。上面的文件中就存在很多的字符，那我们就需要分别对它们进行处理。比如说，通常的分类很可能是这样的，

    a）字符是否是数字，例如7，1，4

    b）字符是否是string类型，例如“p = %d”

    c）字符是否是关键字，例如define

    d）字符是否是变量，例如value，argc， argv， p

    e）字符是否是运算符， 例如 +

    f）字符是否是圆括号、方括号、花括号等等

    （2）语法分析

    语法分析的目的就是构建一个语法树，分析当前的文件是否符合编程语言的文法结构，比如说，

    a）整个字符串是否符合表达式要求

    b）字符串是否符合判断语句要求

    c）字符串是否符合循环语句要求

    d）字符串是否符合函数要求

    e）字符串是否符合include语法要求

    f） 有没有没有未声明就是用的变量等等；

    （3）语义分析

    语义分析有的时候和语法分析是联系在一起的。但是，这里我们把它拆开来单独成了一部分。所谓的语义分析，其实就是把前面生成的语法树拆解下来，生成原子语句操作的过程。比如说，上面的文件很可能是这样的形式，

SET value
mov temp1[inner], 7
add temp1[inner], 1
mul temp2，value[param], 4
add temp1, temp2
mov result, temp1
pop


SET argc[param]
SET argv[param]
SET 3
call test
pop
get result
mov p[inner], result
SET p
SET string "p = %d"
pop
pop
mov result, 1
pop
pop

    这里需要解释一下，语义转换的结构和形式其实是各个编译器自己定义的，未必有通用的结构。这里的语句只是我自己想出来的，可能和实际的形式有很大的出入，但是基本方法应该是一样的。主要解释如下，

    a）SET值为函数参数

    b）call为函数调用

    c）pop为堆栈平衡使用

    d）数据[inner]，表示当前变量是函数中的临时变量

    e）数据[param]，表示当前变量是入参参数

    f）temp表示编译器为了自身计算方便，临时添加的局部变量

    g）result表示返回值

    （4）代码优化

    代码优化是编译器处理的一个重要环节，代码优化的目的主要是减少不必要的计算和处理，比如

    a）计算没有使用价值的临时变量

    b）除去没有判断价值的if语句

    c）对于某些const变量，编译器提前计算，这里就可以对temp1提前计算

    d）其他优化措施等等

    （5）生成汇编代码

    在（3）中生成的代码只是中间代码，并不是完全意义上的汇编语言。所以，编译器还需要把它翻译成对应的二进制代码，比如说arm语言、x86语言或者是powerpc语言等等。当然这中间还是存在一些技巧的，比如

    a）对于多参数的函数，某些cpu可以用寄存器代替，有些cpu用堆栈表示

    b）某些cpu需要对字节对齐，某些cpu则不需要

    c）某些cpu有字节序的要求，某些cpu则无所谓，而有的cpu则可选

    d）对于临时变量，有的cpu可以寄存器表示，而有的cpu只能自己生成一个temp变量等等，

    

    说到这里，我们也可以自己小试一下身手，看看代码怎么生成，熟悉x86代码的同学也可以自己试试，

push ebp
mov ebp, esp
push ebx
push ecx
mov ebx, 8
mov ecx, ebp[8]
mul ecx, 4
add ebx, ecx
mov eax, ebx
pop ecx
pop ebx
mov esp, ebp
pop ebp


push ebp
mov ebp, esp
sub esp, 0x4
push 3
call test
add esp 4
mov ebp[-4], eax
push ebp[-4]
push string "p = %d"
call printf
add esp, 8
mov eax, 1
sub esp, 0x4
mov esp, ebp
pop ebp

     

    （6）汇编级代码优化

    这里的优化其实还挺多的，但是功能基本有限，无外乎就是，

    a）乘法转变成移位

    b）除法转变成移位

    c）寄存器优化使用

    d）删除寄存器的重复操作过程

    e）部分函数参数用寄存器代替等等

    （7）链接和生成可执行文件

    在编译过程中，我们常常看到有些代码编译通过了，但是链接失败了。这是很正常的事情，因为在最后生成的文件当中，每一个变量和函数都应该有出处，否则就会链接失败。不管是什么系统平台，链接都是个大学问。这个时候，做的事情其实还是比较多的，比如

    a）生成执行文件，确定是否带调试信息

    b）链接所有的变量和代码

    c）生成map文件

    d）确定函数和变量的出处，一旦查找失败，结束

    e）调整变量和函数代码的位置，填写文件结构，生成最终可执行文件