精讀《syntax-parser 源碼》

1. 引言

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
//   }
// }]

2. 精讀

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

  • 詞法解析
    • 詞匯與概念
    • 分詞器
  • 語法解析
    • 詞匯與概念
    • 重新做一套 “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，當(dāng) Token 匹配完且完全符合文法規(guī)范后，語法樹就出來了。

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

這個生成器的難點在于，匹配 “或” 邏輯失敗時，調(diào)用棧需要恢復(fù)到失敗前的位置，而 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í)行引擎”

為什么要重新做一套 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 時，我們該怎么寫 tree 函數(shù)呢？

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

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

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

不斷嘗試 tree 中內(nèi)容，直到能正確匹配結(jié)果后返回這個結(jié)果。由于正確的匹配會消耗 Token，因此需要在執(zhí)行前后存儲當(dāng)前 Tokens 內(nèi)容，在執(zhí)行失敗時恢復(fù) 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，顯然不符合輸入。

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

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

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

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

用鏈表設(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)化為對應(yīng) 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í)行

引擎執(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) {
      // 與當(dāng)前 Token 進行匹配，匹配成功則調(diào)用 `visitNextNodeFromParent` 訪問父級 Node 的下一個節(jié)點，匹配失敗則調(diào)用 `tryChances`，這會在 “或” 邏輯里說明。
    } else if (node instanceof FunctionNode) {
      // 執(zhí)行函數(shù)節(jié)點，并替換掉當(dāng)前節(jié)點，重新 `visit` 一遍
    }
  }
);

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

visit 函數(shù)只負責(zé)訪問節(jié)點本身，而 visitChildNode 函數(shù)負責(zé)訪問節(jié)點的子節(jié)點（如果有），而 visitNextNodeFromParent 函數(shù)負責(zé)在沒有子節(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ù)間職責(zé)分明，代碼也更易懂。

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

visit 函數(shù)源碼

何時算執(zhí)行完

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

  • 當(dāng) Tokens 正好消耗完，完美匹配成功。
  • Tokens 沒消耗完，匹配失敗。
  • 還有一種失敗情況，是 Chance 用光時，結(jié)合下面的 “或” 邏輯一起說。

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

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

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

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

在 visitChildNode 函數(shù)中，與 ChainNode 不同之處在于，訪問 TreeNode 子節(jié)點時，還會調(diào)用 addChances 方法，為下一個子元素存儲執(zhí)行狀態(tài)，以便未來恢復(fù)到這個節(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 池還有存檔，就可以恢復(fù)過去繼續(xù)嘗試。
  • 沒有下一個節(jié)點了，但 Tokens 還沒消耗完，也說明匹配失敗了，此時調(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 其實很簡單，除了沒有 chances 就失敗外，找到最近的一個 chance 節(jié)點，恢復(fù) Token 指針位置并 visit 這個節(jié)點就等價于讀檔。

addChance 源碼

tryChances 源碼

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

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

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

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

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

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

為什么呢？因為當(dāng) '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);
      }

      // 這個是畫龍點睛的一筆，所有推薦都當(dāng)作匹配失敗，通過 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é)點了！

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

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

舉個例子：

select | from b;

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

findNextMatchNodes 函數(shù)源碼

First 集優(yōu)化

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

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

generateFirstSet 函數(shù)源碼

3. 總結(jié)

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

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

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

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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容