屬性計算算法

屬性計算算法,給定一個屬性文法,每個文法規則選擇有一個相關依賴圖(associated dependency graph)。文法規則中的每個符號在這個圖中都有用每個屬性X i . a j 標記的節點。

公式

給定一個屬性文法,每個文法規則選擇有一個相關依賴圖(associated dependency graph)。文法規則中的每個符號在這個圖中都有用每個屬性X i . a j 標記的節點,對每個屬性等式:

X i . a j = f i j ( . . . , X m .a k , . . . )

相關於文法規則從在右邊的每個節點X m .a k 到節點X i . a j 有一條邊(表示X i . a j 對X m .a k 的依賴)。依據上下文無關文法,在語言產生時給定一個合法的字元串,這個字元串的依賴圖( dependencygraph )就是字元串語法樹中選擇表示每個(非葉子)節點文法規則依賴圖的聯合。

方法

通常在計算屬性時,利用參數和返回的函式值與屬性值進行通信,而不是把它們作為欄位存儲在語法樹的記錄結構中,這樣做是有意義的。當許多屬性值都相同,或者僅僅在計算其他屬性值時臨時使用,就尤為重要。對於這種情況,使用語法樹的空間在每個節點存儲屬性值就沒什麼意義了。事實上,遞歸遍歷程式用前序計算繼承屬性,而用後序計算合成屬性,在子節點把繼承屬性作為參數傳遞給遞歸函式調用,並接收合成屬性作為那些相同調用的返回值。特別地,算術表達式合成屬性值的計算能通過遞歸分析程式返回當前表達式的值進行。類似地,在語法分析期間,因為直到它的構造完成,也沒有用以記錄作為屬性的自身的數據結構存在,所以語法樹自身作為合成屬性必須通過返回值計算。

相關詞條

相關搜尋

熱門詞條

聯絡我們