2022-09-09 Mysql语法解析器

背景介绍

众所周知，MySQL Parser是利用C/C++实现的开源yacc/lex组合，也就是 GNU bison/flex。Flex负责生成tokens， Bison负责语法解析。开始介绍MySQL 8.0的新特新之前，我们先简单了解一下通用的两种Parser。一种是Bottom-up parser，另外一种是Top-down parser。

Bottom-up parser

Bottom-up解析是从parse tree底层开始向上构造，然后将每个token移进（shift），进而规约（reduce）为较大的token，最终按照语法规则的定义将所有token规约（reduce）成为一个token。移进过程是有先后顺序的，如果按照某种顺序不能将所有token规约为一个token，解析器将会回溯重新选定规约顺序。如果在规约（reduce）的过程中出现了既可以移进生成一个新的token，也可以规约为一个token，这种情况就是我们通常所说的shift/reduce conflicts.

Top-down parser

Top-down解析是从parse tree的顶层开始向下构造历。这种解析的方法是假定输入的解析字符串是符合当前定义的语法规则，按照规则的定义自顶开始逐渐向下遍历。遍历的过程中如果出现了不满足语法内部的逻辑定义，解析器就会报出语法错误。