遞迴下降可以說是直覺且強大的解析方法。
今天會從解析 JSON 開始，講解如何從頭建立一個 JSON 解析器。由於 JSON 的架構簡單，很適合當作練習。雖然解析語法這件事情的確和前端或是平時的開發沒有什麼太大的關聯，不過如果有天要設計一個 DSL，或是有特殊需求可能要建立一個客製化的語言時，這些技巧就可以派上用場。
為什麼要學遞迴下降？
有了 JSON.parse 為什麼還要學遞迴下降？透過簡單的分析語法，除了正常解析 JSON 資料之外，你還可以實作自己的語法。同時將本技巧應用在其他地方。
舉例來說一般的 JSON 像這樣：
{
"name": "kalan",
"age": 20
}假設今天想要加入一個新語法，叫做模板好了，只要包在 {} 裡頭的字串，都會自動用變數取代，例如：
{
"name": "kalan",
"age": 20,
"job": $job$
}透過客製化的 parse 函數解析：
parse(json, { job: 'engineer' });
// {
// "name": kalan,
// "age": 20,
// "job": "engineer"
// }或是今天想要換個新符號：
{
"name" @ "kalan"
"age" @ 20
}今天我們就來寫一個可以解析 JSON 的遞迴下降解析器。並且修改成上述的兩個自肥的功能。
遞迴下降（Recursive Descent）是什麼？
一般在講遞迴下降的時候，難免會陷入各種可怕名詞與符號的迷思，例如 LL、LR、自頂向下、非終止等等，我們試著用最直觀的方式來討論。先來看圖：
我們將 JSON 的形式用圖表示，可以發現 JSON 主要可以用 key + : + value 組成，value 又可以再拆分成字串、布林值、數字、null、object 等。
有沒有發現如果 value 是 object 的話，同樣的規則可以再重新套用一次，也就是回到圖的最上層，並且用同樣的規則繼續解析。
這樣不停的輪迴就叫遞迴，而從上往下查詢可以匹配的規則，就叫自頂向下，整個組合起來就叫遞迴下降。
關於每個型別以及語法的詳細定義，我們可以參考一下 JSON 規範：
先用一個最簡單的例子：只有一個 key 跟 value，且 value 是字串型別。
{
"name": "kalan"
}
以下的過程（可對照上圖作參考）
- 遇到
{，開始 object 解析 - 進入
key解析，預期為字串 - 遇到
"，字串解析 - 遇到 n, a, m, e：將 name 當作 key
- 遇到
"：結束字串匹配，預期會有:以符合規則 - 遇到
:：進入value解析 - 遇到
"：進入字串解析 - 遇到 k, a, l, a, n：將 value 設為
kalan - 遇到
"：結束字串匹配 - 遇到
}：結束 object 匹配 - 遇到空字串（EOF）：結束解析
從過程中可以發現，一個解析的過程很像一連串的狀態變化，每次遇到匹配的值，我們就按照上圖的規則，測試是否要前往下一個方框，每個方框中能夠接收的值也不太一樣。如果能夠順利從左邊走到右邊，代表成功匹配。
接下來我們就試著來實作看看。
一個簡單的解析器實作
一個簡單的解析器可以用一個指標、位置資訊、目前讀取字元幾個資訊達成。
用 parse 函式當作程式進入點，只要符合某個狀態就執行對應的函數。
首先我們先定義會用到的函數：
class Parser {
constructor(raw) {
this.raw = raw;
this.index = 0;
}
// 目前字元
current() {
return this.raw[this.index];
}
// 匹配之後的字串是否為 str
// e.g: next('{')
// 判斷下一個字元是否為 '{'
// 如果是的話將 index 移過去
// 並且回傳 true
// 方便判斷狀態
next(str) {
if (this.raw.slice(this.index, this.index + str.length) === str) {
this.index += str.length;
return true;
}
return false;
}
// 省略空白，目前只考慮 " "
// 不實作 tab 等功能
skip() {
while (this.raw[this.index] <= " ") {
this.index += 1;
}
}
parse() {
const value = object(this); // entry point
return value;
}
}主要的進入點可以看 parse ，同時我們定義了一些輔助函數，像是 skip 跟 next 方便我們確認當前的狀態，再來我們看看 object 函數的實作：
function object(parser) {
const obj = Object.create(null);
let key = "";
// 如果是 { 開頭，代表要用 object 函數解析
if (parser.current() === "{") {
parser.next("{");
parser.skip();
// 如果馬上遇到 }
// 代表他是一個空物件 {}
if (parser.current() === "}") {
parser.next("}");
return obj;
}
// 讀取當前字元，判斷要用哪一個函數解析
while (parser.current()) {
key = string(parser); // key 一定是字串，所以我們用字串解析
parser.skip(); // 省略空白字元
parser.next(":"); // 預期是 :
obj[key] = string(parser); // 先假設值只有字串，一律用字串解析
parser.skip();
if (parser.current() === "}") { // 如果遇到 }，代表物件解析結束，return obj
parser.next("}");
return obj;
}
parser.next(","); // 如果有逗號，代表有下一個 key-value，繼續跑 while 解析
parser.skip();
}
}
}-
如果現在的字元是
{- 如果下一個字元是
}，代表是空物件，回傳後跳出
- 如果下一個字元是
-
進入 while 迴圈，用
string解析 key（因為 JSON 的 key 一定是字串）。string函數的實作我們下面講解。- 省略空白字元（像下列情形）
{ "name" : "value" }- 預期
:出現 - 將 value 用
string解析（這邊我們先暫時假設只有字串，後面再陸續補上其他型別的處理） - 省略空白字元
- 如果遇到
}代表物件結尾，回傳 obj - 如果遇到
,，代表要繼續解析下一個 key-value - 省略空白字元
字串解析實作：
function string(parser) {
parser.next('"'); // 如果下一個字元為 "，代表我們要用 string 的方式解析
if (parser.next('"')) {
// { "": "value" } 我們將 key 為空的 JSON 當做不合法的
throw new Error("JSON key is empty.");
}
let key = "";
let curr = "";
// 不斷讀取下一個字元直到讀到 "
while (((curr = parser.current()), curr)) {
if (parser.next('"')) {
parser.index += 1;
return key;
}
key += curr;
parser.index += 1;
}
}- 預期字元為
" - 如果下一個字元為
"代表是個空字串，為不合法的 key，跳出警告 - 進入 whilte 迴圈直到讀到字元
"
想要練習的話可以參考 Repo
手寫 parser 會比較麻煩一些，有時候會有一些小狀況沒有處理到。我會建議要練習的話，可以一開始就寫測試，會省下很多手動測試的時間。
結語
我們雖然實作了一個遞迴下降解析器，但是並沒有經過轉換成 AST（抽象語法樹）的過程，而是直接轉換成 JavaScript 的物件，這是因為 JSON 的資料結構相對單純，不需要再經過這個轉換。
另外在實作解析器的時候，不妨再思考幾個觀點：
- 為了讓錯誤訊息更友善，或許我們可以用 row, column 二維的方式記錄資訊而非一維。
- 實作更友善的錯誤訊息，例如忘記加
}的時候可以提醒開發者，或是語法錯誤時可以明確指出錯誤的地方
為了保持彈性，你也可以將符號用變數（Token）取代。
在 part2 我們會繼續實作其他型別，像是數字、陣列、布林值、null 等等，把它變成更完整的 JSON 解析器，同時我們也會開始實作剛剛講到的兩個魔改的功能：用 @ 當分隔以及用 {} 當作 template。