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

wuyangnju 发布于2019-08-22 18:35 / 1017人阅读

摘要：解析可以分为如下四步词法分析，将字符串拆分成包含关键词识别的字符段。涉及到语意处理就要考虑上下文，而这都不是词法分析阶段要考虑的。更多讨论讨论地址是精读手写编译器词法分析如果你想参与讨论，请点击这里，每周都有新的主题，周末或周一发布。

1 引言

因为工作关系，需要开发支持众多方言的 SQL 编辑器，所以复习了一下编译原理相关知识。

相比编译原理专家，我们只需要了解部分编译原理即可实现 SQL 编辑器，所以这是一篇写给前端的编译原理文章。

解析 SQL 可以分为如下四步：

词法分析，将 SQL 字符串拆分成包含关键词识别的字符段（Tokens）。

语法分析，利用自顶向下或自底向上的算法，将 Tokens 解析为 AST，可以手动，也可以自动。

错误检测、恢复、提示推断，都需要利用语法分析产生的 AST。

语义分析，做完这一步就可以执行 SQL 语句了，不过对前端而言，不需要深入到这一步，可以跳过。

2 精读

词法分析就像刀削面的过程，拿着一段字符串（面条）一端不断下刀，当面条被切完也就完成了词法分析，所以词法分析是字符串 -> 一堆字符段的过程。

流程很简单，难点就在下刀的分寸了，每次砍几厘米呢？

回到词法分析，为了准备切分，我们需要定义 SQL 的 Token 有哪些类型，即 Token 分类。

Token 分类

SQL 的 Token 可以分为如下几类：

注释。

关键字（SELECT、CREATE）。

操作符（+、-、>=）。

开闭合标志（(、CASE）。

占位符（?）。

空格。

引号包裹的文本、数字、字段。

方言语法（${variable}）。

可以看到，在词法分析阶段，我们的 Tokens 不需要关心关键词是什么，只要识别是不是关键词即可，因为关键词的辨认会留到语法分析时处理。涉及到语意处理就要考虑上下文，而这都不是词法分析阶段要考虑的。

同样，操作符、空格、文本、占位符等构成了 SQL 语句的其他部分，最后通过开闭合标志比如左括号和右括号，让 SQL 支持子语句。

再强调一次，虽然 SQL 支持子语句，但并不是放在任何位置都是合理的，其他类型 Token 同理，但是词法分析不需要考虑 Token 是否合理，只要切分即可。

用正则逐段分词

像大多数语言一样，SQL 为了方便人类阅读，采用从左到右的书写方式，因此分词方向也从左到右。

我们为每个 Token 类型写一个函数，比如匹配空格的匹配函数：

function getTokenWhitespace(restStr: string) {
  const matches = restStr.match(/^(s+)/);

  if (matches) {
    return { type, value: matches[1] };
  }
}

restStr 表示掐去头部剩下的 SQL 字符串，所有匹配函数都拿 restStr 进行匹配，已经匹配的不需要再处理。

通过正则 /^(s+)/ 匹配到第一个以空格开头的空格（读起来有点别扭），匹配时必须保证以你要匹配的内容开头，而且只匹配一次，这样才不会在切词时发生遗漏。

同理匹配 /**/ 类型注释时，也能通过正则轻而易举的实现：

function getTokenBlockComment(restStr: string) {
  const matches = restStr.match(/^(/*[^]*?(?:*/|$))/);

  if (matches) {
    return { type, value: matches[1] };
  }
}

其中 (?:*/) 表示匹配到以 */ 结尾处，而 (?:*/|$) 后面的 |$ 表示或者直接匹配到结尾（如果一直没有遇到 */ 那后面全部当作注释）。

所以只要 Token 分类得当，并且能为每一个分类写一个头匹配正则，分词功能就实现了 90%。

方言拓展

为了支持某些方言，需要从分词时就开始做考虑。比如 ${variable} 作为一种变量用法时，我们需要在普通字段的正则匹配中，加入一项 ${[a-zA-Z0-9]+} 匹配。

如果要支持纯中文作为字段，可以再补充 |u4e00-u9fa5。

分词主流程

有了一个个分词函数，再补充一个不断匹配、切割字符串、再匹配的主函数即可，这一步更简单：

while (sqlStr) {
  token =
    getTokenWhitespace(sqlStr, token) | getTokenBlockComment(sqlStr, token);

  sqlStr = sqlStr.substring(token.value.length);

  tokens.push(token);
}

上面的函数每取一次 Token，都将取到的 Token 长度丢掉，继续匹配剩下的字符串，直到字符串被切分完为止。

有些特殊情况需要拿到上次的 Token 才能判断下一个 Token 该如何切割，所以将 Token 传给每一个下一步 Match 函数。

最后，执行这个主函数，分词就完成了！

3 总结

分词比较简单，到这里就全部结束了。后面即将进入深水区语法分析，敬请期待。

4 更多讨论

讨论地址是：精读《手写 SQL 编译器 - 词法分析》 · Issue #93 · dt-fe/weekly

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

GPU云服务器云服务器 flex词法分析语言简单词法分析器c语言 sql预编译词法

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

转载请注明本文地址：https://www.ucloud.cn/yun/96025.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 引言文法用来描述语言的语法规则，所以不仅可以用在编程语言上，也可用在汉语、英语上。 2 精读我们将一块语法规则称为产生式，使用 Left → Right 表示任意产生式，用 Left => Right 表示产生式的推导过程，比如对...

TNFE 2019-08-22 18:45 评论0 收藏0