LL剖析器


上下文無關文法
語法分析器
· LL剖析器
· 算符優先分析器
· LR剖析器
· SLR剖析器
· LALR剖析器

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

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

一個 LL 分析器若被稱為 LL(k) 分析器,表示它使用 k詞法單元向前探查。對於某個文法,若存在一個分析器可以在不用回溯法進行回溯的情況下處理該文法,則稱該文法為 LL(k) 文法。這些文法中,較嚴格的 LL(1) 文法相當受歡迎,因為它的分析器只需多看一個詞法單元就可以產生分析結果。那些需要很大的 k 才能產生分析結果的編程語言,在分析時的要求也比較高。

概覽

對於給定的上下文無關文法,分析器嘗試尋找該文法的最左推導。例如,給定一個文法 

  1.  
  2.  
  3.  

 的最左推導如下:

 

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

 

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

  1.  
  2.  

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

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

通過上述梗概,下面我們給出   的形式化定義:

  是一個上下文無關文法,且  。對於任意兩個最左推導,當且僅當滿足下述條件時,我們稱    文法:

  1.  
  2.  

以下條件成立:串   中長度為   的前綴等價於串   中長度為   的前綴,表明  .

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

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

本分析器由以下部件組成:

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

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

當分析器一開始執行時,分析棧中已經有兩個符號:

[ 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的時候應該選用哪一條文法規則。我們可以輕鬆的發現到這種規則應該有Aw一類的格式,並且語言中的w應至少有一個字串由a開頭。為了這個目的,我們設定 第一個集合(first set)的w,記作Fiw),表示可以在w中找到的所有字串的集合,如果空字串也屬於w的話還要再加上ε。而透過文法規則A1w1, ..., Anwn,就可以使用以下方法演算每條規則的Fi(wi)及Fi(Ai)了:

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

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

  1. 將每個Fo(Ai)初始成空集合
  2. 若存在AjwAiw' 格式的規則,則
    • 若終端符號a存在Fiw' )中,則將a加入Fo(Ai)
    • 若ε存在Fiw' )中,則將Fo(Aj)加入Fo(Ai)
  3. 重複步驟2直到所有Fo集合固定下來

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

T[A,a]包含Aw規則,若且唯若
aFiw)之中,或
ε在Fiw)之中,且aFoA)之中。

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

建構LL(k)剖析表格

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

參見

外部連結