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 are largely achieved at compile-compile time, which secures actual efficiency at compile-time.
上向式 트리패턴 一致方法들은 現代코드 生成機들에 의해 使用되어 왔다. 트리文法을 잘 表現하고 處理할 수 있는 트리 文法들의 範圍를 擴張하기 위해 上向式 트리패턴 一致方法은 費用을 數式으로 表現할 수 있게 하였다. 이로 인해 컴파일 時間에 다이나믹 프로그래밍을 修行해야 하며 코드 生成機의 速度가 느려진다. 본 硏究에서는, 다이나믹 프로그래밍을 利用하는 上向式 트리패턴 一致方法에서 狀態 作成時 效率을 높이기 위한 컴파일컴파일時間 分析方法 두 가지를 제안한다.
上向式으로 트리패턴 一致를 修行할 때 中間表現트리는 두 번 읽게 된다. 첫 번째는 上向式으로 각 노드에 하나의 狀態情報를 追加한다. 한 狀態는 訪問된 노드에서 주어진 一連의 트리패턴들 에서 만들어진다. 트리 읽기 두 번째는 下向式 으로 最小費用커버를 구한다. 그 후에 코드生成機는 最小費用커버에서 使用된 代替規則에 대한 機械語를 出力해 준다.
一致方法의 效率을 높이기 위해 規則들 集合에서 決定트리가 紹介된다. 決定트리는 點檢될 트리패턴들의 順序를 定해 주고, 한 패턴의 點檢結果가 影響받는 트리패턴과의 關係를 보여준다. 最適의 決定트리를 만드는 問題는 NP-complete이다. 본 硏究에서는 이를 위해 휴리스틱을 提案한다.
效率을 얻기 위한 또 다른 方法은 패턴들의 集合을 一致集合들로 變形하는 것이다. 一致集合은 狀態를 計算하기 위해 必要한 패턴들의 集合이다. 一致集合들과 集合들간 轉移函數는 컴파일컴파일時間에 패턴들간 關係를 이용하여 計算된다.
