CODE GENERATION BASED ON COMBINATION OF DYNAMIC PROGRAMMING AND TREE-PATTERN MATCHING ALGORITHMS

Abstract

After compiler-component generators, such as lexical analyzer and parser a code generator is very important. This paper presents algorithm, which transforms expression trees into code for register machines. This algorithm combines a fast top-down tree pattern matching algorithm with dynamic programming, which produces optimal code for any machine in this class, and this algorithm runs in time linearly proportionals to the size of the input data. Additional Key Words and Phrases: Code generation, code generator-generator, code optimization, dynamic programming, pattern matching.