整合產生式及組裝式技術之編譯器建構方法

Abstract

今日編譯器前端 (front-end)的建構益趨複雜，編譯器建構也因此需要一 可再利用的軟體架構，以適應此種趨勢。大體而言，再利用技術可分成組 裝式 (compositional)及產生式(generative)二類。組裝式技術較少用於 編譯器建構上，產生式技術雖已成功應用於許多編譯工作，然而在語意分 析上目前編譯器實務上仍殊少採用。本文提出一整合此二類技術的編譯器 建構方法，並對這些技術提出一些改進。本文首先對屬性文法( attribute grammars)的觀念加以擴充，做為語意規格定義的基礎，並概 述編譯器建構的軟體元件架構。我們的方法採用屬性文法做為編譯器的骨 架，並配合使用可再利用軟體元件。其次我們提出一編譯器建構的語意規 格語言，融合屬性文法及物件導向的功能、遠端屬性擷取 (remote attribute access)、以及與軟體元件的介面。其中遠端屬性擷取是根據 遠端屬性文法(remote-dependency AGs)的理論模式。接著我們說明編譯 器建構的軟體元件架構，包括符號處理及資料流分析的軟體元件，以及程 式碼輸出的物件導向介面。由於採用軟體元件處理循環依存關係( circular dependency) 及非樹狀的資料結構，排除了屬性文法理論限制 所造成的規格撰寫上的許多困擾。本文所提的方法將可減化編譯器建構上 的困難。最後我們討論有關屬性文法及物件導向程式設計的問題，包括循 環性測式(circularity test)、屬性計算效能的改進、以及軟體元件建構 的相關技術。 Compiler front-ends today are getting bigger and more complex. Compiler designers need a software architecture that can survive or be reused during evolution. There are two kinds of techniques to approach software reuse: compositional and generative. Compositional techniques are rarely explored in compiler domains. Generative techniques are applied well in some compiling tasks; however, few production-quality compilers adopt generative technique for semantic analysis. This thesis proposes an approach that integrates both techniques in compiler construction and presents some improvements in both techniques. First, we propose the issues in extending attribute grammars (AGs) as a practical specification method and sketch a framework of software components for compiler construction. Our approach adopts AGs as the backbone of compilers and employs reusable components in AG specifications. Second, we present a semantic specification language for compiler construction. The language extends AGs with object-oriented features, remote attribute access constructs, and interfaces with state- transitional components. Remote attribute access in the language is based on a theoretical model called remote dependency AGs. Third, we present the software components for symbol processing and data-flow analysis, and an object- oriented code generation interface. By employing reusable components to handle circular dependency and non-tree structures, we can remove the specification difficulties due to theoretical limitations of AGs. Compiler construction can be greatly simplified using our approach. Finally, we discuss the efficiency of AGs and object- oriented programming techniques, including AG circularity test, fine tuning of attribute evaluators, and techniques for constructing software components.