TiDB 源码阅读系列文章（五）TiDB SQL Parser 的实现

本文为 TiDB 源码阅读系列文章的第五篇，主要对 SQL Parser 功能的实现进行了讲解，内容来自社区小伙伴——马震（GitHub ID：mz1999 ）的投稿。

TiDB 源码阅读系列文章的撰写初衷，就是希望能与数据库研究者、爱好者进行深入交流，我们欣喜于如此短的时间内就收到了来自社区的反馈。后续，也希望有更多小伙伴加入到与 TiDB 『坦诚相见』的阵列中来。

PingCAP 发布了 TiDB 的源码阅读系列文章，让我们可以比较系统的去学习了解TiDB的内部实现。最近的一篇“SQL的一生”，从整体上讲解了一条 SQL 语句的处理流程，从网络上接收数据，MySQL 协议解析和转换，SQL 语法解析，查询计划的制定和优化，查询计划执行，到最后返回结果。

其中，SQL解析器的功能是把 SQL 语句按照 SQL 语法规则进行解析，将文本转换成抽象语法树（AST），这部分功能需要些背景知识才能比较容易理解，我尝试做下相关知识的介绍，希望能对读懂这部分代码有点帮助。

TiDB 是使用goyacc根据预定义的 SQL 语法规则文件parser.y生成 SQL 语法解析器。我们可以在 TiDB 的Makefile文件中看到这个过程，先 buildgoyacc工具，然后使用goyacc根据parser.y生成解析器parser.go：

goyacc:$(GOBUILD)-o bin/goyacc parser/goyacc/main.goparser: goyaccbin/goyacc -o /dev/null parser/parser.y bin/goyacc -o parser/parser.go parser/parser.y 2>&1 ...

goyacc是yacc的 Golang 版，所以要想看懂语法规则定义文件parser.y，了解解析器是如何工作的，先要对Lex & Yacc有些了解。

Lex & Yacc 介绍

Lex & Yacc是用来生成词法分析器和语法分析器的工具，它们的出现简化了编译器的编写。Lex & Yacc分别是由贝尔实验室的Mike Lesk和Stephen C. Johnson在 1975 年发布。对于 Java 程序员来说，更熟悉的是ANTLR，ANTLR 4提供了Listener+Visitor组合接口， 不需要在语法定义中嵌入actions，使应用代码和语法定义解耦。Spark的 SQL 解析就是使用了ANTLR。Lex & Yacc相对显得有些古老，实现的不是那么优雅，不过我们也不需要非常深入的学习，只要能看懂语法定义文件，了解生成的解析器是如何工作的就够了。我们可以从一个简单的例子开始：

上图描述了使用Lex & Yacc构建编译器的流程。Lex根据用户定义的patterns生成词法分析器。词法分析器读取源代码，根据patterns将源代码转换成令牌输出。Yacc根据用户定义的语法规则生成语法分析器。语法分析器以词法分析器输出的令牌作为输入，根据语法规则创建出语法树。最后对语法树遍历生成输出结果，结果可以是产生机器代码，或者是边遍历AST边解释执行。

从上面的流程可以看出，用户需要分别为Lex提供patterns的定义，为Yacc提供语法规则文件，Lex & Yacc根据用户提供的输入文件，生成符合他们需求的词法分析器和语法分析器。这两种配置都是文本文件，并且结构相同：

...definitions...%%...rules...%%...subroutines...

文件内容由%%分割成三部分，我们重点关注中间规则定义部分。对于上面的例子，Lex的输入文件如下：

...%%/* 变量 */[a-z] { yylval = *yytext -'a';returnVARIABLE;｝/* 整数 */[0-9]+ { yylval = atoi(yytext); returnINTEGER;｝/* 操作符 */[-+()=/*\n] { return *yytext; } /* 跳过空格 */[ \t] ;/* 其他格式报错 */. yyerror("invalid character");%%...

上面只列出了规则定义部分，可以看出该规则使用正则表达式定义了变量、整数和操作符等几种token。例如整数token的定义如下：

[0-9]+ { yylval = atoi(yytext);returnINTEGER; }

当输入字符串匹配这个正则表达式，大括号内的动作会被执行：将整数值存储在变量yylval中，并返回token类型INTEGER给Yacc。

再来看看Yacc语法规则定义文件：

%tokenINTEGERVARIABLE%left'+'“- - -”%left'*''/'... %% program: programstatement'\n'| ; statement: expr { printf("%d\n",$1); } |VARIABLE'='expr{ sym[$1] = $3;｝;expr:INTEGER|VARIABLE{ $$ = sym[$1]; } | expr'+'expr {$$=$1+$3;｝| expr“- - -”expr {$$=$1-$3;｝| expr'*'expr {$$=$1*$3;｝| expr'/'expr {$$=$1/$3;｝|'('expr')'{$$=$2;｝;%% ...

第一部分定义了token类型和运算符的结合性。四种运算符都是左结合，同一行的运算符优先级相同，不同行的运算符，后定义的行具有更高的优先级。

语法规则使用了BNF定义。BNF可以用来表达上下文无关（上下文无关）语言，大部分的现代编程语言都可以使用BNF表示。上面的规则定义了三个产生式。产生式冒号左边的项（例如statement）被称为非终结符，INTEGER和VARIABLE被称为终结符,它们是由Lex返回的token。终结符只能出现在产生式的右侧。可以使用产生式定义的语法生成表达式：

expr-> expr * expr -> expr *INTEGER-> expr + expr *INTEGER-> expr +INTEGER*INTEGER->INTEGER+INTEGER*INTEGER

解析表达式是生成表达式的逆向操作，我们需要归约表达式到一个非终结符。Yacc生成的语法分析器使用自底向上的归约（shift-reduce）方式进行语法解析，同时使用堆栈保存中间状态。还是看例子，表达式x + y * z的解析过程：

1. x + y * z2x . + y * z3expr. + y * z4expr+ . y * z5expr+ y . * z6expr+ expr . * z7expr+ expr * . z8expr+ expr * z .9expr+ expr * expr .10expr+ expr .11expr.12statement .13program .

点（.）表示当前的读取位置，随着.从左向右移动，我们将读取的token压入堆栈，当发现堆栈中的内容匹配了某个产生式的右侧，则将匹配的项从堆栈中弹出，将该产生式左侧的非终结符压入堆栈。这个过程持续进行，直到读取完所有的令牌，并且只有启始非终结符（本例为program）保留在堆栈中。

产生式右侧的大括号中定义了该规则关联的动作，例如：

expr: expr'*'expr {$$=$1*$3;｝

我们将堆栈中匹配该产生式右侧的项替换为产生式左侧的非终结符，本例中我们弹出expr'*' expr，然后把expr压回堆栈。 我们可以使用$position的形式访问堆栈中的项，$1引用的是第一项，$2引用的是第二项，以此类推。$$代表的是归约操作执行后的堆栈顶。本例的动作是将三项从堆栈中弹出，两个表达式相加，结果再压回堆栈顶。

上面例子中语法规则关联的动作，在完成语法解析的同时，也完成了表达式求值。一般我们希望语法解析的结果是一棵抽象语法树（AST），可以这么定义语法规则关联的动作：

... %% ... expr: INTEGER { $$ = con($1); } | VARIABLE { $$ = id($1); } | expr'+'expr {$$ = opr('+',2, $1, $3); } | expr“- - -”expr {$$ = opr(“- - -”,2, $1, $3); } | expr'*'expr {$$ = opr('*',2, $1, $3); } | expr'/'expr {$$ = opr('/',2, $1, $3); } |'('expr')'{ $$ = $2; } ; %%nodeType*con(intvalue) { ... }nodeType*id(inti) { ... }nodeType*opr(intoper,intnops, ...) { ... }

上面是一个语法规则定义的片段，我们可以看到，每个规则关联的动作不再是求值，而是调用相应的函数，该函数会返回抽象语法树的节点类型nodeType，然后将这个节点压回堆栈，解析完成时，我们就得到了一颗由nodeType构成的抽象语法树。对这个语法树进行遍历访问，可以生成机器代码，也可以解释执行。

至此，我们大致了解了Lex & Yacc的原理。其实还有非常多的细节，例如如何消除语法的歧义，但我们的目的是读懂 TiDB 的代码，掌握这些概念已经够用了。

goyacc 简介

goyacc是 golang 版的Yacc。和Yacc的功能一样，goyacc根据输入的语法规则文件，生成该语法规则的 go 语言版解析器。goyacc生成的解析器yyParse要求词法分析器符合下面的接口：

typeyyLexer interface {Lex(lval*yySymType)intError(estring)｝

或者

typeyyLexerEx interface { yyLexer// Hook for recording a reduction.Reduced(rule,stateint,lval*yySymType)(stopbool)// Client should copy *lval.｝

TiDB 没有使用类似Lex的工具生成词法分析器，而是纯手工打造，词法分析器对应的代码是parser/lexer.go， 它实现了goyacc要求的接口：

...// Scanner implements the yyLexer interface.typeScannerstruct{ r reader buf bytes.Buffer errs []error stmtStartPosint// For scanning such kind of comment: /*! MySQL-specific code */ or /*+ optimizer hint */specialComment specialCommentScanner sqlMode mysql.SQLMode }// Lex returns a token and store the token value in v.// Scanner satisfies yyLexer interface.// 0 and invalid are special token id this function would return:// return 0 tells parser that scanner meets EOF,// return invalid tells parser that scanner meets illegal character.func(s *Scanner)Lex(v *yySymType)int{ tok, pos, lit := s.scan() v.offset = pos.Offset v.ident = lit ... }// Errors returns the errors during a scan.func(s *Scanner)Errors()[]error{returns.errs }

另外lexer使用了字典树技术进行token识别，具体的实现代码在parser/misc.go

TiDB SQL Parser 的实现

终于到了正题。有了上面的背景知识，对 TiDB 的SQL解析器模块会相对容易理解一些。TiDB 的词法解析使用的手写的解析器（这是出于性能考虑），语法解析采用goyacc。先看 SQL 语法规则文件parser.y，goyacc就是根据这个文件生成SQL语法解析器的。

parser.y有 6500 多行，第一次打开可能会被吓到，其实这个文件仍然符合我们上面介绍过的结构：

...definitions...%%...rules...%%...subroutines...

parser.y第三部分subroutines是空白没有内容的， 所以我们只需要关注第一部分definitions和第二部分rules。

第一部分主要是定义token的类型、优先级、结合性等。注意union这个联合体结构体：

%union{ offsetint// offsetiteminterface{} identstringexprast.ExprNode statement ast.StmtNode }

该联合体结构体定义了在语法解析过程中被压入堆栈的项的属性和类型。

压入堆栈的项可能是终结符，也就是token，它的类型可以是item或ident；

这个项也可能是非终结符，即产生式的左侧，它的类型可以是expr、statement、item或ident。

goyacc根据这个union在解析器里生成对应的struct是：

typeyySymTypestruct{ yysintoffsetint// offsetiteminterface{} identstringexprast.ExprNode statement ast.StmtNode }

在语法解析过程中，非终结符会被构造成抽象语法树（AST）的节点ast.ExprNode或ast.StmtNode。抽象语法树相关的数据结构都定义在ast包中，它们大都实现了ast.Node接口：

//Nodeisthe basic element of the AST. // Interfaces embedNodeshouldhave 'Node' namesuffix.typeNodeinterface{接受(v访问者)(nodeNode, ok bool) Text()stringSetText(textstring) }

这个接口有一个Accept方法，接受Visitor参数，后续对AST的处理，主要依赖这个Accept方法，以Visitor模式遍历所有的节点以及对AST做结构转换。

// Visitor visits a Node.typeVisitor interface { Enter(nNode) (nodeNode, skipChildrenbool) Leave(nNode) (nodeNode, okbool) }

例如plan.preprocess是对AST做预处理，包括合法性检查以及名字绑定。

union后面是对token和非终结符按照类型分别定义：

/* 这部分的 token 是 ident 类型 */%token ...add"ADD"all"ALL"alter"ALTER"analyze"ANALYZE"和"AND"as"AS"asc"ASC"between"BETWEEN"bigIntType"BIGINT".../* 这部分的 token 是 item 类型 */%token /*yy:token "1.%d" */floatLit"floating-point literal"/*yy:token "1.%d" */decLit"decimal literal"/ * yy:令牌“% d”* /intLit"integer literal"/*yy:token "%x" */hexLit"hexadecimal literal"/*yy:token "%b" */bitLit"bit literal"和not"&^"assignmentEq":="eq"="ge">=".../* 非终结符按照类型分别定义 */%type Expression"expression"BoolPri"boolean primary expression"ExprOrDefault"expression or default"PredicateExpr"Predicate expression factor"SetExpr"Set variable statement value's expression"...%type AdminStmt"Check table statement or show ddl statement"AlterTableStmt"Alter table statement"AlterUserStmt"Alter user statement"AnalyzeTableStmt"Analyze table statement"BeginTransactionStmt"BEGIN TRANSACTION statement"BinlogStmt"Binlog base64 statement"...%type AlterTableOptionListOpt"alter table option list opt"AlterTableSpec"Alter table specification"AlterTableSpecList"Alter table specification list"AnyOrAll"Any or All for subquery"Assignment"assignment"...%type KeyOrIndex"{KEY|INDEX}"ColumnKeywordOpt"Column keyword or empty"PrimaryOpt"Optional primary keyword"NowSym"CURRENT_TIMESTAMP/LOCALTIME/LOCALTIMESTAMP"NowSymFunc"CURRENT_TIMESTAMP/LOCALTIME/LOCALTIMESTAMP/NOW"...

第一部分的最后是对优先级和结合性的定义：

...%precedencesqlCache sqlNoCache%precedencelowerThanIntervalKeyword%precedenceinterval%precedencelowerThanStringLitToken%precedencestringLit ...%rightassignmentEq%leftpipes or pipesAsOr%leftxor%left和和和%leftbetween ...

parser.y文件的第二部分是SQL语法的产生式和每个规则对应的aciton。SQL语法非常复杂，parser.y的大部分内容都是产生式的定义。

SQL语法可以参照 MySQL 参考手册的SQL Statements部分，例如SELECT语法的定义如下：

SELECT[ALL|DISTINCT| DISTINCTROW ] [HIGH_PRIORITY] [STRAIGHT_JOIN] [SQL_SMALL_RESULT] [SQL_BIG_RESULT] [SQL_BUFFER_RESULT] [SQL_CACHE | SQL_NO_CACHE] [SQL_CALC_FOUND_ROWS] select_expr [, select_expr ...] [FROMtable_references [PARTITIONpartition_list] [WHEREwhere_condition] [GROUPBY{col_name | expr |position｝[ASC|DESC], ... [WITHROLLUP]] [HAVINGwhere_condition] [ORDERBY{col_name | expr |position｝[ASC|DESC], ...] [LIMIT{[offset,] row_count | row_countOFFSEToffset｝] [PROCEDUREprocedure_name(argument_list)] [INTOOUTFILE'file_name'[CHARACTERSETcharset_name] export_options |INTODUMPFILE'file_name'|INTOvar_name [, var_name]] [FORUPDATE| LOCKINSHARE MODE]]

我们可以在parser.y中找到SELECT语句的产生式：

SelectStmt:"SELECT"SelectStmtOpts SelectStmtFieldList OrderByOptional SelectStmtLimit SelectLockOpt {...｝|"SELECT"SelectStmtOpts SelectStmtFieldList FromDual WhereClauseOptional SelectStmtLimit SelectLockOpt {...｝|"SELECT"SelectStmtOpts SelectStmtFieldList"FROM"TableRefsClause WhereClauseOptional SelectStmtGroup HavingClause OrderByOptional SelectStmtLimit SelectLockOpt {...｝

产生式SelectStmt和SELECT语法是对应的。

我省略了大括号中的action，这部分代码会构建出AST的ast.SelectStmt节点：

typeSelectStmtstruct { dmlNode resultSetNode //SelectStmtOptswraps around select hints and switches. *SelectStmtOpts//Distinctrepresents whether the select has distinct option.Distinctbool //Fromis the from clause of the query.From*TableRefsClause//Whereis the where clause in select statement.WhereExprNode//Fieldsis the select expression list.Fields*FieldList//GroupByis the group by expression list.GroupBy*GroupByClause//Havingis the having condition.Having*HavingClause//OrderByis the ordering expression list.OrderBy*OrderByClause//Limitis the limit clause.Limit*Limit//LockTpis the lock typeLockTpSelectLockType//TableHintsrepresents the levelOptimizerHintTableHints[]*TableOptimizerHint｝

可以看出，ast.SelectStmt结构体内包含的内容和SELECT语法也是一一对应的。

其他的产生式也都是根据对应的SQL语法来编写的。从parser.y的注释看到，这个文件最初是用工具从BNF转化生成的，从头手写这个规则文件，工作量会非常大。

完成了语法规则文件parser.y的定义，就可以使用goyacc生成语法解析器：

bin/goyacc -oparser/parser.goparser/parser.y2>&1

TiDB 对lexer和parser.go进行了封装，对外提供parser.yy_parser进行 SQL 语句的解析：

// Parse parses a query string to raw ast.StmtNode.func(parser *Parser)Parse(sql, charset, collationstring)([]ast.StmtNode, error){ ... }

最后,我写了一个简单的例子,使用TiDB的SQL解析器进行 SQL 语法解析，构建出AST，然后利用visitor遍历AST：

packagemainimport("fmt""github.com/pingcap/parser""github.com/pingcap/parser/ast"_"github.com/pingcap/tidb/types/parser_driver")typevisitorstruct{}func(v *visitor)Enter(in ast.Node)(out ast.Node, skipChildrenbool){ fmt.Printf("%T\n", in)returnin,false｝func(v *visitor)Leave(in ast.Node)(out ast.Node, okbool){returnin,true｝funcmain(){ p := parser.New() sql :="SELECT /*+ TIDB_SMJ(employees) */ emp_no, first_name, last_name "+"FROM employees USE INDEX (last_name) "+"where last_name='Aamodt' and gender='F' and birth_date > '1960-01-01'"stmtNodes, _, err := p.Parse(sql,"","")iferr !=nil{ fmt.Printf("parse error:\n%v\n%s", err, sql)return｝for_, stmtNode :=rangestmtNodes { v := visitor{} stmtNode.Accept(&v) } }

我实现的visitor什么也没干，只是输出了节点的类型。 这段代码的运行结果如下，依次输出遍历过程中遇到的节点类型：

*ast.SelectStmt *ast.TableOptimizerHint *ast.TableRefsClause *ast.Join *ast.TableSource *ast.TableName *ast.BinaryOperationExpr *ast.BinaryOperationExpr *ast.BinaryOperationExpr *ast.ColumnNameExpr *ast.ColumnName *ast.ValueExpr *ast.BinaryOperationExpr *ast.ColumnNameExpr *ast.ColumnName *ast.ValueExpr *ast.BinaryOperationExpr *ast.ColumnNameExpr *ast.ColumnName *ast.ValueExpr *ast.FieldList *ast.SelectField *ast.ColumnNameExpr *ast.ColumnName *ast.SelectField *ast.ColumnNameExpr *ast.ColumnName *ast.SelectField *ast.ColumnNameExpr *ast.ColumnName

了解了 TiDBSQL解析器的实现，我们就有可能实现 TiDB 当前不支持的语法，例如添加内置函数，也为我们学习查询计划以及优化打下了基础。希望这篇文章对你能有所帮助。

作者介绍：马震，金蝶天燕架构师，曾负责中间件、大数据平台的研发，今年转向了 NewSQL 领域，关注 OLTP/AP 融合，目前在推动金蝶下一代 ERP 引入 TiDB 作为数据库存储服务。

点击查看更多TiDB 源码阅读系列文章