编译原理

编译原理

编译器的前端技术

**“前端”指的是编译器对程序代码的分析和理解过程。**它通常只跟语言的语法有关，跟目标机器无关。**而与之对应的“后端”则是生成目标代码的过程，跟目标机器有关。**为了方便理解，下图直观地展现了编译器的整个编译过程。

编译器的“前端”技术分为词法分析、语法分析和语义分析三个部分。而它主要涉及自动机和形式语言方面的基础的计算理论。

词法分析

通常，编译器的第一项工作叫做词法分析。就像阅读文章一样，文章是由一个个的中文单词组成的。程序处理也一样，只不过这里不叫单词，而是叫做“词法记号”，英文叫 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;
}

那么，如何写一个程序来识别 Token 呢？可以看到，英文内容中通常用空格和标点把单词分开，方便读者阅读和理解。但在计算机程序中，仅仅用空格和标点分割是不行的。比如“age >= 45”应该分成“age”“>=”和“45”这三个 Token，但在代码里它们可以是连在一起的，中间不用非得有空格。

其实，可以通过制定一些规则来区分每个不同的 Token:

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

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

但是，目前也有用词法分析器的生成工具来生成，比如 Lex（或其 GNU 版本，Flex）。这些生成工具是基于一些规则来工作的，这些规则用“正则文法”表达，符合正则文法的表达式称为“正则表达式”。生成工具可以读入正则表达式，生成一种叫“有限自动机”的算法，来完成具体的词法分析工作。

**有限状态机会分析整个程序的字符串，当遇到不同的字符时，会驱使它迁移到不同的状态。**例如，词法分析程序在扫描 age 的时候，处于“标识符”状态，等它遇到一个 > 符号，就切换到“比较操作符”的状态。词法分析过程，就是这样一个个状态迁移的过程。

有限状态机

词法分析程序在遇到 age、>= 和 45 时，会分别识别成标识符、比较操作符和数字字面量。不过上面的图只是一个简化的示意图，一个严格意义上的有限自动机是下面这种画法：

上面的状态机，会有5个状态：

**1. 初始状态：**刚开始启动词法分析的时候，程序所处的状态。

**2. 标识符状态：**在初始状态时，当第一个字符是字母的时候，迁移到状态 2。当后续字符是字母和数字时，保留在状态 2。如果不是，就离开状态 2，写下该 Token，回到初始状态。

**3. 大于操作符（GT）：**在初始状态时，当第一个字符是 > 时，进入这个状态。它是比较操作符的一种情况。

**4. 大于等于操作符（GE）：**如果状态 3 的下一个字符是 =，就进入状态 4，变成 >=。它也是比较操作符的一种情况。

**5. 数字字面量：**在初始状态时，下一个字符是数字，进入这个状态。如果后续仍是数字，就保持在状态 5。

**依据构造好的有限自动机，在不同的状态中迁移，从而解析出 Token 来。**只要再扩展这个有限自动机，增加里面的状态和迁移路线，就可以逐步实现一个完整的词法分析器了。

语法分析

编译器下一个阶段的工作是语法分析。词法分析是识别一个个的单词，而语法分析就是在词法分析的基础上识别出程序的语法结构。这个结构是一个树状结构，是计算机容易理解和执行的。这棵树叫做抽象语法树（Abstract Syntax Tree，AST）。树的每个节点（子树）是一个语法单元，这个单元的构成规则就叫“语法”。每个节点还可以有下级节点。

下图是以：int age = 45为例的语法树：

语义分析

语义分析是让计算机理解语言的真实意图，把一些模棱两可的地方消除掉。义分析没那么复杂，因为计算机语言的语义一般可以表达为一些规则，语义分析只要检查是否符合这些规则就行了。比如：

• 某个表达式的计算结果是什么数据类型？如果有数据类型不匹配的情况，是否要做自动转换？
• 如果在一个代码块的内部和外部有相同名称的变量，我在执行的时候到底用哪个？ 就像“我喜欢又聪明又勇敢的你”中的“你”，到底指的是谁，需要明确。
• 在同一个作用域内，不允许有两个名称相同的变量，这是唯一性检查。你不能刚声明一个变量 a，紧接着又声明同样名称的一个变量 a，这就不允许了。