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, 0, 0, 0, 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)},
{
static uchar symbols_map[8]= {
0, 0, 1, 0, 0, 0, 0, 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)},
{ {
static uchar symbols_map[100]= {
0, 0, 1, 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(ne)},
static uchar symbols_map[108]= {
0, 0, 1, 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,
};
可以看到，数组表示中存在一定的空间浪费。要是不怕麻烦，我们还可以去榨出一点油水来。