深入浅出MatrixOne Parser

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

数据库内核可以拆分为：

• 接收client发送过来的网络包。

• 处理网络包，将SQL解析成抽象语法树。

• 将语法树转换和优化成查询计划。

• 通过查询计划生成执行计划，并执行返回结果。

将SQL解析成语法树，首先需要进行词法分析。词法分析的过程简而言之是将SQL字符串拆解成若干个 token。例如：select a from t我们可以将其拆解成 select、a、from、t这几个token。而这些token可以作为语法分析的输入。

MatrixOne的Lexer （词法分析器） 是手动编写的，相比于通过工具，比如Lex ，生成Lexer，更加灵活，方便MatrixOne parser兼容MySQL语法。对于手动编写Lexer，可以从有穷自动机说起。

首先，要识别一个token，可以通过正则匹配，例如整数的正则定义：

实现正则匹配，可以通过 FA ，举个例子，比如我们要识别正则文法 r = (a | b) * abb，状态转换图如下：

如此，当状态到达终止状态3时，识别成功。仔细观察可以发现一个问题，在0状态时，接收a ，可以从0到0或者从0到1，这种不确定性无法编程。称之为非确定的有穷状态机（NFA）。

对于上述的例子，将NFA转换成DFA后的状态图如下：

从上图可以看出无论在哪一个状态接收a或b，到达的下一个状态时确定的。

对于MySQL的不同token，比如 数字, 字符串，标识符，数学符号，注释等等，可以参照其定义，写出相应的DFA，最终形成Lexer。感兴趣的同学可以看看MatrixOne的Lexer，实现在scanner.go中，在mysql_lexer.go 中将其封装了起来。

词法分析后tokens将作为语法分析的输入。SQL的语法解析的实现常见有两种方式：

另一种是采用LR文法，自底向上分析。一些工具bison、goyacc可以通过预先定义好的BNF文件生成语法解析器。

goyacc生成的语法分析器，接受LALR(1) （lookahead-LR）文法。与LL文法不同，接受LALR(1) 文法的分析器，其语法分析是从分析树的底部向顶部方向构造分析树，对于LALR(1)

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

• 移入：将下一个 token 移到栈的顶端

• 归约：如果栈中的符号串是某个产生式的左端，则归约成右端，被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串

• 接收：成功完成语法分析过程

• 错误：发现一个语法错误

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

• 语法分析器将0个或多个输入token移入栈的顶端，直到可以对栈顶的一个文法符号串β进行归约为止。

• 然后，β归约为某个产生式的左部。

• 语法分析器不断地重复这个循环，直到检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空（语法分析成功）为止。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

会生成如下语法树：

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

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

可以注意到，Parse需要传入dialect.MySQL参数，这是因为MO Parser在开始设计时，就有支持多方言的想法，目前实现了多方言的框架。