針對 (巡迴型與非巡迴型) 屬性樹的通用計算系統

Abstract

屬性文法是研究編譯技術的正規模型。我們由屬性樹出發，屬性樹先由屬性文法算出， 接著我們要計算樹上的各個屬性。要計算屬性的值，則需依屬性之間的相依關係，決 定計算屬性的順序。而屬性的相依關係必須是非循迴性(non-circular)否則無法計 算。對於非循迴性的屬性樹，我們提出一套二階段的計算法。在第一階段，我們計算 屬性求值的順序，而在第二階段，我們依先前決定的順序，來計算各屬性的值。我們 的方法特殊之處在於這兩個階段皆是使用同一套計值演算法，而第一個階段則利用一 套固定的meta-attribute grammar。這一套計值演算法可以用於所有(巡迴式或非巡迴 式)的屬性文法，只要所欲計值的屬性樹有非循迴的相依關係。目前的演算法之時間複 雜度是多項式時間。在本計畫執行其間，我們將更進一步，仔細研究我們提出的這一 套演算法，加以改進，嘗試降低時間複雜度的可能性，並分析此演算法，以利發展有 效率的實作，並且利用Java 時做出一套屬性系統。我們並且要將研究成果，實際應用 於編譯程式的二元碼產生器上，藉以改善二元碼的品質。

Attribute grammars are a formal model of compiler technology. Syntax trees are generated from attribute grammars in which attributes need evaluation. To evaluate the attributes we need to determine an order of evaluation. This order is determined from the dependency relation among attributes. We say an attributed tree carries non-circular dependencies if and only if the dependence graph among the attribute instances in the tree is non-circular. An attributed tree with non-circular dependencies can be evaluated in two phases. In the first phase, we calculate an evaluation order of the attribute instances while in the second phase, a visit-oriented evaluator together with the evaluation order obtained in the first phase is used to evaluate the attribute instances in the attributed tree. The crux of our work is to show that the first phase can be done with a associated meta-attribute grammar. The associated meta-attribute grammar itself is a two-pass (non-circular) attribute grammar. Our proposed method can be used to evaluate all noncircular attributed trees, be it derived from a non-circular attribute grammar or from a circular one. We will study the properties of our methods and implement it on a Java platform. We will also apply our research in attribute grammars in the code generator of a real compiler in order to improve the quality of the code and the portability of the code generator.