Engineering Efficient Code Generators Using Tree Matching and Dynamic Programming
Report ID: TR-386-92Author: Proebsting, Todd A. / Hanson, David R. / Fraser, Christopher W.
Date: 1992-08-00
Pages: 12
Download Formats: |Postscript|
Abstract:
Many code generator generators use tree pattern matching and dynamic programming. This note describes a simple program that generates matchers that are fast, compact, and easy to understand. It is simpler than common alternatives: 200--700 lines of Icon versus 3000 lines of C for Twig and 5000 for { t burg}. Its matchers run up to 25 times faster than Twig's. They are necessarily slower than { t burg}'s BURS (bottom-up rewrite system) matchers but they are more flexible and still practical.
- This technical report has been published as
- Engineering a Simple, Efficient Code Generator Generator. Christopher W. Fraser, David R. Hanson, and Todd A. Proebsting, ACM Lett. on Prog. Lang. and Sys. 1(3), Sept. 1992, pp. 213-226.