精读《syntax-parser 源码》

摘要：引言是一个版语法解析器生成器，具有分词语法树解析的能力。实现函数用链表设计函数是最佳的选择，我们要模拟调用栈了。但光标所在的位置是期望输入点，这个输入点也应该参与语法树的生成，而错误提示不包含光标，所以我们要执行两次。

syntax-parser 是一个 JS 版语法解析器生成器，具有分词、语法树解析的能力。

通过两个例子介绍它的功能。

第一个例子是创建一个词法解析器 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: [/^(+)/]
  }
]);

如上，通过正则分别匹配了 “空格”、“字母或数字”、“加号”，并将匹配到的空格忽略（不输出）。

分词匹配是从左到右的，优先匹配数组的第一项，依此类推。

接下来使用 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" 会按照上面定义的 “三种类型” 被分割为数组，数组的每一项都包含了原始值以及其位置。

第二个例子是创建一个语法解析器 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 函数书写文法表达式：通过字面量的匹配（比如 + 号），以及 matchTokenType 来模糊匹配我们上面词法解析出的 “三种类型”，就形成了完整的文法表达式。

syntax-parser 还提供了其他几个有用的函数，比如 many optional 分别表示匹配多次和匹配零或一次。

接下来使用 myParser：

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

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

按照下面的思路大纲进行源码解读：

词法解析

词汇与概念

分词器

语法解析

词汇与概念

重新做一套 “JS 执行引擎”

实现 Chain 函数

引擎执行

何时算执行完

“或” 逻辑的实现

many, optional, plus 的实现

错误提示 & 输入推荐

First 集优化

词法解析有点像 NLP 中分词，但比分词简单的时，词法解析的分词逻辑是明确的，一般用正则片段表达。

Lexer：词法解析器。

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

分词器 createLexer 函数接收的是一个正则数组，因此思路是遍历数组，一段一段匹配字符串。

我们需要这几个函数：

class Tokenizer {
  public tokenize(input: string) {
    // 调用 getNextToken 对输入字符串 input 进行正则匹配，匹配完后 substring 裁剪掉刚才匹配的部分，再重新匹配直到字符串裁剪完
  }

  private getNextToken(input: string) {
    // 调用 getTokenOnFirstMatch 对输入字符串 input 进行遍历正则匹配，一旦有匹配到的结果立即返回
  }

  private getTokenOnFirstMatch({
    input,
    type,
    regex
  }: {
    input: string;
    type: string;
    regex: RegExp;
  }) {
    // 对输入字符串 input 进行正则 regex 的匹配，并返回 Token 对象的基本结构
  }
}

tokenize 是入口函数，循环调用 getNextToken 匹配 Token 并裁剪字符串直到字符串被裁完。

语法解析是基于词法解析的，输入是 Tokens，根据文法规则依次匹配 Token，当 Token 匹配完且完全符合文法规范后，语法树就出来了。

词法解析器生成器就是 “生成词法解析器的工具”，只要输入规定的文法描述，内部引擎会自动做掉其余的事。

这个生成器的难点在于，匹配 “或” 逻辑失败时，调用栈需要恢复到失败前的位置，而 JS 引擎中调用栈不受代码控制，因此代码需要在模拟引擎中执行。

Parser：语法解析器。

ChainNode：连续匹配，执行链四节点之一。

TreeNode：匹配其一，执行链四节点之一。

FunctionNode：函数节点，执行链四节点之一。

MatchNode：匹配字面量或某一类型的 Token，执行链四节点之一。每一次正确的 Match 匹配都会消耗一个 Token。

为什么要重新做一套 JS 执行引擎？看下面的代码：

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

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

当输入为 a b y c 时，我们该怎么写 tree 函数呢？

我们期望匹配到 functionB1 时失败，再尝试 functionB2，直到有一个成功为止。

那么 tree 函数可能是这样的：

function tree(...funs) {
  // ... 存储当前 tokens
  for (const fun of funs) {
    // ... 复位当前 tokens
    const result = fun();
    if (result === true) {
      return result;
    }
  }
}

不断尝试 tree 中内容，直到能正确匹配结果后返回这个结果。由于正确的匹配会消耗 Token，因此需要在执行前后存储当前 Tokens 内容，在执行失败时恢复 Token 并尝试新的执行链路。

这样看去很容易，不是吗？

然而，下面这个例子会打破这个美好的假设，让我们稍稍换几个值吧：

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，看看会发生什么？

线路 functionA -> functionB1 是 a b y 很显然匹配会通过，但连上 functionC 后结果就是 a b y y c，显然不符合输入。

此时正确的线路应该是 functionA -> functionB2 -> functionC，结果才是 a b y c！

我们看 functionA -> functionB1 -> functionC 链路，当执行到 functionC 时才发现匹配错了，此时想要回到 functionB2 门也没有！因为 tree(functionB1(), functionB2()) 的执行堆栈已退出，再也找不回来了。

所以需要模拟一个执行引擎，在遇到分叉路口时，将 functionB2 保存下来，随时可以回到这个节点重新执行。

用链表设计 Chain 函数是最佳的选择，我们要模拟 JS 调用栈了。

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

上面的例子只改动了一小点，那就是函数不会立即执行。

chain 将函数转化为 FunctionNode，将字面量 a 或 b 转化为 MatchNode，将 [] 转化为 TreeNode，将自己转化为 ChainNode。

我们就得到了如下的链表：

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

至于为什么 FunctionNode 不直接展开成 MatchNode，请思考这样的描述：const list = () => chain(",", list)。直接展开则陷入递归死循环，实际上 Tokens 数量总有限，用到再展开总能匹配尽 Token，而不会无限展开下去。

那么需要一个函数，将 chain 函数接收的不同参数转化为对应 Node 节点：

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 函数源码

引擎执行其实就是访问链表，通过 visit 函数是最佳手段。

const visit = tailCallOptimize(
  ({
    node,
    store,
    visiterOption,
    childIndex
  }: {
    node: Node;
    store: VisiterStore;
    visiterOption: VisiterOption;
    childIndex: number;
  }) => {
    if (node instanceof ChainNode) {
      // 调用 `visitChildNode` 访问子节点
    } else if (node instanceof TreeNode) {
      // 调用 `visitChildNode` 访问子节点
      visitChildNode({ node, store, visiterOption, childIndex });
    } else if (node instanceof MatchNode) {
      // 与当前 Token 进行匹配，匹配成功则调用 `visitNextNodeFromParent` 访问父级 Node 的下一个节点，匹配失败则调用 `tryChances`，这会在 “或” 逻辑里说明。
    } else if (node instanceof FunctionNode) {
      // 执行函数节点，并替换掉当前节点，重新 `visit` 一遍
    }
  }
);

由于 visit 函数执行次数至多可能几百万次，因此使用 tailCallOptimize 进行尾递归优化，防止内存或堆栈溢出。

visit 函数只负责访问节点本身，而 visitChildNode 函数负责访问节点的子节点（如果有），而 visitNextNodeFromParent 函数负责在没有子节点时，找到父级节点的下一个子节点访问。

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) {
      // 调用 `visit` 函数访问子节点 `child`
    } else {
      // 如果没有子节点，就调用 `visitNextNodeFromParent` 往上找了
    }
  } else {
    // 对于 TreeNode，如果不是访问到了最后一个节点，则添加一次 “存档”
    // 调用 `addChances`
    // 同时如果有子元素，`visit` 这个子元素
  }
}

const visitNextNodeFromParent = tailCallOptimize(
  (
    node: Node,
    store: VisiterStore,
    visiterOption: VisiterOption,
    astValue: any
  ) => {
    if (!node.parentNode) {
      // 找父节点的函数没有父级时，下面再介绍，记住这个位置叫 END 位。
    }

    if (node.parentNode instanceof ChainNode) {
      // A       B <- next node      C
      // └── node <- current node
      // 正如图所示，找到 nextNode 节点调用 `visit`
    } else if (node.parentNode instanceof TreeNode) {
      // TreeNode 节点直接利用 `visitNextNodeFromParent` 跳过。因为同一时间 TreeNode 节点只有一个分支生效，所以它没有子元素了
    }
  }
);

可以看到 visitChildNode 与 visitNextNodeFromParent 函数都只处理好了自己的事情，而将其他工作交给别的函数完成，这样函数间职责分明，代码也更易懂。

有了 vist visitChildNode 与 visitNextNodeFromParent，就完成了节点的访问、子节点的访问、以及当没有子节点时，追溯到上层节点的访问。

visit 函数源码

当 visitNextNodeFromParent 函数访问到 END 位 时，是时候做一个了结了：

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

Tokens 没消耗完，匹配失败。

还有一种失败情况，是 Chance 用光时，结合下面的 “或” 逻辑一起说。

“或” 逻辑是重构 JS 引擎的原因，现在这个问题被很好解决掉了。

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

比如上面的代码，当遇到 [] 数组结构时，被认为是 “或” 逻辑，子元素存储在 TreeNode 节点中。

在 visitChildNode 函数中，与 ChainNode 不同之处在于，访问 TreeNode 子节点时，还会调用 addChances 方法，为下一个子元素存储执行状态，以便未来恢复到这个节点继续执行。

addChances 维护了一个池子，调用是先进后出：

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

  store.restChances.push(chance);
}

与 addChance 相对的就是 tryChance。

下面两种情况会调用 tryChances：

MatchNode 匹配失败。节点匹配失败是最常见的失败情况，但如果 chances 池还有存档，就可以恢复过去继续尝试。

没有下一个节点了，但 Tokens 还没消耗完，也说明匹配失败了，此时调用 tryChances 继续尝试。

我们看看神奇的存档回复函数 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 节点，恢复 Token 指针位置并 visit 这个节点就等价于读档。

addChance 源码

tryChances 源码

这三个方法实现的也很精妙。

先看可选函数 optional:

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

可以看到，可选参数实际上就是一个 TreeNode，也就是：

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

为什么呢？因为当 "a" 匹配失败后，true 是一个不消耗 Token 一定成功的匹配，整体来看就是 “可选” 的意思。

进一步解释下，如果 "a" 没有匹配上，则 true 一定能匹配上，匹配 true 等于什么都没匹配，就等同于这个表达式不存在。

再看匹配一或多个的函数 plus：

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

能看出来吗？plus 函数等价于一个新递归函数。也就是：

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

通过不断递归自身的方式匹配到尽可能多的元素，而每一层的 optional 保证了任意一层匹配失败后可以及时跳到下一个文法，不会失败。

最后看匹配多个的函数 many：

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

many 就是 optional 的 plus，不是吗？

这三个神奇的函数都利用了已有功能实现，建议每个函数留一分钟左右时间思考为什么。

optional plus many 函数源码

错误提示与输入推荐类似，都是给出错误位置或光标位置后期待的输入。

输入推荐，就是给定字符串与光标位置，给出光标后期待内容的功能。

首先通过光标位置找到光标的 上一个 Token，再通过 findNextMatchNodes 找到这个 Token 后所有可能匹配到的 MatchNode，这就是推荐结果。

那么如何实现 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;
        // 调用 visitNextNodeFromParent，忽略自身
      } else {
        // 遍历到的 MatchNode
        nextMatchNodes.push(matchNode);
      }

      // 这个是画龙点睛的一笔，所有推荐都当作匹配失败，通过 tryChances 可以找到所有可能的 MatchNode
      tryChances(matchNode, store, currentVisiterOption);
    }
  };

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

  return nextMatchNodes;
}

所谓找到后续节点，就是通过 Visit 找到所有的 MatchNode，而 MatchNode 只要匹配一次即可，因为我们只要找到第一层级的 MatchNode。

通过每次匹配后执行 tryChances，就可以找到所有 MatchNode 节点了！

再看错误提示，我们要记录最后出错的位置，再采用输入推荐即可。

但光标所在的位置是期望输入点，这个输入点也应该参与语法树的生成，而错误提示不包含光标，所以我们要 执行两次 visit。

举个例子：

select | from b;

| 是光标位置，此时语句内容是 select from b; 显然是错误的，但光标位置应该给出提示，给出提示就需要正确解析语法树，所以对于提示功能，我们需要将光标位置考虑进去一起解析。因此一共有两次解析。

findNextMatchNodes 函数源码

构建 First 集是个自下而上的过程，当访问到 MatchNode 节点时，其值就是其父节点的一个 First 值，当父节点的 First 集收集完毕后，，就会触发它的父节点 First 集收集判断，如此递归，最后完成 First 集收集的是最顶级节点。

篇幅原因，不再赘述，可以看 这张图。

generateFirstSet 函数源码

这篇文章是对 《手写 SQL 编译器》 系列的总结，从源码角度的总结！

该系列的每篇文章都以图文的方式介绍了各技术细节，可以作为补充阅读：

精读《手写 SQL 编译器 - 词法分析》

精读《手写 SQL 编译器 - 文法介绍》

精读《手写 SQL 编译器 - 语法分析》

精读《手写 SQL 编译器 - 回溯》

精读《手写 SQL 编译器 - 语法树》

精读《手写 SQL 编译器 - 错误提示》

精读《手写 SQL 编译器 - 性能优化之缓存》

精读《手写 SQL 编译器 - 智能提示》

讨论地址是：精读《syntax-parser 源码》 · Issue #133 · dt-fe/weekly

如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。前端精读 - 帮你筛选靠谱的内容。