Unlike papers that focus on the theory of pattern matching or its application to code generation, this paper focuses on engineering the pattern matcher. The paper will interest programmers confronted with time or space requirements as well as compiler implementors.

The topic system is iburg, a variant of the burg code generator generator. Initially, iburg was developed for testing burg’s input language. Unlike burg, iburg supports dynamic programming during matching, making iburg the more powerful and flexible of the two systems. The authors have also found iburg useful in teaching.

Sections 1 through 3 introduce code generation using tree pattern matching and dynamic programming along with the specifics of iburg and burg. A consistent running example provides the reader with a solid understanding of the material. Section 4 presents the key implementation issues along with their resolution in iburg. Section 5 then discusses a number of potential improvements to the naïve implementation. Several improvements involve encoding techniques that conserve space without costing execution time. Others involve programming techniques for matching patterns, handling chain rules, and computing costs. Each candidate improvement was implemented and measured; some proved uneconomical. The measurements are provided.

The resulting iburg matchers are small and compact. Despite the improvements, iburg matchers are still slower than burg matchers because of their use of dynamic programming during compilation. The concluding section compares iburg with other code generator generators and attempts to show where iburg is best applied.