An analysis for fast construction of states in the bottom-up tree pattern matching scheme

In this paper, we propose an efficient method of constructing states in bot tom-up tree pattern matching with dynamic programming technique for optimal code generation. This method can be derived from precomputing the analysis which is needed for constructing states. The proposed scheme is more effic ient than other scheme because we can avoid unfruitful tests in constructin g states at compile time. Furthermore, the relevant analyses needed for thi s proposal are largely achieved at compile-compile time, which secures actu al efficiency at compile time.