第五章、使用AST树中间结果来计算表达式值

现在我们已经知道，通过创建ANTLR 语法文件 以及添加一些动作来实现一个“转换器”，这一章节将介绍另外一种方式来实现同样的功能，这需要额外用到一些树结构。我们将使用相同的grammar语法来创建一个中间数据结果，只是用树的创建规则来替换我们之前添加的一些动作。一旦，我们有了树结构，就可以用树解析器来解析树，并且执行一些动作。

ANTLR将会从grammar文件从创建一个树解析器。Parser grammar 会把输入的字符流转换成一个树结构，然后输解析器会对其解析求值。

尽管之前的方法更加直接，但是从语言规划来讲做得不够好。向grammar中添加方法调用、while循环，意味着，解析器要执行相同的代码多次。每当需要调用一个方法时，解析器需要重解析这个方法。因此相比较AST方法，之前的方法不够灵活，AST方法生成AST树来存储中间结果，再遍历树执行相关操作。很明显，重复遍历树比重复解析grammar效率更高。

一个中间结果通常是一棵树，树中节点不止是符号，还有表示符号间关系的节点。举例来说，下面的图表示了3+4这个表达式：

在许多例子中，你会看到树被表示成文本形式。比如，3+4可表示为（+ 3 4 ）。括号后面第一个符号是根节点，随后的事他的孩子。表达式3+4*5的一颗AST树，文本形似为 （+ 3 （* 4  5）），如下图所示：

正如我们看到的，AST树结构严格表示了操作优先级。这里，乘法必须先被执行，因为加法需要乘法的结果作为操作参数。

AST不同于解析树，解析树代表了解析规则。下图展示了本例子中的解析树：

解析树的叶子节点是输入符号，非叶节点是规则名。根节点prog表示，3+4是一个prog。更具体的说是一个stat，而stat是由expr组成。所以解析树，记录了recognizer如何与输入进行匹配的。

在实际中，让语法和树解耦是非常有用的。因此，AST树不受解析树的影响。一个语法通常会改变解析树的结构但不会影响AST,这对处理AST树的代码来说很有意义。

一旦生成好了AST树，你可以有多种方式访问它，来计算你要的结果。一般来说，我建议你使用tree grammar 来生成访问树的代码。

在下一章节，你将学习如何创建AST树，怎样通过一个tree grammar访问它，如何在tree grammar中设置动作。最会，你会得到一个和之前有一样功能的转换器。

 http://www.orczhou.com/index.php/2012/11/mysql-innodb-source-code-optimization-1/

MySQL源代码：从SQL语句到MySQL内部对象

自从有了微薄后博客就写得少了，上一篇博客已经是6月份写的了... 从写第一篇关于MySQL源码的文章之后也已经过了很久，继续上路。

优化器是关系数据库的一个重要而有特色的部分，优化器的理论和实践也多半也都很复杂，本系列文章希望通过解析MySQL优化器，来用好MySQL,扬其长，避其短。顺便也一窥关系数据库优化器的实现思路。文章将重点介绍重要的数据结构和数据结构之间的关系，而不是侧重于代码（"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."）。

0 写在前面

本文解决了什么问题：希望通过这些文章能够帮你更加顺畅的理解MySQL优化器的行为；在你阅读MySQL源代码之前了解更多的背后思路。

本文不解决什么问题：教你如何读懂源代码；

这个系列很长,大概按这样的思路进行下去: 基本的数据结构、语法解析、JOIN的主要算法、JOIN顺序和单表访问。数据结构(以及他们的关系)和算法流程总是相互穿插介绍。

建议阅读：参考文献中的文章和书籍，都建议在阅读本文之前阅读。

1 SQL语句解析基础

1.1 语法解析基础/Flex与Bison

MySQL语法解析封装在函数MYSQLparser中完成。跟其他的语法解析器一样，它包含两个模块：词法分析(Lexical scanner)和语法规则(Grammar rule module)。词法分析将整个SQL语句打碎成一个个单词(Token)，而语法规则模块则根据MySQL定义的语法规则生成对应的数据结构，并存储在对象THD->LEX结构当中。最后优化器，根据这里的数据，生成执行计划，再调用存储引擎接口执行。

词法分析和语法规则模块有两个较成熟的开源工具Flex和Bison分别用来解决这两个问题。MySQL处于性能和灵活考虑，选择了自己完成词法解析部分，语法规则部分使用Bison。词法解析和Bison沟通的核心函数是由词法解析器提供的函数接口yylex()，在Bison中，必要的时候调用yylex()获得词法解析的数据，完成自己的语法解析。Bison的入口时yyparse()，在MySQL中是，MYSQLParse。

如果对词法分析和语法规则模块感到陌生，建议阅读参考文献[4][5][6]先^注1，否则很难理解整个架构，或者至少会有很强的断层感。而且，根据Bison的Action追踪MySQL数据的存储结构是很有效的。

1.2 MySQL语法解析Sample与示意图

简单的解析过程可以使用下面的示意图说明：

具体的解析一个SQL语句的WHERE部分:

2 SQL语句到MySQL的内部对象

Bison在做语法解析后，会将解析结果（一颗解析树/AST）存储在THD::LEX中。这里将通过考察存储WHERE的数据结构来查看语法解析的结果。

2.1 著名的Item对象

在了解MySQL的解析树之前，我们需要先来认识一个重要的数据结构Item。这是一个基础对象，在优化器部分代码，满地都是。在MySQL Internal Manual中也单独介绍：The Item Class。

Item是一个基础类，在他的基础上派生了很多子孙。这些子类基本描述所有SQL语句中的对象，他们包括：

• 一个文本字符串/数值对象
• 一个数据表的某一列（例如，select c1,c2 from dual...中的c1，c2）
• 一个比较动作，例如c1>10
• 一个WHERE子句的所有信息
• ......

可以看到，Item基本上代码SQL语句中的所有对象。在语法解析树中，这些Item以一颗树的形式存在。示意图如下：

2.2 Bison语法中的WHERE

从SELECT子句开始，我们看到对应的where_clause就是我们关注的WHERE：

我们来看看Bison中的几个重要的Action^参考注1：

where_clause: /* empty */ {} | WHERE expr { THD->lex->current_select->where = $2 } expr: ... | expr and expr { $$ = new (YYTHD->mem_root) Item_cond_and($1, $3) } |ident comp_op NUM /*这一行并不是源码的一部分，便于理解简化如此*/ { $$ = new Item_func_ge(a, b); /*这一行并不是源码的一部分，便于理解简化如此*/ }

根据这里的Bison语法，就可以生产上面的WHERE语法树了。如果你是和我一样刚刚了解Flex/Bison/AST，一定也会决定很巧妙！

2.3 WHERE的数据结构和他们之间的关系

绘制了下面的关系图用来描述WHERE和WHERE解析树的各个分支：

例如WHERE条件WHERE c1="orczhou" and c2 > 10，WHERE本身(lex->select->where)就是一个Item_cond_and对象，这个对象中有一个Item List，将List中每一个Item的值做AND运输，也就是这个WHERE的取值了。

这里，WHERE的List中有两个Item对象，分别代表了c1="orczhou"和c2 > 10。具体的，这两个对象的类型分别是Item_func_eq和Item_func_gt。

再单独看看Item_func_gt(代表c2 > 10)对象，这个对象由Item_func派生而来（当然追根朔源都是Item的孩儿们），这个对象有成员：Item **args。args则存放了比较操作需要使用的Item。

对于c2 > 10，这个不等式中有两个Item，分别代表字段c2和整数10，存储这两个对象的类型分别是：Item_field和Item_int。

2.4 通过GDB打印WHERE对象

WHERE条件是：WHERE id = 531389273 AND   reg_date > ‘2012-02-12 09‘;

打印WHERE中的List

(gdb) p ((Item_cond *)select_lex->where)->list $13 = { <base_list> = { <Sql_alloc> = {<No data fields>}, members of base_list: first = 0x7f5bbc005860, last = 0x7f5bbc005870, elements = 2 }

因为WHERE有两个判断，所以这里list中有两个元素。

打印list中的第一个判断（id = 531389273）

(gdb) p *(Item_func *)((Item_cond *)select_lex->where)->list->first->info $69 = { <Item_result_field> = { <Item> = { ...... next = 0x7f2134005320, ...... }, ...... }, members of Item_func: args = 0x7f2134005420, tmp_arg = {0x7f2134005228, 0x7f2134005320}, arg_count = 2, ....... }

这里等于操作有两个操作元素（arg_count=2），并以数组的形式存储在args中

打印上面等式的第一个对象（也就是id）

打印第一个Item的类型 p ((Item_func *)((Item_cond *)select_lex->where)->list->first->info)->args[0]->type() $74 = Item::FIELD_ITEM 将第一个Item转换成正确的类型再打印 p *(Item_field *)((Item_func *)((Item_cond *)select_lex->where)->list->first->info)->args[0] $78 = { <Item_ident> = { <Item> = { ....... name = 0x7f2134005208 "id", ...... }, ...... members of Item_ident: orig_field_name = 0x7f2134005208 "id", field_name = 0x7f2134005208 "id", ....... }, members of Item_field: field = 0x0, result_field = 0x0, ....... }

可以看到这里的id对象的类型是Item::FIELD_ITEM，也就是Item_field类型。

3 关于Item对象

继续从存储WHERE的Item_cond_and对象开始：

(点击可以查看大图)

看到Item_cond_and的继承关系：Item_cond->Item_bool_func->......->Item_result_filed->Item

Item一个很重要的成员函数就是type，所以在gdb的时候如果不清楚Item的类型，可以调用该方法确定：

(gdb) p ((*(Item_func *)thd->lex->current_select->where)->tmp_arg[0])->type() $42 = Item::FIELD_ITEM

这篇文章就到这吧，希望能够继续下去。

参考

[1]OReilly Understanding MySQL Internals

[2]The Skeleton of the Server Code@MySQL Internals Manual

[3]探索MYSQL源代码–SQL历险记@by hoterran

[4]mysql源码分析之网络连接流程@by Timchou

[5]Using Flex and Bison by Aaron Montgomery（由浅到深，较为完整的介绍）

[6]OReilly By John Levine （完整的介绍）

[7]Tutorial@by Aaron Myles Landwehr （简洁明了的介绍）

[8] MySQL Source Code

[注1] 我以前从未了解编译原理、语法解析相关的知识，这次恶补了一下，如果你也一样，那么建议阅读参考文件中的[4][5][6]，我天资平平，大约花费了一周/二十个小时左右