語法分析——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.2cto.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寫博客，感覺比網頁方便多了～～，贊一個
