(An) analysis for the bottom-up tree pattern matching using dynamic programming at compile-time = 컴파일시간에 다이나믹 프로그래밍을 이용하는 상향식 트리패턴 일치를 위한 분석

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 386
  • Download : 0
Bottom-up tree pattern matching scheme is widely accepted by modern code generator generators, and draws more attention for obtaining an efficient code generator. For the flexible expression of the tree grammars and the larger class of tree grammars, the bottom-up tree pattern matching scheme allows the arbitrary cost values and performs dynamic programming at compile-time. Thus, the dynamic programming process make the code generator be slow. In this dissertation, we propose two efficient methods of constructing states in the bottom-up tree pattern matching scheme that performs dynamic programming. The bottom-up tree pattern matching scheme with DP traverses the IR tree twice. In the first traversal, the scheme annotates a state for each node of the IR tree in a bottom-up direction. A state can be extracted by checking sequentially all tree patterns over the given set at each node. In the second traversal, the scheme will find the least-cost cover in a top-down direction. Then a target code is produced by executing the semantic actions from the rewrite rules used for the least-cost cover. To get the efficiency of the matching scheme, the decision tree of a set of rules is introduced, which specify the order of tree patterns to be checked. The check of one pattern might make the matching scheme avoid some unfruitful patterns. The decision tree is formulated by analyzing the relations between tree patterns. However, Finding optimal decision tree is an NP-complete problem that requires heuristic solution. We propose an heuristic. The other method of getting the efficiency transforms the set of patterns into the match sets. The match set is the set of fruitful patterns for extracting a state. The match sets and match set transition tables can be constructed at compile-compile time and are also formulated by analyzing the relations between tree patterns. The proposed methods are derived from the analysis of relations over tree patterns. The relevant analyses ar...
Choe, Kwang-Mooresearcher최광무researcher
한국과학기술원 : 전산학과,
Issue Date
134777/325007 / 000925001

학위논문(박사) - 한국과학기술원 : 전산학과, 1998.2, [ viii, 100 p. ]


Tree pattern matching; Code generator generator; Code generator; Compiler; Dynamic programming; 다이나믹 프로그래밍; 트리패턴일치; 코드생성기생성기; 코드생성기; 컴파일러

Appears in Collection
Files in This Item
There are no files associated with this item.


  • mendeley


rss_1.0 rss_2.0 atom_1.0