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

根据一个带标号的表达式树生成代码

输入：一个带有标号的表达式树，其中的每个运算分量只出现一次（即没有公共子表达式）。

输出：计算根结点对应的值并将该值存放在一个寄存器中的最优的机器指令序列。

方法：下面是一个用来牛成机器代码的递归算法。从树的根结点开始应用下面的步骤。如果算法被应用于一个标号为的结点，那么得到的代码只使用个寄存器。然而，这些代码从某个基线6(6>1)开始使用寄存器，实际使用的寄存器是Rb + 1,…，Rb+k-1。计算结果总是存放在Rb+k-1中。

1)为一个标号为k且两个子结点的标号相同（它们的标号必然是k - 1)的内部结点生成代码时，做如下处理：

①使用基线b+ 1递归地为它的右子树生成代码。其右子树的结果将存放在寄存器Rb+k-1中。

②使用基线b，递归地为它的左子树牛成代码。其左子树的结果将存放在寄存器Rb+k-2 中。|

③生成指令“op Rb+k-1, Rb+k-2 Rb+k-1”，其中op是标号为k的结点对应的运算。

2)假设我们有一个标号为（的内部结点，其子结点的标号不相等。那么，它必然有一个子 结点的标号为k，我们称之为“大子结点”；而另一个子结点的标号为某个m<k，它被称为“小子结点”。使用基线b，通过下列步骤为这个内部结点生成代码：

①使用基线b，递归地为大子结点生成代码，其结果存放在寄存器Rb+k-1中。

②使用基线b，递归地为小子结点生成代码，其结果存放在寄存器Rb+m-1中。请注意，因为 m<k，寄存器Rb+k-1和编号更高的寄存器都没有被使用。

③根据大子结点是该内部结点的右子结点还是左子结点，分别生成指令“OP Rb+k-1,Rb+m-1，Rb+k-1”或者“OP Rb+k-1，Rb+m-1”。

3)对于代表运算分量x的叶子结点，当基线为b时生成指令“LD Rb, X”。