一類擴大的多項式時間之有序屬性文法

Abstract

屬性文法是用來表示程式語言語意的一個標準。本論文探討一類擴大的有 序屬性文法，我們稱為EOAG。在Kastens的有序屬性文法中，藉由增加介 於符號屬性間的相關性，使得屬性文法不具有任何的循環迴圈，其計算所 需時間為多項式時間；我們所提出的EOAG，是將Kanstens有序屬性文法的 演算法加以改進，其時間所需仍為多項式時間；這類屬性文法其範圍介於 有序屬性文法和線性有序屬性文法之間。其次探討屬性的儲存空間，針對 屬性的生命週期發生重疊，以致無法利用堆疊裝置來儲存；在此我們利用 一暫時性的屬性，來改進重疊現象，促使屬性能夠利用堆疊裝置來儲存。 Attribute grammars are a formalism for specifying semantics of programming languages. Kenstens proposes the class of ordered attribute grammars, for which there is a polynomial-time procedure to find an evaluation order. We extend the class of ordered attribute grammars by improving Kanstens's algorithm. The new class of attribute grammars is strictly larger than the class of ordered attribute grammars and it retains the property that there is a polynomial-time procedure to find an evaluation order. Reduction of attribute storage is a vital requirement for practical attribute evaluators. There are four conditions under which the instances of an attribute cannot be stored on a stack. We use temporary attributes to change the lifetimes of attributes, in order to invalidate the four conditions. The introduction of temporary attributes makes it possible to store certain attributes on a global stack.