Kw. Kang et al., AN EFFICIENT BOTTOM-UP TREE PATTERN-MATCHING THAT PERFORMS DYNAMIC-PROGRAMMING FOR CODE GENERATION, Journal of programming languages, 5(1), 1997, pp. 189-199
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.