SQL解析器原理及实现剖析

时至7月中旬，江南梅雨季，没想到疫情还在肆虐，再一次被迫居家办公，连续半月的核酸检测仍然没有结束的迹象，热到爆的天气令人烦躁，唯有书写能使人有片刻平静；城市的夜晚，少了闹市的繁华、炎热的天气连虫蛙也懒得鸣叫，唯有空调吹风声与键盘敲击声遥相呼应......

说明：本文偏向go语言的工程实现，理论方面其他文章讲的已经很详尽了，本文只做提及不做过多说明。

相信做开发的同学对数据库sql的执行过程都能说出一二：连接器（协议层）、解析器、优化器、执行计划、执行引擎、存储引擎......

但具体到某个模块时可能就说不清楚了；自己也喜欢各种技术都去蹭蹭，鲜有深入了解，慢慢发现深入了解某个点后才能找到技术的乐趣。今晚我们就一起深入了解下SQL处理过程中的Parser功能。

1.1 词法分析

词法分析主要是把输入转化成若干个tokens，包含key和非key。比如，一个简单的SQL如下所示：

在分析之后，会得到4个Token，其中有2个key，它们分别是SELECT、FROM。

key	非key	key	非key
SELECT	age	FROM	user

1.2 语法分析

语法分析是生成语法树的过程，这是整个解析过程中最核心、最复杂的环节。

例如，如下SQL语句：

解析上述SQL时会生成如下语法数：

1.3 解析工具

有了上述感性的认识后，那么怎么实现这些功能呢？我们需要了解两个工具 Lex & Yacc 。（本文聚焦GO生态，java生态可以看看 Apache Calcite、antlr）

LexpatternspatternstokensYacc

tokensAST

YaccYacc

词法分析器多数数据库（如crdb、tidb）选择自己编写，实现了goyacc要求的接口，这部分一般很少需要修改。

整体流程如下：

对程序员而言，再华丽的词藻不如两行代码来的实惠，下面我们就试着完成一条新增sql语法的解析工作，但从零开始完全实现，难度还是相当大，日常工作中一般也不会这么做、也没机会或足够时间去从零实现，而且价值也不大，因此我们站在开源大神的肩膀上，在框架上能去扩展、使用就显得更加实惠；语言依然使用 GO语言。

CRDB是GO语言生态中对PG语法兼容性较好的数据库，我们使用 postgresql-parser 项目作为基石，postgresql-parser 是从CRDB项目中抠出的parser模块，可以将sql语句转化为AST，具体参见项目介绍。

以parse sql为例，演示如何新加入一种sql语法解析，先看看未添加时解析 “parse sql” 语句的报错信息：

执行报错：

2.1 定义关键字

打开pkg/sql/parser/sql.y文件，搜索 “Ordinary key words”，会看到按照字母排序的一系列关键字定义，由于SQL关键字已经被定义，所以我们只需添加关键字 PARSE

词法分析器可以通过以上定义识别关键字，由于新定义的关键字仍可以用于其他标识符中，因此我们还需要将PARSE添加到unreserved_keyword中，sql.y文件中搜索 "unreserved_keyword:" ,并将PARSE添加进去。

2.2 解析器处理语句

为使解析器可以处理新添加的语句，需要在三个地方添加处理逻辑：类型列表、语句类型列表、解析子句。

在sql.y中搜索 "<tree.Statement>" 并添加新语句类型，如：

接着搜索"stmt:" ，将语句类型添加进去；

最后，为语句添加一个处理规则，sql.y中搜索 "// %Help: PREPARE" 并添加如下规则：

先把处理逻辑省略，直接返回一个未实现错误，具体实现待会再处理，我们先做个测试看解析器是否能够识别新语句；

首先重新生成sql.go文件，即根据定义的 .y 文件生成go文件，这里直接使用项目Makefile定义好的脚本，执行： make generate

检查sql.go文件是否有新定义的语句生成：

再测试下Parse函数执行的结果：

可以看出这次与未添加语句之前的错误有所不同，已经可以识别语句，该错误说明该语句未实现。

注：编译运行过程中可能会遇到一些包引入错误，按照截图添加、删除即可；

2.3 AST

tree.StatementStatementStatementReturnTypeStatementTypeStatementTagNodeFormatterFormat

pkg/sql/sem/tree/parse_sql.go

$$.val

再次 make generate，再次执行 Parse方法，得到结果如下：

至此，我们就完成了一条新sql的语法解析并生成了对应的AST，当然这仅仅是语法解析，真正完成整条SQL的执行链路还有很长的路要走。

3. 总结

首先介绍了SQL Parser中的词法、语法解析器的理论知识及相关工具（Lex&Yacc），然后通过一个PG 解析器的开源项目演示了如何新增SQL语法解析，希望对有需要的小伙伴有所帮助。

最后，愿疫情早日离开神州大地，经济稳步上升，人民生活幸福安康！

参考文献：