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

Caicloud 发布于2019-08-23 11:31 / 2418人阅读

摘要：返回的语法树作为结果被传递到文法中，其结果可能是。每个元素的子节点全部执行完毕，才会生成当前节点的语法树。更多讨论讨论地址是精读手写编译器语法树如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。

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

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

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 结构的能力。

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

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

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

4 更多讨论

讨论地址是：精读《手写 SQL 编译器 - 语法树》 · Issue #99 · dt-fe/weekly

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97073.html

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

摘要：经过连续几期的介绍，手写编译器系列进入了智能提示模块，前几期从词法到文法语法，再到构造语法树，错误提示等等，都是为智能提示做准备。 1 引言词法、语法、语义分析概念都属于编译原理的前端领域，而这次的目的是做具备完善语法提示的 SQL 编辑器，只需用到编译原理的前端部分。经过连续几期的介绍，《手写 SQL 编译器》系列进入了智能提示模块，前几期从词法到文法、语法，再到构造语法...

ztyzz 2019-08-23 14:15 评论0 收藏0
精读《syntax-parser 源码》

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

yuanxin 2019-08-23 15:37 评论0 收藏0
精读《手写 SQL 编译器 - 错误提示》

摘要：总结做语法解析器错误提示功能时，再次刷新了笔者三观，原来我们以为的必然，在编译器里对应着那么多可能。语法解析器为了让报错符合人们的第一直觉，对错误信息做了过滤，只保留剩余数最短的那条错误信息。 1 引言 showImg(https://segmentfault.com/img/remote/1460000016244315?w=1522&h=272); 编译器除了生成语法树之外，还要在...

王陆宽 2019-08-23 11:41 评论0 收藏0