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

1 引言

重回 “手写 SQL 编辑器” 系列。之前几期介绍了词法、文法、语法的解析，以及回溯功能的实现，这次介绍如何生成语法树。

基于一文介绍的思路，我们利用 JS 实现一个微型 SQL 解析器，并介绍如何生成语法树，如何在 JS SQL 引擎实现语法树生成功能！

解析目标是：

select name, version from my_table;复制代码

文法：

const root = () => chain(selectStatement, many(";", selectStatement));const selectStatement = () => chain("select", selectList, fromClause);const selectList = () => chain(matchWord, many(",", matchWord));const fromClause = () => chain("from", matchWord);const statement = () =>  chain(    "select",    selectList,    "from",    chain(tableName, [whereStatement, limitStatement])  );复制代码

这是本文为了方便说明，实现的一个精简版本。完整版见我们的开源仓库。

root 是入口函数，many() 包裹的文法可以执行任意次，所以

chain(selectStatement, many(";", selectStatement));复制代码

表示允许任意长度的 selectStatement 由 ; 号连接，selectList 的写法也同理。

matchWord 表示匹配任意单词。

语法树是人为对语法结构的抽象，本质上，如果我们到此为止，是可以生成一个 基本语法树 的，这个语法树是多维数组，比如：

const fromClause = () => chain("from", matchWord);复制代码

这个文法生成的默认语法树是：['from', 'my_table']，只不过 from my_table 具体是何含义，只有当前文法知道（第一个标志无含义，第二个标志表示表名）。

fromClause 返回的语法树作为结果被传递到文法 selectStatement 中，其结果可能是：['select', [['name', 'version']], ['from', 'my_table']]。

大家不难看出问题：当默认语法树聚集在一起，就无法脱离文法结构单独理解语法含义了，为了脱离文法结构理解语法树，我们需要将其抽象为一个有规可循的结构。

2 精读

通过上面的分析，我们需要对 chain 函数提供修改局部 AST 结构的能力：

const selectStatement = () =>  chain("select", selectList, fromClause)(ast => ({    type: "statement",    variant: "select",    result: ast[1],    from: ast[2]  }));复制代码

我们可以通过额外参数对默认语法树进行改造，将多维数组结构改变为对象结构，并增加 type variant 属性标示当前对象的类型、子类型。比如上面的例子，返回的对象告诉使用者：“我是一个表达式，一个 select 表达式，我的结果是 result，我的来源表是 from”。

那么，chain 函数如何实现语法树功能呢？

对于每个文法（每个 chain 函数），其语法树必须等待所有子元素执行完，才能生成。所以这是个深度优先的运行过程。

下图描述了 chain 函数执行机制：

生成结构中有四个基本结构，分别是 Chain、Tree、Function、Match，足以表达语法解析需要的所有逻辑。（不包含可选、多选逻辑）。

每个元素的子节点全部执行完毕，才会生成当前节点的语法树。实际上，每个节点执行完，都会调用 callParentNode 访问父节点，执行到了这个函数，说明子元素已成功执行完毕，补全对应节点的 AST 信息即可。

对于修改局部 AST 结构函数，需等待整个 ChainNode 执行完毕才调用，并将返回的新 AST 信息存储下来，作为这个节点的最终 AST 信息并传递给父级（或者没有父级，这就是根结点的 AST 结果）。

3 总结

本文介绍了如何生成语法树，并说明了 默认语法树 的存在，以及我们之所以要一个定制的语法树，是为了更方便的理解含义。

同时介绍了如何通过 JS 运行一套完整的语法解析器，以及如何提供自定义 AST 结构的能力。

本文介绍的模型，只是为了便于理解而定制的简化版，了解全部细节，请访问。

最后说一下为何要做这个语法解析器。如今有许多开源的 AST 解析工具，但笔者要解决的场景是语法自动提示，需要在语句不完整，甚至错误的情况，给出当前光标位置的所有可能输入。所以通过完整重写语法解析器内核，在解析的同时，生成语法树的同时，也给出光标位置下一个可能输入提示，在通用错误场景自动从错误中恢复。

目前在做性能优化，通用 SQL 文法还在陆续完善中，目前仅可当学习参考，不要用于生产环境。

4 更多讨论

讨论地址是：

如果你想参与讨论，请，每周都有新的主题，周末或周一发布。