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

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

在考虑通用的树匹配方法之前，我们先考虑一个特殊的匹配方法。这个方法使用LR语法分析器来完成模式匹配。输人树可以用前缀方式表示为一个串。比如，树的前缀表示为：

=ind + +Ca Rsp  ind + Ci RsP + Mb C1

一个树翻译方案可以转换为一个语法制导的翻译方案，方法是把每个树重写规则替换为相应的上下文无关文法的产生式。对于一个树重写规则，相应的产生式的右部就是其指令模板的前缀表示方式。

根据这个翻译方案的产生式，我们可以使用某个LR语法分析器构造技术来构建一个LK语法分析器。目标代码通过每一步归约中发出的机器指令来生成。