搬运自https://github.com/DoctorWkt/acwj，一个介绍如何使用C语言编写一个可自举的类C语言编译器的说明。进行了粗略的翻译。

【acwj】04，An Actual Compiler 一个真正的编译器

It’s about time that I met my promise of actually writing a compiler. So in this part of the journey we are going to replace the interpreter in our program with code that generates x86-64 assembly code.

现在是我兑现承诺的时候了，我要真正编写一个编译器。因此，在旅程的这一部分，我们将用生成x86-64汇编代码的代码替换程序中的解释器。

Revising the Interpreter 修改解释器

Before we do, it will be worthwhile to revisit the interpreter code in interp.c:

在此之前，我们有必要重温interp.c中的解释器代码：

int interpretAST(struct ASTnode *n) {
  int leftval, rightval;

  if (n->left) leftval = interpretAST(n->left);
  if (n->right) rightval = interpretAST(n->right);

  switch (n->op) {
    case A_ADD:      return (leftval + rightval);
    case A_SUBTRACT: return (leftval - rightval);
    case A_MULTIPLY: return (leftval * rightval);
    case A_DIVIDE:   return (leftval / rightval);
    case A_INTLIT:   return (n->intvalue);

    default:
      fprintf(stderr, "Unknown AST operator %d\n", n->op);
      exit(1);
  }
}

The interpretAST() function walks the given AST tree depth-first. It evaluates any left sub-tree, then the right sub-tree. Finally, it uses the op value at the base of the current tree to operate on these children.

函数interpretAST() 的作用是：首先遍历给定的AST树深度。它计算所有左子树，然后再计算右子树。最后，它使用当前树底部的op值进行操作。

If the op value is one of the four maths operators, then this maths operation is performed. If the op value indicates that the node is simply an integer literal, the literal value is return.

如果op值是四个数学运算符之一，则执行此数学运算。如果op值指示节点只是一个整数字面值，则返回。

The function returns the final value for this tree. And, as it is recursive, it will calculate the final value for a whole tree one sub-sub-tree at a time.

函数返回此树的最终值。而且，由于它是递归的，它将一次计算一棵整棵树的最终值，一个子树。

Changing to Assembly Code Generation 更改为汇编代码生成器

We are going to write an assembly code generator which is generic. This is, in turn, going to call out to a set of CPU-specific code generation functions.

我们将要编写一个通用的汇编代码生成器。意思是说，反过来调用一组与特定CPU有关的代码生成函数。

Here is the generic assembly code generator in gen.c:
以下是汇编代码的生成器

// Given an AST, generate
// assembly code recursively
static int genAST(struct ASTnode *n) {
  int leftreg, rightreg;

  // Get the left and right sub-tree values
  if (n->left) leftreg = genAST(n->left);
  if (n->right) rightreg = genAST(n->right);

  switch (n->op) {
    case A_ADD:      return (cgadd(leftreg,rightreg));
    case A_SUBTRACT: return (cgsub(leftreg,rightreg));
    case A_MULTIPLY: return (cgmul(leftreg,rightreg));
    case A_DIVIDE:   return (cgdiv(leftreg,rightreg));
    case A_INTLIT:   return (cgload(n->intvalue));

    default:
      fprintf(stderr, "Unknown AST operator %d\n", n->op);
      exit(1);
  }
}

Looks familar, huh?! We are doing the same depth-first tree traversal. This time:

• A_INTLIT: load a register with the literal value
• Other operators: perform a maths function on the two registers that hold the left-child’s and right-child’s value

看起来很熟悉，对吧？！我们正在进行相同的深度优先树遍历。这一次：

• A_INTLIT：加载存储字面值的寄存器
• 其他运算符：在两个寄存器上执行数学函数，这两个寄存器分别保存左、右子级的值

Instead of passing values, the code in genAST() passes around register identifiers. For example cgload() loads a value into a register and returns the identity of the register with the loaded value.

genAST()中的代码不传递值，而是传递寄存器标识符。例如，cgload()将一个值加载到寄存器中，并用加载的值返回寄存器的标识。

genAST() itself returns the identity of the register that holds the final value of the tree at this point. That’s why the code at the top is getting register identities:

genAST()本身返回此时保存树的最终值的寄存器的标识。这就是为什么顶部的代码能获得寄存器标识：

  if (n->left) leftreg = genAST(n->left);
  if (n->right) rightreg = genAST(n->right);

Calling genAST() 调用genAST()

genAST() is only going to calculate the value of the expression given to it. We need to print out this final calculation. We’re also going to need to wrap the assembly code we generate with some leading code (the preamble) and some trailing code (the postamble). This is done with the other function in gen.c:

genAST()只计算给定给它的表达式的值。我们需要把最后的计算结果打印出来。我们还需要用一些前导代码和一些后导代码包装生成的汇编代码。这是通过gen.c中的其他函数完成的：

void generatecode(struct ASTnode *n) {
  int reg;

  cgpreamble();
  reg= genAST(n);
  cgprintint(reg);      // Print the register with the result as an int
  cgpostamble();
}

The x86-64 Code Generator x86-64代码生成器

That’s the generic code generator out of the road. Now we need to look at the generation of some real assembly code. For now, I’m targetting the x86-64 CPU as this is still one of the most common Linux platforms. So, open up cg.c and let’s get browsing.

这是一个通用代码生成器。现在我们需要看一些真实汇编代码的生成。目前，我的目标是x86-64 CPU，因为它仍然是最常见的Linux平台之一。打开cg.c，让我们开始浏览。

Allocating Registers 分配寄存器

Any CPU has a limited number of registers. We will have to allocate a register to hold the integer literal values, plus any calculation that we perform on them. However, once we’ve used a value, we can often discard the value and hence free up the register holding it. Then we can re-use that register for another value.

任何CPU的寄存器数量都是有限的。我们必须分配一个寄存器来保存整型文字值，以及我们对它们执行的任何计算。然而，一旦我们使用了一个值，我们通常可以丢弃该值，从而释放保存它的寄存器。然后我们可以将该寄存器重新用于另一个值。

There are three functions that deal with register allocation:
一共有三个和寄存器分配有关的函数

• freeall_registers(): Set all registers as available
• alloc_register(): Allocate a free register
• free_register(): Free an allocated register

I’m not going to go through the code as it’s straight forward but with some error checking. Right now, if I run out of registers then the program will crash. Later on, I’ll deal with the situation when we have run out of free registers.

我不打算通读代码，因为它很直白，除了有一些错误检查的部分。现在，如果寄存器用完，程序就会崩溃。以后，我将处理空闲寄存器用完的情况。(请从https://github.com/DoctorWkt/acwj拉取代码)

The code works on generic registers: r0, r1, r2 and r3. There is a table of strings with the actual register names:

该代码在通用寄存器上工作：r0、r1、r2和r3。有一个包含实际寄存器名称的字符串表：

static char *reglist[4]= { "%r8", "%r9", "%r10", "%r11" };

This makes these functions fairly independent of the CPU architecture.

这使得这些功能相当独立于CPU体系结构。

Loading a Register 加载寄存器

This is done in cgload(): a register is allocated, then a movq instruction loads a literal value into the allocated register.

这在cgload()中完成：分配一个寄存器，然后movq指令将一个文本值加载到分配的寄存器中。

// Load an integer literal value into a register.
// Return the number of the register
int cgload(int value) {

  // Get a new register
  int r= alloc_register();

  // Print out the code to initialise it
  fprintf(Outfile, "\tmovq\t$%d, %s\n", value, reglist[r]);
  return(r);
}

Adding Two Registers 两个寄存器相加

cgadd() takes two register numbers and generates the code to add them together. The result is saved in one of the two registers, and the other one is then freed for future use:

cgadd()获取两个寄存器号并生成将它们相加的代码。结果保存在两个寄存器中的一个寄存器中，然后释放另一个寄存器以供将来使用：

// Add two registers together and return
// the number of the register with the result
int cgadd(int r1, int r2) {
  fprintf(Outfile, "\taddq\t%s, %s\n", reglist[r1], reglist[r2]);
  free_register(r1);
  return(r2);
}

Note that addition is commutative, so I could have added r2 to r1 instead of r1 to r2. The identity of the register with the final value is returned.

注意加法是可交换的，所以我可以将r2添加到r1而不是r1添加到r2。具有最终值的寄存器标识将被返回。

Multiplying Two Registers 两个寄存器相乘

This is very similar to addition, and again the operation is commutative, so any register can be returned:

这个操作和加法很像，仍然是可交换的，因此可以返回任何一个寄存器

// Multiply two registers together and return
// the number of the register with the result
int cgmul(int r1, int r2) {
  fprintf(Outfile, "\timulq\t%s, %s\n", reglist[r1], reglist[r2]);
  free_register(r1);
  return(r2);
}

Subtracting Two Registers 两个寄存器相减

Subtraction is not commutative: we have to get the order correct. The second register is subtracted from the first, so we return the first and free the second:

减法是不可交换的：我们必须把顺序弄对。第二个寄存器从第一个寄存器中减去，因此我们返回第一个寄存器并释放第二个寄存器：

// Subtract the second register from the first and
// return the number of the register with the result
int cgsub(int r1, int r2) {
  fprintf(Outfile, "\tsubq\t%s, %s\n", reglist[r2], reglist[r1]);
  free_register(r2);
  return(r1);
}

Dividing Two Registers 两个寄存器相减

Division is also not commutative, so the previous notes apply. On the x86-64, it’s even more complicated. We need to load %rax with the dividend from r1. This needs to be extended to eight bytes with cqo. Then, idivq will divide %rax with the divisor in r2, leaving the quotient in %rax, so we need to copy it out to either r1 or r2. Then we can free the other register.

除法也不是可交换的。因此前面的笔记还是可以用的。在x86-64上，它甚至更复杂。我们需要把存储在r1的被除数加载在%rax上。这需要使用cqo扩展到8个字节。然后，idivq将用r2中的除数除以%rax，商留在%rax中，因此我们需要将其复制到r1或r2中。然后我们可以释放另一个寄存器。

// Divide the first register by the second and
// return the number of the register with the result
int cgdiv(int r1, int r2) {
  fprintf(Outfile, "\tmovq\t%s,%%rax\n", reglist[r1]);
  fprintf(Outfile, "\tcqo\n");
  fprintf(Outfile, "\tidivq\t%s\n", reglist[r2]);
  fprintf(Outfile, "\tmovq\t%%rax,%s\n", reglist[r1]);
  free_register(r2);
  return(r1);
}

Printing A Register 打印一个寄存器

There isn’t an x86-64 instruction to print a register out as a decimal number. To solve this problem, the assembly preamble contains a function called printint() that takes a register argument and calls printf() to print this out in decimal.

没有x86-64指令将寄存器打印为十进制数。为了解决这个问题，程序前导代码中包含一个名为printint()的函数，该函数接受一个寄存器参数，并调用printf()将其以十进制形式打印出来。

I’m not going to give the code in cgpreamble(), but it also contains the beginning code for main(), so that we can assemble our output file to get a complete program. The code for cgpostamble(), also not given here, simply calls exit(0) to end the program.

我不打算给出cgpassemble()中的代码，但它还包含main()的开始代码，这样我们就可以组装输出文件以获得完整的程序。这里也没有给出cgpostmble()的代码，它只是调用exit(0)来结束程序。

Here, however, is cgprintint():

以下是cgprintint()的代码：

void cgprintint(int r) {
  fprintf(Outfile, "\tmovq\t%s, %%rdi\n", reglist[r]);
  fprintf(Outfile, "\tcall\tprintint\n");
  free_register(r);
}

Linux x86-64 expects the first argument to a function to be in the %rdi register, so we move our register into %rdi before we call printint.

Linux x86-64希望函数的第一个参数位于%rdi寄存器中，因此在调用printint之前，我们将寄存器移到%rdi中。

Doing Our First Compile 进行我们的第一次编译

That’s about it for the x86-64 code generator. There is some extra code in main() to open out out.s as our output file. I’ve also left the interpreter in the program so we can confirm that our assembly calculates the same answer for the input expression as the interpreter.

这就是x86-64代码生成器的内容。main()中有一些额外的代码将out.s作为输出文件打开。我还将解释器留在了程序中，这样我们可以确认我们的程序集为输入表达式计算的答案与解释器的答案相同。

Let’s make the compiler and run it on input01:

让我们编译这个编译期运行：

$ make
cc -o comp1 -g cg.c expr.c gen.c interp.c main.c scan.c tree.c

$ make test
./comp1 input01
15
cc -o out out.s
./out
15

Yes! The first 15 is the interpreter’s output. The second 15 is the assembly’s output.

对前15个是解释器的输出。第二个15是汇编代码的输出。

Examining the Assembly Output 检查汇编文件输出

So, exactly what was the assembly output? Well, here is the input file:

那么，输出的汇编文件里到底是什么内容呢？好，以下是输入文件：

2 + 3 * 5 - 8 / 3

and here is out.s for this input with comments:

以下是和输入文件对应的out.s（有注释）

        .text                           # Preamble code
.LC0:
        .string "%d\n"                  # "%d\n" for printf()
printint:
        pushq   %rbp
        movq    %rsp, %rbp              # Set the frame pointer
        subq    $16, %rsp
        movl    %edi, -4(%rbp)
        movl    -4(%rbp), %eax          # Get the printint() argument
        movl    %eax, %esi
        leaq    .LC0(%rip), %rdi        # Get the pointer to "%d\n"
        movl    $0, %eax
        call    printf@PLT              # Call printf()
        nop
        leave                           # and return
        ret

        .globl  main
        .type   main, @function
main:
        pushq   %rbp
        movq    %rsp, %rbp              # Set the frame pointer
                                        # End of preamble code

        movq    $2, %r8                 # %r8 = 2
        movq    $3, %r9                 # %r9 = 3
        movq    $5, %r10                # %r10 = 5
        imulq   %r9, %r10               # %r10 = 3 * 5 = 15
        addq    %r8, %r10               # %r10 = 2 + 15 = 17
                                        # %r8 and %r9 are now free again
        movq    $8, %r8                 # %r8 = 8
        movq    $3, %r9                 # %r9 = 3
        movq    %r8,%rax
        cqo                             # Load dividend %rax with 8
        idivq   %r9                     # Divide by 3
        movq    %rax,%r8                # Store quotient in %r8, i.e. 2
        subq    %r8, %r10               # %r10 = 17 - 2 = 15
        movq    %r10, %rdi              # Copy 15 into %rdi in preparation
        call    printint                # to call printint()

        movl    $0, %eax                # Postamble: call exit(0)
        popq    %rbp
        ret

Excellent! We now have a legitimate compiler: a program that takes an input in one language and generates a translation of that input in another language.

牛逼！我们现在有了一个合法的编译器：一个程序，它接受一种语言的输入，并生成另一种语言输入的翻译。

我们仍然需要将输出组装成机器代码，并将其与支持库链接，但这是我们现在可以手动执行的。稍后，我们将编写一些代码来自动执行此操作。

Conclusion and What’s Next 总结展望

Changing from the interpreter to a generic code generator was trivial, but then we had to write some code to generate real assembly output. To do this, we had to think about how to allocate registers: for now, we have a naive solution. We also had to deal with some x86-64 oddities like the idivq instruction.

从解释器到泛型代码生成器的更改非常简单，但随后我们必须编写一些代码来生成真正的程序集输出。为此，我们必须考虑如何分配寄存器：目前，我们有一个简单的解决方案。我们还必须处理一些x86-64异常，比如idivq指令。

Something I haven’t touched on yet is: why bother with generating the AST for an expression? Surely, we could have called cgadd() when we hit a ‘+’ token in our Pratt parser, ditto for the other operators. I’m going to leave you to think about this, but I will come back to it in a step or two.

我还没有提到的是：为什么要为表达式生成AST呢？当然，当我们在Pratt解析器中点击“+”标记时，我们可以调用cgadd()，其他操作符也是如此。我将让你们考虑一下这个问题，但我会在一两步后再谈。

In the next part of our compiler writing journey, we will add some statements to our language, so that it starts to resemble a proper computer language.

在编译器编写过程的下一部分中，我们将向我们的语言中添加一些语句，以便它能像一个计算机语言。