摘要：引言上回精讀手寫編譯器語(yǔ)法分析說到了如何利用函數(shù)實(shí)現(xiàn)語(yǔ)法分析時(shí)，留下了一個(gè)回溯問題，也就是存檔讀檔問題。更多討論討論地址是精讀手寫編譯器回溯如果你想?yún)⑴c討論，請(qǐng)點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。

上回 精讀《手寫 SQL 編譯器 - 語(yǔ)法分析》 說到了如何利用 Js 函數(shù)實(shí)現(xiàn)語(yǔ)法分析時(shí)，留下了一個(gè)回溯問題，也就是存檔、讀檔問題。

我們把語(yǔ)法分析樹當(dāng)作一個(gè)迷宮，有直線有岔路，而想要走出迷宮，在遇到岔路時(shí)需要提前進(jìn)行存檔，在后面走錯(cuò)時(shí)讀檔換下一個(gè)岔路進(jìn)行嘗試，這個(gè)功能就叫回溯。

上一篇我們實(shí)現(xiàn)了 分支函數(shù)，在分支執(zhí)行失敗后回滾 TokenIndex 位置并重試，但在函數(shù)調(diào)用棧中，如果其子函數(shù)執(zhí)行完畢，堆棧跳出，我們便無(wú)法找到原來(lái)的函數(shù)棧重新執(zhí)行。

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

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

上面描述了兩條判斷分支，分別是 a -> b1 -> b1" -> c 與 a -> b2 -> b2" -> c，當(dāng)岔路 b1 執(zhí)行失敗后，分支函數(shù) tree 可以復(fù)原到 b2 位置嘗試重新執(zhí)行。

但設(shè)想 b1 -> b1" 通過，但 b1 -> b1" -> c 不通過的場(chǎng)景，由于 b1" 執(zhí)行完后，分支函數(shù) tree 的調(diào)用棧已經(jīng)退出，無(wú)法再嘗試路線 b2 -> b2" 了。

要解決這個(gè)問題，我們要 通過鏈表手動(dòng)構(gòu)造函數(shù)執(zhí)行過程，這樣不僅可以實(shí)現(xiàn)任意位置回溯，還可以解決左遞歸問題，因?yàn)楹瘮?shù)并不是立即執(zhí)行的，在執(zhí)行前我們可以加一些 Magic 動(dòng)作，比如調(diào)換執(zhí)行順序！這文章主要介紹如何通過鏈表構(gòu)造函數(shù)調(diào)用棧，并實(shí)現(xiàn)回溯。

假設(shè)我們擁有了這樣一個(gè)函數(shù) chain，可以用更簡(jiǎn)單的方式表示連續(xù)匹配：

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")

遇到分支條件時(shí)，通過數(shù)組表示取代 tree 函數(shù)：

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")
])

這個(gè) chain 函數(shù)有兩個(gè)特質(zhì)：

非立即執(zhí)行，我們就可以 預(yù)先生成執(zhí)行鏈條 ，并對(duì)鏈條結(jié)構(gòu)進(jìn)行優(yōu)化、甚至控制執(zhí)行順序，實(shí)現(xiàn)回溯功能。

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

我們可以制作 scanner 函數(shù)封裝對(duì) token 的操作：

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

scanner 擁有兩個(gè)主要功能，分別是 read 讀取當(dāng)前 token 內(nèi)容，和 next 將 token 向下移動(dòng)一位，我們可以根據(jù)這個(gè)功能封裝新的 matchToken 函數(shù)：

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 消耗完，或者與比對(duì)不匹配時(shí)，返回 false 且不消耗 token，當(dāng)匹配時(shí)，消耗一個(gè) token 并返回 true。

現(xiàn)在我們就可以用 matchToken 函數(shù)寫一段匹配代碼了：

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 === ";");

我們最終希望表達(dá)成這樣的結(jié)構(gòu)：

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

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

我們需要 createChainNodeFactory 函數(shù)將 scanner 傳進(jìn)去，在內(nèi)部偷偷存起來(lái)，不要在外部代碼顯示傳遞，而且 chain 函數(shù)是一個(gè)高階函數(shù)，不會(huì)立即執(zhí)行，由此可以封裝二階函數(shù)：

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

需要說明兩點(diǎn)：

chain 函數(shù)返回第一個(gè)鏈表節(jié)點(diǎn)，就可以通過 visiter 函數(shù)訪問整條鏈表了。

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

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

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

為了支持 chain("select", "*", "from", "table", ";") 語(yǔ)法，我們需要在參數(shù)類型是文本類型時(shí)，自動(dòng)生成一個(gè) matchToken 函數(shù)作為鏈表節(jié)點(diǎn)，同時(shí)通過 reduce 函數(shù)將鏈表節(jié)點(diǎn)關(guān)聯(lián)上：

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 函數(shù)對(duì)鏈表上下節(jié)點(diǎn)進(jìn)行關(guān)聯(lián)，這一步比較常規(guī)所以忽略掉，通過 createChainChildByElement 函數(shù)對(duì)傳入函數(shù)進(jìn)行分類，如果 傳入函數(shù)是字符串，就構(gòu)造一個(gè) matchToken 函數(shù)塞入當(dāng)前鏈表的子元素，當(dāng)執(zhí)行鏈表時(shí)，再執(zhí)行 matchToken 函數(shù)。

重點(diǎn)是我們對(duì)鏈表節(jié)點(diǎn)的處理，先介紹一下鏈表結(jié)構(gòu)。

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 是對(duì)鏈表節(jié)點(diǎn)的定義，這里給出了和當(dāng)前文章內(nèi)容相關(guān)的部分定義。這里用到了雙向鏈表，因此每個(gè) node 節(jié)點(diǎn)都擁有 prev 與 next 屬性，分別指向上一個(gè)與下一個(gè)節(jié)點(diǎn)，而 childs 是這個(gè)鏈表下掛載的節(jié)點(diǎn)，可以是 matchToken 函數(shù)、鏈表節(jié)點(diǎn)、或者是函數(shù)。

整個(gè)鏈表結(jié)構(gòu)可能是這樣的：

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

對(duì)每一個(gè)節(jié)點(diǎn)，都至少存在一個(gè) child 元素，如果存在多個(gè)子元素，則表示這個(gè)節(jié)點(diǎn)是 tree 節(jié)點(diǎn)，存在分支情況。

而節(jié)點(diǎn)類型 ChainChild 也可以從定義中看到，有三種類型，我們分別說明：

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

chain("word");

鏈表執(zhí)行時(shí)，match 是最基本的執(zhí)行單元，決定了語(yǔ)句是否能匹配，也是唯一會(huì)消耗 Token 的單元。

鏈表節(jié)點(diǎn)的子節(jié)點(diǎn)也可能是一個(gè)節(jié)點(diǎn)，類比嵌套函數(shù)，由如下代碼生成：

chain(chain("word"));

也就是 chain 的一個(gè)元素就是 chain 本身，那這個(gè) chain 子鏈表會(huì)作為父級(jí)節(jié)點(diǎn)的子元素，當(dāng)執(zhí)行到鏈表節(jié)點(diǎn)時(shí)，會(huì)進(jìn)行深度優(yōu)先遍歷，如果執(zhí)行通過，會(huì)跳到父級(jí)繼續(xù)尋找下一個(gè)節(jié)點(diǎn)，其執(zhí)行機(jī)制類比函數(shù)調(diào)用棧的進(jìn)出關(guān)系。

函數(shù)類型非常特別，我們不需要遞歸展開所有函數(shù)類型，因?yàn)槲姆赡艽嬖跓o(wú)限遞歸的情況。

好比一個(gè)迷宮，很多區(qū)域都是相同并重復(fù)的，如果將迷宮完全展開，那迷宮的大小將達(dá)到無(wú)窮大，所以在計(jì)算機(jī)執(zhí)行時(shí)，我們要一步步展開這些函數(shù)，讓迷宮結(jié)束取決于 Token 消耗完、走出迷宮、或者 match 不上 Token，而不是在生成迷宮時(shí)就將資源消耗完畢。函數(shù)類型節(jié)點(diǎn)由如下代碼生成：

chain(root);

所有函數(shù)類型節(jié)點(diǎn)都會(huì)在執(zhí)行到的時(shí)候展開，在展開時(shí)如果再次遇到函數(shù)節(jié)點(diǎn)仍會(huì)保留，等待下次執(zhí)行到時(shí)再展開。

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

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

再對(duì)比如下代碼：

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

無(wú)論是直線還是分支，都可以看作是分支路線，而直線（無(wú)分支）的情況可以看作只有一條分叉的分支，對(duì)比到鏈表節(jié)點(diǎn)，對(duì)應(yīng) childs 只有一個(gè)元素的鏈表節(jié)點(diǎn)。

現(xiàn)在 chain 函數(shù)已經(jīng)支持了三種子元素，一種分支表達(dá)方式：

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

而上文提到了 chain 函數(shù)并不是立即執(zhí)行的，所以我們?cè)趫?zhí)行這些代碼時(shí)，只是生成鏈表結(jié)構(gòu)，而沒有真正執(zhí)行內(nèi)容，內(nèi)容包含在 childs 中。

我們需要構(gòu)造 execChain 函數(shù)，拿到鏈表的第一個(gè)節(jié)點(diǎn)并通過 visiter 函數(shù)遍歷鏈表節(jié)點(diǎn)來(lái)真正執(zhí)行。

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 類比嵌套函數(shù)，而 treeChances 就是實(shí)現(xiàn)回溯的關(guān)鍵。

由于每個(gè)節(jié)點(diǎn)都包含 N 個(gè) child，所以任何時(shí)候執(zhí)行失敗，都給這個(gè)節(jié)點(diǎn)的 child 打標(biāo)，并判斷當(dāng)前節(jié)點(diǎn)是否還有子節(jié)點(diǎn)可以嘗試，并嘗試到所有節(jié)點(diǎn)都失敗才返回 false。

當(dāng)節(jié)點(diǎn)成功時(shí)，為了防止后續(xù)鏈路執(zhí)行失敗，需要記錄下當(dāng)前執(zhí)行位置，也就是利用 treeChances 保存一個(gè)存盤點(diǎn)。

然而我們不知道何時(shí)整個(gè)鏈表會(huì)遭遇失敗，所以必須等待整個(gè) visiter 執(zhí)行完才知道是否執(zhí)行失敗，所以我們需要在每次執(zhí)行結(jié)束時(shí)，判斷是否還有存盤點(diǎn)（treeChances）：

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

同時(shí)，我們需要對(duì)鏈表結(jié)構(gòu)新增一個(gè)字段 tokenIndex，以備回溯還原使用，同時(shí)調(diào)用 scanner 函數(shù)的 setIndex 方法，將 token 位置還原。

最后如果機(jī)會(huì)用盡，則匹配失敗，只要有任意一次機(jī)會(huì)，或者能一命通關(guān)，則匹配成功。

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

chain("a");

這種構(gòu)造方式，本質(zhì)上與根據(jù)文法結(jié)構(gòu)編譯成代碼的方式是一樣的，只是許多詞法解析器利用文本解析成代碼，而我們利用代碼表達(dá)出了文法結(jié)構(gòu)，同時(shí)自身執(zhí)行后的結(jié)果就是 “編譯后的代碼”。

下次我們將探討如何自動(dòng)解決左遞歸問題，讓我們能夠?qū)懗鲞@樣的表達(dá)式：

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

好在 chain 函數(shù)并不是立即執(zhí)行的，我們不會(huì)立即掉進(jìn)堆棧溢出的漩渦，但在執(zhí)行節(jié)點(diǎn)的過程中，會(huì)導(dǎo)致函數(shù)無(wú)限展開從而堆棧溢出。

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

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

如果你想?yún)⑴c討論，請(qǐng)點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。