Mysql源碼學習——打造專屬語法

 

語法分析——YACC

 

         接觸過SQL語句的人都會看過這傢或者那傢的SQL手冊,其語法標準應該是從SQL92開始吧,在看SQL92標準的時候,你會發現裡面定義的都是一些巴科斯范式(BNF),就是一種語法定義的標準。不管是牛X哄哄的ORACLE,還是不幸被其收購的Mysql,都會遵循裡面的標準語法,當然一些擴展的語法除外,比如今天我們就會擴展一個簡單的語法^-^。

 

         OK,大傢知道瞭SQL語法的來源,那麼如何進行語法解析呢?YACC!!(Yet Another Compiler Compiler),它的書寫方式便是BNF,語法解析的利器。YACC接收來自詞法分析階段分解出來的token,然後去匹配那些BNF。今天哥就來揭開它的面紗。(關於YACC的基本使用方法,大傢可以看我上一篇中提到IBM的鏈接,一定要看懂那個先)

 

         繼續上一節的語句SELECT @@VERSION_COMMET,為瞭簡單,這裡省去後綴limit 1。Mysql的語法文件是sql_yacc.yy,首先給出這條語句涉及到的語法節點(大體瀏覽下即可):

 

?

 query:

END_OF_INPUT

{…}

|| verb_clause

{…}

| verb_clause END_OF_INPUT

          {

            /* Single query, not terminated. */

            YYLIP->found_semicolon= NULL;

          }

 

verb_clause:

          statement

        | begin

        ;

 

statement:

          alter

        | analyze

        | backup

        | binlog_base64_event

        | call

        | change

        | check

        | checksum

        | commit

        | create

        | deallocate

        | delete

        | describe

        | do

        | drop

        | execute

        | flush

        | grant

        | handler

        | help

        | insert

        | install

        | kill

        | load

        | lock

        | optimize

        | keycache

        | partition_entry

        | preload

        | prepare

        | purge

        | release

        | rename

        | repair

        | replace

        | reset

        | restore

        | revoke

        | rollback

        | savepoint

        | select

        | set

        | show

        | slave

        | start

        | truncate

        | uninstall

        | unlock

        | update

        | use

        | xa

        ;

 

select:

          select_init

          {

            LEX *lex= Lex;

            lex->sql_command= SQLCOM_SELECT;

          }

        ;

 

select_init:

          SELECT_SYM select_init2

        | '(' select_paren ')' union_opt

        ;

 

 

select_init2:

          select_part2

          {

            LEX *lex= Lex;

            SELECT_LEX * sel= lex->current_select;

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

            {

              my_parse_error(ER(ER_SYNTAX_ERROR));

              MYSQL_YYABORT;

            }

            if (sel->linkage == UNION_TYPE &&

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

            {

              my_parse_error(ER(ER_SYNTAX_ERROR));

              MYSQL_YYABORT;

            }

          }

          union_clause

        ;

 

select_part2:

          {

            LEX *lex= Lex;

            SELECT_LEX *sel= lex->current_select;

            if (sel->linkage != UNION_TYPE)

              mysql_init_select(lex);

            lex->current_select->parsing_place= SELECT_LIST;

          }

          select_options select_item_list

          {

            Select->parsing_place= NO_MATTER;

          }

          select_into select_lock_type

        ;

?

 

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));

 

    for (;;){

      register uchar first_char= (uchar)cur_struct;

 

      if (first_char == 0)

      {

        register int16 ires= (int16)(cur_struct>>16);

        if (ires==array_elements(symbols)) return 0;

        register SYMBOL *res;

        if (ires>=0)

          res= symbols+ires;

        else

          res= sql_functions-ires-1;

          register uint count= (uint) (cur_str – s);

        return lex_casecmp(cur_str,res->name+count,len-count) ? 0 : res;

      }

 

      register uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];

      if (cur_char<first_char) return 0;

      cur_struct>>=8;

      if (cur_char>(uchar)cur_struct) return 0;

 

      cur_struct>>=8;

      cur_struct= uint4korr(hash_map+

                        (((uint16)cur_struct + cur_char – first_char)*4));

      cur_str++;

    }

  }else{

    if (len>symbols_max_len) return 0;

    hash_map= symbols_map;

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

 

    for (;;){

      register uchar first_char= (uchar)cur_struct;

 

      if (first_char==0){

        register int16 ires= (int16)(cur_struct>>16);

        if (ires==array_elements(symbols)) return 0;

        register SYMBOL *res= symbols+ires;

        register uint count= (uint) (cur_str – s);

        return lex_casecmp(cur_str,res->name+count,len-count)!=0 ? 0 : res;

      }

 

      register uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];

      if (cur_char<first_char) return 0;

      cur_struct>>=8;

      if (cur_char>(uchar)cur_struct) return 0;

 

      cur_struct>>=8;

      cur_struct= uint4korr(hash_map+

                        (((uint16)cur_struct + cur_char – first_char)*4));

      cur_str++;

    }

  }

}

其中的get_hash_symbol便是去系統中查找關鍵字,第三個參數function代表是否去查找系統函數,我們這裡是系統變量,不是函數,故為FALSE。所有的關鍵字都掛在瞭hash_map上,即symbols_map上。symbols_maps又是一堆處理過的數據:

?

 

static uchar symbols_map[11828]= {

'<', '>', 29, 0,

'!', '|', 32, 0,

'<', 'X', 150, 0,

'B', 'Y', 11, 1,

'A', 'W', 147, 2,

'A', 'V', 0, 4,

看一下這個文件的最上面的註釋吧,看看有啥有用的信息,果然被找到瞭:

?

1

2

/* Do not edit this file!  This is generated by gen_lex_hash.cc

that seeks for a perfect hash function */

看到瞭這個註釋,心中豁然開朗,原來lex_hash.h是由gen_lex_hash.cc進行生成的,大傢千萬不要自己進行編輯此文件啊!!

 

來gen_lex_hash.cc看下吧,看到瞭個main函數,裡面是一些生成文件的操作,在generate_find_structs函數中找到瞭insert_symbols,

 

這應該是初始化我們的symbols_map數組瞭吧。

 

?

 

void insert_symbols()

{

  size_t i= 0;

  SYMBOL *cur;

  for (cur= symbols; i<array_elements(symbols); cur++, i++){

    hash_lex_struct *root=

      get_hash_struct_by_len(&root_by_len,cur->length,&max_len);

    insert_into_hash(root,cur->name,0,(uint) i,0);

  }

}

看到函數的實現是循環取數組symbols,找到symbols定義,在文件lex.h中,看到這個數組,我想大傢就會瞭然瞭:

?

1

{ "SELECT",     SYM(SELECT_SYM)},

這就是將SELECT字符串與SELECT_SYM關聯的地方瞭,bingo!

 

我們再來捋一下SELECT解析的思路,詞法分析解析到SELECT後,執行find_keyword去找是否是關鍵字,發現SELECT是關鍵字,

 

於是給yacc返回SELECT_SYM用於語法分析。note:如果我們想要加關鍵字,隻需在sql_yacc.yy上面添加一個%token xxx,

 

然後在lex.h裡面加入相應的字符串和SYM的對應即可。

 

下面看下@@version_comment這個系統變量如何解析的,首先給出其語法節點:

 

?

 

variable_aux:

  | '@' 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();

          }

        ;

這裡便是查找系統變量的地方瞭:get_system_var,我們跟進去看下:

 

?

 

Item *get_system_var(THD *thd, enum_var_type var_type, LEX_STRING name,

             LEX_STRING component)

{

  sys_var *var;

  LEX_STRING *base_name, *component_name;

 

  if (component.str)

  {

    base_name= &component;

    component_name= &name;

  }

  else

  {

    base_name= &name;

    component_name= &component;         // Empty string

  }

 

  if (!(var= find_sys_var(thd, base_name->str, base_name->length)))

    return 0;

  if (component.str)

  {

    if (!var->is_struct())

    {

      my_error(ER_VARIABLE_IS_NOT_STRUCT, MYF(0), base_name->str);

      return 0;

    }

  }

  thd->lex->uncacheable(UNCACHEABLE_SIDEEFFECT);

 

  set_if_smaller(component_name->length, MAX_SYS_VAR_LENGTH);

 

  return new Item_func_get_system_var(var, var_type, component_name,

                                      NULL, 0);

}

    由find_sys_var函數不斷跟進去,我們跟到瞭set_var.cc,找到瞭如下定義:

 

?

1

static sys_var_chain vars = { NULL, NULL };

    系統變量都會掛載在次鏈上。在文件中,搜索到瞭version_comment:

 

?

 

static sys_var_const_str    sys_version_comment(&vars, "version_comment",

                                            MYSQL_COMPILATION_COMMENT);

?

1

#define MYSQL_COMPILATION_COMMENT   "Source distribution"

這便是將version_comment加載到vars的鏈表上。

 

OK,我們也來加一個自己的系統變量:

 

?

 

static sys_var_const_str    sys_version_comment(&vars, "version_comment",

                                            MYSQL_COMPILATION_COMMENT);

 

/**add by nocode */

static sys_var_const_str    sys_version_comment_test(&vars, "nocode_test_sysvar",

                                            MYSQL_COMPILATION_NOCODE_TEST_SYSVAR);

#define MYSQL_COMPILATION_COMMENT    "Source distribution"

#define MYSQL_COMPILATION_NOCODE_TEST_SYSVAR  "No code in heart"    /*add by nocode*/

 

?

1

 

註釋add by nocode的地方,即是新添加的系統變量和宏定義,我們的系統變量叫@@nocode_test_sysvar,其值為No code in heartOK,重新編譯代碼,執行SELECT語句,OK瞭。

?

 

mysql> select @@nocode_test_sysvar;

+———————-+

| @@nocode_test_sysvar |

+———————-+

| No code in heart     |

+———————-+

1 row in set (0.01 sec)

上面添加瞭一個系統變量,並沒有修改語法文件sql_yacc.yy,為瞭加深理解,我們添加一個屬於自己的語法:nocode語法,為瞭簡單化實現,我們的目標很簡單,在客戶端輸入no_code後顯示字符串"MAKE BY NOCODE"。

定義關鍵字

首先在sql_yacc.yy文件中添加相應的SYMBOL

?

 

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

%token  NO_CODE_SYM                   /* add by nocode*/

%token  NO_WAIT_SYM

然後在lex.h中的symblos數組中添加nocode的字符串和符號的對應關系:

?

 

{ "NO",       SYM(NO_SYM)},

{ "NO_CODE",      SYM(NO_CODE_SYM)}, /*add by nocode*/

{ "NO_WAIT",      SYM(NO_WAIT_SYM)},

ok,至此我們關鍵字已經添加進去瞭

 

添加語法節點

我們給語法分支節點起名叫nocode,定義如下:

 

?

 

/**add by nocode*/

nocode:

        NO_CODE_SYM

        {

            THD *thd= YYTHD;

            LEX *lex= Lex;

            SELECT_LEX *sel= lex->current_select;

            Item_string* field;

            LEX_STRING tmp;

            CHARSET_INFO *cs_con= thd->variables.collation_connection;

            CHARSET_INFO *cs_cli= thd->variables.character_set_client;

 

            if (sel->linkage != UNION_TYPE)

                mysql_init_select(lex);

            lex->current_select->parsing_place= SELECT_LIST;

 

            uint repertoire= thd->lex->text_string_is_7bit &&

                my_charset_is_ascii_based(cs_cli) ? MY_REPERTOIRE_ASCII : MY_REPERTOIRE_UNICODE30;

 

            tmp.str = "MAKE BY NOCODE";

            tmp.length = strlen(tmp.str);

 

            field= new (thd->mem_root) Item_string(tmp.str, tmp.length, cs_con,

                DERIVATION_COERCIBLE,

                repertoire);

            if (field== NULL)

                MYSQL_YYABORT;

 

            if (add_item_to_list(thd, field))

                MYSQL_YYABORT;

 

            Select->parsing_place= NO_MATTER;

            lex->sql_command= SQLCOM_SELECT;

        }

        ; www.aiwalls.com

    最後要在statement的語法節點上加入nocode分支,我就不貼不來瞭。隻要讀到"no_code"便會進行進入這個語法分支。在這個分支裡,做瞭一些操作,首先構造瞭一個SELECT類型的語句,然後對其添加瞭一列,這列的名稱就是"MAKE BY NOCODE"…具體的細節大傢自己研究吧,這都不是本文的重點。

 

    語法添加完之後,我們重新編譯項目,值得說明的是,Mysql還是項目組織還是非常好的,修改瞭語法文件之後,不需要我們自己去用bison編譯,項目自動就幫我們編譯好瞭,真是不錯。重啟服務器,在客戶端輸入no_code,結果如下:

 

?

 

mysql> no_code;

+—————-+

| MAKE BY NOCODE |

+—————-+

| MAKE BY NOCODE |

+—————-+

1 row in set (3.02 sec)

語法分析到此結束。這裡隻添加瞭一個很簡單的語法分支,沒啥用處,主要是介紹下添加分支的步驟,大傢添加分支的時候要盡量使用已有的分支,既減少勞動量,同時也會減少語法沖突。 嘮叨兩句,最近項目太緊張,壓力山大,每晚都被噩夢驚醒,噩夢中總會想到算法的各種BUG,寫個代碼都提心吊膽的,哎,搞IT的真是悲催啊。PS 終於又更新瞭一篇,oh yeah,-_-ps again: 第一次用windows live writer寫博客,感覺比網頁方便多瞭~~,贊一個

摘自 心中無碼

發佈留言