shift reduce，預測分析，遞歸下降分析（這是解析方法）和LL(K) LR(K) SLR以LALR的關係？

01-12

我知道前面的是語法解析的方法，後面不知道是什麼東西，但是好像關係很大。誰能解釋下後面的幾個縮寫是什麼東西？然後說一下他們之間的關係？
補充一張圖（有圖都看不懂:( ）：

Parsing 演算法大致分為兩派，top-down 和bottom-up。其中top-down parsing 也就是你說的遞歸下降分析，一般實現top-down parser 都要求parsing 是線性運行時間，所以大多數top-down parser 也就是predict parser 即預測分析器，因為這種parser 在運行時每次都要至少向前看一個符號（然後去查每個產生式的predictive set）才能決定用哪個產生式，即predict parser 是由「向前看」（預測）來驅動的。這點建議你看看《Language Implementation Patterns》中給出的LL(1) parser 的模板代碼，馬上就理解了。同時因為它總是把左邊先看到的符合產生式的一串符號構建成一個語法樹，所以也叫LL(k) parsing，其中第二個L就是最左推導的意思，而k 是指最多向前看幾個符號（我剛剛說了，至少一個，有時需要多個），且k 為常數（可以用環形緩衝區實現）。當加入回溯策略時，這個k 就可以是無窮大了。

LL(1)、LL(2) 和更大的k 之間有什麼區別對於新手來說確實不好判斷，所以我建議你可以從top-down parser 開始自己給一門語言寫個parser，開始只選擇幾個特性來寫，然後逐步添加grammar。比如你想給JavaScript寫個parser，那麼參考Lambda Calculus 你可以先實現：1）單參數匿名函數的定義；2）函數調用。這個你只需要LL(1) 就可以了。然後逐步加入其他grammar，當你遇到`function f (x) {...}` 的時候你就發現它和你之前寫的`function (x) {...}` 衝突了（因為前者規約為一個語句，後者規約為一個表達式），這時候你就需要上LL(2).

相對照來說，bottom-up parser 就對應LR(k) parser 了。它和LL(k) 不一樣的地方在於：1）自右向左、自底向上構建語法樹；2）不由「向前看符號」（預測）來驅動。你說的shift、reduce 就是這種演算法中的兩個動作：shift（吞入下一個符號），reduce（將已近吞入的、最右側的、符合某個產生式的一串符號構建成一個語法樹）。但是有時候你會發現在某一步parser 不知道應該shift 還是reduce，這時候SLR 就發揮作用了，它通過向前看一個符號來解決這個衝突。所以說：LL通過預測驅動，而LR通過預測來解決衝突。至於SLR 和LALR 有什麼區別，請移步 SLR與LALR之間的區別？ - vczh 的回答推薦你跟著SLR 演算法，對著一段需要被parse 的程序走一遍，就馬上明白了。

最後再說一下，這張圖應該是想告訴你理論上每種grammar class（以及對應的parsing algirithm）之間描述能力（解析能力）的差別。而且這張圖討論的應該是grammar class 而不是language class。

純理論地來看，它們之間解析能力的差異是很難看出來的，所以給幾個例子，如圖：

你可以看出其實這些特殊的grammar 都是很詭異的，一般不會出現在編程語言中。所以還是像我上面說的那樣，自己挑一門語言實現個parser （不能用parser generator），大多數parsing algorithm 的能力區別你就都明白了。當然，如果你不滿足這種「工程方法」的話，想看一個grammar 可不可以被LL(k) 解析，就手動為每個產生式構建predictive set，看看set 之間有沒有衝突。而LALR（SLR）的話有個更簡單的方法，用Bison 的--report=all 選項生成table，所有的信息都在裡面。