LL(1) 剖析(LL parsing)
LL 這個名字是兩個有精確含義的字母:第一個 L 說剖析器由左到右(Left to right)讀輸入,第二個 L 說它建出最左推導(Leftmost derivation)。括號裡的數字,LL(1) 中的 1,說它用幾個前瞻詞符來決定怎麼做,這裡只看一個。所以 LL(1) 剖析就是:由左到右掃描,展開最左非終端符號,且選規則時絕不需要前瞻超過一個詞符。
當一個前瞻詞符總足以無歧義地挑出正確產生式時,文法即為 LL(1),這正是使預測式剖析表無衝突的條件。形式上,對任何有選項 A -> alpha | beta 的非終端符號,alpha 與 beta 的 FIRST 集必須不相交(沒有詞符能同時開啟兩者),而若某選項能推導出空字串,它的 FOLLOW 集就不能與另一選項的 FIRST 集衝突。當這些條件成立時,你能建出線性時間、無回溯的遞迴下降或表驅動剖析器。LL(1) 是最簡單、最好教的剖析類別,而較大 k 的 LL(k) 只是允許往前多看幾個詞符。
LL(1) 剖析受歡迎,因為它易懂、易手寫,並給出友善、局部化的錯誤訊息,這也是 ANTLR 之類工具與多數教科書剖析器倚賴它的原因。它的弱點在於觸及範圍:LL 文法是由下而上 LR 剖析器所能處理者的嚴格子集,而以自然的左遞迴方式寫的算術(E -> E + T)根本不是 LL,必須先改寫。所以 LL 以一些能力換取簡潔與清晰。
E -> T E'、E' -> + T E' | epsilon、T -> num 是用於加法的 LL(1) 文法:它是 E -> E + T | T 去除左遞迴後的改寫。對 E' 你靠一個前瞻決定:看到 '+' 就選 + T E',看到輸入結束就選 epsilon。
LL(1):由左到右讀、最左推導、1 個前瞻詞符、無回溯。
LL 剖析器嚴格弱於 LR 剖析器:每個 LL(1) 文法都是 LR(1),反之則否。文法非 LL 不代表其語言無法剖析,只代表自然的由上而下方法需要改寫文法或改用更強的方法。