计算机为什么能够读懂程序代码？

第二回

业余码农苦愁程序执行经过

编译原理详解机器代码生成

01 引子

上一回，我们的主人公小A初次亮相，凭借基础的前后端理解，从技术实现的层面为我们剖析了微信扫码登录的原理和机制。可能很多人因此会好奇，小A到底是做什么的呢？为什么能够弄懂这些原理呢？

其实，小A是一名业余码农。为什么要叫业余码农呢，是因为他觉得自己属于半路出家，很多计算机基础思想都不够专业，还有很大的进步空间，因此称自己为业余码农。

但是兴趣总是最好的老师，这不，小A正又盯着屏幕上的几行代码发愁：

#include <iostream>
int main(){
    std::cout << "Hello World!" << std::endl;
    return 0;
}

编译并运行这段 C++ 代码就能够完美打印出Hello World!，似乎没啥毛病呀！

“计算机是怎么知道我敲的这些代码的意思呢？”小A 苦皱着眉头，喃喃道。原来，我们的业余码农小A 是没想明白计算机是如何将这些一串串的字符转变成计算机能够执行的机器码的，这其实不就是编译原理嘛。

小A 回想起之前上过的数电模电课，知道计算机的世界里都是数字化的，也就是说计算机只知道二进制 0 和 1 。不同数量 01 的组合在计算机的内部构成了不同的指令，而不同指令的组合又构成了不同的操作。

这就好比流水线的生产模式，假如把计算机看作一条流水线，那么在这条流水线上有不同的工位，每一个工位代表着不同的指令。生产不同的产品就需要不同工位的一同参与，可能按顺序执行，也有可能并列执行。

想到这，小A意识到其实这些由 0 和 1 构成的指令应该就是计算机能够执行的机器码。不过那这些机器码好像与上面的 C++ 代码还相差甚远，中间肯定是经历了一系列的转换。嗯？这个过程有点像是翻译的过程，好像是将程序代码翻译成了机器码！

小A 茅塞顿开，好像又找回了之前英语四级怒考 605 分的自信。看来，英语没白学！

计算机理解程序代码的过程是不是就像是将英文翻译成了另一种语言呢？一想到英语的那些高阶语法，小A 就开始忍不住头疼，“不会这编程还得学个什么时态转换语态切换从句倒装吧...”。

不过头疼归头疼，该学的还是得耐着性子学。小A 知道，在计算机真正运行 C++ 程序代码之前，还需要经过复杂的编译过程，这个编译过程似乎对计算机理解程序代码起着关键性作用。

02 C++编译过程

找到了分析问题的方向，小A 迫不及待的到处查询 C++ 编译过程到底是如何发生的。他发现 C++ 的整个编译过程包含多项操作，主要可分为四个阶段：

1.编译预处理

2.编译优化阶段

3.汇编过程

4.链接过程

这四个阶段按顺序执行，每一个阶段分别处理上一个阶段的输出代码，并输入下一个阶段。每个阶段的作用分别为：

0x00 编译预处理

读取 C++ 源代码，对其中的伪指令和特殊符号进行处理。这个预处理实际上可看作是将源程序中的一些特殊指令或者符号进行替换。经过预处理的替换，就会生成一个没有特殊指令、没有特殊符号的输出文件。这个文件的含义和源文件本质上是相同的，但内容和表达方式有所不同。

特殊指令：称为伪指令，包括宏定义指令、条件编译指令、头文件包含指令。比如上述 C++ 代码中第一行的 #include 就是头文件包含指令，会在编译预处理阶段被替换。

0x01 编译优化阶段

经过预编译后的输出文件会经过编译优化阶段，将原始代码转化为汇编语言。这个阶段是整个编译过程的核心，也是起到 “ 翻译 ” 作用的关键。整个阶段的工作过程一般可分为六个步骤：

1.词法分析

2.语法分析

3.语义分析

4.中间代码生成

5.代码优化

6.目标代码生成

在进行编译时，会经过词法分析、语法分析和语义分析将高级语言代码一步步分解剖析，按照定义的语法将不同的代码语句拆解，并根据一些标准来对代码语句进行分析检查，最后生成中间形式的代码用于优化。而优化步骤则是对中间代码进行优化改进，力图提升生成的汇编代码的效率。

0x02 汇编过程

汇编语言可看做是一种低级语言，十分接近于机器码的实现。

汇编语言：用于硬件底层编程的低级语言，常用助记符代替机器指令，用地址符号或标号代替指令或操作数的地址。特定的汇编语言和特定的机器语言指令集一一对应，通过汇编过程转换成机器指令。

由此可见，汇编过程实际上就是将汇编语言翻译成为了机器码，这些机器码就是 C++ 源代码的底层表达，理论上计算机可以通过执行这些机器码来实现对源代码的运行。

0x03 链接过程

但是要知道，一个普通的高级语言程序，都不单单只包含一个文件。可能某个源文件就会调用其它库文件中的函数或者其它源文件中定义的符号函数等。因此多个文件在经过编译汇编之后，还需要通过链接过程将不同的目标文件连接起来，建立起引用和调用的联系。直至这步完成之后，程序语言代码才能够真正意义上的被计算机理解和运行。

反复思索 C++ 编译的整个过程，小A 感觉那几行简洁的代码仿佛经过了千锤百炼一般，虽然最终似乎面目全非，但是却变成了最原始最纯洁的样子。

小A 忍不住一阵感叹整个编译过程的环环相扣以及精巧绝伦，同时对编译阶段的原理产生了更大的兴趣。

03 编译原理

编译阶段的过程是通过编译器所实现的，编译器通过六个步骤将由数字、字符串以及一些关键字组成的字符流进行解析，最后经过优化生成汇编代码。

那是如何进行解析的呢？小A这时候想到了中英文中的主谓宾结构，难道也可以把程序代码划分为主语、谓语、宾语吗？不妨举个栗子来分析好了，小A 熟练的写下了一行代码：

position = initial + rate * 60

不如就来分析这一行赋值语句的翻译过程吧。

0x00 词法分析

最先输入编译器的是源程序代码的字符流，如上述例子所示的是由英文、符号和数字组成的字符串。词法分析的过程就是将字符流中有意义的词或符号进行提取并分类表示，同时保存在符号表中，并映射为『词法单元』。

比方说上述代码中的词position，可映射为词法单元<id, 1>。id 表示的是标志符（identifier），而 1 表示符号表中的第一个条目。

但是，符号=却不会保存在符号表中，因为其不具有值的概念，只是一个赋值符号。所以其对应的词法单元直接用它本身来表示<=>。

对上述代码所有词及符号进行词法分析后，可获得词法单元：

对应的符号表为

因此该上述赋值语句代码可用词法单元表示：

<id, 1><=><id, 2><+><id, 3><*><60>

这样一来，通过词法分析就把代码语句给剥离抽象化，清晰的展现出语句的结构性。

0x01 语法分析

语法分析，故名思义就是检查语言的表述是否符合已经设定的语法规则。而在语法分析器中，这样的规则称之为『文法』。

文法：通过集合来描述语法结构的规则。如主谓宾结构就可看作一种文法。

每一种编程语言都有其对应的文法，根据制定的文法规则可以对词法分析产生的词法单元串进行解析。文法解析的方法有多种，优劣势不一，但目的都是为了构建一颗语法分析树。这同时也是语法分析阶段输出的结果。

对于上述赋值语句而言，根据不同运算符的执行顺序，将赋值运算符=作为根节点，可得到语法分析树

获得语法分析树之后，整个代码结构用树的形式进行表示，从而方便后续进一步对源程序进行分析。

0x02 语义分析

语义分析是使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。如果说语法的分析是对程序语句的结构进行分析，那么语义分析则是对语句的逻辑性和合理性进行分析。比方说：

语句：猴子是程序员

语法分析得到主谓宾结构，『猴子』是主语，『是』是谓语，『程序员』是宾语。从语法上来说并没有错误。

但是很明显，语义上是有问题的。

因此在语义分析环节很重要的部分就是对程序语句进行类型检查，比方说应保证运算符两边的数值类型一致。这本质就是要检查出『猴子是程序员』这样的错误。

对于上述的赋值语句，假设position、initial、rate已被声明为浮点数类型，那么表面上整数60应与rate的类型不同，在语义分析的时候就会找出这样的问题。

只不过在很多语言中允许自动类型转换，会将整数60转换成浮点数从而满足语义的要求。因此经过语义分析后，语法树会新增inttofloat节点以达到类型转换的目的：

0x03 中间代码生成

在翻译源程序的过程中，往往会使用多个中间表示形式进行以方便不同的运算处理。一般常用一种称为『三地址代码』的中间表示形式将语法树的结构进行改写。该形式根据运算完成的顺序，生成临时名字以存放运算的值。如上述赋值语句的中间代码：

t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

0x04 代码优化

代码优化阶段试图改进中间代码，以达到提高效率或者其它更有优势的目的。优化阶段会根据一些既有的规则去对中间代码进行改进，不同的编译器之间往往具有差异性。上述中间代码可以将inttofloat操作进行优化，使用浮点数60.0来代替整数60从而满足语义分析。中间代码优化为：

t1 = id3 * 60.0
id1 = id2 + t1

0x05 目标代码生成

目标代码的生成是将中间代码翻译为汇编语言。在这个过程中，需要为变量合理地分配寄存器，选择内存位置。之后再根据汇编语言的操作完成翻译。上述赋值语句对应的汇编代码为：

LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1

在上面的代码中，每个指令的第一个运算分量指定了目标地址以存放计算结果。这样的操作已经是从硬件层面对数值操作和运算执行。之后通过汇编过程即可获得真正的机器指令序列。

看到这，小A 已经快有些迷糊了。尽管例子里对赋值语句的编译过程看起来简单明了，但是一想到其它程序代码里无数的关键字、变量和函数调用还是忍不住微微叹了口气。

毕竟，这些内容还只不过《编译原理》的第一章。真正每一阶段的实现需要考究的东西还有太多。不过学习都是循序渐进的，学到这小A 已经大致清楚 C++ 程序从源代码到运行起来的经过了。

04 解释器

此外，他还发现一个彩蛋。原来除了编译器能够起到翻译的作用，还有一种称作“解释器”的东西同样可以起到翻译作用。

简单来说，编译器是将源代码完整转换为机器码；而解释器是将源代码直接生成机器码并交由硬件执行。因此编译器事先需要将整个程序编译成另外的代码，而解释器可一行一行读取程序，然后翻译执行。