理解代码: 编译器的前端技术

编译器的前端技术，指的是编译器对程序代码的分析和理解过程。它通常指跟语言的语法有关，跟目标机器无关。

而对应的后端，则是生成目标代码的过程，跟目标机器有关。

front-back-end

由图可见，编译器的前端技术氛围词法分析、语法分析、语义分析三个部分。它主要涉及自动机和形式语言方面的基础计算机理论。

词法分析 ( Lexical Analysis )

编译器的第一项工作是词法分析。

程序是由一个个词法记号 ( Token ) 组成的。

如何读懂一段代码？

#include <stdio.h>
int main(int argc, char* argv[]){
    int age = 45;
    if (age >= 17+8+20) {
        printf("Hello old man!\\n");
    }
    else{
        printf("Hello young man!\\n");
    }
    return 0;
}

#include <stdio.h>
int main(int argc, char* argv[]){
    int age = 45;
    if (age >= 17+8+20) {
        printf("Hello old man!\\n");
    }
    else{
        printf("Hello young man!\\n");
    }
    return 0;
}

识别出:

if、else、int 这样的关键字
main、printf、age 这样的标识符
+、-、= 这样的操作符号
{}、()、; 这样的符号
数字字面量、字符串字面量
...

以上的都是 Token 。

如何写一个程序来识别 Token 呢？

英文内容通常用空格和标点把单次分开，方便读者阅读和理解。但在计算机程序中，仅仅用空格和标点分割是不行的。

比如 age >= 45 应该分成 age 、>= 、45 这三个 Token，但在代码里它们可以是连在一起的，中间可以不需要空格。

类似于汉语，汉语里每个词之间也没有空格，但我们会下意识地把局子里的词语正确地拆解出来。

比如把我学习编程拆解成我 学习 编程，这个过程叫做分词。

可以通过制定一些规则来区分每个不同的 Token ：

识别 age 这样的标识符: 它以字母开头，后面可以是字母或数字，直到遇到第一个既不是字母又不是数字的字符时结束
识别 >= 这样的操作符: 当扫描到一个 > 字符时，要注意，它可能是一个 GT ( Greater Than，大于 ) 操作符。但由于 GE ( Greater Equal，大于等于 ) 也是以 > 开头，所以要再往下看一位。如果是 =，那么这个 Token 就是 GE，否则就是 GT。
识别 45 这样的数字字面量。当扫描到一个数字字符的时候，就开始把它看做数字，直到遇到非数字的字符。

以上规则可以通过手写程序来实现。事实上，很多编译器的词法分析器都是手写实现的，例如 GNU 的 C 语言编译器。

如果嫌手写麻烦，可以用词法分析器的生成工具来生成，如 Lex ( 或其 GNU 版本，Flex )。这些生成工具是基于一些规则来工作的，这些规则用正则文法表达，符合正则文法的表达式成为正则表达式。生成工具可以读入正则表达式，生成一种叫有限自动机的算法，来完成具体的词法分析工作。

有限自动机是有限个状态的自动机器。

词法分析器分析整个程序的字符串，当遇到不同的字符时，会驱使它迁移到不同的状态。词法分析过程，就是一个个状态迁移的过程。

语法分析 ( Syntactic Analysis, or Parsing )

编译器下一个阶段的工作是语法分析。词法分析是识别一个个的单词，而语法分析就是在词法分析的基础上识别出程序的语法结构。这个结构是一个树状结构，是计算机容易理解和执行的。

Syntactic Analysis

程序有定义良好的语法结构，它的语法分析过程，就是构造这么一棵树。一个程序就是一棵树，这棵树叫做抽象语法树( Abstract Syntax Tree, AST )。树的每个节点 ( 子树 ) 是一个语法单元，这个单元的构成规则就叫语法。每个节点还可以有下级节点。

层层嵌套的树状结构，是对计算机程序的直观理解。计算机语言总是一个结构套着另一个结构，大的程序套着子的程序，子程序又可以包含子程序。

形成 AST 后，计算机就很容易去处理。比如，针对表达式形成的树，从根节点遍历整棵树就可以获得表达式的值。

如果再把循环语句、判断语句、赋值语句等节点加到 AST 上，并解释执行它，那实际上就实现了一个脚本语言。而执行脚本语言的过程，就是遍历 AST 的过程。

构造 AST

一种直观的构造思路是自上而下进行分析。

ast-build

一棵子树扫描完毕后，程序退回到根节点，开始构建根节点的第二个子节点。这样递归地扫描，知道构建起一棵完整的树。

这个算法就是非常常用的递归下降算法 ( Recursive Descent Parsing )。

递归下降算法是一种自顶向下的算法，与之对应的，还有自底向上的算法。这个算法会先将最下面的叶子结点识别出来，然后再组装上一级节点。像搭积木，总是先构造出小的单元，然后再组装成更大的单元。

语义分析 ( Semantic Analysis )

在词法分析、语法分析后，编译器的在下一步工作是语义分析。语义分析是要让计算机理解开发者的真实意图，把一些模棱两可的地方消除掉。

理解自然语言的含义很难，需要上下文，但其实语义分析并没有那么复杂。计算机语言的语义一般可以表达为一些规则，只要检查是否符合这些规则即可，比如：

某个表达式的计算结果是什么数据类型？如果有数据类型不匹配的情况，是否要做自动转换？
如果在一个代码块的内部和外部有相同名称的变量，在执行的时候到底用哪个？
在同一个作用域内，不允许有两个名称相同的变量，这是唯一性检查。

语义分析基本上就是做这样的事情，也就是根据语义规则进行分析判断。

语义分析工作的某些成果，会作为属性标注在抽象语法树上。

在抽象语法树上还可以标记很多属性，有些属性是在之前的两个阶段就被标注上了，比如所处的源代码行号，这一行的第几个字母。这样，在编译程序报错的时候，就可以比较清楚地了解出错的位置。

做了属性标注后，编译器在后面就可以依据这些信息生成目标代码了。

小结

词法分析是把程序分割成一个个 Token 的过程，可以通过构造有限自动机来实现。
语法分析是把程序的结构识别出来，并形成一棵便于由计算机处理的抽象语法树。可以用递归下降的算法来实现。
语义分析是消除予以模糊，生成一些属性信息，让计算机能够依据这些信息生成目标代码。

理解代码: 编译器的前端技术 ​

词法分析 ( Lexical Analysis ) ​

如何读懂一段代码？ ​

如何写一个程序来识别 Token 呢？ ​

语法分析 ( Syntactic Analysis, or Parsing ) ​

构造 AST ​

语义分析 ( Semantic Analysis ) ​

小结 ​