什麼是 LR 解析表的實現？

LR 解析表是一個二維陣列，其中每個條目表示一個動作或 goto 條目。一個具有大量產生式的程式語言語法具有大量狀態或專案，即 I₀、I₁ … … I_n。

因此，由於狀態過多，將填充更多動作和 goto 條目，這需要大量記憶體。因此，二維陣列不足以儲存如此多的動作條目，因為每個條目至少需要 8 位來編碼。

因此，我們必須使用比二維陣列更有效的編碼來編碼動作和 goto 欄位。

例如，考慮語法。

E → E + T

E → T

T → T * F

T → (F)

F → (E)

F → id

其解析表將是

編碼動作欄位

動作表的一些行是相同的，即它們具有相同的動作條目。因此，它可以透過為每個狀態生成一個指向一維陣列的指標來儲存多個空間。

要從陣列訪問條目，我們可以為每個終結符分配從 0 到 n-1 的順序編號。此整數可以用作訪問特定終結符的偏移量。可以透過建立對列表來管理空間效率。

在給定的解析表中，狀態 0、4、6、7 具有相同的動作條目。它們可以表示為

**狀態 1** 具有列表。

在**狀態 2** 中，如果它可以用 r2 替換錯誤條目。因此，r2 將出現在除 * 之外的所有條目上。

**狀態 3** - 它只有 r4 條目和錯誤條目。如果它也可以用 r4 替換錯誤條目，則所有條目都將由 r4 表示。

**狀態 5、10、11** 可以類似地解決。

狀態 8

狀態 9

編碼 goto 欄位

goto 表也可以由列表編碼。列表包含一對 (當前狀態，下一個狀態)

∴ Goto [當前狀態，A] = 下一個狀態

**列 F** - 列 F 對狀態 7 具有 10，所有其他條目均為 3 或錯誤。我們可以用 3 替換錯誤。

列 T

在**列 E** 中，我們可以選擇 1 或 8 作為預設值。

因此，維護這些列表顯然會節省一些空間，即佔用比之前少大約 10% 的空間。這些列表佔用少量記憶體。但列表表示比矩陣表示慢。

Ginni

更新於： 2021 年 11 月 3 日

2K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始