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

Abstract

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