AN EFFICIENT BOTTOM-UP TREE PATTERN-MATCHING THAT PERFORMS DYNAMIC-PROGRAMMING FOR CODE GENERATION

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