Quick links

Engineering Efficient Code Generators Using Tree Matching and Dynamic Programming

Report ID:
July 1992
Download Formats:


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.
Sept. 1992, pp. 213-226.
Follow us: Facebook Twitter Linkedin