指令选择可能是一个大型的排列组合任务。对于像CISC这样的具有丰富寻址模式的机器，或者具有某些特殊目的指令（比如信号处理指令）的机器尤其如此。即使我们假设求值的顺序已经给定，并且假设寄存器通过另一个独立的机制进行分配，指令选择——为实现中间表示形式中出现的运算符而选择目标语言指令的问题——仍然是一个规模很大的排列组合任务。

我们把指令选择当作一个树重写问题来处理。目标指令的树形表示已经在代码生成器的生成器中得到有效使用。这种生成器可以依据目标机器的高层规约自动构造出一个代码生成器的指令选择阶段。对于某些机器，相对于使用树表示方法而言，使用DAG表示方法能够生成更好的代码。但是DAG匹配比树匹配更加复杂。

树翻译方案

代码生成过程的输人是一个由目标机器的语义层次上的树组成的序列。在中间代码中插人运行时刻地址之后就可以得到这些树。另外，这些树的叶子包含有关它们的标号的存储类型的信息。

一个对应于赋值语句 a[i] =b+l的树，其中数组a存放在运行时刻栈中，而b是一个存放在内存位置财6的全局变量。局部变量a和i的运行时刻地址是以相对于SP的常数偏移量C1和C2的方式给出的，其中SP是存放当前活动记录的起始位置的寄存器。

对a[i]的赋值是一个间接赋值，其中a[i]的位置上的右值被设置成表达式b + 1的右值。

数组a和变量i的地址是通过分别把常量Ca和的值加上寄存器SP的内容而得到的。为了简化数组地址的计算，我们假设每个元素值都是一个字节的字符（某些指令集中提供了特殊指令用于在地址计算中进行乘数为某些常数（比如2、4、8等）的乘法运算）。

在这棵树中，运算符ind把它的参数作为内存地址处理。作为一个赋值运算符的左子结点，ind结点指出了一个内存位置，该位置用来存放赋值运算符右部的右值。如果一个+或者ind运算符的某个参数是内存位置或寄存器，那么该内存位置或寄存器中的内容就是参数的值。这棵树的叶子结点的标号为属性，而下标表示属性的值。

目标代码是通过应用一个树重写规则序列来生成的，这些规则最终会把输人的树归约为单个结点。各个树重写规则形如

replacements-template { action }

其中，replacements(被替换结点）是一个结点，template (模板）是一棵树，action动作是一个像语法制导翻译方案中那样的代码片断。

一组树重写规则被称为一个树翻译方案（tree-translation scheme)。