在設計語言時,如果我們嘗試自行建立剖析器(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的基本認知,就會是個不錯的思考方向。

作者簡介


Advertisement

更多 iThome相關內容