Code generation using tree matching and dynamic programming
Alfred V. Aho, Mahadevan Ganapathi, Steven W. K. Tjiang · ACM Transactions on Programming Languages and Systems · 1989
Compiler-component generators, such as lexical analyzer generators and parser generators, have long been used to facilitate the construction of compilers. A tree-manipulation language called twig has been developed to help construct efficient code generators. Twig transforms a tree-translation scheme into a code generator that combines a fast top-down tree-pattern matching algorithm with dynamic programming. Twig has been used to specify and construct code generators for several experimental compilers targeted for different machines.
Cited by 326 works. doi:10.1145/69558.75700 Open-access PDF
Authors
References
- Compilers: Principles, Techniques, and Tools
- Efficient string matching
- The Generation of Optimal Code for Arithmetic Expressions
- A portable compiler
- DAGON: technology binding and local optimization by DAG matching
- Optimal Code Generation for Expression Trees
- Pattern Matching in Trees
- Code Generation for Expressions with Common Subexpressions
- An experiment in table driven code generation
- Code-generation for machines with multiregister operations