LL分析器

LL 分析器是一種處理某一寡頂下文無關文法的自頂向下跤剖析器。因為伊對倒（Left）四界理輸入去，閣句型執行上左推導出語法樹（Leftderivation，相對的是 LR 分析器）。會當用這款的方法來破析文法叫做LL 文法。

本中欲討論表格驅動的分析器，毋是通常由手工來打造（非絕對，參看如講 ANTLR 等的喔 LL ( \ * ) 遞迴下降破析器生成器）遞迴下降剖析器。

一个 LL 分析器若予人號做 LL ( _ k _ ) 分析器，表示伊使用 _ k _ 個詞法單元作向前探查。對某一个文法，若是存在一个剖析器會當佇毋免回溯法進行回溯的狀況下處理該文法，講這个文法為LL ( _ k _ ) 文法。遮的文法內底，較嚴格的LL ( 一 ) 文法相當的受歡迎，因為伊的分析器只有需要加看一个詞法單元就會當產生解析結果。彼需要足大的 _ k _ 才會當產生解析結果的程式語言，咧分析的時陣的要求嘛較懸。

概覽

對無關係的上下文無關文法，開析器來試驗揣該文法的上左推導。比如講，予定一个文法 $ G $：

一 . $ S \ to E $ 二 . $ E \ to ( E + E ) $ 三 . $ E \ to i $

著 $ w=( ( i + i ) + i ) $ 的上左推導如下：

$ S \ { \ overset { ( 一 ) } { \ Rightarrow } } \ E \ { \ overset { ( 二 ) } { \ Rightarrow } } \ ( E + E ) \ { \ overset { ( 二 ) } { \ Rightarrow } } \ ( ( E + E ) + E ) \ { \ overset { ( 三 ) } { \ Rightarrow } } \ ( ( i + E ) + E ) \ { \ overset { ( 三 ) } { \ Rightarrow } } \ ( ( i + i ) + E ) \ { \ overset { ( 三 ) } { \ Rightarrow } } \ ( ( i + i ) + i ) $

通常，選擇一條規則來展開予定的（上左的）非終結符的時陣，有偌濟選擇的可能。前一个關於上左推導的例中，佇第二步：

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

阮有兩條規則會當選擇：

為著提懸解破析的效率，分析器必須會當趕緊確切地、無回溯地進行規則的選擇。對一寡文法，伊會當透過偷看不回推（即讀取了後袂將伊退回輸入流）的輸入符號來做到這點。佇阮的例當中，若有分析器知影後一个無回推符號是 $ ( $，遐唯一正確會當用的就是規則二。

通常，$ LL ( k ) $ 分析器是會當向前去看 $ k $ 個符號。毋過，予定一个文法，若存在是一个會當辨識該文法 $ LL ( k ) $ 分析器，著其 $ k $ 值的確定問題是不可判定的。也就是講，無法度判定需要向前探查偌濟符號才會當辨識伊。對著每一个 $ k $ 的取值，總存在無法度予 $ LL ( k ) $ 分析器辨識的語言，而且 $ LL ( k + 一 ) $ 分析器煞會當辨識伊。

咧講通過台灣話楗概，下面咱共出 $ LL ( k + 一 ) $ 的形式化定義：

設 $ G $ 是一个上下文無關文法，而且 $ k \ geq 一 $。對任意兩个上左推導，如果只要是滿足下述條件的時候，阮稱 $ G $ 是 $ LL ( k ) $ 文法：

一 . $ S \ \ Rightarrow \ \ dots \ \ Rightarrow \ wA \ alpha \ \ Rightarrow \ \ dots \ \ Rightarrow \ w \ beta \ alpha \ \ Rightarrow \ \ dots \ \ Rightarrow \ wx $ 二 . $ 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ài-sù 一致，而且該定義表明矣，緩衝區會當分任意兩个無仝單詞的推導。

本成析器會當處理特定形式文法的符號串。

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

一个 _ 輸入緩衝區 _，寄輸入符號串（由語法來建立的）。
一个 _ 分析棧 _，用於儲存等待處理的總結符和非終結符的。
一張 _ 分析表 _，標記了敢有存在通用佇目前破棧佮後一个輸入符號的語法規則。

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

當剖析器一開始執行的時陣，分析棧內底已經有兩个符號：

` ` ` [S , $] ` ` `

'$'時一个特殊的終結符，用佇表示破析棧的棧底抑是輸入的結束；而且'S'則的時文法的開始符號。破析器會試根據伊佇輸入流當中看著的符號來崁寫析棧中的資料，毋過猶是需要修改的資料存回破析棧內底。

實際的例

設定

為解說 LL 分析器的工作方式，咱創造以下這个小語法：

一 . S → F 二 . S → ( S + F ) 三 . F → 一並處理以下輸入：

( 一 + 一 )

這个語法的分析表現出來：

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

分析的流程

分析器先對輸入資料流中讀到頭一个'('，以及堆疊中的'S'。伊對表格中伊發現必須愛套用規則 ( 二 )；伊必須愛疊起來的'S'重寫為'( S + F )'，並且將規則的號碼輸出。到尾仔疊起來變：

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

閣來伊徙掉輸入去疊著的'('：

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

這馬分析器對輸入資料流中掠著一个'一'，所以伊知影講著愛套用規則 ( 一 ) 佮規則 ( 三 )，並將結果輸出。則疊起來變做：

` ` ` [F , + , F , ) , $] [一 , + , F , ) , $] ` ` `

紲落來的兩个步驟中，分析器讀著'一'佮'+'，因為𪜶和堆疊中的資料仝款，所以規堆的疊起來。尾仔疊起來賰：

` ` ` [F , ) , $] ` ` `

閣紲落來三个步驟中間，疊起來的'F'會'一'予人取代，規則 ( 三 ) 會輸出去。才來疊佮輸入資料流內底的'一'佮')'攏會去予人徙掉。才破析器看著疊佮輸入資料流攏干焦賰'$'的時陣，就知影家己的代誌做了矣。

佇這个例中，分析器接受輸入資料，並產生以下輸出（規則的代號）：

[二 , 一 , 三 , 三]

這確實是對輸入的倒手爿優先推導。咱會當看出咱對左至右的輸入順序為：

S → ( S + F ) → ( F + F ) → ( 一 + F ) → ( 一 + 一 )

備註

由以上範例會使看出破析器根據堆疊上頂面層為非終端符號、終端符號、閣是特殊符號 $ 來決定採取三種無仝的步數：

若疊上頂懸層為非終端符號，是根據輸入資料流中的符號對照分析表，決定欲用語法內面的佗一條規則來取代堆疊中的資料，順帶輸出規則的號碼。若表格內底並無遮爾濟規則，是回報錯誤並終止執行。
若疊上頂懸層為終端符號，是佮輸入資料流中的符號較。若仝款徙掉，若無仝款回報錯誤並終止執行。
你若疊了上頂懸層的為'$'，而且輸入資料流中嘛是'$'，是表示破析器成功的處理了輸入，若無會回報錯誤。毋管按怎，落尾手破析器攏共終止執行。

遮的步數會繼續到輸入結束，然後解剖析器成功處理一則倒爿優先推導，抑是會回報錯誤。

建構 LL ( 一 ) 分析表格

為著欲添予滿表格，咱著愛決定破析器咧疊看著非終 ( 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 ) 了：

一 . 將逐个Fi( _ w _ i ) 佮Fi( _ A _ i ) 初成空集合二 . 將 _ 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 _ ( ε )={ ε }

三 . 針對逐條 _ A _ i → _ w _ i 規則，將Fi( _ w _ i ) 加入Fi( _ A _ i ) 四 . 重複步驟二佮步驟三，一直到所有Fi集合固定落來。

不幸的是，頭一集合猶無夠用來產生出破析表。因為規則中正手爿的 _ w _ 可能無限制的予人寫做空字串，所以分析器嘛佇 ε 佇佗位咧Fi（_ w _）而且輸入資料流內底的符號會當符合 _ A _ 的時陣套用 _ A _ → _ w _。所以閣需要一个記持Fo（_ A _）的 _ A _ 的 _ 佮隨集合 _ ( follow set )，表示會當由開始的符號衍生出 _ αAaβ _ 字串的終端符號 _ a _ 的集合。非終端符號的跟隨集合會用得用下跤法得出：

一 . 將逐个Fo( _ A _ i ) 初成空集合二 . 若存在 _ A _ j → _ wAiw'_ 格式的規則，著

若是尾仔符號 _ a _ 存在 _ Fi _（_ w'_）中，則將 _ a _ 加入Fo( _ A _ i )
若是 ε 存在 _ Fi _（_ w'_）中，則將Fo( _ A _ j ) 加入Fo( _ A _ i )

三 . 重複步數二直到所有Fo集合固定落來這馬咱會當清楚定義逐條規則愛囥佇咧剖析表的佗位矣。若是 _ T _ [_ A _ , _ a _] 用表示講表格中代表非終端符號 _ A _ 佮終端符號 _ a _ 的規則，著

_ T _ [_ A _ , _ a _] 包含 _ A _ → _ w _ 規則，若是唯一

_ a _ 佇咧Fi（_ w _）之中，抑是

ε 佇咧Fi（_ w _）之中，而且 _ a _ 佇咧Fo（_ A _）之中。

若表格的逐格中攏干焦包含一个規則，是分析器總是知影講這个規則用啥物規則，所以會當佇咧毋免回溯的前提著破析字捾。此情形下，這个語法會當講 _ LL ( 一 ) 語法 _。

建構 LL ( _ k _ ) 分析表格

分析的表格可能（一般來講，上䆀狀況下）著愛有 _ k _ 次的指數複雜度的觀念佇一九九二年左右 PCCTS 發表了後改觀，伊示範矣真濟程式語言會使用 LL ( _ k _ ) 來有效率的處理，毋過袂發生析器上䆀的狀況。再者，佇某著愛無限前瞻的狀況之下，LL 分析嘛是合理的。顛倒反的，傳統分析器產生器，如 yacc 使用 LALR ( 一 ) 分析表格建立被限制的 LR 分析器，這種解析器干焦會當向後看固定的一个語彙符號。

參見

編譯器破析器較表
抽象語法樹仔
由頂懸才下來分析
由下而上的分析

外部連結

An easy explanation of First and Follow Sets（用一種比 c 較直觀的方法去共產生解說 First 佮 Follow 集合的過程）
A tutorial on implementing LL ( 一 ) parsers in C #