通過閱讀 Douglas Crockford 的源碼學習如何寫 JSON parser（一）

github.com

Douglas Crockford 是 JSON 的發明者，所以通過 DC 的代碼來學習 JSON 和 parser 絕對是上乘之選。這個倉庫裡面有四個 JS 文件，今天我們先研究 json_parse.js。

json_parse 定義了如下 API：

json_parse(string) => objectjson_parse(string, (key,value)=>newValue ) => object

今天我們只研究第一種 API。

代碼結構

用 WebStorm 打開源碼方便閱讀，把主要函數摺疊起來，就會發現代碼結構非常清晰，完整結構如下：

var json_parse = (function(){ use strict var at; // The index of the current character var ch; // The current character var escape = {...} var text var error = function(){...} var next = function(){...} var number = function(){...} var string = function(){...} var white = function(){...} var word = function(){...} var array = function(){...} var object = function(){...} var value = function(){...} return function parser(source, reciver){...}}())

代碼首先用一個立即執行函數造出一個局部作用域，ES 6 中我們只需要用 block 和 let 代替就行了。

思路

主要思路在最後一個 parser 函數里，我們來看一下：

return function (source, reviver) { var result; text = source; at = 0; ch = " "; result = value(); white(); if (ch) { error("Syntax error"); } return result; };

看起來毫無邏輯呀。

為什麼我老是說「看源碼的投入產出比很低」呢，因為你需要看完所有代碼，才知道主要邏輯是在做什麼。

還好代碼不多，我看完之後總結作者的思路如下。

有三個重要的變數，ch、at 和 text

• ch 指向一個字元（實際上是複製了字元的值，但是用指向更好理解源碼），ch 默認指向一個空字元串（不要問這個空字元串有什麼意義，主要是為了讓代碼簡潔）
• at 指向下一個字元，at 存儲了下一個字元的索引（index）
• text 包含了所有字元，也就是一個符合 JSON 語法的字元串

接下來我們定義一個動作：吃。

1. 吃，表示將 ch 指向 at 所指的字元，然後 at 指向下一個字元。
2. 吃一個空格，表示 ch 指向的字元必須是空格，然後吃（吃的定義見第一條）；換句話說，吃一個空格的意思就是：我吃掉的字元必須是空格，不是空格就報錯。
3. 吃一個{，表示我吃掉的字元必須是{，否則就報錯
4. 吃一個}，表示我吃掉的字元必須是}，否則就報錯
5. 以此類推……

好了，parser 的難點講完了，接下來就是細節了，假設 text 是字元串 { "name" : "Frank" }，一次完整的邏輯如下

1. ch=" "，at=0, text = `{ "name" : "Frank" }`
2. 吃一個空格。由於 ch 一開始的默認值是空格，所以這個空格就被吃掉了，然後 ch 指向text 的第一個字元，at 指向 ch 後面一個字元（存下標，也就是1）。
3. 如果 ch 是空格就繼續吃，吃到 ch 不是空格為止。
4. 發現 ch 是 {，就說明這是一個對象，生成一個空對象 object 用來存儲 key 和 value。而且後面的字元就要按照對象的語法來吃。
5. 吃空格直到遇到非空格。理論上 { 後面應該接一個 "key"，所以這個非空格必須是 "。
6. 吃一個 "
7. 吃 N 個非 " 的字元（N >= 0）
8. 吃一個 "
9. 把剛才吃到的 N 個字元作為一個 key，放到空對象 object 里
10. 吃空格直到遇到非空格。理論上 "key" 後面應該接 : 所以這個非空格必須是 :
11. 吃一個 :
12. 吃空格直到遇到非空格。理論上冒號後面應該接 value，value 的值可以是對象、數組、字元串、bool、null 等，所以不能預期這個非空格是什麼
13. 發現是一個 "，吃掉這個 "
14. 吃 N 個非 " 的字元
15. 吃一個 "
16. 把剛才吃到的 N 個字元作為一個 value，放到空對象 object 里
17. 吃空格直到遇到非空格。理論上 value 後面可以接逗號或者 }
18. 發現 ch 是 }，吃掉 }，說明 object 的數據已經讀完了
19. 一直吃空格，如果發現非空格，說明語法錯誤，報錯。
20. 將 object 返回，這個 object 就是 text 對應的數據了。

如果你能在大腦里過一遍這個過程，就可以看懂所有源碼了：

var json_parse = (function(){ use strict var at; // The index of the current character var ch; // The current character var escape = {...} var text var error = function(){...} var next = 吃(){} var number = 吃一個完整的數字(){...} var string = 吃一個完整的字元串(){...} var white = 吃N個空格(){...} var word = 吃true/false/null這幾個單詞(){...} var array = 吃一個完整的字元串(){...} var object = 吃一個對象(){...} var value = 吃一個值，包括對象數組字元串數組bool和null(){...} return function parser(source, reciver){...}}())

然後我們就可以重點看主邏輯了：

return function (source, reviver) { var result; text = source; at = 0; ch = " "; result = value(); // 吃一個值 white(); // 吃掉後面的空格 if (ch) { // 如果空格後面還有字元，就是語法錯誤了 error("Syntax error"); } return result; };

也就是說主邏輯其實很簡單

1. 用 value() 吃一個值，這個值就是 text 對應的數據
2. 繼續吃掉所有空格
3. 吃完發現還有字元（一定是非空格），就說明語法錯了（畫蛇添足）

接下來我們看 value() 的邏輯

value = function () { white(); switch (ch) { case "{": return object(); case "[": return array(); case """: return string(); case "-": return number(); default: return (ch >= "0" && ch <= "9") ? number() : word(); } };

邏輯也很簡單：

1. 吃掉所有空格。
2. 看當前的字元（ch）是什麼
3. 如果 ch 是 {，就吃一整個對象，然後把對象返回
4. 如果 ch 是 [，就吃一整個數組，然後把數組返回
5. 如果 ch 是 "，就吃一整個字元串，然後把字元串返回
6. 如果 ch 是 -，就吃一整個數字，然後把數字返回
7. 如果 ch 是 0~9，就吃一整個數字，然後把數字返回
8. 其他情況只可能是 true/false/null，見啥吃啥，然後返回

圖示如下：

DC 用 ch >= "0" && ch <= "9" 來判斷字元是不是 0~9，這用到了 ASCII 字符集，如果你不懂就去搜一下。

大家應該對如何吃一個對象最感興趣，我們來看看 object() 的邏輯

var object = function () { var key; var obj = {}; if (ch === "{") { // 當前字元必然是 { next("{"); // 吃掉這個 { white(); // 吃掉所有空格 if (ch === "}") { // 遇到 } 說明對象結束了 next("}"); // 吃掉這個 } return obj; // 返回空對象 } while (ch) { // 沒有遇到 } 說明有 key key = string(); // 吃一個 string 當做 key white(); // 吃掉所有空格 next(":"); // 吃掉一個 : if (Object.hasOwnProperty.call(obj, key)) { error("Duplicate key " + key + ""); } // 如果這個 key 之前遇到過就報錯 obj[key] = value();// 把key當做object的key，然後吃一個value作為值 white(); // 吃掉所有空格 if (ch === "}") { // 如果遇到 } 說明對象結束了 next("}"); // 吃掉這個 } return obj; // 返回對象 } next(","); // 沒有遇到 } 說明還有 key，吃一個逗號 white(); // 吃掉空格然後繼續回到上面吃 key } } error("Bad object"); // 如果運行到這裡說明語法有問題 };

到此我們基本搞清楚 DC 的 json_parser 的思路了，大家可以自己看一下 white()、array() 的源碼，結構十分清晰。

下次我們講 json_parse_state.js 如何使用狀態機的思路重寫了這個 parser。