深入浅出 MatrixOne Parser
作者:林俊洪 MO 研发工程师
▌Part 1 - 概述
数据库内核博大精深,但执行 SQL 的流程大同小异。
数据库内核可以拆分为:
接收 client 发送过来的网络包
处理网络包,将 SQL 解析成抽象语法树
将语法树转换和优化成查询计划
通过查询计划生成执行计划,并执行返回结果
为什么说是博大精深呢?因为每个部分都有拿出来讨论和研究的价值,各个厂家的数据库实现方式和细节也是花样百出。本文将主要讨论 SQL 是如果被解析成抽象语法树的。简单来说,就是如何将 SQL 字符串如果解析成相应数据库语言的结构体。
▌Part 2 - 词法分析
将 SQL 解析成语法树,首先需要进行词法分析。词法分析的过程简而言之是将 SQL 字符串拆解成若干个 token。例如, select a from t 我们可以将其拆解成 select、a、from、t 这几个 token。而这些 token 可以作为语法分析的输入。
>>> DFA
MatrixOne 的 Lexer (词法分析器) 是手动编写的,相比于通过工具,比如 Lex ,生成 Lexer,更加灵活,方便 MatrixOne parser 兼容 MySQL 语法。对于手动编写 Lexer,可以从有穷自动机说起。
有穷自动机(Finite Automata, FA)由两位神经物理学家 MeCuloch 和 Pitts 在 1948 年首先提出,是对一类处理系统建立的数学模型。简单的定义是:给定输入串 x,如果存在一个对应于 x 的从初始状态到某个终止状态的转换序列,则称 x 被改 FA 接收。
首先,要识别一个 token,可以通过正则匹配,例如整数的正则定义:
实现正则匹配,可以通过 FA ,举个例子,比如我们要识别正则文法 r = (a | b) * abb,状态转换图如下:
如此,当状态到达终止状态 3 时,识别成功。仔细观察可以发现一个问题,在 0 状态时,接收 a ,可以从 0 到 0 或者从 0 到 1,这种不确定性无法编程。称之为非确定的有穷状态机(NFA)。
给出一个结论,对任何 NFA,存在定义同一语言的确定的有穷自动机(DFA)。可以通过子集构造法将 NFA 转换成 DFA。
对于上述的例子,将 NFA 转换成 DFA 后的状态图如下:
从上图可以看出无论在哪一个状态接收 a 或 b,到达的下一个状态时确定的。
这样,通过对不同类型的 token 作出状态图,再将其整合,一个简单识别 token DFA 如下:
对于 MySQL 的不同 token,比如 数字, 字符串,标识符,数学符号,注释等等,可以参照其定义,写出相应的 DFA,最终形成 Lexer。感兴趣的同学可以看看 MatrixOne 的 Lexer,实现在 scanner.go 中,在 mysql_lexer.go 中将其封装了起来。
▌Part 3 - 语法分析
词法分析后 tokens 将作为语法分析的输入。SQL 的语法解析的实现常见有两种方式:
一种是采用 LL 文法,自顶向下的分析。手动编写的 parser 一般会采取这种方式,比如 clickhouse 的 parser、sqlparser-rs。
另一种是采用 LR 文法,自底向上分析。一些工具 bison、goyacc 可以通过预先定义好的 BNF 文件生成语法解析器。
这两种方式有各自的优缺点,理论上性能相差不大。手动编写的语法分析易于调试,代码直观显而易见,但也因其手动编写,开发时间会较长。MatrixOne 的语法分析器使用 goyacc 生成的,目前主要兼容 MySQL 语法。可以通过 MySQL 给出的相关文档,定义出 BNF 文件(.y 文件),生成解析器。当然生成的解析器代码难以阅读调试。
>>>工作过程
goyacc 生成的语法分析器,接受 LALR(1) (lookahead-LR)文法。与 LL 文法不同,接受 LALR(1) 文法的分析器,其语法分析是从分析树的底部向顶部方向构造分析树,对于 LARL(1)
L:对输入进行从左到右的扫描
R:反向构造出一个最右推导序列
1 则是需要向前查看 1 个 token
自底向上的语法分析采用最左规约的方式,通用框架是移入-规约分析(Shift-Reduce Parsing)。
移入-规约分析器可采取的 4 种动作:
移入:将下一个 token 移到栈的顶端
归约:如果栈中的符号串是某个产生式的左端,则归约成右端,被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端,并决定用哪个非终结符来替换这个串
接收:成功完成语法分析过程
错误:发现一个语法错误
移入-规约分析的工作过程:
语法分析器将 0 个或多个输入 token 移入栈的顶端,直到可以对栈顶的一个文法符号串 β 进行归约为止。
然后,β 归约为某个产生式的左部
语法分析器不断地重复这个循环,直到检测到一个语法错误,或者栈中包含了开始符号且输入缓冲区为空(语法分析成功)为止。
举个例子,分析如下表达式 E 语法时:
可以定义出如下产生式,其中表达式 E 是非终结符,id、+、-、(, ) 是终结符:
通过移入-规约分析,可以得出表达式语法正确:
>>>冲突
如果某些输入字符串可以按两种或以上的方式来构造,那么可以说这组文法存在二义性。还是看上文所说到的一个例子,对于产生式
是表达算数表达式的一种自然的方式。但这种递归定义的方式并没有完全规定所有复杂输入的情况,比如,输入是:
如果是左结合,则被构造为:
如果是右结合,则被构造为:
语法分析器遇到这种情况是能检测到歧义的,当语法分析器读到 b 时,栈中可见的输入是:
匹配上述文法规则的右端,进行归约操作。在应用则个规则后,栈中输入被规约成 E,语法分析器接着可以读取后续部分:
并再次归约,产生左结合。但语法分析器可以选择 lookahead 1,直到读完:
然后对 b + c 进行归约,变成
最后再次归约,产生右结合。实际上,语法分析器在遇到 b 时,可以选择移进或者归约,无法选择时,产生移进/归约冲突。而右结合时,语法分析器选择两个归约动作,产生归约/归约冲突。
实际上,我们可以在 BNF 文件中补充规则。算术表达式中,常用优先级,左或右结合来补充规则,以此来消除掉一些歧义,比如,可以定义:
将加减乘除都定义成左结合,其次在 BNF 文件中,越晚(靠下)定义的 token,优先级越高。显然,乘除的优先级高于加减。
▌Part 4 - MatrixOne Parser
MO Parser 的词法分析是手动编写的,主要的作用就是分词,为语法分析器提供 token。数据库语法分析其实就是生成语法树的过程,也是整个 SQL 解析的重点。在 mysql_sql.y 中定义了 MatrixOne 的语法规则,规则文件的结构如下:
在 select.go 中可以看到简单的 select 的部分定义 SelectClause
当成功解析完 SQL,MO 定义的结构体里的字段都会被相应赋值。比如,解析 SQL
会生成如下语法树:
接着,就可以将语法树转化和优化成逻辑计划。
熟悉了 MO 的语法树后,欢迎大家为 MO Parser 兼容更多的 MySQL 语法。修改了 mysql_sql.y 后,进入到 parsers 目录下执行 make,就会生成新的语法分析器,该文件是 mysql_sql.go。
最后,一个简单的例子,使用 MO Parser 进行 SQL 解析:
可以注意到,Parse 需要传入 dialect.MySQL 参数,这是因为 MO Parser 在开始设计时,就有支持多方言的想法,目前实现了多方言的框架。
矩阵起源全面拥抱开源生态,以开源开放的方式探索数字化道路。矩阵起源有多个行业的数字化转型最佳实践。欢迎扫码加入 MatrixOne 社群参与讨论:
添加 MO 小助手微信 → ID:MatrixOrigin001,加入 MatrixOne 社群参与讨论!
源码:github.com/matrixorigin/matrixone
Slack:matrixoneworkspace.slack.com
知乎 | CSDN | 墨天轮 | OSCHINA | SegmentFault:MatrixOrigin
版权声明: 本文为 InfoQ 作者【MatrixOrigin】的原创文章。
原文链接:【http://xie.infoq.cn/article/d156a2da9b4e453fdac48b667】。文章转载请联系作者。
评论