摘要：引言是一個版語法解析器生成器，具有分詞語法樹解析的能力。實現(xiàn)函數(shù)用鏈表設(shè)計函數(shù)是最佳的選擇，我們要模擬調(diào)用棧了。但光標所在的位置是期望輸入點，這個輸入點也應該參與語法樹的生成，而錯誤提示不包含光標，所以我們要執(zhí)行兩次。

syntax-parser 是一個 JS 版語法解析器生成器，具有分詞、語法樹解析的能力。

通過兩個例子介紹它的功能。

第一個例子是創(chuàng)建一個詞法解析器 myLexer：

import { createLexer } from "syntax-parser";

const myLexer = createLexer([
  {
    type: "whitespace",
    regexes: [/^(s+)/],
    ignore: true
  },
  {
    type: "word",
    regexes: [/^([a-zA-Z0-9]+)/]
  },
  {
    type: "operator",
    regexes: [/^(+)/]
  }
]);

如上，通過正則分別匹配了 “空格”、“字母或數(shù)字”、“加號”，并將匹配到的空格忽略（不輸出）。

分詞匹配是從左到右的，優(yōu)先匹配數(shù)組的第一項，依此類推。

接下來使用 myLexer：

const tokens = myLexer("a + b");

// tokens:
// [
//   { "type": "word", "value": "a", "position": [0, 1] },
//   { "type": "operator", "value": "+", "position": [2, 3] },
//   { "type": "word", "value": "b", "position": [4, 5] },
// ]

"a + b" 會按照上面定義的 “三種類型” 被分割為數(shù)組，數(shù)組的每一項都包含了原始值以及其位置。

第二個例子是創(chuàng)建一個語法解析器 myParser：

import { createParser, chain, matchTokenType, many } from "syntax-parser";

const root = () => chain(addExpr)(ast => ast[0]);

const addExpr = () =>
  chain(matchTokenType("word"), many(addPlus))(ast => ({
    left: ast[0].value,
    operator: ast[1] && ast[1][0].operator,
    right: ast[1] && ast[1][0].term
  }));

const addPlus = () =>
  chain("+"), root)(ast => ({
    operator: ast[0].value,
    term: ast[1]
  }));

const myParser = createParser(
  root, // Root grammar.
  myLexer // Created in lexer example.
);

利用 chain 函數(shù)書寫文法表達式：通過字面量的匹配（比如 + 號），以及 matchTokenType 來模糊匹配我們上面詞法解析出的 “三種類型”，就形成了完整的文法表達式。

syntax-parser 還提供了其他幾個有用的函數(shù)，比如 many optional 分別表示匹配多次和匹配零或一次。

接下來使用 myParser：

const ast = myParser("a + b");

// ast:
// [{
//   "left": "a",
//   "operator": "+",
//   "right": {
//     "left": "b",
//     "operator": null,
//     "right": null
//   }
// }]

按照下面的思路大綱進行源碼解讀：

詞法解析

詞匯與概念

分詞器

語法解析

詞匯與概念

重新做一套 “JS 執(zhí)行引擎”

實現(xiàn) Chain 函數(shù)

引擎執(zhí)行

何時算執(zhí)行完

“或” 邏輯的實現(xiàn)

many, optional, plus 的實現(xiàn)

錯誤提示 & 輸入推薦

First 集優(yōu)化

詞法解析有點像 NLP 中分詞，但比分詞簡單的時，詞法解析的分詞邏輯是明確的，一般用正則片段表達。

Lexer：詞法解析器。

Token：分詞后的詞素，包括 value:值、position:位置、type:類型。

分詞器 createLexer 函數(shù)接收的是一個正則數(shù)組，因此思路是遍歷數(shù)組，一段一段匹配字符串。

我們需要這幾個函數(shù)：

class Tokenizer {
  public tokenize(input: string) {
    // 調(diào)用 getNextToken 對輸入字符串 input 進行正則匹配，匹配完后 substring 裁剪掉剛才匹配的部分，再重新匹配直到字符串裁剪完
  }

  private getNextToken(input: string) {
    // 調(diào)用 getTokenOnFirstMatch 對輸入字符串 input 進行遍歷正則匹配，一旦有匹配到的結(jié)果立即返回
  }

  private getTokenOnFirstMatch({
    input,
    type,
    regex
  }: {
    input: string;
    type: string;
    regex: RegExp;
  }) {
    // 對輸入字符串 input 進行正則 regex 的匹配，并返回 Token 對象的基本結(jié)構(gòu)
  }
}

tokenize 是入口函數(shù)，循環(huán)調(diào)用 getNextToken 匹配 Token 并裁剪字符串直到字符串被裁完。

語法解析是基于詞法解析的，輸入是 Tokens，根據(jù)文法規(guī)則依次匹配 Token，當 Token 匹配完且完全符合文法規(guī)范后，語法樹就出來了。

詞法解析器生成器就是 “生成詞法解析器的工具”，只要輸入規(guī)定的文法描述，內(nèi)部引擎會自動做掉其余的事。

這個生成器的難點在于，匹配 “或” 邏輯失敗時，調(diào)用棧需要恢復到失敗前的位置，而 JS 引擎中調(diào)用棧不受代碼控制，因此代碼需要在模擬引擎中執(zhí)行。

Parser：語法解析器。

ChainNode：連續(xù)匹配，執(zhí)行鏈四節(jié)點之一。

TreeNode：匹配其一，執(zhí)行鏈四節(jié)點之一。

FunctionNode：函數(shù)節(jié)點，執(zhí)行鏈四節(jié)點之一。

MatchNode：匹配字面量或某一類型的 Token，執(zhí)行鏈四節(jié)點之一。每一次正確的 Match 匹配都會消耗一個 Token。

為什么要重新做一套 JS 執(zhí)行引擎？看下面的代碼：

const main = () =>
  chain(functionA(), tree(functionB1(), functionB2()), functionC());

const functionA = () => chain("a");
const functionB1 = () => chain("b", "x");
const functionB2 = () => chain("b", "y");
const functionC = () => chain("c");

假設(shè) chain("a") 可以匹配 Token a，而 chain(functionC)) 可以匹配到 Token c。

當輸入為 a b y c 時，我們該怎么寫 tree 函數(shù)呢？

我們期望匹配到 functionB1 時失敗，再嘗試 functionB2，直到有一個成功為止。

那么 tree 函數(shù)可能是這樣的：

function tree(...funs) {
  // ... 存儲當前 tokens
  for (const fun of funs) {
    // ... 復位當前 tokens
    const result = fun();
    if (result === true) {
      return result;
    }
  }
}

不斷嘗試 tree 中內(nèi)容，直到能正確匹配結(jié)果后返回這個結(jié)果。由于正確的匹配會消耗 Token，因此需要在執(zhí)行前后存儲當前 Tokens 內(nèi)容，在執(zhí)行失敗時恢復 Token 并嘗試新的執(zhí)行鏈路。

這樣看去很容易，不是嗎？

然而，下面這個例子會打破這個美好的假設(shè)，讓我們稍稍換幾個值吧：

const main = () =>
  chain(functionA(), tree(functionB1(), functionB2()), functionC());

const functionA = () => chain("a");
const functionB1 = () => chain("b", "y");
const functionB2 = () => chain("b");
const functionC = () => chain("y", "c");

輸入仍然是 a b y c，看看會發(fā)生什么？

線路 functionA -> functionB1 是 a b y 很顯然匹配會通過，但連上 functionC 后結(jié)果就是 a b y y c，顯然不符合輸入。

此時正確的線路應該是 functionA -> functionB2 -> functionC，結(jié)果才是 a b y c！

我們看 functionA -> functionB1 -> functionC 鏈路，當執(zhí)行到 functionC 時才發(fā)現(xiàn)匹配錯了，此時想要回到 functionB2 門也沒有！因為 tree(functionB1(), functionB2()) 的執(zhí)行堆棧已退出，再也找不回來了。

所以需要模擬一個執(zhí)行引擎，在遇到分叉路口時，將 functionB2 保存下來，隨時可以回到這個節(jié)點重新執(zhí)行。

用鏈表設(shè)計 Chain 函數(shù)是最佳的選擇，我們要模擬 JS 調(diào)用棧了。

const main = () => chain(functionA, [functionB1, functionB2], functionC)();

const functionA = () => chain("a")();
const functionB1 = () => chain("b", "y")();
const functionB2 = () => chain("b")();
const functionC = () => chain("y", "c")();

上面的例子只改動了一小點，那就是函數(shù)不會立即執(zhí)行。

chain 將函數(shù)轉(zhuǎn)化為 FunctionNode，將字面量 a 或 b 轉(zhuǎn)化為 MatchNode，將 [] 轉(zhuǎn)化為 TreeNode，將自己轉(zhuǎn)化為 ChainNode。

我們就得到了如下的鏈表：

ChainNode(main)
    └── FunctionNode(functionA) ─ TreeNode ─ FunctionNode(functionC)
                                      │── FunctionNode(functionB1)
                                      └── FunctionNode(functionB2)

至于為什么 FunctionNode 不直接展開成 MatchNode，請思考這樣的描述：const list = () => chain(",", list)。直接展開則陷入遞歸死循環(huán)，實際上 Tokens 數(shù)量總有限，用到再展開總能匹配盡 Token，而不會無限展開下去。

那么需要一個函數(shù)，將 chain 函數(shù)接收的不同參數(shù)轉(zhuǎn)化為對應 Node 節(jié)點：

const createNodeByElement = (
  element: IElement,
  parentNode: ParentNode,
  parentIndex: number,
  parser: Parser
): Node => {
  if (element instanceof Array) {
    // ... return TreeNode
  } else if (typeof element === "string") {
    // ... return MatchNode
  } else if (typeof element === "boolean") {
    // ... true 表示一定匹配成功，false 表示一定匹配失敗，均不消耗 Token
  } else if (typeof element === "function") {
    // ... return FunctionNode
  }
};

createNodeByElement 函數(shù)源碼

引擎執(zhí)行其實就是訪問鏈表，通過 visit 函數(shù)是最佳手段。

const visit = tailCallOptimize(
  ({
    node,
    store,
    visiterOption,
    childIndex
  }: {
    node: Node;
    store: VisiterStore;
    visiterOption: VisiterOption;
    childIndex: number;
  }) => {
    if (node instanceof ChainNode) {
      // 調(diào)用 `visitChildNode` 訪問子節(jié)點
    } else if (node instanceof TreeNode) {
      // 調(diào)用 `visitChildNode` 訪問子節(jié)點
      visitChildNode({ node, store, visiterOption, childIndex });
    } else if (node instanceof MatchNode) {
      // 與當前 Token 進行匹配，匹配成功則調(diào)用 `visitNextNodeFromParent` 訪問父級 Node 的下一個節(jié)點，匹配失敗則調(diào)用 `tryChances`，這會在 “或” 邏輯里說明。
    } else if (node instanceof FunctionNode) {
      // 執(zhí)行函數(shù)節(jié)點，并替換掉當前節(jié)點，重新 `visit` 一遍
    }
  }
);

由于 visit 函數(shù)執(zhí)行次數(shù)至多可能幾百萬次，因此使用 tailCallOptimize 進行尾遞歸優(yōu)化，防止內(nèi)存或堆棧溢出。

visit 函數(shù)只負責訪問節(jié)點本身，而 visitChildNode 函數(shù)負責訪問節(jié)點的子節(jié)點（如果有），而 visitNextNodeFromParent 函數(shù)負責在沒有子節(jié)點時，找到父級節(jié)點的下一個子節(jié)點訪問。

function visitChildNode({
  node,
  store,
  visiterOption,
  childIndex
}: {
  node: ParentNode;
  store: VisiterStore;
  visiterOption: VisiterOption;
  childIndex: number;
}) {
  if (node instanceof ChainNode) {
    const child = node.childs[childIndex];
    if (child) {
      // 調(diào)用 `visit` 函數(shù)訪問子節(jié)點 `child`
    } else {
      // 如果沒有子節(jié)點，就調(diào)用 `visitNextNodeFromParent` 往上找了
    }
  } else {
    // 對于 TreeNode，如果不是訪問到了最后一個節(jié)點，則添加一次 “存檔”
    // 調(diào)用 `addChances`
    // 同時如果有子元素，`visit` 這個子元素
  }
}

const visitNextNodeFromParent = tailCallOptimize(
  (
    node: Node,
    store: VisiterStore,
    visiterOption: VisiterOption,
    astValue: any
  ) => {
    if (!node.parentNode) {
      // 找父節(jié)點的函數(shù)沒有父級時，下面再介紹，記住這個位置叫 END 位。
    }

    if (node.parentNode instanceof ChainNode) {
      // A       B <- next node      C
      // └── node <- current node
      // 正如圖所示，找到 nextNode 節(jié)點調(diào)用 `visit`
    } else if (node.parentNode instanceof TreeNode) {
      // TreeNode 節(jié)點直接利用 `visitNextNodeFromParent` 跳過。因為同一時間 TreeNode 節(jié)點只有一個分支生效，所以它沒有子元素了
    }
  }
);

可以看到 visitChildNode 與 visitNextNodeFromParent 函數(shù)都只處理好了自己的事情，而將其他工作交給別的函數(shù)完成，這樣函數(shù)間職責分明，代碼也更易懂。

有了 vist visitChildNode 與 visitNextNodeFromParent，就完成了節(jié)點的訪問、子節(jié)點的訪問、以及當沒有子節(jié)點時，追溯到上層節(jié)點的訪問。

visit 函數(shù)源碼

當 visitNextNodeFromParent 函數(shù)訪問到 END 位 時，是時候做一個了結(jié)了：

當 Tokens 正好消耗完，完美匹配成功。

Tokens 沒消耗完，匹配失敗。

還有一種失敗情況，是 Chance 用光時，結(jié)合下面的 “或” 邏輯一起說。

“或” 邏輯是重構(gòu) JS 引擎的原因，現(xiàn)在這個問題被很好解決掉了。

const main = () => chain(functionA, [functionB1, functionB2], functionC)();

比如上面的代碼，當遇到 [] 數(shù)組結(jié)構(gòu)時，被認為是 “或” 邏輯，子元素存儲在 TreeNode 節(jié)點中。

在 visitChildNode 函數(shù)中，與 ChainNode 不同之處在于，訪問 TreeNode 子節(jié)點時，還會調(diào)用 addChances 方法，為下一個子元素存儲執(zhí)行狀態(tài)，以便未來恢復到這個節(jié)點繼續(xù)執(zhí)行。

addChances 維護了一個池子，調(diào)用是先進后出：

function addChances(/* ... */) {
  const chance = {
    node,
    tokenIndex,
    childIndex
  };

  store.restChances.push(chance);
}

與 addChance 相對的就是 tryChance。

下面兩種情況會調(diào)用 tryChances：

MatchNode 匹配失敗。節(jié)點匹配失敗是最常見的失敗情況，但如果 chances 池還有存檔，就可以恢復過去繼續(xù)嘗試。

沒有下一個節(jié)點了，但 Tokens 還沒消耗完，也說明匹配失敗了，此時調(diào)用 tryChances 繼續(xù)嘗試。

我們看看神奇的存檔回復函數(shù) tryChances 是如何做的：

function tryChances(
  node: Node,
  store: VisiterStore,
  visiterOption: VisiterOption
) {
  if (store.restChances.length === 0) {
    // 直接失敗
  }

  const nextChance = store.restChances.pop();

  // reset scanner index
  store.scanner.setIndex(nextChance.tokenIndex);

  visit({
    node: nextChance.node,
    store,
    visiterOption,
    childIndex: nextChance.childIndex
  });
}

tryChances 其實很簡單，除了沒有 chances 就失敗外，找到最近的一個 chance 節(jié)點，恢復 Token 指針位置并 visit 這個節(jié)點就等價于讀檔。

addChance 源碼

tryChances 源碼

這三個方法實現(xiàn)的也很精妙。

先看可選函數(shù) optional:

export const optional = (...elements: IElements) => {
  return chain([chain(...elements)(/**/)), true])(/**/);
};

可以看到，可選參數(shù)實際上就是一個 TreeNode，也就是：

chain(optional("a"))();
// 等價于
chain(["a", true])();

為什么呢？因為當 "a" 匹配失敗后，true 是一個不消耗 Token 一定成功的匹配，整體來看就是 “可選” 的意思。

進一步解釋下，如果 "a" 沒有匹配上，則 true 一定能匹配上，匹配 true 等于什么都沒匹配，就等同于這個表達式不存在。

再看匹配一或多個的函數(shù) plus：

export const plus = (...elements: IElements) => {
  const plusFunction = () =>
    chain(chain(...elements)(/**/), optional(plusFunction))(/**/);
  return plusFunction;
};

能看出來嗎？plus 函數(shù)等價于一個新遞歸函數(shù)。也就是：

const aPlus = () => chain(plus("a"))();
// 等價于
const aPlus = () => chain(plusFunc)();
const plusFunc = () => chain("a", optional(plusFunc))();

通過不斷遞歸自身的方式匹配到盡可能多的元素，而每一層的 optional 保證了任意一層匹配失敗后可以及時跳到下一個文法，不會失敗。

最后看匹配多個的函數(shù) many：

export const many = (...elements: IElements) => {
  return optional(plus(...elements));
};

many 就是 optional 的 plus，不是嗎？

這三個神奇的函數(shù)都利用了已有功能實現(xiàn)，建議每個函數(shù)留一分鐘左右時間思考為什么。

optional plus many 函數(shù)源碼

錯誤提示與輸入推薦類似，都是給出錯誤位置或光標位置后期待的輸入。

輸入推薦，就是給定字符串與光標位置，給出光標后期待內(nèi)容的功能。

首先通過光標位置找到光標的 上一個 Token，再通過 findNextMatchNodes 找到這個 Token 后所有可能匹配到的 MatchNode，這就是推薦結(jié)果。

那么如何實現(xiàn) findNextMatchNodes 呢？看下面：

function findNextMatchNodes(node: Node, parser: Parser): MatchNode[] {
  const nextMatchNodes: MatchNode[] = [];

  let passCurrentNode = false;

  const visiterOption: VisiterOption = {
    onMatchNode: (matchNode, store, currentVisiterOption) => {
      if (matchNode === node && passCurrentNode === false) {
        passCurrentNode = true;
        // 調(diào)用 visitNextNodeFromParent，忽略自身
      } else {
        // 遍歷到的 MatchNode
        nextMatchNodes.push(matchNode);
      }

      // 這個是畫龍點睛的一筆，所有推薦都當作匹配失敗，通過 tryChances 可以找到所有可能的 MatchNode
      tryChances(matchNode, store, currentVisiterOption);
    }
  };

  newVisit({ node, scanner: new Scanner([]), visiterOption, parser });

  return nextMatchNodes;
}

所謂找到后續(xù)節(jié)點，就是通過 Visit 找到所有的 MatchNode，而 MatchNode 只要匹配一次即可，因為我們只要找到第一層級的 MatchNode。

通過每次匹配后執(zhí)行 tryChances，就可以找到所有 MatchNode 節(jié)點了！

再看錯誤提示，我們要記錄最后出錯的位置，再采用輸入推薦即可。

但光標所在的位置是期望輸入點，這個輸入點也應該參與語法樹的生成，而錯誤提示不包含光標，所以我們要 執(zhí)行兩次 visit。

舉個例子：

select | from b;

| 是光標位置，此時語句內(nèi)容是 select from b; 顯然是錯誤的，但光標位置應該給出提示，給出提示就需要正確解析語法樹，所以對于提示功能，我們需要將光標位置考慮進去一起解析。因此一共有兩次解析。

findNextMatchNodes 函數(shù)源碼

構(gòu)建 First 集是個自下而上的過程，當訪問到 MatchNode 節(jié)點時，其值就是其父節(jié)點的一個 First 值，當父節(jié)點的 First 集收集完畢后，，就會觸發(fā)它的父節(jié)點 First 集收集判斷，如此遞歸，最后完成 First 集收集的是最頂級節(jié)點。

篇幅原因，不再贅述，可以看 這張圖。

generateFirstSet 函數(shù)源碼

這篇文章是對 《手寫 SQL 編譯器》 系列的總結(jié)，從源碼角度的總結(jié)！

該系列的每篇文章都以圖文的方式介紹了各技術(shù)細節(jié)，可以作為補充閱讀：

精讀《手寫 SQL 編譯器 - 詞法分析》

精讀《手寫 SQL 編譯器 - 文法介紹》

精讀《手寫 SQL 編譯器 - 語法分析》

精讀《手寫 SQL 編譯器 - 回溯》

精讀《手寫 SQL 編譯器 - 語法樹》

精讀《手寫 SQL 編譯器 - 錯誤提示》

精讀《手寫 SQL 編譯器 - 性能優(yōu)化之緩存》

精讀《手寫 SQL 編譯器 - 智能提示》

討論地址是：精讀《syntax-parser 源碼》 · Issue #133 · dt-fe/weekly

如果你想?yún)⑴c討論，請點擊這里，每周都有新的主題，周末或周一發(fā)布。前端精讀 - 幫你篩選靠譜的內(nèi)容。