0.简介

在前一篇文章中我们对编译链接整体过程以及本系列文章涉及的内容进行了介绍，预编译和汇编阶段做的事情较为简单，而编译与链接阶段涉及更多复杂技术，本文将对编译阶段的词法分析、语法分析、语义分析、代码优化与生成结合实际例子进行介绍。

1.整体介绍

我们知道在编译阶段编译器会分为四步：词法分析、语法分析、语义分析以及代码优化和生成，经过这四步分别得到Tokens、Syntax Tree、Commented Syntax Tree和Intermediate Representation、Target Code，整体如下图，本文将结合实际例子去逐步解析整个流程。

2.词法分析

词法分析就是把代码拆分成Tokens，我们的代码在预处理完成后会进入到扫描器（Scanner），其实就是通过类似有限状态机的方法去将字符序列转换为一系列的Token，为后续的语法分析做准备。

词法分析一般拆分出的Token可以分为以下几类：标识符、关键字、字面量（字符串、数字等）、符号（加号、等于等），在扫描时进行识别并记录，我们可以来实际看一个词法分析的结果来理解其扫描要做的事情。

源代码如下：

int main() {
    int a = 1 + 2;
    return 0;
}

token生成如下：

clang -Xclang -dump-tokens test.c
int 'int'        [StartOfLine]  Loc=<test.c:1:1>
identifier 'main'        [LeadingSpace] Loc=<test.c:1:5>
l_paren '('             Loc=<test.c:1:9>
r_paren ')'             Loc=<test.c:1:10>
l_brace '{'      [LeadingSpace] Loc=<test.c:1:12>
int 'int'        [StartOfLine] [LeadingSpace]   Loc=<test.c:2:5>
identifier 'a'   [LeadingSpace] Loc=<test.c:2:9>
equal '='        [LeadingSpace] Loc=<test.c:2:11>
numeric_constant '1'     [LeadingSpace] Loc=<test.c:2:13>
plus '+'         [LeadingSpace] Loc=<test.c:2:15>
numeric_constant '2'     [LeadingSpace] Loc=<test.c:2:17>
semi ';'                Loc=<test.c:2:18>
return 'return'  [StartOfLine] [LeadingSpace]   Loc=<test.c:3:5>
numeric_constant '0'     [LeadingSpace] Loc=<test.c:3:12>
semi ';'                Loc=<test.c:3:13>
r_brace '}'      [StartOfLine]  Loc=<test.c:4:1>
eof ''          Loc=<test.c:4:2>

词法分析不仅是编译器，数据库的sql解析也要使用，现在常用的工具有lex，这个此处不重点讨论。

3.语法分析

语法分析是词法分析后对于Token关系的组织，把Token组合成语法树，其生成方式通过上下文无关语法来进行分析，生成语法树，比如还是int a = 1 + 2;。

语法树其实就是代码的组织结构，其清晰的展示了谁是主体，谁是动作。那么语法分析如何发现语法错误呢？比如int a = 1 + ;，对于这种语句可以根据“+”必须有两个操作数，单个无法生成语法树去检测错误，常见的缺少括号或者少逗号等都在此阶段发现。

我们还是以之前程序为例去看语法树生成效果。

clang -Xclang -ast-dump -fsyntax-only test.c
TranslationUnitDecl 0x11833b8 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 0x1183c50 <<invalid sloc>> <invalid sloc> implicit __int128_t '__int128'
| `-BuiltinType 0x1183950 '__int128'
|-TypedefDecl 0x1183cc0 <<invalid sloc>> <invalid sloc> implicit __uint128_t 'unsigned __int128'
| `-BuiltinType 0x1183970 'unsigned __int128'
|-TypedefDecl 0x1183fc8 <<invalid sloc>> <invalid sloc> implicit __NSConstantString 'struct __NSConstantString_tag'
| `-RecordType 0x1183da0 'struct __NSConstantString_tag'
|   `-Record 0x1183d18 '__NSConstantString_tag'
|-TypedefDecl 0x1184060 <<invalid sloc>> <invalid sloc> implicit __builtin_ms_va_list 'char *'
| `-PointerType 0x1184020 'char *'
|   `-BuiltinType 0x1183450 'char'
|-TypedefDecl 0x1184358 <<invalid sloc>> <invalid sloc> implicit __builtin_va_list 'struct __va_list_tag [1]'
| `-ConstantArrayType 0x1184300 'struct __va_list_tag [1]' 1 
|   `-RecordType 0x1184140 'struct __va_list_tag'
|     `-Record 0x11840b8 '__va_list_tag'
`-FunctionDecl 0x11e3010 <test.c:1:1, line:4:1> line:1:5 main 'int ()'
  `-CompoundStmt 0x11e3220 <col:12, line:4:1>
    |-DeclStmt 0x11e31d8 <line:2:5, col:18>
    | `-VarDecl 0x11e3110 <col:5, col:17> col:9 a 'int' cinit
    |   `-BinaryOperator 0x11e31b8 <col:13, col:17> 'int' '+'
    |     |-IntegerLiteral 0x11e3178 <col:13> 'int' 1
    |     `-IntegerLiteral 0x11e3198 <col:17> 'int' 2
    `-ReturnStmt 0x11e3210 <line:3:5, col:12>
      `-IntegerLiteral 0x11e31f0 <col:12> 'int' 0

对于语法分析的实现来说，如果我们也想自己做一个语法分析工具，可以使用yacc。

4.语义分析

语法分析保证了代码的结构正确（即能正确生成语法树），但还没检查“逻辑的合理性”，比如int a = "hello world";，这明显在语义上是由问题的。编译器所能分析的语义称为静态语义，相对应的动态语义需要在运行期才能确定语义。静态语义检查的东西有很多，主要如下：

1）类型检查：保证满足运算符的要求（比如int+int合法，int + string不合法）

2）变量声明检查：确保使用的变量已经被声明且在作用域中。

5.代码优化和生成

代码的优化和生成包含几个步骤，第一个就是根据语义分析后的结果生成中间代码，它是对于语法树的顺序表示，产生机器无关的代码，这就使得编译器可以分为前端和后端，前端产生机器无关的中间代码，后端将中间代码转换成目标机器代码。这就使得可以针对不同平台使用同一个前端和针对不同机器平台的数个后端。

后端分为代码生成器和目标代码优化器：

1）代码生成器：将中间代码转换成目标机器代码，这个依赖于目标机器，因为不同机器有不同的字长、寄存器、整数数据类型和浮点数数据类型等。

2）代码优化器：代码优化器就是将代码进行优化改写，常见的优化方式有：常量折叠（把int a = 1 + 2; 优化成int a = 3;）、代码消除（对于走不到的分支会直接删掉）、循环展开（把for循环展开减少判断）等。

我们用实际的例子去看，先看没有开启优化的情况，可以明显看到其中的addl指令：

开启O2优化后可以看到直接变成一条movl指令：

6.总结

经过编译器上述处理后，将会根据代码文件生成目标文件（.o）。但这个二进制文件格式是什么？链接时为什么会报 “undefined reference”？符号表和重定位表又是什么？这些将在下一篇文章中进行说明。