CODE GENERATION BASED ON FORMAL BURS THEORY AND HEURISTIC-SEARCH

BURS theory provides a powerful mechanism to efficiently generate patt ern matches in a given expression tree. BURS, which stands for bottom- up rewrite system, is based on term rewrite systems, to which costs ar e added. We formalise the underlying theory, and derive an algorithm t hat computes all pattern matches. This algorithm terminates if the ter m rewrite system is finite. We couple this algorithm with the well-kno wn search algorithm A that carries out pattern selection. The search algorithm is directed by a cost heuristic that estimates the minimum c ost of code that has yet to be generated. The advantage of using a sea rch algorithm is that we need to compute only those costs that may be part of an optimal rewrite sequence (and not the costs of all possible rewrite sequences as in dynamic programming). A system that implement s the algorithms presented in this work has been built.