서지주요정보
(An) analysis for the bottom-up tree pattern matching using dynamic programming at compile-time = 컴파일시간에 다이나믹 프로그래밍을 이용하는 상향식 트리패턴 일치를 위한 분석
서명 / 저자 (An) analysis for the bottom-up tree pattern matching using dynamic programming at compile-time = 컴파일시간에 다이나믹 프로그래밍을 이용하는 상향식 트리패턴 일치를 위한 분석 / Kyung-Woo Kang.
저자명 Kang, Kyung-Woo ; 강경우
발행사항 [대전 : 한국과학기술원, 1998].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8008435

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 98002

SMS전송

도서상태

이용가능

대출가능

반납예정일

등록번호

9004880

소장위치/청구기호

서울 학위논문 서가

DCS 98002 c. 2

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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이다. 본 硏究에서는 이를 위해 휴리스틱을 提案한다. 效率을 얻기 위한 또 다른 方法은 패턴들의 集合을 一致集合들로 變形하는 것이다. 一致集合은 狀態를 計算하기 위해 必要한 패턴들의 集合이다. 一致集合들과 集合들간 轉移函數는 컴파일컴파일時間에 패턴들간 關係를 이용하여 計算된다.

서지기타정보

서지기타정보
청구기호 {DCS 98002
형태사항 viii, 100 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 강경우
지도교수의 영문표기 : Kwang-Moo Choe
지도교수의 한글표기 : 최광무
수록잡지명 : "An Efficient Bottom-Up Tree Pattern Matching that Performs Dynamic Programming for Code Generation". Journal of Programming Languages. Chapman & Hall, vol. 5, pp. 189-199 (1997)
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 Reference : p. 95-100
주제 Compiler
Code generator
Code generator generator
Tree pattern matching
Dynamic programming
컴파일러
코드생성기
코드생성기생성기
트리패턴일치
다이나믹 프로그래밍
QR CODE qr code