本文为编写C语言编译器系列文章的第一篇，为此我先说明一下我要如此做的一些理由：

1.通过编写过程，你会对抽象语法树（AST）以及程序如何表示和操作其他程序有清晰地了解，并可以熟练地使用linters、静态分析器与各种各样的元编程。

2.你将对汇编，调用约定，以及所有相关的技术细节有个系统了解。

3.由于这是很困难的项目，所以整个过程我都在探索，有不对的地方请大家多指正。

在过去的几个星期里，我一直在借鉴Abdulaziz Ghuloum的“编译器构建的增量方法”，在自己的C语言编译器nqcc进行探索。Ghuloum的方法的大致是这样的：

第一，本文介绍的只是基本的X86汇编语言的一个子集，其中涉及汇编语言的最核心部分，包括寄存器结构，数据表示，基本的操作指令（包括数据传送指令、逻辑计算指令、算数运算指令），以及函数的调用规则。

第二，添加新的语言特性，整个添加过程可以一步一步地慢慢进行。一开始，只会返回常数，而随着步骤的增加，就要处理加减法了。

第三，虽然每一步的进展都很慢，但这保证了你对每一步进行充分的管理，在每一步的末尾，都有一个编译器。

我将在本文中，介绍算术运算，条件语句，局部变量，函数调用等概念。除此以外，我还编写了一些测试程序，以方便验证编译器的每个阶段是否在正常工作。

准备阶段

在编写C语言编译器之前，你还需要完成两件事：

1.决定使用哪种编译器的语言；

2.如何处理解析和词法分析。

对于编写语言，虽然我没有什么硬性规定，你可以用你喜欢的任何语言来编写编译器，但我的建议是使用具有和类型(sum types)和模式匹配的语言，比如OCaml，Haskell或者Rust。因为根据我的经验，这些语言在构建和遍历一个AST时会更加容易。其实最初，我也用的是Python，但是到最后，我还是选择了OCaml。

另外，你还需要决定是编写自己的解析和词法分析器，还是使用自动解析器和扫描生成器（例如flex和bison）。我会在本文中，向你展示如何手动去编写紫的词法分析器（或扫描器）以及递归下降语法分析器。虽然使用 解析生成器可能更容易编写，但我还没有尝试过该方法。你还可以使用扫描生成器来实现词法分析，但前提是要手动编写自己的解析器。

整数分析

一开始，我会编译一个可以返回单个整数的程序。另外，我还将为编译器设置三个基本的路径（pass）。这些被定义的体系结构将为以后添加更多的语言功能提供便利。

下面就是一个经过编译的程序，我将其称为return_2.c。

int main() {
    return 2;}

我只能用一个单一的函数来处理程序main，它由一个单一的return语句组成。唯一不同的是正在返回的整数值，不过我不会处理十六进制或八进制的整数。为了验证你的编译器运行是否正常，你需要编译一个程序，运行它，然后检查它的返回码。

$ ./YOUR_COMPILER return_2.c # compile the source file shown above
$ ./gcc -m32 return_2.s -o return_2 # assemble it into an executable
$ ./return_2 # run the executable you just compiled
$ echo $? # check the return code; it should be 2
2

此时，编译器将生成x86汇编。我不会将汇编程序转换成可执行文件，它们是独立的程序。为了了解这个汇编程序，我用gcc对它进行了编译。

$ gcc -S -O3 -fno-asynchronous-unwind-tables return_2.c
$ cat return_2.s
    .section __TEXT,__text_startup,regular,pure_instructions
    .align 4
    .globl _main
_main:
    movl    $2, %eax
    ret
    .subsections_via_symbols

现在，你就可以看到汇编程序的全貌了。不过，我忽略了.section，.align和.subsections_via_symbols指令，如果你删除它们，你仍然可以组装并运行

return_2.s。 .globl _main表示_main符号应该对链接器可见，否则你无法找到程序的入口点。另外，其中还附有汇编指令：
_main:                  ; label for start of "main" function
    movl    $2, %eax    ; move constant "2" into the EAX register
    ret                 ; return from function

当函数返回时，EAX寄存器将包含它的返回值，而main函数的返回值将是程序的出口代码。

这个汇编程序代码中唯一可以改变的是返回值。因此，一个非常简单的方法就是使用正则表达式从源代码中提取返回值，然后将其插入汇编程序中，你可以利用以下这20行的Python脚本来实现。

import sys, os, re
#expected form of a C program, without line breaks
source_re = r"int mains*(s*)s*{s*returns+(?P<ret>[0-9]+)s*;s*}" 
assembly_format = """    
    .globl _main
_main:
    movl    ${}, %eax
    ret
"""
source_file = sys.argv[1]
assembly_file = os.path.splitext(source_file)[0] + ".s"
with open(source_file, 'r') as infile, open(assembly_file, 'w') as outfile:
    source = infile.read().strip()
    match = re.match(source_re, source)
    # extract the named "ret" group, containing the return value
    retval = match.group('ret') 
    outfile.write(assembly_format.format(retval))

由于用正则表达式来解析整个程序并不是一个长期可行的方法，所以我将编译器分成三个阶段：词法分析，解析和代码生成，这是一个非常标准的编译器结构。

词法分析

词法分析器（也称为扫描器或标记器）是编译器将字符串（源代码）分解为标记列表（list of token）的阶段。标记记号是词法分析器可以理解的最小单位，许多标记就是用空格分隔的单个单词。变量名，关键字和常量以及大括号等标点符号都是标记记号。以下是return_2.c中所有标记的列表：

int关键字
标识符“main”
左括号
右括号
前大括号
返回关键字
常量“2”
分号
后大括号

请注意，某些标记只有一个值（例如，常量标记的值为“2”），另外请注意，没有空格标记。在某些语言中，如Python，空格是很重要的，而且你需要对它进行标记。

以下是你的词法分析器需要识别的所有标记，以及定义每个标记的正则表达式：

前大括号{
后大括号}
左括号(
右括号)
分号
Int关键字int
返回关键字return
标识符[a-zA-Z]w*
整数值[0-9]+

如果你愿意，你可以只使用一个“关键字”标记，而不是为每个关键字都进行不同标记。

可以进行的编写

此时，我就可以编写一个接受文件的lex函数并返回一个标记列表。它应该适用于测试套件中的所有起始示例，包括无效的示例。 所谓无效的示例就是在解析器中引发错误，而不是词法分析器。为了简单起见，我只使用十进制整数。如果你喜欢，你可以扩展你的词法分析器来处理八进制和十六进制整数。不过要注意，没有负整数。

解析过程

现在将我的令牌列表转换为AST， AST是表示程序结构的一种方式。在大多数编程语言中，像条件语句和函数语句这样的语言结构是由简单的结构组成的，比如变量和常量。 而AST可以捕捉到这种关系，AST的根就是整个程序，每个节点都有代表其组成部分的子节点。比如下面这个示例：

if (a < b) {
    c = 2;
    return c;
} else {
    c = 3;
}

由于这个代码片段是一个if语句，所以我将AST的根标记为“if语句”。它将有三个节点：

条件部分（a <b）；
if 部分（c = 2; return c;）；
其它部分（c = 3;）。

其中每个部分都可以进一步分解。例如，条件部分就可以再拆分成两个：

第一个操作数（变量a）；
第二个操作数（变量b）。

赋值语句（如c = 2;）也能再分两部分：被更新的变量（c）和分配给它的表达式（2）。

除此之外，if 部分可以有任意数量的子节点，因为每个语句都是一个子节点。在这种情况下，因为有两个语句，也能再分两部分c = 2; 和return c;。

下面是这个代码片段的完整AST：

下面是构建这个AST的伪代码：

//create if condition
cond = BinaryOp(op='>', operand_1=Var(a), operand_2=Var(b))
//create if body
assign = Assignment(var=Var(c), rhs=Const(2))
return = Return(val=Var(c))
if_body = [assign, return]
//create else body
assign_else = Assignment(var=Var(c), rhs=Const(3))
else_body = [assign_else]
//construct if statement
if = If(condition=cond, body=if_body, else=else_body)

但现在，我不需要担心条件，变量赋值或二元运算符。现在，我需要支持的唯一AST节点是程序，函数语句，语句和表达式。以下是我将如何定义它们的方法：

program = Program(function_declaration)
function_declaration = Function(string, statement) //string is the function name
statement = Return(exp)
exp = Constant(int)

现在，一个程序由一个单一的函数main组成，稍后我会将一个程序定义为函数列表。一开始，每个函数只有一个名称和一个主体。后来，又多了一个参数列表。对于投入运行的C编译器来说，我也需要存储函数的返回类型，不过现在我只有整数类型。函数体是一个单独的语句，稍后我会将它变成语句列表（list of statements）。现在，它只有一种类型的语句——返回语句。稍后我将添加其他类型的语句，如条件和变量语句。返回语句有一个子节点，一个表达式即返回的值。现在表达式只能是一个整数常量。稍后我将让表达式包含算术运算，这将允许我解析像return 2+2这样的语句。

当我添加新的语言结构时，我将更新我的AST节点的定义。例如，当我添加一个新类型的语句——变量赋值，我会在statement定义中添加一个新的范式（form ）：

statement = Return(exp) | Assign(variable, exp)

以下是return_2.c的AST图：

最后，我需要一个正式的语法，它负责定义如何将一系列的标记组合起来形成完整的语言结构。我将在巴科斯范式中定义它：

<program> ::= <function>
<function> ::= "int" <id> "(" ")" "{" <statement> "}"
<statement> ::= "return" <exp> ";"
<exp> ::= <int>

上面的每一行都表示一个运行规则，定义了如何从其他语言结构和标记构建语言结构。运行规则左侧出现的每个符号（例如，<program>，<function>，<statement>）都是非终结符号。而单个标记（例如，关键字，标点符等）则是终端符号。需要注意的是，虽然这个语法让我可以构建一个有效的C程序，但它并没有告诉我如何将这个程序转换成一个AST，例如，在AST中没有对应于常量节点的运行规则。当重写我的语法来为常量创建一个运行规则后，

我发现语法就变得非常简单，起初，每个非终端符号只需一个运行规则。例如，如果我添加了对变量语句的支持，则可以用以下规则来派生语句：

<statement> ::= "return" <int> ";" | "int" <id> "=" <int> ";"

为了将令牌列表转换成AST，我将使用一种称为递归下降解析的技术。我将定义一个函数来解析语法中的每个非终结符号，并返回相应的AST节点。解析符号S的函数应该从列表的开始处删除标记，直到形成S. If的有效派生。如果在解析完成之前，就碰到了一个不在S的运行规则中的标记，将会派生失败。如果S的规则包含其它非终结符，则应该调用其他函数来解析它们。

以下是解析语句的伪代码：

def parse_statement(tokens):
    tok = tokens.next()
    if tok.type != "RETURN_KEYWORD":
        fail()
    tok = tokens.next()
    if tok.type != "INT"
        fail()
    exp = parse_exp(tokens) //parse_exp will pop off more tokens
    statement = Return(exp)
    tok = tokens.next()
    if tok.type != "SEMICOLON":
        fail()
    return statement

稍后，运行规则将是递归的（例如，一个算术表达式可以包含其他表达式），这意味着解析函数也将是递归的，因此此方法就顺理地被称为递归下降解析。

编写一个解析函数，从而接受一个标记列表并返回一个基于程序节点的AST。该函数应该为所有有效的示例构建正确的AST，并在所有无效的示例中引发错误。

有许多表示AST的代码，具体取决于编译器所使用的语言。例如，可以将AST节点定义为OCaml数据类型：

type exp = Const(int)
type statement = Return(exp)
type fun_decl = Fun(string, statement)
type prog = Prog(fun_decl)

代码的生成

现在我已经构建了一个AST，并准备生成一些汇编程序，我只需要发送四行汇编即可。为了发送，我将遍历AST，这意味着我将按以下顺序访问：

1.函数名称（不是一个真正的节点，而是函数定义中的第一项）；

2.返回值；

3.返回语句。

这个遍历可以确保在使用汇编程序之前预定义一个值，例如，我在返回语句中引用之前生成的返回值。

以下就是我需要的汇编程序：

1.生成一个函数（例如函数“foo”）：

 .globl _foo
_foo:
 <FUNCTION BODY GOES HERE>

2.生成返回语句（例如，return 3;）：

 movl    $3, %eax
 ret

可以进行的编写

编写一个接受AST并生成汇编程序的生成函数。它可以将程序集作为字符串返回，也可以直接将其写入文件。它应该为所有有效示例生成正确的汇编程序。

输出

此时，你可能需要一个实用程序函数来打印出AST，以帮助进行调试。你可以现在就编写或者等到你需要的时候再写。下面是使用nqcc输出的return_2.c。

FUN INT main:
    params: ()
    body:
        RETURN Int<2>

这个示例包含了AST不需要的一些信息，比如返回类型和函数参数列表。

可以进行的编写

用一种可读的方式写一个预打印的函数，它以AST的形式打印出来。

编写一个接受C源文件并输出可执行文件的程序，该程序要实现的功能如下：

1.阅读文件；

2.词法分析；

3.解析；

4.生成汇编程序；

5.将汇编程序写入文件；

6.调用GCC命令将汇编程序转换为可执行文件：

gcc -m32 assembly.s -o out

在此命令中，“assembly.s”是汇编程序文件的名称，“out”是要生成的可执行文件的名称。 -m32选项会调用GCC命令构建一个32位的二进制文件。如果需要，可以省略该选项并构建64位二进制文件，但稍后需要对代码生成步骤进行一些更改（例如，使用64位寄存器）。

7.删除汇编程序文件。

测试

你可以通过测试你的编译器查看是否正确地使用了测试脚本，正常情况下，它会使用你的编译器编译一组测试程序，然后执行它们，并确保它们返回正确的值。

调用过程如下：

./test_compiler.sh /path/to/your/compiler

要用脚本测试，你的编译器就需要遵循下面这3个标准：

1.可以从命令行调用一个C源文件作为参数，例如：./YOUR_COMPILER /path/to/program.c。

2.当通过program.c时，它会在同一个目录下生成可执行程序。

3.如果解析失败，它不会生成程序集或可执行文件，因为这是测试脚本检查无效测试程序的方法。

要注意的是，虽然该脚本不负责检查编译器是否输出了合理的错误信息，但可以使用无效的测试程序来手动测试。