网站开发成本会计科目,网站首页一般做多大,网站设计网站维护,北京app定制公司设计#xff1a;小艾
审核#xff1a;丁奇
编辑#xff1a;宇亭
作者#xff1a;柳湛宇#xff08;花名#xff1a;乌淄#xff09; 浙江大学-软件工程-在读硕士、StoneDB 内核研发实习生
一、MySQL 的解析器
MySQL 所使用的解析器#xff08;即 Lexer 和 Parser … 设计小艾
审核丁奇
编辑宇亭
作者柳湛宇花名乌淄 浙江大学-软件工程-在读硕士、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 exp1 d可以被规约为a exp3 a exp3可以被规约 a exp3可以被规约为exp2 「达到序列末尾」a b c d「成功匹配表达式」exp2 a b c可以被规约为a exp1 a exp1 d可以被规约
自顶向下Top-Down解析模式
自顶向下的表达式类似于「多叉树的先序遍历」。对于给定的每一个 token 子序列都尝试断言Assertion其匹配一个表达式并进一步递归地考察
❝ 1.这个序列是否能通过断言匹配该表达式的子选项 2.断言匹配子选项后其对应改规则可归约的子串是否匹配子选项中的表达式。 ❞ 每当断言失败时同样进行回溯来尝试匹配不同的表达式或表达式内不同的子选项直至构建正确的语法解析树或匹配失败而报错。
对于例 1自顶向下解析模式的解析步骤为 假设此处的原语是断言Assertiona b c d匹配exp1的第一个子选项a b 断言错误因此排除这一选项 同样地显然可以排除exp1的第二个子选项b c和exp2的第一个子选项x y z,此处省略这些步骤 假设a b c d匹配exp2的第二个子选项a exp3 应有b c匹配exp1 假设b c匹配a b 断言错误排除这一选项 假设b c匹配b c 「断言正确且无子表达式匹配成功」a b c d「匹配」exp2 应有b c d匹配exp3 假设b c d匹配c d 断言错误排除这一选项 假设b c d匹配exp1 d
二者的对比与 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
对于如下语法定义
%typeint 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:
对于如下语法定义
%typeint num
%%
numToken:numToken numToken | num;
%%❝ 当处理输入1 2 3时处理到符号2时解析器既可以仅仅将其视作numToken的第二个子选项移入shift语法栈也可以将其与语法栈中部分内容结合组成1 2匹配成为一个numToken表达式。因此这个输入合法语法树指最终结果只有一个顶层表达式就有 2 个 ❞ 规约/规约冲突规约/规约冲突是在解析器在遇到一个输入符号时存在多个可以进行归约操作的情况。这种冲突通常在文法规则中存在二义性或相似的产生式时发生。简单演示见下例 5:
对于如下语法定义
%typeint 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 语法进行扩展和兼容的开发者更加友好。
参考资料 https://www.gnu.org/software/bison/manual/bison.html https://qntm.org/top https://github.com/postgres/postgres/blob/47556a0013fa64d44add2760577d49cf2eca4cd0/src/pl/plpgsql/src/pl_gram.y#L4 MySQL Bugs: #2690: bison -y -d sql_yacc.yy mv y.tab.c sq y.tab.c - No such file or directory https://github.com/mysql/mysql-server/blob/trunk/sql/sql_yacc.yy
