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

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

通過(guò)兩個(gè)例子介紹它的功能。

第一個(gè)例子是創(chuàng)建一個(gè)詞法解析器 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: [/^(+)/]
  }
]);

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

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

接下來(lái)使用 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" 會(huì)按照上面定義的 “三種類型” 被分割為數(shù)組，數(shù)組的每一項(xiàng)都包含了原始值以及其位置。

第二個(gè)例子是創(chuàng)建一個(gè)語(yǔ)法解析器 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ù)書寫文法表達(dá)式：通過(guò)字面量的匹配（比如 + 號(hào)），以及 matchTokenType 來(lái)模糊匹配我們上面詞法解析出的 “三種類型”，就形成了完整的文法表達(dá)式。

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

接下來(lái)使用 myParser：

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

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

按照下面的思路大綱進(jìn)行源碼解讀：

詞法解析

詞匯與概念

分詞器

語(yǔ)法解析

詞匯與概念

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

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

引擎執(zhí)行

何時(shí)算執(zhí)行完

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

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

錯(cuò)誤提示 & 輸入推薦

First 集優(yōu)化

詞法解析有點(diǎn)像 NLP 中分詞，但比分詞簡(jiǎn)單的時(shí)，詞法解析的分詞邏輯是明確的，一般用正則片段表達(dá)。

Lexer：詞法解析器。

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

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

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

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

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

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

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

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

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

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

Parser：語(yǔ)法解析器。

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

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

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

MatchNode：匹配字面量或某一類型的 Token，執(zhí)行鏈四節(jié)點(diǎn)之一。每一次正確的 Match 匹配都會(huì)消耗一個(gè) 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。

當(dāng)輸入為 a b y c 時(shí)，我們?cè)撛趺磳?tree 函數(shù)呢？

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

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

function tree(...funs) {
  // ... 存儲(chǔ)當(dāng)前 tokens
  for (const fun of funs) {
    // ... 復(fù)位當(dāng)前 tokens
    const result = fun();
    if (result === true) {
      return result;
    }
  }
}

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

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

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

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，看看會(huì)發(fā)生什么？

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

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

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

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

用鏈表設(shè)計(jì) 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")();

上面的例子只改動(dòng)了一小點(diǎn)，那就是函數(shù)不會(huì)立即執(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，請(qǐng)思考這樣的描述：const list = () => chain(",", list)。直接展開則陷入遞歸死循環(huán)，實(shí)際上 Tokens 數(shù)量總有限，用到再展開總能匹配盡 Token，而不會(huì)無(wú)限展開下去。

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

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í)行其實(shí)就是訪問(wèn)鏈表，通過(guò) visit 函數(shù)是最佳手段。

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

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

visit 函數(shù)只負(fù)責(zé)訪問(wèn)節(jié)點(diǎn)本身，而 visitChildNode 函數(shù)負(fù)責(zé)訪問(wèn)節(jié)點(diǎn)的子節(jié)點(diǎn)（如果有），而 visitNextNodeFromParent 函數(shù)負(fù)責(zé)在沒(méi)有子節(jié)點(diǎn)時(shí)，找到父級(jí)節(jié)點(diǎn)的下一個(gè)子節(jié)點(diǎn)訪問(wèn)。

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ù)訪問(wèn)子節(jié)點(diǎn) `child`
    } else {
      // 如果沒(méi)有子節(jié)點(diǎn)，就調(diào)用 `visitNextNodeFromParent` 往上找了
    }
  } else {
    // 對(duì)于 TreeNode，如果不是訪問(wèn)到了最后一個(gè)節(jié)點(diǎn)，則添加一次 “存檔”
    // 調(diào)用 `addChances`
    // 同時(shí)如果有子元素，`visit` 這個(gè)子元素
  }
}

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

    if (node.parentNode instanceof ChainNode) {
      // A       B <- next node      C
      // └── node <- current node
      // 正如圖所示，找到 nextNode 節(jié)點(diǎn)調(diào)用 `visit`
    } else if (node.parentNode instanceof TreeNode) {
      // TreeNode 節(jié)點(diǎn)直接利用 `visitNextNodeFromParent` 跳過(guò)。因?yàn)橥粫r(shí)間 TreeNode 節(jié)點(diǎn)只有一個(gè)分支生效，所以它沒(méi)有子元素了
    }
  }
);

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

有了 vist visitChildNode 與 visitNextNodeFromParent，就完成了節(jié)點(diǎn)的訪問(wèn)、子節(jié)點(diǎn)的訪問(wèn)、以及當(dāng)沒(méi)有子節(jié)點(diǎn)時(shí)，追溯到上層節(jié)點(diǎn)的訪問(wèn)。

visit 函數(shù)源碼

當(dāng) visitNextNodeFromParent 函數(shù)訪問(wèn)到 END 位 時(shí)，是時(shí)候做一個(gè)了結(jié)了：

當(dāng) Tokens 正好消耗完，完美匹配成功。

Tokens 沒(méi)消耗完，匹配失敗。

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

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

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

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

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

addChances 維護(hù)了一個(gè)池子，調(diào)用是先進(jìn)后出：

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

  store.restChances.push(chance);
}

與 addChance 相對(duì)的就是 tryChance。

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

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

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

我們看看神奇的存檔回復(fù)函數(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 其實(shí)很簡(jiǎn)單，除了沒(méi)有 chances 就失敗外，找到最近的一個(gè) chance 節(jié)點(diǎn)，恢復(fù) Token 指針位置并 visit 這個(gè)節(jié)點(diǎn)就等價(jià)于讀檔。

addChance 源碼

tryChances 源碼

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

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

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

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

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

為什么呢？因?yàn)楫?dāng) "a" 匹配失敗后，true 是一個(gè)不消耗 Token 一定成功的匹配，整體來(lái)看就是 “可選” 的意思。

進(jìn)一步解釋下，如果 "a" 沒(méi)有匹配上，則 true 一定能匹配上，匹配 true 等于什么都沒(méi)匹配，就等同于這個(gè)表達(dá)式不存在。

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

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

能看出來(lái)嗎？plus 函數(shù)等價(jià)于一個(gè)新遞歸函數(shù)。也就是：

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

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

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

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

many 就是 optional 的 plus，不是嗎？

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

optional plus many 函數(shù)源碼

錯(cuò)誤提示與輸入推薦類似，都是給出錯(cuò)誤位置或光標(biāo)位置后期待的輸入。

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

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

那么如何實(shí)現(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);
      }

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

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

  return nextMatchNodes;
}

所謂找到后續(xù)節(jié)點(diǎn)，就是通過(guò) Visit 找到所有的 MatchNode，而 MatchNode 只要匹配一次即可，因?yàn)槲覀冎灰业降谝粚蛹?jí)的 MatchNode。

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

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

但光標(biāo)所在的位置是期望輸入點(diǎn)，這個(gè)輸入點(diǎn)也應(yīng)該參與語(yǔ)法樹的生成，而錯(cuò)誤提示不包含光標(biāo)，所以我們要 執(zhí)行兩次 visit。

舉個(gè)例子：

select | from b;

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

findNextMatchNodes 函數(shù)源碼

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

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

generateFirstSet 函數(shù)源碼

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

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

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

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

精讀《手寫 SQL 編譯器 - 語(yǔ)法分析》

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

精讀《手寫 SQL 編譯器 - 語(yǔ)法樹》

精讀《手寫 SQL 編譯器 - 錯(cuò)誤提示》

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

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

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

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