編譯器設計中的優先順序函式是什麼？

優先順序表中任意兩個運算子或符號之間的優先順序關係可以轉換為兩個將終結符對映到整數的優先順序函式 f 和 g。

• 如果 a <. b，則 f (a) <. g (b)
• 如果 a = b，則 f (a) =. g (b)
• 如果 a .> b，則 f (a) .> g (b)

這裡 a、b 表示終結符。f (a) 和 g (b) 表示具有整數值的優先順序函式。

優先順序函式的計算

• 對於每個終結符 a，建立符號 f_a 和 g_a。
• 為每個符號建立一個節點。

               如果 a =. b，則 fa 和 gb 在同一組或節點中。

               如果 a =. b 和 c =. b，則 fa 和 fc 必須在同一組或節點中。

• (a) 如果 a <. b，則從 g_b 到 f_a 畫一條邊。

             (b) 如果 a .>b，則從 f_a 到 g_b 畫一條邊。

• 如果構造的圖具有迴圈，則不存在優先順序函式。
• 如果沒有迴圈。

        (a) f_a = 從 f_a 組開始的最長路徑的長度。

        (b) g_a = 從 g_a 組開始的最長路徑的長度。

示例 1 - 為下表構建優先順序圖和優先順序函式。

解決方案

步驟 1 - 建立符號

步驟 2 - 從給定表中可以看出，沒有符號具有相同的優先順序；因此，每個符號將保留在不同的節點中。

步驟 3 - 如果 a <. b，則從 f_a → g_a 建立一條邊

              如果 a .>b，則從 g_b → f_a 建立一條邊

由於 $ <. +,*, id。因此，從 g₊、g_*、g_id 到 f_s 畫一條邊

類似地 + <. ,∗, id。∴ 從 g_*、g_id 到 f₊ 畫一條邊

類似地 * <. id。因此，從 g_id 到 f_* 畫一條邊。

由於 +,*, id . > $ 因此，從 f₊、f_*、f_id 到 g_s 畫一條邊。

類似地 +,*, id . > +。從 f₊、f_*、f_id 到 g₊ 畫一條邊。

類似地 *, id . > *。從 f_*、f_id 到 g 畫一條邊。

組合所有邊，我們得到

步驟 4 - 計算每個節點路徑的最大長度，我們得到以下優先順序函式

示例 2 - 為下表構建優先順序圖和優先順序函式。

解決方案

由於我們有 (=.)。因此 f 和 g 將在同一組中。

優先順序圖的計算

優先順序函式表的計算

由於 f_$ 和 g_$ 沒有輸出邊，因此 f($ ) = g($ ) = 0。

由於 f 和 g 沒有輸出邊，因此 f(( ) = g( )) = 0。

對於所有其他情況，計算從其開始的最長路徑。

例如 -

取 f₊，

它有三條輸出邊並追蹤其路徑。

f₊ → g_$

f₊ → f₍

f₊ → g₊ → f₍ 和 f₊ → g₊ → f_$

選擇最大長度的路徑，長度為 2。

因此，f₊ = 2。計算 f 和 g 的所有路徑，我們得到優先順序表

Ginni

更新於： 2021 年 10 月 30 日

4K+ 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始