在PVM環境下有序屬性文法的平行求值

Abstract

屬性文法提供了一種語意分析以及轉換樹狀結構物件的技巧，在許多的 編譯器、編譯器產生器和以語言相關之文書編輯器中都大量利用屬性文法 來做為描敘的工具。近來有愈來愈多的相關研究朝向將屬性文法求值器平 行化, 歸其原因有以下兩點：一、因為它可以提昇編譯器以及其相關應用 的速度，在編譯器執行的幾個步驟中，語意分析的步驟往往是最費時的， 因此將此步驟以平行方式加速將可相對提昇其執行速度。二、因為屬性文 法隱含有相當的平行度,屬性文法是以函數方式寫成的，屬性之間的相依 程度有限，因此文法中具有許多可平行之處。在這篇論文□，我們設計一 些平行屬性求值器的演算法將它實作於一套稱為（ＰＶＭ）的平行工作平 台上。ＰＶＭ結合了同一個網路上的一些異質（ｈｅｔｅｒｏｇｅｎｅｏ ｕｓ）的機器資源，構成一個虛擬的平行環境。將此類應用實作於如此的 異質平行環境中是一種新的嚐試。我們並會在文中作一些簡單的實驗來討 論其可行性。 Attribute grammars provide a basis for the semantic analysis andtranslation of tree-structure objects. A number of programming languagecompilers, compiler generators and language- based editor generators haveused them as the description tools. The research of parallel attribute evaluators is of high interest because of the following two reasons. First, it can be used to speed up some applications such as compiler. In a compiler, attribute evaluation of AGs always takes a significant amount of time relative to other phases. Speeding it up would promote the overall performance of a compiler. Second, attribute grammars have inherently parallel characteristics due toits nature of functional specification. In the thesis, we design and implement several algorithms for parallel attribute evaluation in the PVM environment, which consists of a heterogeneous network of computers. This is a new attempt to implement such applications in a heterogeneousenvironment. A simple experiment is conducted for discussing the behaviorof the parallel evaluator.