LL/LR不神祕

在設計語言時，如果我們嘗試自行建立剖析器（Parser），終究會遇上LL、LR剖析器等名詞，不過，面對相關文件上的數學定義，往往令人覺得神祕難解。

實際上，關於剖析樹（Parser tree）生成的兩個方向，開發者也可能早就做過類似的剖析。

文法與剖析樹

開發者多半都做過文字剖析，只是文字來源複雜度不同，可能是單純以某符號分格的字串，或是需透過規則表示式定義的格式。

若進一步來看，文字來源具有某種結構，就必須套用某種資料結構與演算法，然而，只要能達到剖析需求，撰寫的程式就都是剖析器，只不過採用的資料結構或演算法可能專用於特定需求，以及差別在於有沒有效率罷了。

事實上，描述文字結構的方式就是文法，在實現剖析器時，開發者可能早就設計過文法，只是文法隱含在實作之中。

例如，剖析四則運算時，會根據優先權尋找運算子符號，以決定運算元的計算順序，這實際上就是在套用四則運算中的優先權文法規則。另一方面，我在先前專欄〈語言文法淺淺談〉也談過，如果我們定義了一個規則表示式，實際上，這也是在定義某門語言的文法。

套用文法規則的過程，其實，就是試著以文法來衍生（derive）某串文字。

我在先前發表的〈語言文法淺淺談〉中也談過，若我們將衍生過程逐一畫下，會是個樹狀結構，而如果衍生出的文字就是想剖析的來源文字，這棵樹就是來源文字的剖析樹。如果文法不曖昧，此時，文字只會建立唯一的剖析樹，而從葉節點往根節點化簡（reduce）運算的過程，就是解讀文字意義的方式，當中唯一的剖析樹，也代表著文字只會有一種解釋。

剖析器的任務就是根據文法，正確（且有效率）地建立出剖析樹。面對簡單的文字剖析作業，開發者雖然未必在程式的實作上，直接去構造剖析樹的資料結構，但實際上，剖析樹也會是隱含在流程之中。

例如，剖析四則運算式的處理方式之一，是找出優先權最低的運算符號位置，將運算式切為左右兩份，分別進行遞迴處理，若我們將遞迴流程畫出來，也會看到是個樹狀結構。

LL/LR剖析器？

為了能夠探討剖析文字時的通用性與效率，如果我們將相關的資料結構與演算流程，隱含在程式實現之中，其實並不是個好主意。於是，也就有了LL、LR之類的名詞，以此代表著剖析器建立剖析樹時的方式。

方才我們談到以遞迴處理四則運算的方式，就是屬於LL剖析器，而這裡所稱的第一個L，其實是代表從左而右讀取輸入的詞法單元（Token），至於第二個L，代表的是左衍生，也就是，剖析樹的生成過程，是以先消除最左邊符號的方式來進行。

事實上，從簡單的文法與文字剖析的角度，我們會比較能理解LL與LR的差別。

例如，若有個文法S->Ac、A->ab，以及輸入文字abc，開發者可以如何剖析呢？

此時，剖析樹可以從S節點開始進行，基於ab，而衍出A節點，A節點也衍生出對應a與b的節點，接著，基於c衍生出S的子節點來對應。基本上，上述這種衍生方式，是基於文法來進行左衍生，屬於LL剖析器。

另一種剖析方式則是，看到a，就建立對應的節點，看到b，也建立對應節點，接著，依文法規則來化簡出A作為父節點，進一步地，看到c，也建立對應節點，基於文法規則，來化簡出S節點。基本上，類似這種自底而上建立剖析樹的方式，正是屬於LR剖析器。

相較之下，LL剖析器是自頂而下建立剖析樹，而另一種LR剖析器的R，代表著右衍生。其實，這是因為，節點生成順序，會是依文法規則進行右衍生後的相反順序。

LL剖析器由於是「自頂而下」，實現起來比較直覺。例如，1+2*3是個運算式，剖析時，就是想辦法切分為1、+、2*3，然後1與2*3也是個運算式，因此，可以再分別對它們進行剖析。

若開發者曾經實作過簡單的語言剖析器，很有可能就是採取了LL剖析器的概念。就像在Gof設計模式中談到的Interpreter模式，基本上，就是用來實作LL剖析器的一種模式。

後序運算式

單看LR剖析器以化簡、從底而上建立剖析樹的方式，就滿違反直覺的。

而且，若想一窺實現的原理，相關的文件往往就讓人看得一個頭兩個大。然而，開發者若曾經試著實現將中序運算式轉為後序式，然後進行後序式的運算，其實，在那當下，也就已經實現簡單的LR剖析器。

而這種運算式的後序運算式，又稱逆向波蘭運算式（Reverse polish notation）。例如，(a+b)*(c+d)，轉為後序運算式後是ab+cd+*，接著，運算時將a、b置入堆疊，看到+的話，取出a、b計算後、置回堆疊，接著，c、d置入堆疊，看到+取出cd運算後、放入堆疊，最後，看到*將堆疊中兩個值取出相乘，就是最終的結果。

對照至LR剖析器對剖析樹的建立，就會是取得a、b後建立對應節點、各置入堆疊，看到+取出a、b對應節點，建立運算節點包含a、b節點後、置入堆疊，這就是化簡動作，而如此持續下去，就可以建立起完整的剖析樹。

也就是說，將輸入的中序運算式轉換為後序運算式，之後，我們再按照後序運算的方式，來建立節點關係，而這樣就會是一種自底而上建立剖析樹的過程。

在〈LL and LR Parsing Demystified〉中，作者也談到下列狀況：如果我們將四則運算式的剖析樹繪製出來，可以看到LL剖析器與LR剖析器的建立節點方式，會分別對應於「前序遍歷（Pre-Order Traversal）」，以及「後序遍歷（Post-Order Traversal）」，而且，前者是先存取根，再來存取子樹，後者是先存取子樹，然後再存取根。

例如，該篇文章當中的1+2*3剖析樹，若是後序遍歷，會是123*+，這就是後序運算式；若是前序遍歷，會是+1*23，這就是前序表示式了。

試著從經驗中理解

簡單來說，如果將剖析器當成黑箱，並且令其將剖析樹各節點依建立順序輸出的話，根據結果相當於樹的前序或後序遍歷，將會決定了它是LL或LR剖析器。

如果開發者過去實現過某種剖析器，就算沒有真的實現樹狀資料結構，此時，也可以從處理符號的順序上來看看，判斷其大概會是屬於LL剖析器，或是LR剖析器。

雖說真想設計個語言，我們多半會使用剖析產生器（parser generator），像是Yacc、ANTLR之類，不過，下次如果想自行實現簡單的剖析器，或者必須理解LL、LR這類名詞，才能善用某個剖析產生器時，對於LL、LR的基本認知，就會是個不錯的思考方向。