MySQL的词法分析漫谈

wer32

关键点：
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,
};
                              
可以看到，数组表示中存在一定的空间浪费。要是不怕麻烦，我们还可以去榨出一点油水来。