摘要：引言上回精讀手寫編譯器語法分析說到了如何利用函數實現語法分析時，留下了一個回溯問題，也就是存檔讀檔問題。更多討論討論地址是精讀手寫編譯器回溯如果你想參與討論，請點擊這里，每周都有新的主題，周末或周一發布。

上回 精讀《手寫 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 動作，比如調換執行順序！這文章主要介紹如何通過鏈表構造函數調用棧，并實現回溯。

假設我們擁有了這樣一個函數 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 函數封裝對 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 函數將 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 node

    node.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 也可以從定義中看到，有三種類型，我們分別說明：

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

chain("word");

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

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

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 again
      scanner.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 位置還原。

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

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

chain("a");

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

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

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

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

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

討論地址是：精讀《手寫 SQL 編譯器 - 回溯》 · Issue #96 · dt-fe/weekly

如果你想參與討論，請點擊這里，每周都有新的主題，周末或周一發布。