Back to University of Twente portal
Code generation based on formal BURS theory and heuristic search
Nymeyer, A. and Katoen, J.P. (1997) Code generation based on formal BURS theory and heuristic search. Acta informatica, 34 (8). pp. 597-635. ISSN 0001-5903
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 444Kb |
| Abstract: | BURS theory provides a powerful mechanism to efficiently generate pattern matches in a given expression tree. BURS, which stands for bottom-up rewrite system, is based on term rewrite systems, to which costs are added. We formalise the underlying theory, and derive an algorithm that computes all pattern matches. This algorithm terminates if the term rewrite system is finite. We couple this algorithm with the well-known search algorithm A* that carries out pattern selection. The search algorithm is directed by a cost heuristic that estimates the minimum cost of code that has yet to be generated. The advantage of using a search 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 implements the algorithms presented in this work has been built. |
| Item Type: | Article |
| Copyright: | © 1997 Springer |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/63263 |
| Official URL: | http://dx.doi.org/10.1007/s002360050099 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 118459