我们的编译器模型的最后一个步骤是代码生成器。它以编译器前端生成的中间表示（IR)和相关的符号表信息作为输人，输出语义等价的目标程序。

对代码生成器的要求是很严格的。目标程序必须保持源程序的语义含义，还必须具有很的质量。也就是说，它必须有效地利用目标机器上的可用资源。此外，代码生成器本身必须能高效运行。

具有挑战性的是，从数学上讲，为给定源程序生成一个最优的目标程序是不可判定问题码生成中碰到的很多子问题（比如寄存器分配)都具有难以处理的计算复杂性。在实践中，我们使用那些能够产生良好但不一定最优的代码的启发性技术。幸运的是，启发性技术已经非常成熟，一个精心设计的代码生成器所产生的代码要比那些由简单的生成器生成的代码快好几倍。

目标机指令集本身的特性对指令选择的难度有很大的影响。比如，指令集的统一性和完整性是两个很重要的因素。如果目标机没有以统一的方式支持每种数据类型，那么总体规则的每个例外都需要进行特别处理。比如，在某些机器上，浮点数运算使用单独的寄存器完成。
代码生成器必须把IR程序映射成为可以在目标机上运行的代码序列。完成这个映射的复杂性由如下的因素决定：

*IR的层次。

*指令集体系结构本身的特性。

*想要达到的生成代码的质量。

如果IR是高层次的，代码生成器就要使用代码模板把每个IR语句翻译成为机器指令序列。但是，这种逐个语句生成代码的方式通常会产生质量不佳的代码。这些代码需要进一步优化。如果IR中反映了相关计算机的某些低层次细节，那么代码生成器就可以使用这些信息来生成更 加高效的代码序列。

当一个基本块仅包含单一的表达式求值时，或者我们认为以逐次处理各个表达式的方式为基本块生成代码就已经足够了，那么我们就可以最佳地选择寄存器。在下面的算法中，我们引人对一个表达式树（即一个表达式的语法树）的结点添加数字标号的方案。在使用固定个数的寄存器来对一个表达式求值的情况下，该方案允许我们为表达式生成最优的代码。

Ershov 数

一开始，我们给一个表达式树的每个结点各赋予一个数值。该数表示如果我们不把任何临时值存放问内存的话，计算该表达式需要多少个寄存器。这些数有时被称为Ershou数（Ershov nurnher)。这是根据A.Ershov命名的，他为只有一个算术寄存器的机器使用了类似的方案。对我们的机器模型而言，计算Ershov数的规则如下：

假设在我们的机器模型中，所有的运算分量都必须在寄存器中，且寄存器可以同时用于存放某个运算的运算分量和结果。可以证明，如果在计算表达式的过程中不允许把中间结果保存回内存，那么一个结点的标号就等于计算该结点对应的表达式时需要的最少的寄存器个数。因为在这个机器模型中，我们必须把每个运算分量加载到寄存器中，且必须计算每个内部结点所对应的中间结果，所以，造成生成代码不是最优代码的唯一可能是我们使用了不必要的将临时结果存回内存的指令。对这个断言的证明包含在下面的算法中。这个算法生成的代码不包含将临时结果存回内存的指令，而这个代码所使用的寄存器数目就是根结点的标号。