C# 語法分析器（二）LR(0) 語法分析

系列導航

首先，需要介紹下 LALR 語法分析的基礎：LR(0) 語法分析。

還是以之前的算式文法為例：

$E \to E + T$
$E \to T$
$T \to T * F$
$T \to F$
$F \to id$
$F \to (E)$

先來看一下 $(id+id)$ 是如何被 LR(0) 語法分析執行的。這裡使用 $\$$ 這個特殊符號來標記輸入的結束。

棧	輸入	動作
	$(id_1+id_2)\$$	移入
$($	$id_1+id_2)\$$	移入
$(id_1$	$+id_2)\$$	按照 $F \to id$ 歸約
$(F$	$+id_2)\$$	按照 $T \to F$ 歸約
$(T$	$+id_2)\$$	按照 $E \to T$ 歸約
$(E$	$+id_2)\$$	移入
$(E+$	$id_2)\$$	移入
$(E+id_2$	$)\$$	按照 $F \to id$
$(E+F$	$)\$$	按照 $T \to F$
$(E+T$	$)\$$	按照 $E \to E + T$
$(E$	$)\$$	移入
$(E)$	$\$$	按照 $F \to (E)$ 歸約
$F$	$\$$	按照 $T \to F$ 歸約
$T$	$\$$	按照 $E \to T$ 歸約
$E$	$\$$	接受

可以看到，LR(0) 語法分析會不斷將輸入的符號移入到棧中，如果棧裡的符號是某個產生式的右部，就會彈出棧內符號並歸約為其頭部，再將頭部符號入棧，直到找到起始非終結符，接受並完成語法分析。

每次都去比較棧裡的符號和所有產生式，也可以完成語法分析，但顯然這樣太過低效，實際使用中會構造出 LR(0) 自動機，利用 LR 語法分析表來提高匹配效率。

一、項和 LR(0) 自動機

LR(0) 語法分析器會通過維護一些狀態，來表明我們在語法分析過程中所處的位置，從而決定現在需要移入還是歸約。

LR(0) 使用「項」（item）來表示現在已經看到了產生式的哪些部分。項是由產生式再加上一個位於它的右部中某處的點組成的。例如產生式 $A \to XYZ$ 產生了四個項：

$$\begin{matrix}
A \to \cdot \ XYZ \\
A \to X \cdot YZ \\
A \to XY \cdot Z \\
A \to XYZ\ \cdot \ \\
\end{matrix}$$

例如，項 $A \to \cdot \ XYZ$ 表示我們希望在接下來的輸入中看到一個從 $XYZ$ 推導得到的串。項 $A \to X \cdot YZ$ 表示我們剛剛在輸入中看到了一個可以由 $X$ 推導得到的串，並且我們希望接下來看到一個能從 $YZ$ 推導的串。項 $A \to XYZ\ \cdot \ $ 表示我們已經看到了產生式體 $XYZ$，已經是時候把 $XYZ$ 歸約為 $A$ 了。

LR(0) 語法分析器的狀態，就是這樣的項的集合（或者稱為「項集」），因此可以用於決定現在需要移入還是歸約。這些狀態的集合（或者稱為「項集族」）就可以構造出 LR(0) 自動機，自動機的狀態就對應一個項集。

二、構造 LR(0) 自動機

為了構造 LR(0) 自動機，首先定義一個增廣文法（augmented grammar），如果 $G$ 是一個以 $S$ 為開始符號的文法，那麼它的增廣文法 $G'$ 就是在 $G$ 中加上新的開始符號 $S'$ 和產生式 $S' \to S$ 而得到的文法。

引入新的開始符號的目的是告訴語法分析器何時應該停止語法分析並接受輸入符號串，當且僅當使用產生式 $S' \to S$ 進行歸約時，輸入符號串被接受。

上面算式文法對應的增廣文法如下所示：

$0.\ E' \to E$
$1.\ E \to E + T$
$2.\ E \to T$
$3.\ T \to T * F$
$4.\ T \to F$
$5.\ F \to id$
$6.\ F \to (E)$

然後，需要兩個函數 $\text{CLOSURE}$（閉包）和 $\text{GOTO}$。

項集的閉包

如果 $I$ 是文法 $G$ 的一個項集，那麼 $\text{CLOSURE}(I)$ 就是能夠從 $I$ 的定點右側繼續推導時可能用到的所有產生式對應的項。

構造閉包的方法很簡單：

首先 $\text{CLOSURE}(I)$ 只包含 $I$ 本身
如果 $A \to \alpha \cdot B \beta$ 在 $\text{CLOSURE}(I)$ 中，且 $B \to \gamma$ 是一個產生式，且項 $B \to \cdot \gamma$ 不在 $\text{CLOSURE}(I)$ 中，那麼就將這個項新增到閉包中。不斷應用這個規則，直到沒有新項可以新增到 $\text{CLOSURE}(I)$ 中為止。

還是以之前的算式文法為例，其增廣文法的項 $E' \to \cdot E$ 對應的閉包如下所示：

$E' \to \cdot E$
$E \to \cdot E+T$
$E \to \cdot T$
$T \to \cdot T*F$
$T \to \cdot F$
$F \to \cdot id$
$F \to \cdot (E)$

其計算過程為：

根據規則 1，將 $E' \to \cdot E$ 加入閉包。
根據規則 2，定點右側包含 $E$，因此將 $E$ 的產生式的項（定點位於最左端）$E \to \cdot E+T$ 和 $E \to \cdot T$ 加入閉包。
現在定點右側包含 $T$，因此將 $T$ 的產生式的項 $T \to \cdot T*F$ 和 $T \to \cdot F$ 加入閉包。
現在定點右側包含 $F$，因此將 $F$ 的產生式的項 $F \to \cdot id$ 和 $F \to \cdot (E)$ 加入閉包。
現在定點右側沒有更多非終結符，過程終止。

該演演算法的具體實現可以參見這裡。

對於閉包，還可以進一步劃分為如下兩類：

核心項：包含初始項 $S' \to \cdot S$ 和所有定點不在最左端的項。
非核心項：除了初始項 $S' \to \cdot S$ 意外所有定點在最左端的項。

在上面的例子中，只有 $E' \to \cdot E$ 是核心項，其它的都是非核心項。或者說，在計算 $\text{CLOSURE}(I)$ 時，只有 $I$ 是核心項，其它後加入的都是非核心項。

這樣區分的原因，是在生成語法分析器的過程中，只有核心項需要一直儲存在記憶體中，非核心項只需要在使用時臨時計算出來即可，可以有效減少不必要的記憶體佔用。

GOTO 函數

接下來就是另一個函數 $GOTI(I, X)$ 了，其中 $I$ 是一個項集，$X$ 是一個符號（終結符或非終結符）。$\text{GOTO}(I, X)$ 表示了項集 $I$ 中所有形如 $A \to \alpha \cdot X \beta$ 的項所對應的 $ \to \alpha X \cdot \beta$ 的閉包。由於項集對應了 LR(0) 自動機中的狀態，$\text{GOTO}(I,X)$ 就表示了自動機中的狀態 $I$ 在看到輸入 $X$ 後，需要轉換到的新狀態。

拿上面 $E' \to \cdot E$ 的閉包為例：

$E' \to \cdot E$
$E \to \cdot E+T$
$E \to \cdot T$
$T \to \cdot T*F$
$T \to \cdot F$
$F \to \cdot id$
$F \to \cdot (E)$

這個閉包中，定點右邊會可能出現 $E$、$T$、$F$、$id$ 和 $($ 這五個符號，因此對應的 $\text{GOTO}$ 也只存在五個，其內容分別為（只列出核心項）：

$\text{GOTO}(I, E) = [ E' \to E \cdot,\ E \to E \cdot +T ] $
$\text{GOTO}(I, T) = [ E \to T \cdot,\ T \to T \cdot *F ] $
$\text{GOTO}(I, F) = [ T \to F \cdot] $
$\text{GOTO}(I, id) = [ F \to id \cdot] $
$\text{GOTO}(I, () = [ F \to ( \cdot E)] $

如果計算出算式文法的完整項集，那麼其自動機如下圖所示，其中陰影部分表示閉包：

圖 1 算式文法的 LR(0) 自動機，圖片來自編譯原理

構造 LR(0) 自動機的具體實現可以參見這裡。

三、構造 LR 語法分析表

當然，在實際使用中，肯定要將自動機轉換為其它易於處理的的資料結構，就是 LR 語法分析表。

LR 語法分析器一般都會包含兩個棧：狀態棧和符號棧。狀態棧就代表了已歸約的非終結符，與餘下的輸入一起表示瞭如下的最右句型（狀態棧右側為棧頂）。

$$X_1X_2 \cdots X_ma_ia_{i+1} \cdots a_n$$

本來根據狀態棧就足夠復原出相應的符號了，但在實際使用中，符號一般都會附加一些額外資料，因此需要一個符號棧來維護這些額外資料。

然後，就需要兩個表格 $\text{ACTION}$ 和 $\text{GOTO}$。

$\text{ACTION}[i, a]$ 表示當前處於自動機的狀態 $i$ 時，下一個輸入是終結符 $a$（$a$ 也可能是輸入的結束 $\$$）需要執行的動作，其可能的值為：

移入 $j$，其中 $j$ 是一個狀態。表示需要將 $j$ 移入棧中，同時將 $a$ 也移入符號棧。
歸約 $A \to \beta$，其中 $k$ 是產生式的索引。表示需要將棧頂的 $\beta$ 歸約為產生式頭 $A$，彈出棧頂的多個狀態和符號（$\beta$ 長度個），再將歸約後的狀態和符號壓入棧中。
接受，表示完成了語法分析過程。
報錯，$\text{ACTION}$ 表格中一般不會特意寫明。表示在輸入中發現了一個錯誤並應當執行某個錯誤恢復動作，會在後面再來具體討論。

$\text{GOTO}$ 表格則與之前的 $\text{GOTO}$ 函數一致，只是用狀態來代表項集，並且只需要包含非終結符部分。它的用途是在遇到歸約動作時，確認需要將哪個狀態壓入狀態棧中。

對於 LR(0) 文法來說，可以如下構造語法分析表，假設已構造 LR(0) 的項集族 ${I_0, I_1, \cdots, I_n}$：

根據 $I_i$ 構造得到狀態 $i$，狀態 $i$ 的 $\text{ACTION}$ 根據以下方法決定：
1. 如果 $A \to \alpha \cdot a \beta$ 在 $I_i$ 中，且 $\text{GOTO}(I_i, a) = I_j$，那麼將 $\text{ACTION}[i, a]$ 設定為「移入 $j$」。
2. 如果 $A \to \alpha \cdot$ 在 $I_i$中，那麼對於任意非終結符 $x$（包含輸入結束），將 $\text{ACTION}[i, x]$ 設定為「歸約 $A \to \alpha$」
3. 如果 $S' \to S \cdot$ 在 $I_i$ 中，那麼將 $\text{ACTION}[i, \$]$ 設定為「接受」。
狀態 $i$ 的 $\text{GOTO}$ 根據以下方法決定：設 $A$ 是一個非終結符，如果 $\text{GOTO}(I_i, A) = I_j$，那麼 $\text{GOTO}[i, A] = j$。
規則 1 和 2 未定義的所有條目都設定為「報錯」。
語法分析器的初始狀態就是根據 $S' \to \cdot S$ 所在項集構造得到的狀態。

上面算式文法生成的 LR(0) 語法分析表如下所示：

$$\begin{array}
{|c|cccccc|ccc|}
狀態 & id & + & * & ( & ) & \$ & E & T & F \\
0 & s5 & & & s4 & & & 1 & 2 & 3 \\
1 & & s6 & & & & acc & & & \\
2 & r2 & r2 & r2/s7 & r2 & r2 & r2 & & & \\
3 & r4 & r4 & r4 & r4 & r4 & r4 & & & \\
4 & s5 & & & s4 & & & 8 & 2 & 3 \\
5 & r5 & r5 & r5 & r5 & r5 & r5 & & & \\
6 & s5 & & & s4 & & & & 9 & 3 \\
7 & s5 & & & s4 & & & & & 10 \\
8 & & s6 & & & s11& & & & \\
9 & r1 & r1 & r1/s7 & r1 & r1 & r1 & & & \\
10 & r3 & r3 & r3 & r3 & r3 & r3 & & & \\
11 & r6 & r6 & r6 & r6 & r6 & r6 & & & \\
\end{array}$$

這裡使用 si 表示「移入 $i$，rj 表示按照索引為 $j$ 的產生式歸約，acc 表示接受，空白表示報錯。

如果注意檢查前面的 LR(0) 自動機和語法分析表，可以發現狀態 2 是包含 $E \to T \cdot$ 和 $T \to T \cdot * F$ 這兩個項的，這兩個項在 * 上對應的動作應當是 r2 和 s7 —— 同一個非終結符上可能出現兩個不同的動作，無法不在檢視更多輸入的前提下決定使用哪個動作。這就說明上面的算式文法存在衝突動作，不是 LR(0) 文法，狀態 9 也會有同樣問題。

這裡的移入-歸約衝突，就是 LR 語法分析中可能遇到的衝突之一，另一個則是歸約-歸約衝突，這種情況下無法選擇使用哪個產生式進行歸約。為了解決衝突，最簡單的辦法就是向前檢視更多符號。例如同樣是基於 LR(0) 自動機，但利用 $\text{FOLLOW}$ 集減少衝突的 SLR 技術，或者利用向前看符號的 LALR 技術，或者是直接擴充套件為 LR(1) 語法分析。

如果允許向前檢視一個字元，那麼在到達狀態 2 時，就可以發現在後一個字元是「」時，只能選擇移入而不能歸約，因為歸約後的非終結符是 $E$，但卻不存在 $X \to E * \cdots$ 這樣的產生式。狀態 9 也是同理，在遇到「」時只能選擇移入。

使用修正後的語法分析表，就可以正確對 $(id+id)$ 進行語法分析了，其過程如下所示：

狀態棧	符號棧	輸入	動作
0		$(id_1+id_2)\$$	移入到 4
0 4	$($	$id_1+id_2)\$$	移入到 5
0 4 5	$(id_1$	$+id_2)\$$	按照 5 $F \to id$ 歸約
0 4 3	$(F$	$+id_2)\$$	按照 4 $T \to F$ 歸約
0 4 2	$(T$	$+id_2)\$$	按照 2 $E \to T$ 歸約
0 4 8	$(E$	$+id_2)\$$	移入到 6
0 4 8 6	$(E+$	$id_2)\$$	移入到 5
0 4 8 6 5	$(E+id_2$	$)\$$	按照 5 $F \to id$
0 4 8 6 3	$(E+F$	$)\$$	按照 4 $T \to F$
0 4 8 6 9	$(E+T$	$)\$$	按照 1 $E \to E + T$
0 4 8	$(E$	$)\$$	移入到 11
0 4 8 11	$(E)$	$\$$	按照 6 $F \to (E)$ 歸約
0 3	$F$	$\$$	按照 4 $T \to F$ 歸約
0 2	$T$	$\$$	按照 2 $E \to T$ 歸約
0 1	$E$	$\$$	接受

有了 LR(0) 語法分析作為基礎，下一章就會來介紹 LALR 語法分析。

本系列相關程式碼都可以在這裡找到。