Mysql源码学习——词法分析MYSQLlex

 

 

词法分析MYSQLlex

语法分析——YACC

 

 

      
客户端向服务器发送过来SQL语句后,服务器首先要进行词法分析,而后进行语法分析,语义分析,构造执行树,生成执行计划。词法分析是第一阶段,虽然在理解Mysql实现上意义不是很大,但作为基础还是学习下比较好。

        
接触过SQL语句的人都会看过这家或者那家的SQL手册,其语法标准应该是从SQL92开始吧,在看SQL92标准的时候,你会发现里面定义的都是一些巴科斯范式(BNF),就是一种语法定义的标准。不管是牛X哄哄的ORACLE,还是不幸被其收购的Mysql,都会遵循里面的标准语法,当然一些扩展的语法除外,比如今天我们就会扩展一个简单的语法^-^。

 

 

词法分析即将输入的语句进行分词(token),解析出每个token的意义。分词的本质便是正则表达式的匹配过程,比较流行的分词工具应该是lex,通过简单的规则制定,来实现分词。Lex一般和yacc结合使用。关于lex和yacc的基础知识请参考Yacc
与Lex 快速入门- IBM。如果想深入学习的话,可以看下《LEX与YACC》。

        
OK,大家知道了SQL语法的来源,那么如何进行语法解析呢?YACC!!(Yet
Another Compiler
Compiler),它的书写方式便是BNF,语法解析的利器。YACC接收来自词法分析阶段分解出来的token,然后去匹配那些BNF。今天哥就来揭开它的面纱。(关于YACC的基本使用方法,大家可以看我上一篇中提到IBM的链接,一定要看懂那个先)

 

 

然而Mysql并没有使用lex来实现词法分析,但是语法分析却用了yacc,而yacc需要词法分析函数yylex,故在sql_yacc.cc文件最前面我们可以看到如下的宏定义:

         继续上一节的语句SELECT
@@VERSION_COMMET,为了简单,这里省去后缀limit
1。Mysql的语法文件是sql_yacc.yy,首先给出这条语句涉及到的语法节点(大体浏览下即可):

 

 

/* Substitute the variable and function names.  */

?

#define yyparse         MYSQLparse

 query:

#define yylex           MYSQLlex

END_OF_INPUT

 

{…}

  这里的MYSQLlex也就是本文的重点,即MYSQL自己的词法分析程序。源码版本5.1.48。源码太长,贴不上来,算啦..在sql_lex.cc里面。

|| verb_clause

 

{…}

  我们第一次进入词法分析,state默认值为MY_LEX_START,就是开始状态了,其实state的宏的意义可以从名称上猜个差不多,再比如MY_LEX_IDEN便是标识符。对START状态的处理伪代码如下:

| verb_clause END_OF_INPUT

 

          {

case MY_LEX_START:

            /* Single query, not terminated. */

{

            YYLIP->found_semicolon= NULL;

Skip空格

          }

获取第一个有效字符c

 

state = state_map[c];

verb_clause:

Break;

          statement

}

        | begin

 

        ;

  我困惑了,这尼玛肿么出来个state_map?找到了在函数开始出有个赋值的地方:

 

 

statement:

uchar *state_map= cs->state_map;

          alter

  cs?!不会是反恐精英吧!!快速监视下cs为my_charset_latin1,哥了然了,原来cs是latin字符集,character
set的缩写吧。那么为神马state_map可以直接决定状态?找到其赋值的地方,在init_state_maps函数中,代码如下所示:

        | analyze

 

        | backup

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

        | binlog_base64_event

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

        | call

  {

        | change

    if (my_isalpha(cs,i))

        | check

      state_map[i]=(uchar) MY_LEX_IDENT;

        | checksum

    else if (my_isdigit(cs,i))

        | commit

      state_map[i]=(uchar) MY_LEX_NUMBER_IDENT;

        | create

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

        | deallocate

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

        | delete

      state_map[i]=(uchar) MY_LEX_IDENT;

        | describe

#endif

        | do

    else if (my_isspace(cs,i))

        | drop

      state_map[i]=(uchar) MY_LEX_SKIP;

        | execute

    else

        | flush

      state_map[i]=(uchar) MY_LEX_CHAR;

        | grant

  }

        | handler

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

        | help

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

        | insert

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

        | install

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

        | kill

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

        | load

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

        | lock

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

        | optimize

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

        | keycache

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

        | partition_entry

  state_map[0]=(uchar) MY_LEX_EOL;

        | preload

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

        | prepare

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

        | purge

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

        | release

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

        | rename

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

        | repair

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

        | replace

 

        | reset

  先来看这个for循环,256应该是256个字符了,每个字符的处理应该如下规则:如果是字母,则state
= MY_LEX_IDENT;如果是数字,则state =
MY_LEX_NUMBER_IDENT,如果是空格,则state =
MY_LEX_SKIP,剩下的全为MY_LEX_CHAR。 

        | restore

       for循环之后,又对一些特殊字符进行了处理,由于我们的语句“select
@@version_comment limit
1”中有个特殊字符@,这个字符的state进行了特殊处理,为MY_LEX_USER_END。

        | revoke

对于my_isalpha等这几个函数是如何进行判断一个字符属于什么范畴的呢?跟进去看下,发现是宏定义:

        | rollback

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

        | savepoint

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

        | select

#define    _MY_U   01    /* Upper case */

        | set

#define    _MY_L   02    /* Lower case */

        | show

 

        | slave

  ctype里面到底存放了什么?在ctype-latin1.c源文件里面,我们找到了my_charset_latin1字符集的初始值:

        | start

 

        | truncate

CHARSET_INFO my_charset_latin1=

        | uninstall

{

        | unlock

    8,0,0,                           /* number    */

        | update

    MY_CS_COMPILED | MY_CS_PRIMARY, /* state     */

        | use

    “latin1”,                        /* cs name    */

        | xa

    “latin1_swedish_ci”,              /* name      */

        ;

    “”,                                /* comment   */

 

    NULL,                         /* tailoring */

select:

    ctype_latin1,

          select_init

    to_lower_latin1,

          {

    to_upper_latin1,

            LEX *lex= Lex;

    sort_order_latin1,

            lex->sql_command= SQLCOM_SELECT;

    NULL,           /* contractions */

          }

    NULL,           /* sort_order_big*/

        ;

    cs_to_uni,             /* tab_to_uni   */

 

    NULL,           /* tab_from_uni */

select_init:

    my_unicase_default, /* caseinfo     */

          SELECT_SYM select_init2

    NULL,           /* state_map    */

        | ‘(‘ select_paren ‘)’ union_opt

    NULL,           /* ident_map    */

        ;

    1,                  /* strxfrm_multiply */

 

    1,                  /* caseup_multiply  */

 

    1,                  /* casedn_multiply  */

select_init2:

    1,                  /* mbminlen   */

          select_part2

    1,                  /* mbmaxlen  */

          {

    0,                  /* min_sort_char */

            LEX *lex= Lex;

    255,        /* max_sort_char */

            SELECT_LEX * sel= lex->current_select;

    ‘ ‘,                /* pad char      */

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

    0,                  /* escape_with_backslash_is_dangerous */

            {

    &my_charset_handler,

              my_parse_error(ER(ER_SYNTAX_ERROR));

    &my_collation_8bit_simple_ci_handler

              MYSQL_YYABORT;

};

            }

 

            if (sel->linkage == UNION_TYPE &&

  可以看出ctype = ctype_latin1;而ctype_latin1值为:

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

 

            {

static uchar ctype_latin1[] = {

              my_parse_error(ER(ER_SYNTAX_ERROR));

    0,

              MYSQL_YYABORT;

   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,

          }

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

          union_clause

  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,

 

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

select_part2:

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

          {

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

            LEX *lex= Lex;

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

            SELECT_LEX *sel= lex->current_select;

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

            if (sel->linkage != UNION_TYPE)

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

              mysql_init_select(lex);

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

            lex->current_select->parsing_place= SELECT_LIST;

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

          }

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

          select_options select_item_list

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

          {

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

            Select->parsing_place= NO_MATTER;

};

          }

 

          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里面第66个(略过第一个无意义的0)元素,为129

10000001,显然第0位为1(右边起),说明为大写字母。写代码的人确实比较牛X,如此运用位,哥估计这辈子也想不到了,小小佩服下。State的问题点到为止了。

 

继续进行词法分析,第一个字母为s,其state =
MY_LEX_IDENT(IDENTIFIER:标识符的意思),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_KEYWORD,再之后便是解析MY_LEX_IDENT_OR_KEYWORD了,也就是version_comment了,此解析应该和SELECT解析路径一致,但不是KEYWORD。剩下的留给有心的读者了(想起了歌手经常说的一句话:大家一起来,哈哈)。

 

Mysql的词法解析的状态还是比较多的,如果细究还是需要点时间的,但这不是Mysql的重点,我就浅尝辄止了。下节会针对上面的SQL语句讲解下语法分析。

 

PS:
一直想好好学习下Mysql,总是被这样或那样的事耽误,当然都是自己的原因,希望这次能走的远点…..

 

PS again:本文只代表本人的学习感悟,如有异议,欢迎指正。

 

摘自 心中无码

http://www.bkjia.com/Mysql/489352.htmlwww.bkjia.comtruehttp://www.bkjia.com/Mysql/489352.htmlTechArticle词法分析MYSQLlex
客户端向服务器发送过来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

          {

            $$= $3;

          }

        ;

 

variable_aux:

          ident_or_text SET_VAR expr

          {

            Item_func_set_user_var *item;

            $$= item= new (YYTHD->mem_root)
Item_func_set_user_var($1, $3);

            if ($$ == NULL)

              MYSQL_YYABORT;

            LEX *lex= Lex;

            lex->uncacheable(UNCACHEABLE_RAND);

            lex->set_var_list.push_back(item);

          }

        | ident_or_text

          {

            $$= new (YYTHD->mem_root)
Item_func_get_user_var($1);

            if ($$ == NULL)

              MYSQL_YYABORT;

            LEX *lex= Lex;

            lex->uncacheable(UNCACHEABLE_RAND);

          }

        | ‘@’ opt_var_ident_type ident_or_text opt_component

          {

            /* disallow “SELECT @@global.global.variable” */

            if ($3.str && $4.str && check_reserved_words(&$3))

            {

              my_parse_error(ER(ER_SYNTAX_ERROR));

              MYSQL_YYABORT;

            }

            if (!($$= get_system_var(YYTHD, $2, $3, $4)))

              MYSQL_YYABORT;

            if (!((Item_func_get_system_var*)
$$)->is_written_to_binlog())

              Lex->set_stmt_unsafe();

          }

        ;

下面我们仔细的来看一下整个SELECT语法节点的执行流程:

 

?

query->verb_clause->statement->select->select_init->select_init2->select_part2->select_item_list->select_item…->variable

语法是自上而下的,实际的解析过程是自下而上的匹配过程。词法分析首先yacc送来SELECT关键字,上一节说过为什么SELECT是关键字呢?

 

我们看下sql_yacc.yy,可以找到如下一个定义:

 

?

%token  SELECT_SYM                    /* SQL-2003-R */

这里其实是定义了一个宏SELECT_SYM,代表一个关键字,宏定义如下:

 

?

#define SELECT_SYM 687

那么字符串”SELECT”和SELECT_SYM是如何联系在一起的呢?我们回头看下MYSQLlex中的find_keyword这个函数:

?

static int find_keyword(Lex_input_stream *lip, uint len, bool
function)

{

  const char *tok= lip->get_tok_start();

 

  SYMBOL *symbol= get_hash_symbol(tok, len, function);

  if (symbol)

  {

    lip->yylval->symbol.symbol=symbol;

    lip->yylval->symbol.str= (char*) tok;

    lip->yylval->symbol.length=len;

 

    if ((symbol->tok == NOT_SYM) &&

        (lip->m_thd->variables.sql_mode &
MODE_HIGH_NOT_PRECEDENCE))

      return NOT2_SYM;

    if ((symbol->tok == OR_OR_SYM) &&

    !(lip->m_thd->variables.sql_mode & MODE_PIPES_AS_CONCAT))

      return OR2_SYM;

 

    return symbol->tok;

  }

  return 0;

}

 

static SYMBOL *get_hash_symbol(const char *s,

                               unsigned int len,bool function)

{

  register uchar *hash_map;

  register const char *cur_str= s;

 

  if (len == 0) {

    DBUG_PRINT(“warning”, (“get_hash_symbol() received a request for
a zero-length symbol, which is probably a mistake.”));

    return(NULL);

  }

  if (function){

    if (len>sql_functions_max_len) return 0;

    hash_map= sql_functions_map;

    register uint32 cur_struct= uint4korr(hash_map+((len-1)*4));