如何实现一个简易版语言编译器？

野性酷女 2022-11-09 03:59 137阅读 0赞

# 编译器实现之旅——第一章 编译器概观 #

编译器，近在咫尺却又远在天边。当我们写下任何非机器语言代码后，我们都需要借助编译器将这些代码变为通过计算机可运行的状态。但是，就是这样一个使用率极高的程序，我们对其却知之甚少。什么是编译器？编译器对我们的代码做了什么？又是怎么做的呢？如果你也怀有这些疑问，想要深入编译器内部一探究竟的话，那就随我一起踏上这趟编译器实现的旅程吧。

## 1. 什么是编译器 ##

广义上，编译器是这样一个程序：其读入A语言代码，并输出B语言代码。如下图所示：

+-------+
        A语言代码 -> | 编译器 | -> B语言代码
                    +-------+

仅从定义上看，A、B可以是同一种语言。也就是说，如果我们写了一个只是具有“复制粘贴”功能的程序，其也可以被称为是一个编译器。但显然，这样的编译器是无意义的。在实际中，编译器的输入一般是高级语言代码，如C语言、Python语言等，而编译器的输出一般是低级语言代码，如汇编语言、各种字节码等。汇编语言代码经由汇编语言编译器继续编译，最终产生机器语言，以供计算机执行；而字节码可由能够执行此字节码的虚拟机执行。这样，就完成了一个程序从编写到执行的过程。

## 2. 编译器的结构组成 ##

编译器的内部并不是一个整体，而是由多个组件分工合作，共同完成编译功能。这些组件总体上可被分为两个部分：编译器前端和编译器后端。如下图所示：

+----------+               +----------+
        A语言代码 -> | 编译器前端 | -> 中间代码 -> | 编译器后端 | -> B语言代码
                    +----------+               +----------+

由于我们写下的高级语言代码并不是编译器比较喜欢的形式，故编译器通过编译器前端读取、检查并重新组织源代码，使之等价变换为编译器喜欢的形式，即中间代码；一般来说，语法错误也由编译器前端负责检查。接下来，编译器后端就拿着中间代码进行进一步的检查、优化，最终生成目标代码。

事实上，编译器前后端又分别可以进一步细分为多个组件，这些组件将在我们接下来的旅程中逐一讲述。

## 3. 我们将要实现什么 ##

在这次旅程的终点，我们将实现一个名为CMM（即C Minus Minus）语言的编译器，这个编译器的输出将是由我们自己设计的一套指令集中的指令所构成的指令文件。所以，我们还将实现一套虚拟机程序，以运行编译器输出的指令文件。

CMM语言是一门将C语言的语法进行缩减后得到的语言。其主要特点如下：

*  只有一种类型：int
 *  支持赋值、四则运算与比较运算
 *  支持if、while语句
 *  支持函数
 *  支持数组
 *  区分全局作用域与局部作用域

接下来，就让我们深入编译器前端一探究竟吧。请看下一章：

# 编译器实现之旅——第二章 编译器前端概观 #

在这一章的旅程中，我们将要深入编译器前端一探究竟。看看编译器前端到底由哪些组件组成，其分别又是在做什么。

## 1. 编译器前端的结构组成 ##

似乎比我们想象的要简单，编译器前端仅由两个组件组成，词法分析器与语法分析器。请看下图：

+----------+             +-----------+
        源代码 -> | 词法分析器 | -> 记号流 -> | 语法分析器 | -> 抽象语法树
                 +----------+             +-----------+

## 2. 什么是词法分析器 ##

词法分析器（Lexer）是“前端中的前端”。作为整个编译器的第一个组件，词法分析器负责阅读并分割源代码，将编译器看来“胡子连着辫子”的源代码，分割为一个个的记号（Token）流，同时，词法分析器还负责识别并归类每一个记号。当然了，一旦词法分析器发现了一个不应该出现的字符，其就会产生一个错误信息。词法分析器的工作内容如下图所示：

+----------+
        源代码 -> | 词法分析器 | -> (记号的类别, 记号字符串), (记号的类别, 记号字符串), ...
                 +----------+

我们将在词法分析器的相关章节进一步讲述词法分析器的故事。

## 3. 什么是语法分析器 ##

源代码在经过词法分析器无情的切割后，就到了语法分析器该上场的时候了。不难发现，词法分析器所做的工作虽然很厉害，但其终究只是完成了类似于数据清洗的工作，输出的只是线性的记号流，这就像一大段没有章节，甚至没有标点的文字，根本没法阅读。

语法分析器利用词法分析器的工作成果，将线性的，扁平的记号流，根据语法规则重新组织为一棵立体的巨大的树，这就是抽象语法树（AST）。抽象语法树在整个编译器中起着举足轻重的地位，其是整个编译器后端都很喜欢，并需要不断访问的一种数据结构。语法分析器的工作内容如下图所示：

+-----------+
        (记号的类别, 记号字符串), (记号的 类别, 记号字符串), ... -> | 语法分析器 | -> 抽象语法树
                                                             +-----------+

我们将在语法分析器的相关章节进一步讲述语法分析器的故事。

接下来，就让我们来看看这“前端中的前端”：词法分析器，是怎么实现的吧。请看下一章：

# 编译器实现之旅——第三章 实现词法分析器前的准备 #

在这一章的旅程中，我们将要为整个编译器的“前端中的前端”：词法分析器的实现做好充足的准备。

## 1. 词法分析器概观 ##

纵观编译器的输入：源代码，我们不难发现，源代码说白了也就是一个很长很长的字符串。而说到字符串，我们不难想到字符串的分割函数。这类分割函数以空格，或任意的什么字符或字符串作为分隔符，将一个字符串分割成多个小字符串片段。这不就是词法分析器么？你可能会想。但是，我们将遇到这样的问题：

"1 + 1" -> ("1", "+", "1")
        "1+1"   -> ?

确实，使用普通的字符串分割函数可以很轻易的将上面第一个字符串进行分割，但我们发现，无论怎么设置分隔符，我们都无法将第二个字符串也分割成同样的结果了。也就是说，普通的字符串分割函数及其算法是不能胜任词法分析器的工作的，我们必须另想办法。

要想分割一个字符串，其思路无非就是寻找一个分割点，然后将当前起点到分割点的这段字符串分割出去，再将当前起点设置于分割点之后，并继续寻找下一个分割点，不断重复这个过程，直至到达字符串的结尾。那么，为什么字符串分割函数不能胜任词法分析器的工作呢？略加思索不难发现原因：字符串分割函数的“寻找下一个分割点”的逻辑过于简单了，只是一个相等性判断。而我们所需要的逻辑更复杂，比如：看到一个空格，就分割；再比如：看到一个不是数字的字符，就分割；等等。所以，只要我们扩充字符串分割函数的“寻找下一个分割点”的逻辑，我们就能实现出词法分析器了。

## 2. 词法分析器的状态 ##

我们首先需要做什么呢？我们需要为词法分析器定义许多不同的状态，处于不同状态的词法分析器执行不同的行为。显然，词法分析器需要一个开始状态，一个完成状态，其可能还需要一个或多个中间状态。词法分析器从开始状态开始，不断读取源代码中的每个字符，最终结束于完成状态，当词法分析器处于完成状态时，其就分割出了一个记号。词法分析器不断执行这样的“开始, ..., 完成”过程，直至到达字符串的结尾。

为了获知词法分析器到底需要哪些状态，我们需要看一看CMM语言对于记号的定义。请注意，这里的记号是广义的，其不仅代表一个英文单词，还代表一个符号，一串数字等，即，一个记号就是词法分析器需要分割出来的一段字符串。CMM语言对于记号的定义如下所示：

1.  一串连续的，由大写或小写字母构成的字符串
2.  一串连续的，由数字构成的字符串
3.  这些符号：+ - \* / < <= > >= == != = ; , ( ) \[ \] \{ \}
4.  /\* ... \*/ 构成注释
5.  关键词：void int if else while return

这里需要说明的是：所谓关键词，仅仅是上述第1条的一种特例。即：当我们分割出一个单词时，我们需要额外判定一下这个单词是不是关键词，如果是，则我们需要将这个单词的类别从“单词”变为“关键词XX”。例如：当我们分割出字符串“abc”时，我们将其归类为“单词”；而当我们分割出字符串“if”时，我们就需要将其归类为“关键词if”。

有了CMM语言对于记号的定义，我们就可以着手考虑词法分析器到底需要哪些状态了。我们不妨以上述第一条规则为例进行思考，即：为了分割出一个单词，词法分析器需要哪些状态？

首先，词法分析器从“开始”状态开始，如果此时词法分析器读入了一个大写或小写字母，则我们知道：接下来读取到的将是一个单词了；但同时，仅凭读取到的这个字符，我们永远不可能知道当前的这个单词是否已经读取结束；我们只有看到一个不是大写或小写字母的字符时，才能确定刚刚的这个单词已经读取结束了，我们应令词法分析器进入“完成”状态。为了处理这种情况，我们引入中间状态“正在读取单词”。当词法分析器读入一个大写或小写字母时，其应立即由“开始”状态转入“正在读取单词”状态；词法分析器应保持这个状态，并不断读入新的字符，直至当前读入的字符不是大写或小写字母，此时，词法分析器应立即由“正在读取单词”状态转入“完成”状态，完成此次分割。

那么，如何利用上述思路，使词法分析器跳过注释呢？请看：

首先，词法分析器还是从“开始”状态开始，当其读入一个“/”时，我们此时并不知道这个“/”是一个除号，还是注释的开始，故我们先令词法分析器进入“正在读取除号”这个中间状态。在此状态中，如果词法分析器读入的下一个字符是一个“*”，则此时我们就可以确定词法分析器现在进入了注释中，我们就再令词法分析器转入“正在读取注释”状态；反之，如果词法分析器读入的下一个字符不是一个“*”，我们也可以确定词法分析器这次读取到的真的是一个除号，此时，我们当然是令词法分析器进入“完成”状态。

当词法分析器处于“正在读取注释”状态中时，我们需要关注两件事：

1.  词法分析器应丢掉任何读取到的字符
2.  词法分析器应努力的逃离注释

怎么逃离注释呢？显然，如果要逃离注释，我们就需要同时满足这两个条件：

1.  遇到一个“\*”
2.  紧接着，再遇到一个“/”

所以，当词法分析器被困在注释中时，其一边一视同仁的丢掉一切读取到的字符，一边也留心着读取到的字符是不是“*”，如果是，词法分析器就看到了希望。此时，词法分析器应转入“正在逃离注释”状态，在这个状态下，如果词法分析器又读取到了“/”，那么恭喜，此时词法分析器就成功的逃离了注释，又回到了久违的“开始”状态；如果不是“/”，希望也没有完全破灭，此时，如果词法分析器读取到的还是“*”，那么其就还应该停留在“正在逃离注释”状态；而如果读取到的既不是“/”也不是“\*”，那么很遗憾，逃离就彻底失败了，词法分析器又将回退到“正在读取注释”状态。

利用上述思路举一反三，我们即可得到词法分析器所需要的所有状态了。请看：

1.  显然，我们需要“开始”和“完成”状态
2.  为了读取单词和数字，我们需要“正在读取单词”和“正在读取数字”状态
3.  为了处理注释相关问题，我们需要“正在读取除号”、“正在读取注释”和“正在逃离注释”状态
4.  为了明确词法分析器读取到的到底是“<”还是“<=”、是“>”还是“>=”、是“=”还是“==”，我们需要“正在读取小于号”、“正在读取大于号”和“正在读取等号”状态
5.  为了使词法分析器正确的读取到“!=”（而不是“!” + 别的错误符号），我们需要“正在读取不等号”状态

至此，我们就得到了词法分析器所需要的所有状态。代码如下所示：

enum class LEXER_STAGE
    {
        // Start
        START,
    
        // abc...
        //  ^^^^^
        IN_ID,
    
        // 123...
        //  ^^^^^
        IN_NUMBER,
    
        // /?
        //  ^
        IN_DIVIDE,
    
        // /* ...
        //    ^^^
        IN_COMMENT,
    
        // ... */
        //      ^
        END_COMMENT,
    
        // <?
        //  ^
        IN_LESS,
    
        // >?
        //  ^
        IN_GREATER,
    
        // =?
        //  ^
        IN_ASSIGN,
    
        // !?
        //  ^
        IN_NOT,
    
        // Done
        DONE,
    };

## 3. 记号的类别 ##

当词法分析器读取到一个记号后，我们就需要将其进行归类。有了词法分析器的各种状态的辅助，这样的归类将变的十分容易。例如，当我们从“正在读取数字”状态转移至“完成”状态时，我们当然知道当前的这个记号的类别是“数字”；而当我们读取到一个“(”时，我们当然也知道这个记号的类别是“左圆括号”；以此类推。我们可以从上文中给出的记号的定义中，得到所有记号的类别。代码如下所示：

enum class TOKEN_TYPE
    {
        // Word
        ID,                    // ID
        NUMBER,                // Number
    
        // Keyword
        VOID,                  // void
        INT,                   // int
        IF,                    // if
        ELSE,                  // else
        WHILE,                 // while
        RETURN,                // return
    
        // Operator
        PLUS,                  // +
        MINUS,                 // -
        MULTIPLY,              // *
        DIVIDE,                // /
        LESS,                  // <
        LESS_EQUAL,            // <=
        GREATER,               // >
        GREATER_EQUAL,         // >=
        EQUAL,                 // ==
        NOT_EQUAL,             // !=
        ASSIGN,                // =
        SEMICOLON,             // ;
        COMMA,                 // ,
        LEFT_ROUND_BRACKET,    // (
        RIGHT_ROUND_BRACKET,   // )
        LEFT_SQUARE_BRACKET,   // [
        RIGHT_SQUARE_BRACKET,  // ]
        LEFT_CURLY_BRACKET,    // {
        RIGHT_CURLY_BRACKET,   // }
    
        // EOF
        END_OF_FILE,           // EOF
    
        // AST
        DECL_LIST,             // AST: DeclList
        VAR_DECL,              // AST: VarDecl
        FUNC_DECL,             // AST: FuncDecl
        PARAM_LIST,            // AST: ParamList
        PARAM,                 // AST: Param
        COMPOUND_STMT,         // AST: CompoundStmt
        LOCAL_DECL,            // AST: LocalDecl
        STMT_LIST,             // AST: StmtList
        IF_STMT,               // AST: IfStmt
        WHILE_STMT,            // AST: WhileStmt
        RETURN_STMT,           // AST: ReturnStmt
        EXPR,                  // AST: Expr
        VAR,                   // AST: Var
        SIMPLE_EXPR,           // AST: SimpleExpr
        ADD_EXPR,              // AST: AddExpr
        TERM,                  // AST: Term
        CALL,                  // AST: Call
        ARG_LIST,              // AST: ArgList
    };

需要说明的是，上述代码的最后一部分是AST节点类别，与词法分析器无关。我们将在后续的旅程中讲述这部分类别的作用。

## 4. 其他准备工作 ##

在实现词法分析器之前，我们还有一些比较简单的准备工作需要做，列举如下：

1.  我们需要定义一个用于保存记号的结构体：

struct Token
    {
        // Attribute
        TOKEN_TYPE tokenType;
        string tokenStr;
        int lineNo;
    };

在这个结构体中，我们保存了记号的类别、记号字符串，以及这个记号在源代码中所处的行数。

1.  我们需要定义一个哈希表，以完成普通单词到关键词的识别与转换：

const unordered_map<string, TOKEN_TYPE> KEYWORD_MAP
    {
        {"void",   TOKEN_TYPE::VOID},
        {"int",    TOKEN_TYPE::INT},
        {"if",     TOKEN_TYPE::IF},
        {"else",   TOKEN_TYPE::ELSE},
        {"while",  TOKEN_TYPE::WHILE},
        {"return", TOKEN_TYPE::RETURN},
    };

通过键的存在性检测，我们就可以判定一个单词是否是一个关键词了；如果是，我们也可以得到这个关键词所对应的记号的类别。

1.  我们需要定义一个报错函数，用于在词法分析器发现语法错误时报错并退出：

void InvalidChar(char invalidChar, int lineNo)
    {
        printf("Invalid char: %c in line: %d\n", invalidChar, lineNo);
    
        exit(1);
    }