前 言
CockroachDB是著名的开源NewSQL数据库，对外提供了标准SQL接口。上一篇文章《CockroachDB
SQL引擎介绍》从全局视角出发，介绍了在CockroachDB中，一个SQL语句从用户发送请求到服务端进行解析和处理的过程。其中用户输入的SQL语句，是如何被内部的执行引擎识别并处理的？为什么有些SQL语句CockroachDB支持，而MySQL却不能识别？本文将详细介绍CockroachDB的SQL解析器，帮助用户理解SQL引擎是如何将用户输入的SQL语句从String解析为内部可理解的结构，从而进行后续的分析和优化。
概 述
parser模块位于SQL引擎的第一个环节，它负责根据SQL语法规则对SQL语句进行解析，将用户输入的SQL text通过词法解析和语法解析，生成一颗抽象语法树（AST）。将用户的SQL text转化为抽象语法树后，就可以被内部SQL执行引擎识别和处理了。
在计算机科学中，AST是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。
在SQL处理中AST的概念也是类似的，不过它翻译的不是源代码，而是用户的SQL语句。举个例子，下述SQL语句通过一定的语法规则解析后，生成了一颗抽象语法树：
执行过程
生成AST的过程，主要分两个阶段：词法解析和语法解析。 
词法解析
词法解析器Lexer主要是把用户输入的SQL从String转化成一个个Token，然后传递给语法解析器。
通常可以使用工具Lex解析patterns规则文件来生成词法解析器，用户只需要定义相应的规则文件即可。在CockroachDB中直接提供了对应的词法解析器，这部分代码主要在 pkg/sql/parser/scan.go 中。
其中通过MakeScanner函数根据输入的string来构造一个scanner，然后调用对应的scan函数进行解析。 
词法解析器仅做初步的字符识别和解析，通常情况下我们并不需要修改词法解析器的内容。
语法解析
词法解析器通过一定的规则，将string转化为一个个的token，然后传递语法解析器进行语法解析。
语法解析的目的是将词法解析器传递过来的token，通过定义的语法规则进行解析，生成一颗抽象语法树。
通常可以使用工具Yacc来解析用户定义的语法规则文件，从而生成语法解析器。CockroachDB的语法规则文件是 pkg/sql/parser/sql.y，该文件配置了CockroachDB目前支持的SQL语法规则，然后通过工具go-yacc解析生成对应的语法解析器，语法解析器代码在pkg/sql/parser/parse.go 中。
sql.y文件通过‘%%‘将文件内容分为3个部分：定义区，规则区，子程序区。 
定义区声明了许多数据类型、结构体和运算符结合规则等，声明通常由‘%‘开头，一些常见的声明如下：
%{…}% ：package\import声明，代码声明等，这部分声明会出现在生成的解析器代码中
%token：定义SQL标准的语句关键字，语法规则中的终结符
%type：声明数据类型
%union：声明结构体
%left，%right：左结合，右结合
%nonassoc ：不可结合（不能连续出现）
在规则区定义了许多SQL语法的规则，举个例子，下图是 SHOW STATISTICS 语句的语法规则片段： 
该语法规则以冒号‘:‘分为左右两部分，左边 show_stats_stmt 是非终结符；
右侧定义了对应的语法规则，可能是终结符和非终结符的组合；
大括号里是相应的关联动作，其中 $$ 是用来存储结果，存储的是语法树的相应节点类型，$5 表示右侧的第5个字段的值，在SHOW STATISTICS FOR TABLE table_name 中 $5 表示的是 table_name 的值，调用的方法在该文件的声明区中定义;
‘|’ 表示‘或‘，代表多种不同的规则，从该语法规则可以看出，该语句支持两种正常的语法形式：
SHOW STATISTICS FOR TABLE table_name
SHOW STATISTICS USING JSON FOR TABLE table_name
终结符和非终结符是编译原理中常见的概念。非终结符可理解为一个可拆分元素，而终结符是不可拆分的最小元素，通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导。这里面的非终结符就是指Lexer产生的Token，例如 SHOW、STATISTICS 等都是终结符，可以在第一部分声明区中找到： 
而 table_name 是非终结符，可以继续推导，因而可以在规则区中找到对应的推导规则。
更多CockroachDB支持的语法规则可以在sql.y中查看，如果需要新增和调整支持的语法形式，则需要调整该文件，然后重新通过go-yacc编译生成语法解析器。
总 结
本篇文章介绍了CockroachDB的SQL解析器，主要通过词法解析器将SQL语句解析成token，然后通过语法解析器生成抽象语法树。后续我们将通过一篇添加新语法的教程，来更具体和深入得了解CockroachDB中的Parser模块。
关于我们：我们是百度 DBA 团队，团队有多位 CockroachDB PMC Member 及 Contributor, 目前正积极推动 NewSQL 在百度内部以及外部的发展。除了NewSQL, 我们在MySQL, PostgreSQL, GreenPlum 有多年的内核开发经验及实践经验，对数据库和大数据领域有疑问或者需求欢迎联系我们，同时欢迎有志青年加入我们！
关注我们
