C4编译器复现：CmmCompiler

Catz! by Ann-Sophie De Steur

引言

“C4编译器复现” 这一系列教程将带你从头编写一个 C 语言的编译器。希望通过这个系列，我们能对编译器的构建有一定的了解，同时，我们也将构建出一个能用的 C 语言编译器，尽管有许多语法并不支持。

“compiler” is primarily used for programs that translate source code from a high-level programming language to a lower level language (e.g. assembly language, object code, or machine code) to create an executable program.

在开始进入正题之前，本篇是一些闲聊，谈谈这个系列的初衷。如果你急切地想进入正篇，请跳过本章。

为什么要学编译原理

如果要我说计算机专业最重要的三门课，我会说是《数据结构》、《算法》和《编译原理》。在我看来，能不能理解“递归”像是程序员的第一道门槛，而会不会写编译器则是第二道。

（当然，并不是说是没写过编译器就不是好程序员，只能说它是一个相当大的挑战吧）

以前人们会说，学习了编译原理，你就能写出更加高效的代码，但随着计算机性能的提升，代码是否高效显得就不那么重要了。那么为什么要学习编译原理呢？

原因只有一个：装B。

好吧，也许现在还想学习编译原理的人只可能是因为兴趣了。一方面想了解它的工作原理；另一方面希望挑战一下自己，看看自己能走多远。

理论很复杂，实现也很复杂？

我对编译器一直心存敬佩。所以当学校开《编译原理》的课程后，我是抱着满腔热情去上课的，但是两节课后我就放弃了。原因是太复杂了，听不懂。

一般编译原理的课程会说一些：

1. 如何表示语法（BNF什么的）
2. 词法分析，用什么有穷自动机和无穷自动机
3. 语法分析，递归下降法，什么 LL(k)，LALR 分析。
4. 中间代码的表示
5. 代码的生成
6. 代码优化

我相信绝大多数（98％）的学生顶多学到语法分析就结束了。并且最重要的是，学了这么多也没用！依旧帮助不了我们学习编译器！这其中最主要的原因是《编译原理》试图教会我们的是如何构造“编译器生成器”，即构造一个工具，根据文法来生成编译器（如 lex/yacc）等等。

这些理论试图教会我们如何用通用的方法来自动解决问题，它们有很强的实际意义，只是对于一般的学生或程序员来说，它们过于强大，内容过于复杂。如果你尝试阅读 lex/yacc （或 flex/bison）的代码，就会发现太可怕了。

然而如果你能跟我一样，真正来实现一个简单的编译器，那么你会发现，比起可怕的《编译原理》，这点复杂度还是不算什么的（因为好多理论根本用不上）。

项目的初衷

有一次在 Github 上看到了一个项目（当时很火的），名叫 c4，号称用 4 个函数来实现了一个小的 C 语言编译器。它最让我震惊的是能够自举，即能自己编译自己。并且它用很少的代码就完成了一个功能相当完善的 C 语言编译器。

一般的编译器相关的教程要么就十分简单（如实现四则运算），要么就是借助了自动生成的工具（如 flex/bison）。而 c4 的代码完全是手工实现的，不用外部工具。可惜的是它的代码初衷是代码最小化，所以写得很乱，很难懂。所以本项目的主要目的：

1. 实现一个功能完善的 C 语言编译器
2. 通过教程来说明这个过程。

c4 大致500+行。重写的代码历时一周，总共代码加注释1400行。项目地址: Write a C Interpreter。

声明：本项目中的代码逻辑绝大多数取自 c4 ，但确为自己重写。

做好心理准备

在写编译器的时候会遇到两个主要问题：

1. 繁琐，会有许多相似的代码，写起来很无聊。
2. 难以调试，一方面没有很好的测试用例，另一方面需要对照生成的代码来调试（遇到的时候就知道了）。

所以我希望你有足够的耐心和时间来学习，相信当你真正完成的时候会像我一样，十分有成就感。

PS. 第一篇完全没有正题相关的内容也是希望你能有所心理准备再开始学习。

参考资料

最后想介绍几个资料：

1. Let’s Build a Compiler 很好的初学者教程，英文的。
2. Lemon Parser Generator，一个语法分析器生成器，对照《编译原理》观看效果更佳。

由于本人水平一般，文章、代码难免会有错误，敬请批评指正！

最后祝你学得愉快。

设计

首先要说明的是，虽然标题是编译器，但实际上我们构建的是 C 语言的解释器，这意味着我们可以像运行脚本一样去运行 C 语言的源代码文件。这么做的理由有两点：

1. 解释器与编译器仅在代码生成阶段有区别，而其它方面如词法分析、语法分析是一样的。
2. 解释器需要我们实现自己的虚拟机与指令集，而这部分能帮助我们了解计算机的工作原理。

编译器的构建流程

一般而言，编译器的编写分为 3 个步骤：

1. 词法分析器，用于将字符串转化成内部的表示结构。
2. 语法分析器，将词法分析得到的标记流（token）生成一棵语法树。
3. 目标代码的生成，将语法树转化成目标代码。

已经有许多工具能帮助我们处理阶段1和2，如 flex 用于词法分析，bison 用于语法分析。只是它们的功能都过于强大，屏蔽了许多实现上的细节，对于学习构建编译器帮助不大。所以我们要完全手写这些功能。

所以我们会依照以下步骤来构建我们的编译器：

1. 构建我们自己的虚拟机以及指令集。这后生成的目标代码便是我们的指令集。
2. 构建我们的词法分析器
3. 构建语法分析器

编译器框架

我们的编译器主要包括 4 个函数：

1. next() 用于词法分析，获取下一个标记，它将自动忽略空白字符。
2. program() 语法分析的入口，分析整个 C 语言程序。
3. expression(level) 用于解析一个表达式。
4. eval() 虚拟机的入口，用于解释目标代码。

这里有一个单独用于解析“表达式”的函数 expression 是因为表达式在语法分析中相对独立并且比较复杂，所以我们将它单独作为一个模块（函数）。下面是相应的源代码：

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>  // open()
#include <zconf.h>  // close()

int token;              // current token
char* src, *old_src;    // pointer to source code string
int poolsize;           // default size of text/data/stack
int line;               // line number

void next() {
    token = *src++;
    return;
}

void expression(int level) {
    // do nothing
}

void program() {
    next();                 // get next token
    while (token > 0) {
        printf("token is: %c\n", token);
        next();
    }
}

int eval() {  // do nothing yet
    return 0;
}

int main(int argc, char** argv) {
    int i, fd;

    argc--;
    argv++;

    poolsize = 256 * 1024;  // arbitrary size
    line = 1;

    fd = open(*argv, 0);
    if (fd < 0) {
        printf("could not open(%s)\n", *argv);
        return -1;
    }

    if (!(src = old_src = malloc(poolsize))) {
        printf("could not malloc(%d) for source area\n", poolsize);
        return -1;
    }

    // read the source file
    if ((i = read(fd, src, poolsize - 1)) <= 0) {
        printf("read() returned %d\n", i);
        return -1;
    }
    src[i] = 0; // add EOF character
    close(fd);

    program();
    return eval();
}

上面的代码看上去挺复杂，但其实内容不多。它的流程为：读取一个文件（内容为 C 语言代码），逐个读取文件中的字符，并输出。这里需要的是注意每个函数的作用，后面的文章中，我们将逐个填充每个函数的功能，最终构建起我们的编译器。

这样我们就有了一个最简单的编译器：什么都不干的编译器，下一章中，我们将实现其中的eval函数，即我们自己的虚拟机。

虚拟机

计算机的内部工作原理

计算机中有三个基本部件需要我们关注：CPU、寄存器及内存。代码（汇编指令）以二进制的形式保存在内存中；CPU 从中一条条地加载指令执行；程序运行的状态保存在寄存器中。

内存

内存用于存储数据，这里的数据可以是代码，也可以是其它的数据。现代操作系统在操作内存时，并不是直接处理”物理内存“，而是操作”虚拟内存“。虚拟内存可以理解为一种映射，它的作用是屏蔽了物理的细节。例如 32 位的机器中，我们可以使用的内存地址为 2^32 = 4G，而电脑上的实际内存可能只有 256 M。操作系统将我们使用的虚拟地址映射到了到实际的内存上。

当然，我们这里并不需要了解太多，但需要了解的是：进程的内存会被分成几个段：

1. 代码段（text）用于存放代码（指令）
2. 数据段（data）用于存放初始化了的数据，如int i = 10;，就需要存放到数据段中
3. 未初始化数据段（bss）用于存放未初始化的数据，如 int i[1000];，因为不关心其中的真正数值，所以单独存放可以节省空间，减少程序的体积
4. 栈（stack）用于处理函数调用相关的数据，如调用帧（calling frame）或是函数的局部变量等
5. 堆（heap）用于为程序动态分配内存

它们在内存中的位置类似于下图：

+------------------+
|    stack   |     |      high address
|    ...     v     |
|                  |
|                  |
|                  |
|                  |
|    ...     ^     |
|    heap    |     |
+------------------+
| bss  segment     |
+------------------+
| data segment     |
+------------------+
| text segment     |      low address
+------------------+

我们的虚拟机并不打算模拟完整的计算机，因此简单起见，我们只关心三个内容：代码段、数据段以及栈。其中的数据段我们只用来存放字符串，因为我们的编译器并不支持初始化变量，因此我们也不需要未初始化数据段。

当用户的程序需要分配内存时，理论上我们的虚拟机需要维护一个堆用于内存分配，但实际实现上较为复杂且与编译无关，故我们引入一个指令MSET，使我们能直接使用编译器（解释器）中的内存。

综上，我们需要首先在全局添加如下代码：

int *text,            // text segment
    *old_text,        // for dump text segment
    *stack;           // stack
char *data;           // data segment

注意这里的类型，虽然是int型，但理解起来应该作为无符号的整型，因为我们会在代码段（text）中存放如指针/内存地址的数据，它们就是无符号的。其中数据段（data）由于只存放字符串，所以是 char * 型的。

接着，在main函数中加入初始化代码，真正为其分配内存：

int main() {
    close(fd);
    ...

    // allocate memory for virtual machine
    if (!(text = old_text = malloc(poolsize))) {
        printf("could not malloc(%d) for text area\n", poolsize);
        return -1;
    }
    if (!(data = malloc(poolsize))) {
        printf("could not malloc(%d) for data area\n", poolsize);
        return -1;
    }
    if (!(stack = malloc(poolsize))) {
        printf("could not malloc(%d) for stack area\n", poolsize);
        return -1;
    }

    memset(text, 0, poolsize);
    memset(data, 0, poolsize);
    memset(stack, 0, poolsize);

    ...
    program();
}

寄存器

计算机中的寄存器用于存放计算机的运行状态，真正的计算机中有许多不同种类的寄存器，但我们的虚拟机中只使用 4 个寄存器，分别如下：

1. PC 程序计数器，它存放的是一个内存地址，该地址中存放着 下一条 要执行的计算机指令。
2. SP 指针寄存器，永远指向当前的栈顶。注意的是由于栈是位于高地址并向低地址增长的，所以入栈时 SP 的值减小。
3. BP 基址指针。也是用于指向栈的某些位置，在调用函数时会使用到它。
4. AX 通用寄存器，我们的虚拟机中，它用于存放一条指令执行后的结果。

要理解这些寄存器的作用，需要去理解程序运行中会有哪些状态。而这些寄存器只是用于保存这些状态的。

在全局中加入如下定义：

int *pc, *bp, *sp, ax, cycle; // virtual machine registers

在 main 函数中加入初始化代码，注意的是PC在初始应指向目标代码中的main函数，但我们还没有写任何编译相关的代码，因此先不处理。代码如下：

memset(stack, 0, poolsize);
...

bp = sp = (int *)((int)stack + poolsize);
ax = 0;

...
program();

与 CPU 相关的是指令集，我们将专门作为一个小节。

指令集

指令集是 CPU 能识别的命令的集合，也可以说是 CPU 能理解的语言。这里我们要为我们的虚拟机构建自己的指令集。它们基于 x86 的指令集，但更为简单。

首先在全局变量中加入一个枚举类型，这是我们要支持的全部指令：

// instructions
enum {
            // save & load:
    IMM,    // load immediatily
    LEA,    // load effective adress
    LC,     // load char
    LI,     // load int
    SC,     // save char
    SI,     // save int
    PUSH,   // stack peak

            // (a/b/L)
    ADD,    // +
    SUB,    // -
    MUL,    // *
    DIV,    // /
    MOD,    // %
    OR,     // or
    XOR,    // exclusive or
    AND,    // and
    SHL,    // left shift
    SHR,    // right shift
    EQ,     // equal
    NE,     // not equal
    LT,     // less than
    LE,     // less equal
    GT,     // great than
    GE,     // great equal

            // branch & jump
    JMP,    // jump code
    JZ,     // jump zero
    JNZ,    // jump no zero
    CALL,   // return
    NVAR,   // new stack framework for variable
    DARG,   // delte stack framework for argument

            // native call
    OPEN,   // open file
    CLOS,   // close file
    READ,   // read file
    PRTF,   // output file
    MALC,   // memory malloc
    MSET,   // memory set
    MCMP,   // memory compare
    EXIT,   // exit program
};

这些指令的顺序安排是有意的，稍后你会看到，带有参数的指令在前，没有参数的指令在后。这种顺序的唯一作用就是在打印调试信息时更加方便。

load & save

MOV 是所有指令中最基础的一个，它用于将数据放进寄存器或内存地址，有点类似于 C 语言中的赋值语句。x86 的 MOV 指令有两个参数，分别是源地址和目标地址：MOV dest, source （Intel 风格），表示将 source 的内容放在 dest 中，它们可以是一个数、寄存器或是一个内存地址。

一方面，我们的虚拟机只有一个寄存器，另一方面，识别这些参数的类型（是数据还是地址）是比较困难的，因此我们将 MOV 指令拆分成 5 个指令，这些指令只接受一个参数，如下：

1. IMM <num> 将 <num> 放入寄存器 ax 中。
2. LC 将对应地址中的字符载入 ax 中，要求 ax 中存放地址。
3. LI 将对应地址中的整数载入 ax 中，要求 ax 中存放地址。
4. SC 将 ax 中的数据作为字符存放入地址中，要求栈顶存放地址。
5. SI 将 ax 中的数据作为整数存放入地址中，要求栈顶存放地址。

你可能会觉得将一个指令变成了许多指令，整个系统就变得复杂了，但实际情况并非如此。首先是 x86 的 MOV 指令其实有许多变种，根据类型的不同有 MOVB, MOVW 等指令，我们这里的 LC/SC 和 LI/SI 就是对应字符型和整型的存取操作。

但最为重要的是，通过将 MOV 指令拆分成这些指令，只有 IMM 需要有参数，且不需要判断类型，所以大大简化了实现的难度。

在 eval() 函数中加入下列代码：

int eval() {
    // load & save
    int op, *tmp;
    while (1) {
        if (op == IMM)          ax = *pc++;                 // load immediate value to ax
        else if (op == LEA)     ax = (int)(bp + *pc++);     // load immediate value to ax
        else if (op == LC)      ax = *(char*)ax;            // load character to ax, address in ax
        else if (op == LI)      ax = *(int*)ax;             // load integer to ax, address in ax
        else if (op == SC)      *(char*)*sp++ = ax;         // save character to address, value in ax, address on stack
        else if (op == SI)      *(int*)*sp++ = ax;          // save integer to address, value in ax, address on stack
        else if (op == PUSH)    *--sp = ax;
    }


    return 0;
}

IMM

IMM <num> 将 <num> 放入寄存器 ax 中：

if (op == IMM)          ax = *pc++;

LEA

假设我们有一个寄存器 bx 装着一个内存的地址（430430），然后我们想算这个地址往后移 8 位的一个地址。我们可能会用加法存到 ax 里面，如果我们没有 LEA，我们需要：

ADD bx 8	// bx 430430 -> 430438
MOV ax bx	// ax = 430438

这种方式会有几个问题。首先我们改变了 bx 原本的值，计算是有副作用的；加法可能会导致溢出，相加的结果可能大于 32 位的值。为了计算这样一个值带来了大量的副作用，这是我们不希望它发生的，会给后续的计算带来更多的复杂性。

所以我们会通过 LEA 简化实现：

LEA ax (bx + 8)

这样一个指令就会把 bx 加 8 的地址计算好，存到 ax 里面去，在 x86 里面 LEA 就是这么一个作用。在 C4 的实现中 LEA 就不是基于任何地方去算地址的，我们的想法是基于栈去读取地址，其实最多的是用来读取函数的参数和局部变量参数，它们会基于 bp 所在位置。所以我们直接基于 bp 进行加减：

else if (op == LEA)     ax = (int)(bp + *pc++);

这样我们就可以得到这个函数的第几个参数或者是第几个局部变量。

LOAD

load 操作很简单，它就是把现在 ax 里面装的地址所对应的内存的值加载回 ax 里面去，语法如下：

ax = adress;
ax = *ax;

由于类型不同我们会使用不同的指针做一个强制转换：

else if (op == LC)      ax = *(char*)ax;
else if (op == LI)      ax = *(int*)ax;   

SAVE

save 操作依赖于栈顶的 sp 指针，它指向一个地址。我们需要先对这个指针进行强制转换，再对这个地址取 dereference：

sp = adress;
sp = (int*/char*) sp;
*sp = ax;
sp++;

如果对 C 语言熟悉的朋友应该不是很困难：

else if (op == SC)      *(char*)*sp++ = ax;
else if (op == SI)      *(int*)*sp++ = ax;

PUSH

在 x86 中，PUSH 的作用是将值或寄存器，而在我们的虚拟机中，它的作用是将 ax 的值放入栈中。这样做的主要原因是为了简化虚拟机的实现，并且我们也只有一个寄存器 ax 。代码如下：

else if (op == PUSH)    *--sp = ax;                 // push the value of ax onto the stack

a/b/L

我们为 C 语言中支持的运算符都提供对应汇编指令。每个运算符都是二元的，即有两个参数，第一个参数放在栈顶，第二个参数放在 ax 中。这个顺序要特别注意。因为像 -，/ 之类的运算符是与参数顺序有关的。计算后会将栈顶的参数退栈，结果存放在寄存器 ax 中。因此计算结束后，两个参数都无法取得了（汇编的意义上，存在内存地址上就另当别论）。

实现如下：

// a/b/L
else if (op == OR)      ax = *sp++ |  ax;
else if (op == XOR)     ax = *sp++ ^  ax;
else if (op == AND)     ax = *sp++ &  ax;
else if (op == EQ)      ax = *sp++ == ax;
else if (op == NE)      ax = *sp++ != ax;
else if (op == LT)      ax = *sp++ <  ax;
else if (op == LE)      ax = *sp++ <= ax;
else if (op == GT)      ax = *sp++ >  ax;
else if (op == GE)      ax = *sp++ >= ax;
else if (op == SHL)     ax = *sp++ >> ax;
else if (op == SHR)     ax = *sp++ << ax;
else if (op == ADD)     ax = *sp++ +  ax;
else if (op == SUB)     ax = *sp++ -  ax;
else if (op == MUL)     ax = *sp++ *  ax;
else if (op == DIV)     ax = *sp++ /  ax;
else if (op == MOD)     ax = *sp++ %  ax;

branch & jump

JMP

JMP <addr> 是跳转指令，无条件地将当前的 PC 寄存器设置为指定的 <addr>，实现如下：

else if (op == JMP)     pc = (int*)*pc;                 // jump to the address

需要注意的是，pc 寄存器指向的是 下一条 指令。所以此时它存放的是 JMP 指令的参数，即 <addr> 的值。

JZ/JNZ

为了实现 if 语句，我们需要条件判断相关的指令。这里我们只实现两个最简单的条件判断，即结果（ax）为零或不为零情况下的跳转。

实现如下：

else if (op == JZ)      pc = ax ? pc + 1 : (int*)*pc;   // jump if ax is zero
else if (op == JNZ)     pc = ax ? (int*)*pc : pc + 1;   // jump if ax is not zero

function call

CALL

首先我们介绍 CALL <addr> 与 RET 指令，CALL 的作用是跳转到地址为 <addr> 的子函数，RET 则用于从子函数中返回。

为什么不能直接使用 JMP 指令呢？原因是当我们从子函数中返回时，程序需要回到跳转之前的地方继续运行，这就需要事先将这个位置信息存储起来。反过来，子函数要返回时，就需要获取并恢复这个信息。因此实际中我们将 PC 保存在栈中。如下：

else if (op == CALL) {                                  // call function
	*--sp = (int)(pc + 1);                              // push pc + 1 to stack & pc jump to func addr(pc point to)
	pc = (int*)pc;
}

NVAR

else if (op == NVAR) {                                  // new stack frame for vars
    *--sp = (int)bp;                                    // save bp, bp -> caller stack, stack add frame
    bp = sp;
    sp = sp - *pc++;
}

DARG

else if (op == DARG)    sp = sp + *pc++;                // delete stack frame for args

RET

else if (op == RET) {                                   // return caller
    sp = bp;                                            // retore stack, restore old bp, pc point to caller code addr
    bp = (int*)*sp++;
    pc = (int*)*sp++;
}

native call

写的程序要”有用“，除了核心的逻辑外还需要输入输出，例如 C 语言中我们经常使用的 printf 函数就是用于输出。但是 printf 函数的实现本身就十分复杂，如果我们的编译器要达到自举，就势必要实现 printf 之类的函数，但它又与编译器没有太大的联系，因此我们继续实现新的指令，从虚拟机的角度予以支持。

编译器中我们需要用到的函数有：exit, open, close, read, printf, malloc, memset 及 memcmp。代码如下：

// native call
else if (op == OPEN)    ax = open((char*)sp[1], sp[0]);
else if (op == CLOS)    ax = close(*sp);
else if (op == READ)    ax = read(sp[2], (char*)sp[1], *sp);
else if (op == PRTF) {
    tmp = sp + pc[1];
    ax = printf((char*)tmp[-1], tmp[-2]);
}
else if (op == MALC)    ax = (int)malloc(*sp);
else if (op == MSET)    ax = (int)memset((char *)sp[2], sp[1], *sp);
else if (op == MCMP)    ax = memcmp((char *)sp[2], (char *)sp[1], *sp);
else if (op == EXIT) {
    printf("exit(%lld)", *sp);
    return -1;
}
else {
    printf("unknown instruction:%lld, cycle: %lld\n", op, cycle);
    return -1;
}

这里的原理是，我们的电脑上已经有了这些函数的实现，因此编译编译器时，这些函数的二进制代码就被编译进了我们的编译器，因此在我们的编译器/虚拟机上运行我们提供的这些指令时，这些函数就是可用的。换句话说就是不需要我们自己去实现了。

最后再加上一个错误判断：

else {
    printf("unknown instruction:%d\n", op);
    return -1;
}

测试

下面我们用我们的汇编写一小段程序，来计算 10+20，在 main 函数中加入下列代码：

int main(int argc, char *argv[])
{
    ax = 0;
    ...

    i = 0;
    text[i++] = IMM;
    text[i++] = 10;
    text[i++] = PUSH;
    text[i++] = IMM;
    text[i++] = 20;
    text[i++] = ADD;
    text[i++] = PUSH;
    text[i++] = EXIT;
    pc = text;

    ...
    program();
}

编译程序 gcc xc-tutor.c，运行程序：./a.out hello.c。输出

exit(30)

另外，我们的代码里有一些指针的强制转换，默认是 32 位的，因此在 64 位机器下，会出现 segmentation fault，解决方法（二选一）：

1. 编译时加上 -m32 参数：gcc -m32 xc-tutor.c
2. 在代码的开头，增加 #define int long long，long long 是 64 位的，不会出现强制转换后的问题。

注意我们的之前的程序需要指令一个源文件，只是现在还用不着，但从结果可以看出，我们的虚拟机还是工作良好的。

词法分析器

什么是词法分析器

简而言之，词法分析器用于对源码字符串做预处理，以减少语法分析器的复杂程度。

词法分析器以源码字符串为输入，输出为标记流（token stream），即一连串的标记，每个标记通常包括： (token, token value) 即标记本身和标记的值。例如，源码中若包含一个数字 '998' ，词法分析器将输出 (Number, 998)，即（数字，998）。再例如：

2 + 3 * (4 - 5)
=>
(Number, 2) Add (Number, 3) Multiply Left-Bracket (Number, 4) Subtract (Number, 5) Right-Bracket

通过词法分析器的预处理，语法分析器的复杂度会大大降低，这点在后面的语法分析器我们就能体会。

词法分析器与编译器

要是深入词法分析器，你就会发现，它的本质上也是编译器。我们的编译器是以标记流为输入，输出汇编代码，而词法分析器则是以源码字符串为输入，输出标记流。

                   +-------+                      +--------+
-- source code --> | lexer | --> token stream --> | parser | --> assembly
                   +-------+                      +--------+

在这个前提下，我们可以这样认为：直接从源代码编译成汇编代码是很困难的，因为输入的字符串比较难处理。所以我们先编写一个较为简单的编译器（词法分析器）来将字符串转换成标记流，而标记流对于语法分析器而言就容易处理得多了。

词法分析器的实现

由于词法分析的工作很常见，但又枯燥且容易出错，所以人们已经开发出了许多工具来生成词法分析器，如 lex, flex。这些工具允许我们通过正则表达式来识别标记。

这里注意的是，我们并不会一次性地将所有源码全部转换成标记流，原因有二：

1. 字符串转换成标记流有时是有状态的，即与代码的上下文是有关系的。
2. 保存所有的标记流没有意义且浪费空间。

所以实际的处理方法是提供一个函数（即前几篇中提到的 next()），每次调用该函数则返回下一个标记。

支持的标记

在全局中添加如下定义：

// tokens and classes (operators last and in precedence order)
enum {
  Num = 128, Fun, Sys, Glo, Loc, Id,
  Char, Else, Enum, If, Int, Return, Sizeof, While,
  Assign, Cond, Lor, Lan, Or, Xor, And, Eq, Ne, Lt, Gt, Le, Ge, Shl, Shr, Add, Sub, Mul, Div, Mod, Inc, Dec, Brak
};

这些就是我们要支持的标记符。例如，我们会将 = 解析为 Assign；将 == 解析为 Eq；将 != 解析为 Ne 等等。

所以这里我们会有这样的印象，一个标记（token）可能包含多个字符，且多数情况下如此。而词法分析器能减小语法分析复杂度的原因，正是因为它相当于通过一定的编码（更多的标记）来压缩了源码字符串。

当然，上面这些标记是有顺序的，跟它们在 C 语言中的优先级有关，如 *(Mul) 的优先级就要高于 +(Add)。它们的具体使用在后面的语法分析中会提到。

最后要注意的是还有一些字符，它们自己就构成了标记，如右方括号 ] 或波浪号 ~ 等。我们不另外处理它们的原因是：

1. 它们是单字符的，即并不是多个字符共同构成标记（如 == 需要两个字符）；
2. 它们不涉及优先级关系。

词法分析器的框架

即 next() 函数的主体：

void next() {
    char *last_pos;
    int hash;

    while (token = *src) {
        ++src;
        // parse token here
    }
    return;
}

这里的一个问题是，为什么要用 while 循环呢？这就涉及到编译器（记得我们说过词法分析器也是某种意义上的编译器）的一个问题：如何处理错误？

对词法分析器而言，若碰到了一个我们不认识的字符该怎么处理？一般处理的方法有两种：

1. 指出错误发生的位置，并退出整个程序
2. 指出错误发生的位置，跳过当前错误并继续编译

这个 while 循环的作用就是跳过这些我们不识别的字符，我们同时还用它来处理空白字符。我们知道，C 语言中空格是用来作为分隔用的，并不作为语法的一部分。因此在实现中我们将它作为“不识别”的字符，这个 while 循环可以用来跳过它。

换行符

换行符和空格类似，但有一点不同，每次遇到换行符，我们需要将当前的行号加一：

// parse token here
...

if (token == '\n') {
    ++line;
}
...

宏定义

C 语言的宏定义以字符 # 开头，如 # include <stdio.h>。我们的编译器并不支持宏定义，所以直接跳过它们。

else if (token == '#') {
    // skip macro, because we will not support it
    while (*src != 0 && *src != '\n') {
        src++;
    }
}

标识符与符号表

标识符（identifier）可以理解为变量名。对于语法分析而言，我们并不关心一个变量具体叫什么名字，而只关心这个变量名代表的唯一标识。例如 int a; 定义了变量 a，而之后的语句 a = 10，我们需要知道这两个 a 指向的是同一个变量。

基于这个理由，词法分析器会把扫描到的标识符全都保存到一张表中，遇到新的标识符就去查这张表，如果标识符已经存在，就返回它的唯一标识。

那么我们怎么表示标识符呢？如下：

struct identifier {
    int token;
    int hash;
    char * name;
    int class;
    int type;
    int value;
    int Bclass;
    int Btype;
    int Bvalue;
}

这里解释一下具体的含义：

1. token：该标识符返回的标记，理论上所有的变量返回的标记都应该是 Id，但实际上由于我们还将在符号表中加入关键字如 if, while 等，它们都有对应的标记。
2. hash：顾名思义，就是这个标识符的哈希值，用于标识符的快速比较。
3. name：存放标识符本身的字符串。
4. class：该标识符的类别，如数字，全局变量或局部变量等。
5. type：标识符的类型，即如果它是个变量，变量是 int 型、char 型还是指针型。
6. value：存放这个标识符的值，如标识符是函数，刚存放函数的地址。
7. BXXXX：C 语言中标识符可以是全局的也可以是局部的，当局部标识符的名字与全局标识符相同时，用作保存全局标识符的信息。

由上可以看出，我们实现的词法分析器与传统意义上的词法分析器不太相同。传统意义上的符号表只需要知道标识符的唯一标识即可，而我们还存放了一些只有语法分析器才会得到的信息，如 type 。

由于我们的目标是能自举，而我们定义的语法不支持 struct，故而使用下列方式。

Symbol table:
----+-----+----+----+----+-----+-----+-----+------+------+----
 .. |token|hash|name|type|class|value|btype|bclass|bvalue| ..
----+-----+----+----+----+-----+-----+-----+------+------+----
    |<---       one single identifier                --->|

即用一个整型数组来保存相关的ID信息。每个ID占用数组中的9个空间，分析标识符的相关代码如下：

int token_val;                // value of current token (mainly for number)
int *current_id,              // current parsed ID
    *symbols;                 // symbol table

// fields of identifier
enum {Token, Hash, Name, Type, Class, Value, BType, BClass, BValue, IdSize};


void next() {
        ...

        else if ((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || (token == '_')) {

            // parse identifier
            last_pos = src - 1;
            hash = token;

            while ((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || (*src == '_')) {
                hash = hash * 147 + *src;
                src++;
            }

            // look for existing identifier, linear search
            current_id = symbols;
            while (current_id[Token]) {
                if (current_id[Hash] == hash && !memcmp((char *)current_id[Name], last_pos, src - last_pos)) {
                    //found one, return
                    token = current_id[Token];
                    return;
                }
                current_id = current_id + IdSize;
            }


            // store new ID
            current_id[Name] = (int)last_pos;
            current_id[Hash] = hash;
            token = current_id[Token] = Id;
            return;
        }
        ...
}

查找已有标识符的方法是线性查找 symbols 表。

数字

数字中较为复杂的一点是需要支持十进制、十六进制及八进制。逻辑也较为直接，可能唯一不好理解的是获取十六进制的值相关的代码。

token_val = token_val * 16 + (token & 15) + (token >= 'A' ? 9 : 0);

这里要注意的是在ASCII码中，字符a对应的十六进制值是 61, A是41，故通过 (token & 15) 可以得到个位数的值。其它就不多说了，这里这样写的目的是装B（其实是抄 c4 的源代码的）。

void next() {
        ...


        else if (token >= '0' && token <= '9') {
            // parse number, three kinds: dec(123) hex(0x123) oct(017)
            token_val = token - '0';
            if (token_val > 0) {
                // dec, starts with [1-9]
                while (*src >= '0' && *src <= '9') {
                    token_val = token_val*10 + *src++ - '0';
                }
            } else {
                // starts with number 0
                if (*src == 'x' || *src == 'X') {
                    //hex
                    token = *++src;
                    while ((token >= '0' && token <= '9') || (token >= 'a' && token <= 'f') || (token >= 'A' && token <= 'F')) {
                        token_val = token_val * 16 + (token & 15) + (token >= 'A' ? 9 : 0);
                        token = *++src;
                    }
                } else {
                    // oct
                    while (*src >= '0' && *src <= '7') {
                        token_val = token_val*8 + *src++ - '0';
                    }
                }
            }

            token = Num;
            return;
        }

        ...
}

递归下降

变量定义

函数定义

语句

表达式

总结