The author describes a simple, efficient algorithm to generate bottom-up rewrite system (BURS) tables. A BURS table can be used in a code generator to select optimal instructions efficiently. Efficiency is achieved because the dynamic programming to select optimal patterns is performed when the BURS table is built, and not at code generation time.

The input to a BURS code-generator generator is a set of tree rewriting rules, written much like a context-free grammar. Typically, this set of rules describes the instruction set of a computer. Additionally, as the author illustrates, BURS technology can be applied to other problems, such as type inferencing.

The author describes in detail his algorithm for generating BURS tables. In particular, he describes a new algorithm for state trimming, called “triangle trimming,” which allows his table generator to execute from 9 to 30 times faster than its predecessor.

The paper is moderately long (26 pages), due to the detailed description of the algorithm. Of course, this description is the highlight of the paper. The author also does a good job of describing background material and offers valuable references to related work. This paper should be of interest to compiler writers, and of particular interest to those responsible for the optimization phase of a compiler.