深入浅出MatrixOne Parser

原创林俊洪MatrixOrigin服务号2022-09-16 17:00

作者：林俊洪 MO研发工程师

1. 概述

2. 词法分析

3. 语法分析

工作过程
冲突

4. MatrixOne Parser

本文字数：3000字+

阅读时间：10分钟+

Part 1

概述

数据库内核博大精深，但执行 SQL 的流程大同小异。

数据库内核可以拆分为：

接收client发送过来的网络包。
处理网络包，将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，可以通过正则匹配，例如整数的正则定义：

 digit : 0|1|2|...|9 integer : digit digit*

实现正则匹配，可以通过 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) 文法的分析器，其语法分析是从分析树的底部向顶部方向构造分析树，对于LALR(1)

L：对输入进行从左到右的扫描
R：反向构造出一个最右推导序列
1则是需要向前查看1个 token

自底向上的语法分析采用最左规约的方式，通用框架是移入-规约分析（Shift-Reduce Parsing）。

移入-规约分析器可采取的4种动作：

移入：将下一个 token 移到栈的顶端
归约：如果栈中的符号串是某个产生式的左端，则归约成右端，被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
接收：成功完成语法分析过程
错误：发现一个语法错误

移入-规约分析的工作过程：

语法分析器将0个或多个输入token移入栈的顶端，直到可以对栈顶的一个文法符号串β进行归约为止。
然后，β归约为某个产生式的左部。
语法分析器不断地重复这个循环，直到检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空（语法分析成功）为止。

举个例子，分析如下表达式E语法时：

id + (id + id)

可以定义出如下产生式，其中表达式 E 是非终结符，id、+、-、(, ) 是终结符：

E : E + EE : E * EE : (E)E : id

通过移入-规约分析，可以得出表达式语法正确：

>>> 冲突

如果某些输入字符串可以按两种或以上的方式来构造，那么可以说这组文法存在二义性。还是看上文所说到的一个例子，对于产生式

E : E + E

是表达算数表达式的一种自然的方式。但这种递归定义的方式并没有完全规定所有复杂输入的情况，比如，输入是：

a + b + c

如果是左结合，则被构造为：

(a + b) + c

如果是右结合，则被构造为：

a + (b + c)

语法分析器遇到这种情况是能检测到歧义的，当语法分析器读到b时，栈中可见的输入是：

a + b

匹配上述文法规则的右端，进行归约操作。在应用则个规则后，栈中输入被规约成E，语法分析器接着可以读取后续部分:

+ c

并再次归约，产生左结合。但语法分析器可以选择 lookahead 1，直到读完：

a + b + c

然后对 b + c 进行归约，变成

a + E

最后再次归约，产生右结合。实际上，语法分析器在遇到b时，可以选择移进或者归约，无法选择时，产生移进/归约冲突。而右结合时，语法分析器选择两个归约动作，产生归约/归约冲突。

实际上，我们可以在BNF文件中补充规则。算术表达式中，常用优先级，左或右结合来补充规则，以此来消除掉一些歧义，比如，可以定义：

%left '+' '-'%left '*' '/'

将加减乘除都定义成左结合，其次在BNF文件中，越晚（靠下）定义的token，优先级越高。显然，乘除的优先级高于加减。

Part 4

MatrixOne Parser

MatrixOne Parser（以下简称“MO Parser”）的词法分析是手动编写的，主要的作用就是分词，为语法分析器提供token。数据库语法分析其实就是生成语法树的过程，也是整个SQL解析的重点。mysql_sql.y中定义了MO的语法规则，规则文件的结构如下：

%{// 在这里可以引入包名，在解析的过程中就可以调用到相应的函数}%
%struct {  id int // token id  str string // token 字符串  item interface{} // 将 token 转化为实际的类型，比如 1 会转化成 int64 类型}
%union {// 在这里定义 mo 设计好的语法树结构，比如  selectStatement tree.SelectStatement}
// 这里定义一系列的终结符，即 token。goyacc 会生成对应的 token id，比如%token<str> SELECT
// 接着定义一系列非终结符。可以用 %union 中的字段来定义，goyacc 会做相应的映射，比如%type <selectStatement> simple_select_clause
%%// 在这编写 BNF，为了兼容 MySQL 语法，语法规则会参考 MySQL，当然，也会有 MatrixOne 自己的一些语法// 比如 simple_select_clause 的一部分定义
simple_select_clause:    SELECT distinct_opt select_expression_list from_opt where_expression_opt group_by_opt having_opt    {        $$ = &tree.SelectClause{            Distinct: $2,            Exprs: $3,            From: $4,            Where: $5,            GroupBy: $6,            Having: $7,        }    }%%

在select.go中可以看到简单的select的部分定义 SelectClause：

type SelectClause struct {  SelectStatement  Distinct bool  Exprs    SelectExprs  From     *From  Where    *Where  GroupBy  GroupBy  Having   *Where  Option   string}

当成功解析完 SQL，MO定义的结构体里的字段都会被相应赋值。比如，解析 SQL：

select a, b from t1 where a > 3 and b = 4;

会生成如下语法树：

接着，就可以将语法树转化和优化成逻辑计划。

熟悉了MO的语法树后，欢迎大家为MO Parser兼容更多的MySQL语法。修改了mysql_sql.y后，进入到parsers目录下执行make，就会生成新的语法分析器，该文件是mysql_sql.go。

最后，一个简单的例子，使用MO Parser进行SQL 解析：

package main
import (  "fmt"
  "github.com/matrixorigin/matrixone/pkg/sql/parsers"  "github.com/matrixorigin/matrixone/pkg/sql/parsers/dialect"  "github.com/matrixorigin/matrixone/pkg/sql/parsers/tree")
func main() {  sql := `select u.a, (select t.a from sa.t, u) from u, (select t.a, u.a from sa.t, u where t.a = u.a) as t where (u.a, u.b, u.c) in (select t.a, u.a, t.b * u.b as tubb from t)`  // 也可以调用 parsers.Parse(dialect.MySQL, sqls), 进行多条 sql 解析  ast, err := parsers.ParseOne(dialect.MYSQL, sql)  if err != nil {    fmt.Println(err)  }  fmt.Println(tree.String(ast, dialect.MYSQL))}