关于数据库:MySQL-的解析器以及-MySQL80-做出的改进-StoneDB技术分享-2

设计：小艾
审核：丁奇
编辑：宇亭

作者：柳湛宇（花名：乌淄）
浙江大学 - 软件工程 - 在读硕士、StoneDB 内核研发实习生

一、MySQL 的解析器

MySQL 所应用的解析器（即 Lexer 和 Parser 的组合）是嵌入了 C/C++ 语言的 yacc/lex 组合，在 linux/GNU 体系上，这一组合的实现是 GNU Bison/Flex，即 Flex 负责生成 tokens，Bison 负责语法解析。

对于 Bison，请参阅[1]

Bison 本是一个自底向上（Bottom-Up）的解析器，然而因为历史起因，MySQL 语法编写的规定是以自顶向下（Top-Down）的，这将会产生一些问题，咱们首先简要介绍这两种解析模式。

二、自底向上与自顶向下解析模式

更多具体解说，请参阅[2]

当咱们在议论自底向上和自顶向下两种解析模式时，场面是咱们手上曾经有了编写实现的语法规定和将输出语句词法解析实现后的 token 数组，而之后的工作总体上就是构建语法解析树。

以下 yacc 语法束缚和匹配序列（「例 1」）用于展现两种解析模式的不同。

exp1:
 'a' 'b' | 'b' 'c';
exp2:
 'x' 'y' 'z' | 'a' exp3;
exp3:
 'c' 'd' | exp1 'd';

以 a b c d 作为输出序列。

自底向上（Bottom-Up）解析模式

自底向上的解析模式相似于进行「拼图」。对每一个入栈后 token 组成的序列，都尽可能尝试将其规约（reduce）成一个语法规定中规定的表达式并将新的表达式压栈。在达到 token 数组开端时，栈中的表达式应且仅应匹配一个顶层表达式，如果因为规约程序不符合实际表达式程序而无奈匹配到顶层表达式，则该当进行回溯并尝试新的规约抉择。

对于例 1，自底向上解析模式的解析步骤为：

• a不能被规约（没有能够匹配 a 的表达式子项）
• a b能够被规约：
• • exp1 c d被规约为exp1 exp3
  • exp1 exp3无奈被规约
  • 达到序列开端，须要回溯
• • a b规约为exp1
  • exp1 c无奈被规约
  • exp1 c d能够被规约:
  • 因而，exp1 c d无奈被规约
  • 达到序列开端，须要回溯
• 因而，a b无奈被规约
• a b c能够被规约：
• • a b c能够被规约为a exp1
  • a exp1 d能够被规约
• • a exp1 d能够被规约为a exp3
  • a exp3能够被规约：
• • a exp3能够被规约为exp2
  • 达到序列开端， a b c d胜利匹配表达式exp2

自顶向下（Top-Down）解析模式

自顶向下的表达式相似于「多叉树的先序遍历」。对于给定的每一个 token 子序列，都尝试断言（Assertion）其匹配一个表达式，并进一步递归地考查：

❝

1. 这个序列是否能通过断言匹配该表达式的子选项；
2. 断言匹配子选项后，其对应改规定可归约的子串是否匹配子选项中的表达式。

❞

每当断言失败时，同样进行回溯，来尝试匹配不同的表达式或表达式内不同的子选项，直至构建正确的语法解析树或匹配失败而报错。

对于例 1，自顶向下解析模式的解析步骤为：

• 假如（此处的原语是断言，Assertion）a b c d匹配 exp1 的第一个子选项'a' 'b'
• 断言谬误，因而排除这一选项；
• 同样地，显然能够排除 exp1 的第二个子选项 'b' 'c' 和exp2的第一个子选项'x' 'y' 'z', 此处省略这些步骤；
• 假如 a b c d 匹配 exp2 的第二个子选项'a' exp3
• • 应有 b c d 匹配exp3
  • 假如 b c d 匹配'c' 'b'
  • 断言谬误，排除这一选项
  • 假如 b c d 匹配'exp1' 'd'
• • 应有 b c 匹配exp1
  • 假如 b c 匹配'a' 'b'
  • 断言谬误，排除这一选项
  • 假如 b c 匹配'b' 'c'
  • 「断言正确且无子表达式，匹配胜利，」a b c d「匹配」exp2

二者的比照与 MySQL 面临的问题

能够看到，自底向上解析模式更合乎计算机程序的格调，其将规约操作提前，在后半局部执行匹配和回溯动作。但其毛病在于，每一次匹配和回溯的触发点都仅仅在达到 token 数组开端时进行，因而如果没有优先级束缚，每次无效回溯的代价都较大。

自顶向下的解析模式更合乎人类浏览和编写语法文件的习惯，其将断言和回溯动作提前，将理论的匹配动作置于解析的后半段。这样的模式毛病在于，它须要回溯的次数更多，同时语法愈发简单，如果没有适合的断言程序（实际上对于不同的 SQL 语句，最优的断言程序也不尽相同），就会有更多冗余的比拟分支和更深的无效回溯长度。

因为 MySQL 因历史起因抉择了易读的自顶向下的解析模式，其在语法解析时，会产生二义性带来的两种抵触（conflict）：移位 / 规约（shift/reduce）抵触和规约 / 规约（reduce/reduce）抵触，而应用自底向上解析模式的 posgres[3]则不会产生这两种抵触。

三、移位 / 规约抵触与规约 / 规约抵触

两种操作

首先简要介绍自底向上分析方法的移位（shift）和规约（reduce）操作。按自底向上的解析模式，解析器对输出符号串从左到右扫描，读取输出并与语法规定比拟，其中：

• 移位操作是将符号从输出流转入剖析栈中的操作。如果以后输出与语法规定匹配，解析器就将以后输出移入（shift）语法栈中，并持续尝试解决下一个符号。简略演示见下例 2:

对于如下语法定义：

simpleStrSeq:
 'a' 'b' 'c' | 'e' 'f' 'g';

解决输出串 a b c 时，解决前两个 token 时都会将其间接放入语法栈，因为它们匹配 simpleStrSeq 表达式。

• 规约操作是将语法栈上的一部分内容替换为相应的非终结符的操作。当解析器发现输出与语法规定的右侧匹配时，它能够执行归约操作，将右侧的符号替换为对应的非终结符。简略演示见下例 3：

对于如下语法定义：

%type<int> num
%%
product:
num '*' num;
plus:
product '*' product;
%%

解决输出串 1 * 2 + 3 * 4 时，在解决到符号 2 时，会将语法栈中现有的 1 * 2 规约（reduce）为 product，进一步地，会在解决到4 时将 3 * 4 规约为 product，将product + product 规约为plus。

两种抵触

上述的移位和规约操作是针对自底向上范式提出的，因而应用自顶向下程序编写语法束缚，就会产生移位 / 规约抵触与规约 / 规约抵触：

• 移位 / 规约抵触：移位 / 规约抵触指当解析器解决一个符号时，它既能够进行移位（shift）操作，将符号局部或齐全匹配一个表达式，同时也能够进行规约（reduce）操作，将以后语法栈内的内容联结输出替换成表达式。简略演示见下例 4:

对于如下语法定义：

%type<int> num
%%
numToken:
 numToken '+' numToken | num;
%%

❝

当解决输出 1 + 2 + 3 时，解决到符号 2 时，解析器既能够仅仅将其视作 numToken 的第二个子选项，移入（shift）语法栈，也能够将其与语法栈中局部内容联合组成 1 + 2，匹配成为一个numToken 表达式。因而，这个输出非法语法树（指最终后果只有一个顶层表达式）就有 2 个：

❞

• 规约 / 规约抵触：规约 / 规约抵触是在解析器在遇到一个输出符号时，存在多个能够进行归约操作的状况。这种抵触通常在文法规定中存在二义性或类似的产生式时产生。简略演示见下例 5:

对于如下语法定义：

%type<int> num
%%
numToken:
 numToken '+' numToken |  numToken '*' numToken | num;
%%

❝

当解决输出 1 + 2 * 3 时，解析器既能够将 2 其视作 numToken 的第 1 个子选项的后半局部规约为加法，也能够将其视作 numToken 第 2 个与子项的前半正本，规约为乘法。因而，这个输出非法语法树（指最终后果只有一个顶层表达式）就有 2 个：

❞

MySQL 中的语法抵触

咱们之前提到，因为历史起因和可读性思考，MySQL 的 yacc 语法文件采纳自顶向下的编写形式，它引入了上述两种语法抵触。产生抵触的起因是，自顶向下的解析办法须要层层进行断言与子表达式的匹配，而在更顶层的子表达式无奈在实际上以自底向上执行的 Bison 解析器中间接确定匹配选项。

这意味着语法抵触并不总是意味着语句的二义性而导致解析失败（对于的确须要指定关联性和优先级的操作符，MySQL 也对它们进行了%left、%right、%nonassoc），事实上 MySQL 的问题是宽泛存在的 shift/reduce 抵触引起的断言失败数量减少，进而使得解析工夫变长。

正如咱们从上图中看到的，MySQL 各个版本中都有相当数量的 shift/reduce 抵触，但除了图中显示的 MySQL 4.0 中存在的 4 个会导致解析二义性的 reduce/reduce 抵触[4]，shift/reduce 抵触不会使得解析器最终失去正确的后果，因而 MySQL8.0 的态度是：

❝

1.We do not accept any reduce/reduce conflicts
2.We should not introduce new shift/reduce conflicts any more.

❞

四、MySQL 8.0 对语法束缚的改良

从上图中能够看到，MySQL 8.0 版本升高了语法文件中的 shift/reduce 抵触数量，且随着版本不断更新，目前这一抵触数量已降落到了 63[5‍]（通过语法文件中的 %expect 语句显式申明）。

MySQL 8.0 做出了很多致力来达到这一成绩。其中最要害一点在于对 query 语句整体格局的重构。MySQL 8.0 以前，雷同的语法结构（如 create select 和 select 语句都是用的参数列表，select、update 和 delete 语句中都须要应用的 table 列表等）会间接被不同类型的语句间接援用，而没有做额定的束缚。

在 MySQL 8.0 中，它批准了所有语句的语法结构，将共用的子结构段进行了进一步的束缚和封装，这使得自顶向下的断言能够更快地匹配到对应的语法，同时也能体现于构造上的简洁性。

以下是 MySQL 5.7 到 MySQL 8.0 下层语法结构比照一览：

能够看出 MySQL 8.0 使得整体架构更加清晰有序。

同时，8.0 将局部只有一处定义的语法结构开展到下层构造的子选项中，这样的操作以减少边缘性能的代码行数、升高可读性为代价缩小了 shift/reduce 抵触。此外，MySQL 8.0 通过显示定义两个伪 token：%left KEYWORD_USED_AS_IDENT和 %left KEYWORD_USED_AS_KEYWORD 来显式地申明对以关键字作为标识符的行为，缩小了解析过程中二义性因其的断言失败。

论断

从整体上看，关系数据库系统对于典型的 SQL 语句在语法解析阶段的耗时很短，简直能够忽略不计，因而 MySQL 维持其自顶向下解析构造以取得语法文件的可读性和可扩展性是能够了解的。咱们能够看到 MySQL 8.0 并没有对将语法解析模块更改成相似 Posgres 那样 LALR 的模式以打消语法抵触，而是尽可能地将语法树表白的更加简洁，进而使其对基于 MySQL 语法进行扩大和兼容的开发者更加敌对。

参考资料

1. https://www.gnu.org/software/bison/manual/bison.html
2. https://qntm.org/top
3. https://github.com/postgres/postgres/blob/47556a0013fa64d44add2760577d49cf2eca4cd0/src/pl/plpgsql/src/pl_gram.y#L4
4. MySQL Bugs: #2690: bison -y -d sql_yacc.yy && mv y.tab.c sq y.tab.c – No such file or directory
5. https://github.com/mysql/mysql-server/blob/trunk/sql/sql_yacc.yy

退出 StoneDB 社区

Github： https://github.com/stoneatom/stonedb

Gitee： https://gitee.com/StoneDB/stonedb

社区官网： https://stonedb.io/

哔哩哔哩： https://space.bilibili.com/1154290084

Twitter： https://twitter.com/StoneDataBase

Linkedin： https://www.linkedin.com/in/stonedb/