預測式剖析(predictive parsing)
想像一個從不猜了又後悔的剖析器。在每個岔路口,它瞄一眼下一個詞符,便立刻確定該往哪走,不會試一條路再退回。預測式剖析就是用這種篤定方式做的由上而下剖析:藉由前瞻固定數目的詞符(通常只看一個),它總能預測出正確的產生式,毫無回溯。
訣竅是一張從文法一次算好的剖析表。列是非終端符號,欄是可能的下一個詞符,每格指明當你在展開那個非終端符號、且看到那個詞符時要用的唯一產生式。此表用 FIRST 與 FOLLOW 集填寫:大致而言,當 alpha 能以 t 開頭時,就把規則 A -> alpha 放進詞符 t 的格子(且若 alpha 能消為空字串,則當 t 能跟在 A 之後時也放)。接著一個驅動程式以明確的堆疊(而非遞迴)運行:它彈出頂端符號,若是終端符號就與輸入匹配,若是非終端符號就查該非終端符號與目前詞符對應的表格格,並把所選規則的右側壓入。在行為良好的文法中,沒有任何格子裝兩條規則,這正是保證無回溯的關鍵。
預測式剖析是 LL 剖析的實用、表驅動形式,而遞迴下降是它的手寫雙生子。它很快(線性時間)並提供精準的錯誤回報:當目前非終端符號與詞符對應的表格格為空時,你立刻知道輸入不合規,以及究竟期望的是什麼。其限制是:唯有文法為 LL(1) 時,此表才能無衝突地建出;含左遞迴或共同前綴的文法須先轉換,而有些文法根本無法變成 LL(1)。
對 S -> if S | print,其中 FIRST(if S) = {if}、FIRST(print) = {print},表中每個詞符一個項目:格 [S, if] = (S -> if S)、格 [S, print] = (S -> print)。看到詞符 if,剖析器毫無遲疑、毫無回溯地選第一條規則。
剖析表把(非終端符號,下一個詞符)對映到恰好一條規則,因此無需猜測。
預測式剖析唯有在每個表格格至多裝一條規則時才能不回溯運作。若兩條規則落入同一格,該文法就不是 LL(1),必須改寫,或改用更強的方法剖析。