MySQL的词法分析漫谈

 

其一链接上稍稍介绍,能够驾驭个大要:

 

语法深入分析——YACC

关键点:

词法剖判MYSQLlex

 

  1. SQL剖析包蕴语法深入分析器和词法深入分析器。
    方便人民群众的做法是用bison/flex组合。可是MySQL的词法深入分析器是手工业制作的。
    语法剖判器的入口函数是MYSQLparse,词法深入分析器的入口函数是MYSQLlex。
  2. 词法深入分析中会检查token是还是不是为机要字。
    最直白的做法是弄个大的严重性字数组,进行折半查找。MySQL在此做了些优化。
    正文首要介绍的是这一有的。

 

        
接触过SQL语句的人都会看过这家或许那家的SQL手册,其语法标准应该是从SQL92先导吧,在看SQL92行业内部的时候,你会意识内部定义的都以部分巴科斯范式(BNF),就是一种语法定义的标准。不管是牛X哄哄的ORACLE,照旧不幸被其收购的Mysql,都会服从里面包车型大巴专门的学问语法,当然有个别扩展的语法除却,例如前天大家就能够扩展学一年级个归纳的语法^-^。

思虑到根本字是一个只读的列表,对它做贰个只读的探究树能够改进查找的属性。
爆发查找树:

      
客户端向服务器发送过来SQL语句后,服务器首先要进行词法剖判,而后实行语法深入分析,语义深入分析,构造实践树,生成实践安顿。词法深入分析是第一阶段,即使在知情Mysql完毕上意义不是极大,但作为基础还是学习下相比好。

 

  1. 读取关键字数组,发生贰个Trie树。
  2. 调节那棵树,并发出多少个数组(也正是多个不用链表表示的树)。

 

        
OK,大家清楚了SQL语法的来源,那么怎么着进展语法深入分析呢?YACC!!(Yet
Another Compiler
Compiler),它的书写情势正是BNF,语法深入分析的利器。YACC接收来自词法解析阶段分解出来的token,然后去相配这几个BNF。前几日哥就来揭秘它的面纱。(关于YACC的主干使用方法,我们能够看本人上一篇中提到IBM的链接,必须求看懂那多少个先)

选用查找树:
其一比较轻便,直接看函数get_hash_symbol好了。

词法深入分析将在输入的语句实行分词(token),分析出各个token的意思。分词的本来面目就是正则表明式的非常进程,相比较流行的分词工具应该是lex,通过轻巧的规则制定,来实现分词。Lex一般和yacc结合使用。关于lex和yacc的基础知识请参照他事他说加以考察Yacc
与Lex 快捷入门- IBM。如若想深切学习的话,可以看下《LEX与YACC》。

 

发生查找树,相关的Makefile规则:
In `sql/CMakeFiles/sql.dir/build.make’:

 

         继续上一节的语句SELECT
@@VE本田CR-VSION_COMMET,为了轻易,这里省去后缀limit
1。Mysql的语法文件是sql_yacc.yy,首先付诸那条语句涉及到的语法节点(概略浏览下就能够):

sql/lex_hash.h: sql/gen_lex_hash
$(CMAKE_COMMAND) -E cmake_progress_report
/home/zedware/Workspace/mysql/CMakeFiles $(CMAKE_PROGRESS_153)
@$(CMAKE_COMMAND) -E cmake_echo_color –switch=$(COLOR) –blue –bold
“Generating lex_hash.h”
cd /home/zedware/Workspace/mysql/sql && ./gen_lex_hash >
lex_hash.h

可是Mysql并从未行使lex来达成词法深入分析,但是语法解析却用了yacc,而yacc须求词法深入分析函数yylex,故在sql_yacc.cc文件最前面大家能够看看如下的宏定义:

 

轻松觉察,最根本的函数便是`get_hash_symbol’,它至关心珍视要的调用关系为:

 

?

/* sql/lex_hash.h */
get_hash_symbol->sql_functions_map
get_hash_symbol->symbols_map

/* Substitute the variable and function names.  */

 query:

/* sql/sql_lex.cc */
find_keyword->get_hash_symbol
is_keyword->get_hash_symbol
is_lex_native_function->get_hash_symbol

#define yyparse         MYSQLparse

END_OF_INPUT

文件”gen_lex_hash.cc”注释中的树的言传身教:

#define yylex           MYSQLlex

{…}

+———–+-+-+-+
| len |1|2|3|
+———–+-+-+-+
|first_char |0|0|a|
|last_char |0|0|d|
|link |0|0|+|
|
V
+———-+-+-+-+–+
| 1 char|a|b|c|d |
+———-+-+-+-+–+
|first_char|d|0|0|0 |
|last_char |n|0|0|-1|
|link |+|0|0|+ |
| |
| V
| symbols[2] ( “DAY” )
V
+———-+–+-+-+-+-+-+-+-+-+-+–+
| 2 char|d |e|f|j|h|i|j|k|l|m|n |
+———-+–+-+-+-+-+-+-+-+-+-+–+
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
|link |+ |0|0|0|0|0|0|0|0|0|+ |
| |
V V
symbols[0] ( “ADD” ) symbols[1] ( “AND” )

 

|| verb_clause

假令你还记得Trie树,通晓起来会轻松一点。上面是见仁见智的输入数组对应的树。
i=0

  这里的MYSQLlex也正是本文的机要,即MYSQL本人的词法剖判程序。源码版本5.1.48。源码太长,贴不上去,算啦..在sql_lex.cc里面。

{…}

+———–+-+–+
| len |1| 2|
+———–+-+–+
|first_char |0|-1|
|last_char |0| 0|
|char_tails |0| x|
|ithis |0| 0|
|iresult |0| 0|
|
&&

 

| verb_clause END_OF_INPUT

static SYMBOL symbols[] = {
{ “&&”, SYM(AND_AND_SYM)},

  大家第一回进入词法深入分析,state暗许值为MY_LEX_START,正是始于景况了,其实state的宏的意义可以从名称上猜个大约,再例如说MY_LEX_IDEN正是标记符。对START状态的拍卖伪代码如下:

          {

static uchar symbols_map[8]= {
0, 0, 1, 0, <=== 1 == symbols[]数组的要素个数,表示没找到
0, 0, 0, 0, <=== symbols[0]
};

 

            /* Single query, not terminated. */

i=1

case MY_LEX_START:

            YYLIP->found_semicolon= NULL;

+———–+–+–+
| len | 1| 2|
+———–+–+–+
|first_char |-1|-1|
|last_char | 0| 0|
|char_tails | x| x|
|ithis | 0| 0|
|iresult | 1| 0|
| |
< &&

{

          }

static SYMBOL symbols[] = {
{ “&&”, SYM(AND_AND_SYM)},
{ “<“, SYM(LT)},

Skip空格

 

static uchar symbols_map[8]= {
0, 0, 1, 0, <=== 1 <
symbols[]数组的要素个数2,戫示找到的正是symbols[1]
0, 0, 0, 0, <=== symbols[0]
};

赢得第三个有效字符c

verb_clause:

i=2

state = state_map[c];

          statement

+———–+–+–+
| len | 1| 2|
+———–+–+–+
|first_char |-1| &|
|last_char | 0| <|
|char_tails | x| ^|
|ithis | 0| 0|
|iresult | 1| x|
| |
< |
|
+———-+–+–+ +–+
| 1 char| &| |…| <|
+———-+–+–+ +–+
|first_char|-1| 0| |-1|
|last_char | 0| 0| | 0|
|char_tails| 0| 0| | x|
|ithis | 0| 0| | 0|
|iresult | 0| 0| | 2|
| |
&& <=

Break;

        | begin

static SYMBOL symbols[] = {
{ “&&”, SYM(AND_AND_SYM)},
{ “<“, SYM(LT)},
{ “<=”, SYM(LE)},

}

        ;

static uchar symbols_map[100]= {
0, 0, 1, 0,
‘&’, ‘<‘, 2, 0,
0, 0, 0, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 2, 0,
};

 

 

i=3

  笔者思疑了,那尼玛肿么出来个state_map?找到了在函数初叶出有个赋值的地点:

statement:

+———–+–+–+
| len | 1| 2|
+———–+–+–+
|first_char |-1| &|
|last_char | 0| <|
|char_tails | x| ^|
|ithis | 0| 0|
|iresult | 1| x|
| |
< |
|
+———-+–+–+ +–+
| 1 char| &| |…| <|
+———-+–+–+ +–+
|first_char|-1| 0| |-1|
|last_char | 0| 0| | 0|
|char_tails| 0| 0| | x|
|ithis | 0| 0| | 0|
|iresult | 0| 0| | p|
| |
&& |
|
+———-+–+–+
| 2 char| =| >|
+———-+–+–+
|first_char|-1|-1|
|last_char | 0| 0|
|char_tails| x| x|
|ithis | 0| 0|
|iresult | 2| 3|
| |
<= <>

 

          alter

static SYMBOL symbols[] = {
{ “&&”, SYM(AND_AND_SYM)},
{ “<“, SYM(LT)},
{ “<=”, SYM(LE)},
{ “<>”, SYM(NE)},

uchar *state_map= cs->state_map;

        | analyze

static uchar symbols_map[108]= {
0, 0, 1, 0,
‘&’, ‘<‘, 2, 0,
0, 0, 0, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
‘=’, ‘>’, 25, 0,
0, 0, 2, 0,
0, 0, 3, 0,
};

  cs?!不会是CS:GO吧!!急速监视下cs为my_charset_latin1,哥领会了,原本cs是latin字符集,character
set的缩写吧。那么为神马state_map能够一直调控状态?找到其赋值的地点,在init_state_maps函数中,代码如下所示:

        | backup

能够见见,数组表示中留存一定的上空浪费。尽管不怕麻烦,大家仍可以去榨出一点油水来。

 

        | binlog_base64_event

关键点: 1. SQL解析包括语法分析器和词法解析器。 简便的做法…

/* Fill state_map with states to get a faster parser */

        | call

  for (i=0; i < 256 ; i++)

        | change

  {

        | check

    if (my_isalpha(cs,i))

        | checksum

      state_map[i]=(uchar) MY_LEX_IDENT;

        | commit

    else if (my_isdigit(cs,i))

        | create

      state_map[i]=(uchar) MY_LEX_NUMBER_IDENT;

        | deallocate

#if defined(USE_MB) && defined(USE_MB_IDENT)

        | delete

    else if (my_mbcharlen(cs, i)>1)

        | describe

      state_map[i]=(uchar) MY_LEX_IDENT;

        | do

#endif

        | drop

    else if (my_isspace(cs,i))

        | execute

      state_map[i]=(uchar) MY_LEX_SKIP;

        | flush

    else

        | grant

      state_map[i]=(uchar) MY_LEX_CHAR;

        | handler

  }

        | help

  state_map[(uchar)’_’]=state_map[(uchar)’$’]=(uchar)
MY_LEX_IDENT;

        | insert

  state_map[(uchar)’\”]=(uchar) MY_LEX_STRING;

        | install

  state_map[(uchar)’.’]=(uchar) MY_LEX_REAL_OR_POINT;

        | kill

 
state_map[(uchar)’>’]=state_map[(uchar)’=’]=state_map[(uchar)’!’]=
(uchar) MY_LEX_CMP_OP;

        | load

  state_map[(uchar)'<‘]= (uchar) MY_LEX_LONG_CMP_OP;

        | lock

  state_map[(uchar)’&’]=state_map[(uchar)’|’]=(uchar)
MY_LEX_BOOL;

        | optimize

  state_map[(uchar)’#’]=(uchar) MY_LEX_COMMENT;

        | keycache

  state_map[(uchar)’;’]=(uchar) MY_LEX_SEMICOLON;

        | partition_entry

  state_map[(uchar)’:’]=(uchar) MY_LEX_SET_VAR;

        | preload

  state_map[0]=(uchar) MY_LEX_EOL;

        | prepare

  state_map[(uchar)’\\’]= (uchar) MY_LEX_ESCAPE;

        | purge

  state_map[(uchar)’/’]= (uchar) MY_LEX_LONG_COMMENT;

        | release

  state_map[(uchar)’*’]= (uchar) MY_LEX_END_LONG_COMMENT;

        | rename

  state_map[(uchar)’@’]= (uchar) MY_LEX_USER_END;

        | repair

  state_map[(uchar) ‘`’]= (uchar)
MY_LEX_USER_VARIABLE_DELIMITER;

        | replace

  state_map[(uchar)'”‘]= (uchar) MY_LEX_STRING_OR_DELIMITER;

        | reset

 

        | restore

  先来看这么些for循环,256应当是2伍十九个字符了,各个字符的处理相应如下规则:要是是字母,则state
= MY_LEX_IDENT;假若是数字,则state =
MY_LEX_NUMBER_IDENT,要是是空格,则state =
MY_LEX_SKIP,剩下的全为MY_LEX_CHAR。 

        | revoke

       for循环之后,又对有的特殊字符举行了拍卖,由于大家的语句“select
@@version_comment limit
1”中有个独树一帜字符@,那个字符的state实行了极度管理,为MY_LEX_USER_END。

        | rollback

对于my_is阿尔法等那多少个函数是何等实行判别三个字符属于怎么规模的呢?跟进去看下,开掘是宏定义:

        | savepoint

#define    my_isalpha(s, c)  (((s)->ctype+1)[(uchar) (c)] &
(_MY_U | _MY_L))

        | select

Wtf,肿么又来了个ctype,c作为ctype的下标,_MY_U | _MY_L如下所示,

        | set

#define    _MY_U   01    /* Upper case */

        | show

#define    _MY_L   02    /* Lower case */

        | slave

 

        | start

  ctype里面究竟存放了何等?在ctype-latin1.c源文件之中,大家找到了my_charset_latin1字符集的初步值:

        | truncate

 

        | uninstall

CHARSET_INFO my_charset_latin1=

        | unlock

{

        | update

    8,0,0,                           /* number    */

        | use

    MY_CS_COMPILED | MY_CS_PRIMARY, /* state     */

        | xa

    “latin1”,                        /* cs name    */

        ;

    “latin1_swedish_ci”,              /* name      */

 

    “”,                                /* comment   */

select:

    NULL,                         /* tailoring */

          select_init

    ctype_latin1,

          {

    to_lower_latin1,

            LEX *lex= Lex;

    to_upper_latin1,

            lex->sql_command= SQLCOM_SELECT;

    sort_order_latin1,

          }

    NULL,           /* contractions */

        ;

    NULL,           /* sort_order_big*/

 

    cs_to_uni,             /* tab_to_uni   */

select_init:

    NULL,           /* tab_from_uni */

          SELECT_SYM select_init2

    my_unicase_default, /* caseinfo     */

        | ‘(‘ select_paren ‘)’ union_opt

    NULL,           /* state_map    */

        ;

    NULL,           /* ident_map    */

 

    1,                  /* strxfrm_multiply */

 

    1,                  /* caseup_multiply  */

select_init2:

    1,                  /* casedn_multiply  */

          select_part2

    1,                  /* mbminlen   */

          {

    1,                  /* mbmaxlen  */

            LEX *lex= Lex;

    0,                  /* min_sort_char */

            SELECT_LEX * sel= lex->current_select;

    255,        /* max_sort_char */

            if (lex->current_select->set_braces(0))

    ‘ ‘,                /* pad char      */

            {

    0,                  /* escape_with_backslash_is_dangerous */

              my_parse_error(ER(ER_SYNTAX_ERROR));

    &my_charset_handler,

              MYSQL_YYABORT;

    &my_collation_8bit_simple_ci_handler

            }

};

            if (sel->linkage == UNION_TYPE &&

 

                sel->master_unit()->first_select()->braces)

  能够见见ctype = ctype_latin1;而ctype_latin1值为:

            {

 

              my_parse_error(ER(ER_SYNTAX_ERROR));

static uchar ctype_latin1[] = {

              MYSQL_YYABORT;

    0,

            }

   32, 32, 32, 32, 32, 32, 32, 32, 32, 40, 40, 40, 40, 40, 32, 32,

          }

   32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,

          union_clause

   72, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,

        ;

  132,132,132,132,132,132,132,132,132,132, 16, 16, 16, 16, 16, 16,

 

   16,129,129,129,129,129,129,  1,  1,  1,  1,  1,  1,  1,  1,  1,

select_part2:

    1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 16, 16, 16, 16, 16,

          {

   16,130,130,130,130,130,130,  2,  2,  2,  2,  2,  2,  2,  2,  2,

            LEX *lex= Lex;

    2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2, 16, 16, 16, 16, 32,

            SELECT_LEX *sel= lex->current_select;

   16,  0, 16,  2, 16, 16, 16, 16, 16, 16,  1, 16,  1,  0,  1,  0,

            if (sel->linkage != UNION_TYPE)

    0, 16, 16, 16, 16, 16, 16, 16, 16, 16,  2, 16,  2,  0,  2,  1,

              mysql_init_select(lex);

   72, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,

            lex->current_select->parsing_place= SELECT_LIST;

   16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,

          }

    1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,

          select_options select_item_list

    1,  1,  1,  1,  1,  1,  1, 16,  1,  1,  1,  1,  1,  1,  1,  2,

          {

    2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,

            Select->parsing_place= NO_MATTER;

    2,  2,  2,  2,  2,  2,  2, 16,  2,  2,  2,  2,  2,  2,  2,  2

          }

};

          select_into select_lock_type

 

        ;

  看到这里哥再二回知道了,这一个值都以经过预总括的,第贰个0是不行的,那也是为啥my_isalpha(s,

?

c)定义里面ctype要先+1的缘由。通过_MY_U和_MY_L的概念,能够清楚,这个值料定是比照相应的ASCII码的切实意思举办置位的。举个例子字符’A’,其ASCII码为65,其实大写字母,故一定具备_MY_U,即第0位必然为1,找到ctype里面第陆11个(略过第一个抽象的0)成分,为129

一千0001,分明第0位为1(右侧起),表达为大写字母。写代码的人真正比较牛X,如此运用位,哥推断那辈子也想不到了,小小钦佩下。State的标题点到告竣了。

 

传承拓展词法分析,第一个字母为s,其state =
MY_LEX_IDENT(IDENTIFIE冠道:标记符的意味),break出来,继续循环,case进入MY_LEX_IDENT分支:

 

Case MY_LEX_IDENT:

{

由s开端读,直到空格停止

If(读入的单词为首要字)

{

nextstate = MY_LEX_START;

Return tokval;        //关键字的唯一标志

}

Else

{

return IDENT_QUOTED 或许IDENT;表示为一般标记符

}

}

 

  这里SELECT分明为重要字,至于为何吗?下节的语法深入分析会讲。

 

剖判完SELECT后,必要分析@@version_comment,第七个字符为@,进入START分支,state
= MY_LEX_USER_END;

 

进入MY_LEX_USER_END分支,如下:

 

case MY_LEX_USER_END:        // end ‘@’ of
[email protected]

      switch (state_map[lip->yyPeek()]) {

      case MY_LEX_STRING:

      case MY_LEX_USER_VARIABLE_DELIMITER:

      case MY_LEX_STRING_OR_DELIMITER:

    break;

      case MY_LEX_USER_END:

    lip->next_state=MY_LEX_SYSTEM_VAR;

    break;

      default:

    lip->next_state=MY_LEX_HOSTNAME;

    break;

 

  哥会心的笑了,四个@符号正是系统变量吧~~,上面进入MY_LEX_SYSTEM_VAR分支

 

case MY_LEX_SYSTEM_VAR:

      yylval->lex_str.str=(char*) lip->get_ptr();

      yylval->lex_str.length=1;

      lip->yySkip();                                    // Skip ‘@’

      lip->next_state= (state_map[lip->yyPeek()] ==

            MY_LEX_USER_VARIABLE_DELIMITER ?

            MY_LEX_OPERATOR_OR_IDENT :

            MY_LEX_IDENT_OR_KEYWORD);

      return((int) ‘@’);

 

  所作的操作是略过@,next_state设置为MY_LEX_IDENT_OR_KEYWOMuranoD,再然后就是解析MY_LEX_IDENT_OR_KEYWORD了,也就是version_comment了,此剖析应该和SELECT解析路线一致,但不是KEYWO奥德赛D。剩下的留下有心的读者了(想起了明星平时说的一句话:大家共同来,哈哈)。

 

Mysql的词法深入分析的景况依旧相比多的,假诺细究依然要求点时间的,但那不是Mysql的根本,我就浅尝辄止了。下节会针对地点的SQL语句疏解下语法剖判。

 

PS:
一贯想好好学习下Mysql,总是被如此或那样的事拖延,当然都以自个儿的开始和结果,希望此番能走的远点…..

 

PS again:本文只表示本人的学习感悟,如有争议,迎接指正。

 

摘自 心中无码

客户端向服务器发送过来SQL语句后,服务器首先要开展词法剖析,而后实行语法深入分析,语义解析,构造试行树,生成施行计…

 

select_item_list:

          select_item_list ‘,’ select_item

        | select_item

        | ‘*’

          {

            THD *thd= YYTHD;

            Item *item= new (thd->mem_root)

                         
Item_field(&thd->lex->current_select->context,

                                     NULL, NULL, “*”);

            if (item == NULL)

              MYSQL_YYABORT;

            if (add_item_to_list(thd, item))

              MYSQL_YYABORT;

            (thd->lex->current_select->with_wild)++;

          }

        ;

 

select_item:

          remember_name select_item2 remember_end select_alias

          {

            THD *thd= YYTHD;

            DBUG_ASSERT($1 < $3);

 

            if (add_item_to_list(thd, $2))

              MYSQL_YYABORT;

            if ($4.str)

            {

              if (Lex->sql_command == SQLCOM_CREATE_VIEW &&

                  check_column_name($4.str))

              {

                my_error(ER_WRONG_COLUMN_NAME, MYF(0), $4.str);

                MYSQL_YYABORT;

              }

              $2->is_autogenerated_name= FALSE;

              $2->set_name($4.str, $4.length,
system_charset_info);

            }

            else if (!$2->name)

            {

              $2->set_name($1, (uint) ($3 – $1), thd->charset());

            }

          }

        ;

 

variable:

          ‘@’

          {

            if (! Lex->parsing_options.allows_variable)

            {

              my_error(ER_VIEW_SELECT_VARIABLE, MYF(0));

              MYSQL_YYABORT;

            }

          }

          variable_aux