LL剖析器

LL剖析器是一種處理某些上下文無關文法的自頂向下剖析器。因為它從左（Left）到右處理輸入，再對句型執行最左推導出語法樹（Left derivation，相對於LR剖析器）。能以此方法剖析的文法稱為LL文法。

在解析句子時使用 $k$ 個詞法單元作向前探查的LL剖析器被稱為 ${\text{LL}}(k)$ 解析器。若一個文法能構造出可以在不用回溯法進行回溯的情況下處理文法的剖析器，則稱該文法為 LL(k) 文法。如果一個形式語言擁有 ${\text{LL}}(k)$ 文法，則該語言被稱為 ${\text{LL}}(k)$ 語言。對於每個 $k\geq 0$，${\text{LL}}(k)$ 語言集合都嚴格包含於 ${\text{LL}}(k+1)$ 語言集合中。因此，並非所有上下文無關語言都能被 ${\text{LL}}(k)$ 解析器辨識。這些文法中，較嚴格的 LL(1) 文法相當受歡迎，因為它的剖析器只需多看一個詞法單元就可以產生剖析結果。那些需要很大的 $k$ 才能產生剖析結果的程式語言，在剖析時的要求也比較高。

本文中將討論表格驅動的剖析器，而非通常由手工打造（非絕對，參看如ANTLR等的 LL(*) 遞歸下降剖析器生成器）的遞歸下降剖析器。

概述

對於給定的上下文無關文法，剖析器嘗試尋找該文法的最左推導。例如，給定一個文法$G$：

1. $S\to E$
2. $E\to (E+E)$
3. $E\to i$

對$w=((i+i)+i)$的最左推導如下：

$S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)$

通常, 選擇一條規則來展開給定的（最左的）非終結符時，有多個選擇的可能。前一個關於最左推導的例子中， 在第2步：

$S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?$

我們有兩條規則可以選擇：

2. $E\to (E+E)$
3. $E\to i$

為了提高剖析的效率，剖析器必須能夠儘可能確切地、無回溯地進行規則的選擇。對於一些文法，它可以透過偷看不回推（即讀取之後不將它退回輸入流）的輸入符號來做到這點。在我們的例子中，如果剖析器知道下一個無回推符號是 $($ ，那麼唯一正確可用的就是規則 2。

通常，$LL(k)$ 剖析器可以向前探查 $k$ 個符號。然而，給定一個文法，若存在一個能辨識該文法 $LL(k)$ 剖析器，則其 $k$ 值的確定問題是不可判定的。也就是說，無法判定需要向前探查多少個符號才能辨識它。對於每一個 $k$ 的取值，總存在無法被 $LL(k)$ 剖析器辨識的語言，而 $LL(k+1)$ 剖析器卻可以辨識它。

通過上述梗概，下面我們給出 $LL(k+1)$ 的形式化定義：

設 $G$ 是一個上下文無關文法，且 $k\geq 1$。對於任意兩個最左推導，若且唯若滿足下述條件時，我們稱 $G$ 是 $LL(k)$ 文法：

1. $S\ \Rightarrow \ \dots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \dots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \dots \ \Rightarrow \ wx$
2. $S\ \Rightarrow \ \dots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \dots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \dots \ \Rightarrow \ wy$

以下條件成立：串 $x$ 中長度為 $k$ 的字首等價於串 $y$ 中長度為 $k$ 的字首，表明 $\beta \ =\ \gamma$.

在該定義中， $S$ 文法的開始符號， $A$ 是任意非終結符。之前取得的輸入 $w$，以及還沒回推的 $x$ 和 $y$ 均為終結符串。希臘字母 $\alpha$, $\beta$ 和 $\gamma$ 代表任意終結符和非終結符組成的串（也可能是空字串）。字首長度與用於儲存向前探查結果的緩衝區尺寸一致，並且該定義表明了，緩衝區足以區分任意兩個不同單詞的推導。

本剖析器可以處理特定形式文法的符號串。

本剖析器由以下部件組成：

• 一個輸入緩衝區，存放輸入符號串（由語法建立的）。
• 一個剖析棧，用於儲存等待處理的終結符與非終結符的。
• 一張剖析表，標記了是否存在可用於目前剖析棧與下一個輸入符號的語法規則。

剖析器根據剖析棧的棧頂符號（行）以及當前輸入流中的符號（列）來決定使用哪一條規則。

當剖析器一開始執行時，剖析棧中已經有兩個符號：

[ S, $ ]

'$'時一個特殊的終結符，用於表示剖析棧的棧底或者輸入的結束；而'S'則時文法的開始符號。剖析器會嘗試根據它在輸入流中看到的符號來覆寫剖析棧中的數據，但只會將仍需修改的數據存回剖析棧中。

實際的例子

設置

為解釋LL剖析器的工作方式，我們創造了以下這個小語法：

1. S → F
2. S → ( S + F )
3. F → 1

並處理以下輸入：

( 1 + 1 )

這個語法的剖析表如下：

	（	）	1	+	$
S	2	-	1	-	-
F	-	-	3	-	-

（注意到有一列特殊終端符號，在這裏表示為$，是用來標示輸入結束的。）

剖析流程

剖析器先從輸入資料流中讀到第一個 '('，以及堆疊中的'S'。從表格中他發現必須套用規則 (2)；它必須將堆疊中的'S'重寫為 '( S + F )'，並將規則的號碼輸出。最後堆疊變成：

[ (, S, +, F, ), $ ]

再來它移除輸入及堆疊中的 '('：

[ S, +, F, ), $ ]

現在剖析器從輸入資料流中抓到一個'1'，所以他知道必須套用規則 (1)與規則 (3)，並將結果輸出。則堆疊變成：

[ F, +, F, ), $ ]
[ 1, +, F, ), $ ]

接下來的兩個步驟中，剖析器讀到'1'及 '+'，因為他們跟堆疊中的資料一樣，所以從堆疊中移除。最後堆疊剩下：

[ F, ), $ ]

再接着的三個步驟中，堆疊中的'F'會'1'被取代，而規則 (3)會被輸出。再來堆疊與輸入資料流中的'1'與')'都會被移除。而剖析器看到堆疊與輸入資料流都只剩下'$'的時候，就知道自己的事情做完了。

在這個例子中，剖析器接受了輸入資料，並產生以下輸出（規則的代號）：

[ 2, 1, 3, 3 ]

這的確是從輸入的左邊優先推導。我們可以看出由左至右的輸入順序為：

S → ( S + F ) → ( F + F ) → ( 1 + F ) → ( 1 + 1 )

備註

由以上範例可以看出剖析器根據堆疊最上層為非終端符號、終端符號、還是特殊符號$來決定採取三種不同的步驟：

• 若堆疊最上層為非終端符號，則根據輸入資料流中的符號對照剖析表，決定要用語法中的哪條規則來取代堆疊中的資料，順帶輸出規則的號碼。若表格中並沒有這麼個規則，則回報錯誤並終止執行。
• 若堆疊最上層為終端符號，則與輸入資料流中的符號比較。若相同則移除，若不同則回報錯誤並終止執行。
• 若堆疊最上層為'$'，並且輸入資料流中也是'$'，則表示剖析器成功的處理了輸入，否則將回報錯誤。不管怎樣，最後剖析器都將終止執行。

這些步驟會持續到輸入結束，然後剖析器成功處理了一則左邊優先推導，或者會回報錯誤。

建構LL(1)剖析表格

為了要填滿剖析表格，我們必須決定剖析器在堆疊看到非終端(nonterminal)符號A又在輸入資料流看到a的時候應該選用哪一條文法規則。我們可以輕鬆的發現到這種規則應該有A → w一類的格式，並且語言中的w應至少有一個字串由a開頭。為了這個目的，我們設置 第一個集合(first set)的w，記作Fi（w），表示可以在w中找到的所有字串的集合，如果空字串也屬於w的話還要再加上ε。而透過文法規則A₁ → w₁, ..., A_n → w_n，就可以使用以下方法演算每條規則的Fi(w_i)及Fi(A_i)了：

1. 將每個Fi(w_i)及Fi(A_i)初始成空集合
2. 將Fi(w_i)加入每條A_i → w_i規則中的Fi(A_i)，Fi定義如下：
   • 所有的a皆為終端符號時，Fi（a w' ）= { a }
   • Fi（A）不包含ε時，相對於每個非終端符號A，Fi（A w' ）= Fi（A）
   • Fi（A）包含ε時，相對於每個非終端符號A，Fi（A w' ）= Fi（A）\ { ε } ∪ Fi（w' ）
   • Fi(ε) = { ε }
3. 針對每條A_i → w_i規則，將Fi(w_i)加入Fi(Ai)
4. 重複步驟2與步驟3，直到所有Fi集合固定下來。

不幸的是，第一集合還不夠用來產生出剖析表。由於規則中右手邊的w可能無限制的被覆寫成空字串，所以剖析器也在ε位於Fi（w）並且輸入資料流中的符號可以符合A的時候套用A → w。所以還需要一個記作Fo（A）的A的跟隨集合(follow set)，表示可以由開始的符號衍生出αAaβ字串的終端符號a的集合。非終端符號的跟隨集合可以用以下方法得出：

1. 將每個Fo(A_i)初始成空集合
2. 若存在A_j → wA_iw' 格式的規則，則
   • 若終端符號a存在Fi（w' ）中，則將a加入Fo(A_i)
   • 若ε存在Fi（w' ）中，則將Fo(A_j)加入Fo(A_i)
3. 重複步驟2直到所有Fo集合固定下來

現在我們可以清楚定義每條規則要放在剖析表的哪裏了。若T[A,a]用以表示表格中代表非終端符號A及終端符號a的規則，則

T[A,a]包含A → w規則，若且唯若

a在Fi（w）之中，或

ε在Fi（w）之中，且a在Fo（A）之中。

若表格的每格中都僅包含一個規則，則剖析器總是知道該套用什麼規則，所以可在不用回溯的前提下剖析字串。在此情形下，這個語法可以稱為LL(1)語法。

建構LL(k)剖析表格

剖析表格可能（一般來說，在最差狀況下）必須有k次的指數複雜度的觀念在1992年左右PCCTS發表後改觀，它示範了許多程式語言可以用LL(k)來有效率的處理，而不會觸發剖析器的最差狀況。再者，在某些必須無限前瞻的狀況下，LL剖析也是合理的。相反的，傳統剖析器產生器，如yacc使用LALR(1)剖析表格建立被限制的LR剖析器，這種剖析器只能向後看固定的一個語彙符號。

參見

• 編譯器剖析器比較表
• 抽象語法樹
• 由上而下剖析
• 由下而上剖析

外部連結

• An easy explanation of First and Follow Sets （頁面存檔備份，存於互聯網檔案館）（使用一種比c較直觀的方法解釋產生First與Follow集合的過程）
• A tutorial on implementing LL(1) parsers in C#