如何從CFG轉換到State Machine？

01-28

看了rapidjson的相關設計(http://rapidjson.org/zh-cn/md_doc_internals.html#IterativeParserGrammar)，想問一下如何從JSON的CFG、Parsing
Table轉換成State Machine，以及如何判定轉換後的State Machine是否和CFG等價？能否詳細解答一下或者有沒有相關書籍推薦？

CFG轉state machine的時候，每條邊的輸入不是一個token，而是一個token+一個自己維護的堆棧，這個堆棧恰好可以代表所有已經看過的token留下來的一個歷史狀態，好讓你在輸入同一個token的時候，從同一個狀態出發跑到不同的地方去。這種state machine叫push down automaton。

在一般的開發過程中，這個堆棧是一顆組合了一半的AST（也就是以樹作為數據結構表達的、你最終需要的JSON對象）。你要標記出當前需要填充的位置，加上每一個AST到parent的指針，恰好是堆棧的結構。一個AST節點parse完了（譬如說遇到了}）就pop掉，一個AST節點開始（譬如說遇到了{）就push進去。

既然已經有了這個名字，剩下的就是bing了，把演算法背下來就好了，你要的大概就是什麼LALR(∞)之類的東西。你應該慶幸JSON的CFG都沒有什麼左遞歸這樣的爛事（逃

我們從recursive parser開始。

你怎麼寫一個recursive parser呢？

在一個parse函數裡面，根據一個look ahead token，然後遞歸的調用相應的parseObject，parseArray。

這個時候，系統棧狀態表達你的狀態機狀態，look ahead token表達一條狀態機的邊，將當前狀態映射到新的狀態上。

言下之意 stack state x look ahead token -&> new state

然後開始說iterative parser。我們不想使用系統棧（因為它尺寸受限）。

原先的stack state被轉換為一個具體的符號（代碼表現為一個enum tag），而不是一個隱式存儲在函數棧里的狀態。

以上部分在vczh的答案里有詳細解釋。

那怎麼把stack state轉換為一個具體的符號呢？

在文檔里的流程是這樣：算First，然後算Follow，最後出Parse Table。

然後你在代碼里把Parse Table抄進去，代碼上表現為一個look up table。

你可以在reader.h裡面搜索iterative parsing。第一個命中之後的表就是parsing table的實現。

Q: 為什麼算First？

A: 因為要算Follow。

Q: 為什麼算Follow？

A: 直觀的說，Follow的意思是，給出一個production rule，它後面跟隨（follow）一個什麼樣的terminal，可以映射到另一個production rule？

可以想見，這個Follow集合用來構建state machine的邊。

RapidJSON文檔里展現出來的state machine，還經過了一個手工處理：

形如這樣一個長鏈，且中間沒有出入邊的子圖： A -&> B -&> C -&> D，

都被摺疊成了A -&> D。

但是我發覺這部分內容，在文檔里都沒有詳細說明。

所以當我現在重新閱讀這部分文字的時候感受到了很大跳躍性。

我覺得CFG到iterative parsing state machine的轉換是可以自動完成的。

只是生成的節點名稱可能不會如手工製作的這麼直觀。

參考資料方面，

所有這些都稱為Predictive parsing。你可以用這個關鍵字搜索到非常多的資料。

最後，怎樣證明CFG和生成的state machine等價？

說實話當時我沒有考慮這個問題。

如果現在立即來想的話，我的思路是這樣：

首先證明CFG production中的狀態（這個需要定義）一定可以對應到state machine中的節點；CFG production中的狀態轉移（這個需要定義）也一定可以對應到state machine中的邊。

然後state machine中的節點，一定可以覆蓋CFG production中的狀態；state machine中的邊，也一定要覆蓋CFG production中的狀態轉移。

注意上面這種證明是構造式的。那隨意一個，可能不是由這種方法構造而來的state machine呢？

需要證明它可以轉化為我們的構造式state machine；或者證明state machine唯一（我覺得這路走不通）。

我想我不能完整回答這個問題了。

書不在手邊一下講不清 CFG 到 pushdown automata 的轉換。關於 Formal Language Automata 方面的問題，Introduction to the Theory of Computation by Sipser 值得一看，前半本書講了各類 formal language 和對應的 automata 的構造及證明。