Engineering E cient Code Generators using Tree Matching and Dynamic Programming
Christopher W. Fraser, David R. Hanson, Todd A. Proebsting · 2007
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 burg. Its matchers run up to 25 times faster than Twig's. They are necessarily slower than burg's BURS (bottom-up rewrite system) matchers but they are more exible and still practical. AT&T Bell Laboratories, 600 Mountain Avenue 2C-464, Murray Hill, NJ 07974 Department of Computer Science, The University of Arizona, Tucson, AZ 85721