Engineering Efficient Code Generators Using Tree Matching and Dynamic Programming

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.