MySQL的词法分析纵谈

MySQL的词法分析漫谈 这个链接上有点介绍，可以了解个大概：http://blog.imaginea.com/mysql-query-parsing/ 关键点： 1. SQL解析包括语法分析器和词法分析器。 简便的做法是用bison/flex组合。不过MySQL的词法分析器是手工打造的。 语法分析器的入口函数是MY

MySQL的词法分析漫谈
这个链接上有点介绍，可以了解个大概：http://blog.imaginea.com/mysql-query-parsing/

关键点：
1. SQL解析包括语法分析器和词法分析器。
简便的做法是用bison/flex组合。不过MySQL的词法分析器是手工打造的。
语法分析器的入口函数是MYSQLparse，词法分析器的入口函数是MYSQLlex。
2. 词法分析中会检查token是否为关键字。
最直接的做法是弄个大的关键字数组，进行折半查找。MySQL在此做了些优化。
本文主要介绍的是这一部分。

考虑到关键字是一个只读的列表，对它做一个只读的查找树可以改善查找的性能。
产生查找树：
1. 读取关键字数组，产生一个Trie树。
2. 调整这棵树，并产生一个数组（也就是一个不用链表表示的树）。

使用查找树：
这个比较简单，直接看函数get_hash_symbol好了。

产生查找树，相关的Makefile规则：
In `sql/CMakeFiles/sql.dir/build.make':

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

容易发现，最主要的函数就是`get_hash_symbol'，它主要的调用关系为：

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

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

文件"gen_lex_hash.cc"注释中的树的示例：

+-----------+-+-+-+
| 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" )

如果你还记得Trie树，理解起来会容易一点。下面是不同的输入数组对应的树。
i=0

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

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

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

i=1

+-----------+--+--+
| 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)},

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

i=2

+-----------+--+--+
| 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|
| |
&& <=

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

+-----------+--+--+
| 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|
| |
<= <>

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

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,
};

可以看到，数组表示中存在一定的空间浪费。要是不怕麻烦，我们还可以去榨出一点油水来。