An efficient bottom-up tree pattern matching that performs dynamic programming for code generation

Abstract

We propose an efficient scheme of constructing states in bottom-up tree pattern matching with dynamic programming technique for code generation. The proposed scheme, which is derived from relations on tree patterns, is efficient because its smaller size makes it possible to avoid unfruitful tests. Furthermore, the relevant analyses are largely achieved at compile-compile time, which secures actual efficiency of code generator at compilation time.