摘要：?1 引言 上回 精讀《手寫 SQL 編譯器 - 語法分析》 說到了如何利用 Js 函數實現語法分析時，留下了一個回溯問題，也就是存檔、讀檔問題。 我們把語法分析樹當作一個迷宮，有直線有岔路，而想要走出迷宮，在遇到岔路時需要提前進行存檔，在后面走錯時讀檔換下一個岔路進行嘗試，這個功能就叫回溯。

1 引言

上回?精讀《手寫 SQL 編譯器 - 語法分析》?說到了如何利用 Js 函數實現語法分析時，留下了一個回溯問題，也就是存檔、讀檔問題。

我們把語法分析樹當作一個迷宮，有直線有岔路，而想要走出迷宮，在遇到岔路時需要提前進行存檔，在后面走錯時讀檔換下一個岔路進行嘗試，這個功能就叫回溯。

上一篇我們實現了?分支函數，在分支執行失敗后回滾 TokenIndex 位置并重試，但在函數調用棧中，如果其子函數執行完畢，堆棧跳出，我們便無法找到原來的函數棧重新執行。

為了更加詳細的描述這個問題，舉一個例子，存在以下岔路：

a -> tree() -> c-> b1 -> b1'-> b2 -> b2'

上面描述了兩條判斷分支，分別是?a -> b1 -> b1' -> c?與?a -> b2 -> b2' -> c，當岔路?b1?執行失敗后，分支函數?tree?可以復原到?b2?位置嘗試重新執行。

但設想?b1 -> b1'?通過，但?b1 -> b1' -> c?不通過的場景，由于?b1'?執行完后，分支函數?tree的調用棧已經退出，無法再嘗試路線?b2 -> b2'?了。

要解決這個問題，我們要?通過鏈表手動構造函數執行過程，這樣不僅可以實現任意位置回溯，還可以解決左遞歸問題，因為函數并不是立即執行的，在執行前我們可以加一些 Magic 動作，比如調換執行順序！這文章主要介紹如何通過鏈表構造函數調用棧，并實現回溯。

2 精讀

假設我們擁有了這樣一個函數?chain，可以用更簡單的方式表示連續匹配：

const root = (tokens: IToken[], tokenIndex: number) => match('a', tokens, tokenIndex) && match('b', tokens, tokenIndex) && match('c', tokens, tokenIndex) ↓ ↓ ↓ ↓ ↓ ↓ const root = (chain: IChain) => chain('a', 'b', 'c')

遇到分支條件時，通過數組表示取代?tree?函數：

const root = (tokens: IToken[], tokenIndex: number) => tree(line(match('a', tokens, tokenIndex) && match('b', tokens, tokenIndex)),line(match('c', tokens, tokenIndex) && match('d', tokens, tokenIndex)) ) ↓ ↓ ↓ ↓ ↓ ↓ const root = (chain: IChain) => chain([chain('a', 'b'),chain('c', 'd') ])

這個?chain?函數有兩個特質：

非立即執行，我們就可以?預先生成執行鏈條?，并對鏈條結構進行優化、甚至控制執行順序，實現回溯功能。

無需顯示傳遞 Token，減少每一步匹配寫的代碼量。

封裝 scanner、matchToken

我們可以制作 scanner 函數封裝對 token 的操作：

const query = "select * from table;"; const tokens = new Lexer(query); const scanner = new Scanner(tokens);

scanner 擁有兩個主要功能，分別是?read?讀取當前 token 內容，和?next?將 token 向下移動一位，我們可以根據這個功能封裝新的?matchToken?函數：

function matchToken(scanner: Scanner,compare: (token: IToken) => boolean ): IMatch {const token = scanner.read();if (!token) {return false;}if (compare(token)) {scanner.next();return true;} else {return false;} }

如果 token 消耗完，或者與比對不匹配時，返回 false 且不消耗 token，當匹配時，消耗一個 token 并返回 true。

現在我們就可以用?matchToken?函數寫一段匹配代碼了：

const query = "select * from table;"; const tokens = new Lexer(query); const scanner = new Scanner(tokens); const root =matchToken(scanner, token => token.value === "select") &&matchToken(scanner, token => token.value === "*") &&matchToken(scanner, token => token.value === "from") &&matchToken(scanner, token => token.value === "table") &&matchToken(scanner, token => token.value === ";");

我們最終希望表達成這樣的結構：

const root = (chain: IChain) => chain("select", "*", "from", "table", ";");

既然 chain 函數作為線索貫穿整個流程，那 scanner 函數需要被包含在 chain 函數的閉包里內部傳遞，所以我們需要構造出第一個 chain。

封裝 createChainNodeFactory

我們需要 createChainNodeFactory 函數將 scanner 傳進去，在內部偷偷存起來，不要在外部代碼顯示傳遞，而且 chain 函數是一個高階函數，不會立即執行，由此可以封裝二階函數：

const createChainNodeFactory = (scanner: Scanner, parentNode?: ChainNode) => (...elements: any[] ): ChainNode => {// 生成第一個節點return firstNode; };

需要說明兩點：

chain 函數返回第一個鏈表節點，就可以通過 visiter 函數訪問整條鏈表了。

(...elements: any[]): ChainNode?就是 chain 函數本身，它接收一系列參數，根據類型進行功能分類。

有了 createChainNodeFactory，我們就可以生成執行入口了：

const chainNodeFactory = createChainNodeFactory(scanner); const firstNode = chainNodeFactory(root); // const root = (chain: IChain) => chain('select', '*', 'from', 'table', ';')

為了支持?chain('select', '*', 'from', 'table', ';')?語法，我們需要在參數類型是文本類型時，自動生成一個 matchToken 函數作為鏈表節點，同時通過 reduce 函數將鏈表節點關聯上：

const createChainNodeFactory = (scanner: Scanner, parentNode?: ChainNode) => (...elements: any[] ): ChainNode => {let firstNode: ChainNode = null;elements.reduce((prevNode: ChainNode, element) => {const node = new ChainNode();// ... Link nodenode.addChild(createChainChildByElement(node, scanner, element));return node;}, parentNode);return firstNode; };

使用 reduce 函數對鏈表上下節點進行關聯，這一步比較常規所以忽略掉，通過 createChainChildByElement 函數對傳入函數進行分類，如果?傳入函數是字符串，就構造一個 matchToken 函數塞入當前鏈表的子元素，當執行鏈表時，再執行 matchToken 函數。

重點是我們對鏈表節點的處理，先介紹一下鏈表結構。

鏈表結構

class ChainNode {public prev: ChainNode;public next: ChainNode;public childs: ChainChild[] = []; }class ChainChild {// If type is function, when run it, will expend.public type: "match" | "chainNode" | "function";public node?: IMatchFn | ChainNode | ChainFunctionNode; }

ChainNode 是對鏈表節點的定義，這里給出了和當前文章內容相關的部分定義。這里用到了雙向鏈表，因此每個 node 節點都擁有 prev 與 next 屬性，分別指向上一個與下一個節點，而 childs 是這個鏈表下掛載的節點，可以是 matchToken 函數、鏈表節點、或者是函數。

整個鏈表結構可能是這樣的：

node1 <-> node2 <-> node3 <-> node4|- function2-1|- matchToken2-1|- node2-1 <-> node2-2 <-> node2-3|- matchToken2-2-1

對每一個節點，都至少存在一個 child 元素，如果存在多個子元素，則表示這個節點是 tree 節點，存在分支情況。

而節點類型?ChainChild?也可以從定義中看到，有三種類型，我們分別說明：

matchToken 類型

這種類型是最基本類型，由如下代碼生成：

chain("word");

鏈表執行時，match 是最基本的執行單元，決定了語句是否能匹配，也是唯一會消耗 Token 的單元。

node 類型

鏈表節點的子節點也可能是一個節點，類比嵌套函數，由如下代碼生成：

chain(chain("word"));

也就是 chain 的一個元素就是 chain 本身，那這個 chain 子鏈表會作為父級節點的子元素，當執行到鏈表節點時，會進行深度優先遍歷，如果執行通過，會跳到父級繼續尋找下一個節點，其執行機制類比函數調用棧的進出關系。

函數類型

函數類型非常特別，我們不需要遞歸展開所有函數類型，因為文法可能存在無限遞歸的情況。

好比一個迷宮，很多區域都是相同并重復的，如果將迷宮完全展開，那迷宮的大小將達到無窮大，所以在計算機執行時，我們要一步步展開這些函數，讓迷宮結束取決于 Token 消耗完、走出迷宮、或者 match 不上 Token，而不是在生成迷宮時就將資源消耗完畢。函數類型節點由如下代碼生成：

chain(root);

所有函數類型節點都會在執行到的時候展開，在展開時如果再次遇到函數節點仍會保留，等待下次執行到時再展開。

分支

普通的鏈路只是分支的特殊情況，如下代碼是等價的：

chain("a"); chain(["a"]);

再對比如下代碼：

chain(["a"]); chain(["a", "b"]);

無論是直線還是分支，都可以看作是分支路線，而直線（無分支）的情況可以看作只有一條分叉的分支，對比到鏈表節點，對應 childs 只有一個元素的鏈表節點。

回溯

現在 chain 函數已經支持了三種子元素，一種分支表達方式：

chain("a"); // MatchNode chain(chain("a")); // ChainNode chain(foo); // FunctionNode chain(["a"]); // 分支 -> [MatchNode]

而上文提到了 chain 函數并不是立即執行的，所以我們在執行這些代碼時，只是生成鏈表結構，而沒有真正執行內容，內容包含在 childs 中。

我們需要構造 execChain 函數，拿到鏈表的第一個節點并通過 visiter 函數遍歷鏈表節點來真正執行。

function visiter(chainNode: ChainNode,scanner: Scanner,treeChances: ITreeChance[] ): boolean {const currentTokenIndex = scanner.getIndex();if (!chainNode) {return false;}const nodeResult = chainNode.run();let nestedMatch = nodeResult.match;if (nodeResult.match && nodeResult.nextNode) {nestedMatch = visiter(nodeResult.nextNode, scanner, treeChances);}if (nestedMatch) {if (!chainNode.isFinished) {// It's a new chance, because child match is true, so we can visit next node, but current node is not finished, so if finally falsely, we can go back here.treeChances.push({chainNode,tokenIndex: currentTokenIndex});}if (chainNode.next) {return visiter(chainNode.next, scanner, treeChances);} else {return true;}} else {if (chainNode.isFinished) {// Game over, back to root chain.return false;} else {// Try againscanner.setIndex(currentTokenIndex);return visiter(chainNode, scanner, treeChances);}} }

上述代碼中，nestedMatch 類比嵌套函數，而 treeChances 就是實現回溯的關鍵。

當前節點執行失敗時

由于每個節點都包含 N 個 child，所以任何時候執行失敗，都給這個節點的 child 打標，并判斷當前節點是否還有子節點可以嘗試，并嘗試到所有節點都失敗才返回 false。

當前節點執行成功時，進行位置存檔

當節點成功時，為了防止后續鏈路執行失敗，需要記錄下當前執行位置，也就是利用 treeChances 保存一個存盤點。

然而我們不知道何時整個鏈表會遭遇失敗，所以必須等待整個 visiter 執行完才知道是否執行失敗，所以我們需要在每次執行結束時，判斷是否還有存盤點（treeChances）：

while (!result && treeChances.length > 0) {const newChance = treeChances.pop();scanner.setIndex(newChance.tokenIndex);result = judgeChainResult(visiter(newChance.chainNode, scanner, treeChances),scanner); }

同時，我們需要對鏈表結構新增一個字段 tokenIndex，以備回溯還原使用，同時調用 scanner 函數的?setIndex?方法，將 token 位置還原。

最后如果機會用盡，則匹配失敗，只要有任意一次機會，或者能一命通關，則匹配成功。

3 總結

本篇文章，我們利用鏈表重寫了函數執行機制，不僅使匹配函數擁有了回溯能力，還讓其表達更為直觀：

chain("a");

這種構造方式，本質上與根據文法結構編譯成代碼的方式是一樣的，只是許多詞法解析器利用文本解析成代碼，而我們利用代碼表達出了文法結構，同時自身執行后的結果就是 “編譯后的代碼”。

下次我們將探討如何自動解決左遞歸問題，讓我們能夠寫出這樣的表達式：

const foo = (chain: IChain) => chain(foo, bar);

好在 chain 函數并不是立即執行的，我們不會立即掉進堆棧溢出的漩渦，但在執行節點的過程中，會導致函數無限展開從而堆棧溢出。

解決左遞歸并不容易，除了手動或自動重寫文法，還會有其他方案嗎？歡迎留言討論。

原文鏈接?

本文為云棲社區原創內容，未經允許不得轉載。?

總結

以上是生活随笔為你收集整理的精读《手写 SQL 编译器 - 回溯》的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。