数据库技术部作者

MySQL内核源码解读-SQL解析一

本文基于MySQL5.7.22进行分析。

1.    SQL总体执行流程图

通过上面图,可以从全局上了解SQL语句执行流程以及与其他模块交互。

1.1 SQL查询执行流程

2.    语法解析

2.1 编程语言知识回顾

在介绍具体的MySQL数据库解析SQL之前,先来回归一下编程语言的知识点

  • 1.  形式语言(Formal language)

形式语言是用精确的数学或机器可处理的公式定义的语言,个人理解形式语言就是符号化的语言,比如编程语言(C C++ JAVA PYTHON),都是定义一组符号来描述映射人的思维逻辑的,符号化的语言的好处就是能够准确表达所要表达的,不会产生二义性.

  • 2.  文法(grammar)

当我们要描述一种语言时,需要给出这种语言的所有句子,当句子的数目是有限可数时,就要都列出来;当句子是一个无穷集,也就是无限不可数时,就要给出可以表示它们的结构的描述方法或者说,句子的组成规则。这种规则就是文法。即从形式上用于描述和规定结构的称为文法(或者说语法), 也可以理解为指怎么由一堆符号组成一个有含义的句子的规则和协议.

  • 3.  上下文无关文法(context-free grammar)(数学描述)

一个四元数组G=(VN,VT,S,P):

VN:非空有限的非终结符集合VT:非空有限的终结符集

S:开始符号P:产生式集合

其中,VN∩VT=∅,S∈VN

P中产生式一般形式为A→α|β,其中A∈VN,α,β∈(VN∪VT)*

大写字母表示非终结符,小写字母表示终结符,α、β、γ等代表由 终结符和非终结符号的并集的闭包 中的元素 组成的符号串

上下文无关文法取名为“上下文无关”的原因就是因为字符A总可以被字串α或β自由替换,而无需考虑字符A出现的上下文

  • 4.  终结符(terminal symbol )

终结符是一个形式语言的基本符号。就是说,它们能在一个形式语法的推导规则的输入或输出字符串存在,而且它们不能被分解成更小的单位。可以理解为产生式推导到什么时候停止呢,推导到终止符为止.

  • 5.  非终结符(nonterminal symbol)

非终结符是可以被取代的符号。一个形式文法中必须有一个起始符号;这个起始符号属于非终结符的集合。在上下文无关文法中,每个推导规则的左边只能有一个非终结符而不能有两个以上的非终结符或终结符。

  • 6.  巴科斯范式(BNF: Backus-Naur Form)

以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法,用来描述语法的一种形式体系,是一种典型的元语言。又称巴科斯-诺尔形式(Backus-Naur form)。它不仅能严格地表示语法规则,而且所描述的语法是与上下文无关的。它具有语法简单,表示明确,便于语法分析和编译的特点。

编程语言的文法除了数学化的描述,还需要在在实际生产中易于描述的符号化语言,BNF就是用来描述上下文无关文法的符号化的语言.

2.2 概念与bison

2.1章节说明的概念跟bison又是一种什么关系呢?

bison是属于 GNU 项目的一个语法分析器生成器。

bison能够将上下文无文法解释语法分析表,由于兼容yacc,而yacc是BNF进行描述文法规则的, 所以可以理解为bison能够解析以BNF描述上下文无关文法语法分析器生成器.

2.3 MySQL与bison

MySQL使用bison作为其解析SQL语句的语法分析器.

2.4 SQL解析相关文件及关联

  • 1. 相关文件

SQL词法解析文件:

sql/sql_lex.h 、sql/lex_token.h 、sql/lex.h、 sql/lex_symbol.h、

sql/sql_lex.cc 、sql/ gen_lex_token.cc

SQL语法解析文件:

sql/sql_yacc.yy 、sql/sql_yacc.cc、 sql/sql_yacc.h

SQL语句的hint语法解析文件:

sql/sql_hints.yy 、sql/sql_hints.yy.cc

  • 2. 语法解析


3.    sql/sql_yacc.cc

3.1 sql_yacc.cc描述

sql_yacc.cc规定了SQL语句语法规则,定义了SQL语句的关键字.

3.2 sql_yacc.cc文件结构

%{

  Prologue

%}

Bison declarations

%%

Grammar rules

%%

Epilogue

  • 1.  Prologue部分包括宏定义和在语法规则动作中使用的函数和变量的声明. 这些将复制到分析器文件的开头以便先于yyparse的定义. 你可以使用`#include'来从头文件获取声明. 如果你不需要任何的C声明, 可以省略这个部分的括号分隔符`%{'和`%}', 这部分被BISON原封不动地复制到输出的.C文件中

  • 2.  Bison declatations部分包含了定义终结符和非终结符的声明,优先级等等

  • 3.  Grammar Rules部分包含了一个或多个Bison语法规则, 在这里至少应该有一个语法规则,并且第一个%%, 绝对不能省略,解释它在文件的最开头.

  • 4.  就像Prologue部分被复制到开头一样,Epilogue部分被逐字地复制到分析器文件的结尾. 如果你想放一些代码却没必要放在yyparse的定义之前,这里是最方便的地方. 如果最后一部分为空,你可以省略分隔它的分隔符%%.

3.3 sql_yacc.cc文件解析

3.3.1 Prologue部分

该部分包含了C语言的头文件,宏定义,该部分主要声明和定义了2个关键函数,如下:

int yylex(void *yylval, void *yythd);词法解析函数的声明

void MYSQLerror(YYLTYPE *, THD *thd, const char *s);语法分析错误函数的定义。

3.3.2 Bison declatations部分

本部分与prologue部分使用 %% 进行分隔

3.3.3 Grammar Rules部分

本部分与Bison declatations部分,使用 %% 进行分隔

例子分析:

Bison产生式: result: components…;

下面的例子就是一个产生式

query是产生式的左端, 冒号后面是产生式的右端, 代表或的意思, {}当query产生式推出右端情况的时候所执行的动作,一个产生式结束要是

其中query verb_clause 都是非终止符, END_OF_INPUT 是终止符, 也就是说产生式推导到终止符就停止推导.

即query->END_OF_INPUT | verb_clause | verb_clause END_OF_INPUT

query:

      END_OF_INPUT

      { THD *thd= YYTHD;

        if (!thd->bootstrap   &&!thd->m_parser_state->has_comment())

        {

            my_message(ER_EMPTY_QUERY,   ER(ER_EMPTY_QUERY), MYF(0));

            MYSQL_YYABORT;

        }

        thd->lex->sql_command=   SQLCOM_EMPTY_QUERY;

        YYLIP->found_semicolon= NULL;

      }

      |verb_clause

      { Lex_input_stream *lip = YYLIP;

        if   (YYTHD->get_protocol()->has_client_capability(CLIENT_MULTI_QUERIES)

            && lip->multi_statements &&  !lip->eof())

        {

          lip->next_state= MY_LEX_END;

          lip->found_semicolon=   lip->get_ptr();

        }

        else

        {

          lip->found_semicolon= NULL;

        }

      }

      ';'

      opt_end_of_input

     |verb_clause   END_OF_INPUT

     {

         YYLIP->found_semicolon= NULL;

     }

     ;

4.    参考资料

1.  《lex与yacc》(第二版)

2.  《flex与bison》(第二版)

3.   Bison操作手册:http://www.gnu.org/software/bison/manual/bison.html

京东
京东

京东是全球最大零售商之一,业务涵盖零售、数科、物流、保险和健康等,公司目标是基于海量数据的挖掘和计算,持续驱动业务增长

专栏二维码
理论语法分析器上下文无关文法SQL数据库MySQL
3
相关数据
元语言技术

广义来说,元语言是指讨论或研究语言本身时所使用的语言或符号。在逻辑和语言学里,元语言是用来对其他语言的句子形成另一个句子的语言。元语言通常会用斜体字、引号或写在单独一行里来和对象语言相区别

非终结符技术

终结符和非终结符在计算机科学和语言学的领域是用来指定推导规则的元素。在某个形式语法之中,终结符和非终结符是两个不交的集合。

数据库技术

数据库,简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

上下文无关文法技术

上下文无关文法,在计算机科学中,若一个形式文法 G = 的产生式规则都取如下的形式:V -> w,则谓之。其中 V∈N,w∈* 。上下文无关文法取名为“上下文无关”的原因就是因为字符V 总可以被字串w 自由替换,而无需考虑字符V 出现的上下文。

Prolog技术

Prolog是一种逻辑编程语言。它创建在逻辑学的理论基础之上, 最初被运用于自然语言等研究领域。现在它已广泛的应用在人工智能的研究中,它可以用来建造专家系统、自然语言理解、智能知识库等。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

语法分析器技术

在计算机科学和语言学中,语法分析是根据某种给定的形式文法对由单词序列构成的输入文本进行分析并确定其语法结构的一种过程。 语法分析器通常是作为编译器或解释器的组件出现的,它的作用是进行语法检查、并构建由输入的单词组成的数据结构。

暂无评论
暂无评论~