一套屬性文法的平行計算法

Abstract

屬性文法是用來表示程式語言語意的一個標準方法。在 Kastens 所提出的有序屬性文法中，藉由增加介於符號屬性間的相關性，使得屬性文法不具有任何的循環迴圈，其所需的計算時間為多項式時間，而計算出一靜態的循序計算順序。在 Klein 所提出的平行有序屬性文法中，則是找出一靜態與動態混合的平行計算順序。 在這篇論文□，我們提出一套屬性文法的平行計算演算法，這套演算法較 Klein 所提出的方式簡易，稱做平行計算有序屬性文法 (PEOAG)，可找出一靜態的平行計算順序。

Attribute grammars are a formalism for specifying semantics of programmaing languages. Kastens proposes the ordered attribute grammars, for which there is a procedure to find a static sequential evaluation order. Klein proposes the parallel ordered attribute grammars, which is a procedure of finding parallel evaluation order with a hybrid method. In the thesis, we propose a parallel evaluation algorithm which is simpler than Klein's method, called the parallelly evaluatable ordered attribute grammars (PEOAG), is a procedure to find a static parallel evaluation order.