May you do good and not evil.
May you find forgiveness for yourself and forgive others.
May you share freely, never taking more than you give.

SQLite詞法分析過程

詞法分析入口

?如前面分析睦刃，SQLite是前端+虛擬機(jī)+后端形式的架構(gòu)涩拙，拿到SQL語句后兴泥，需要先在前端編譯搓彻，得到虛擬機(jī)代碼指令旭贬。編譯過程開始的首要任務(wù)即是詞法分析稀轨。SQLite的詞法分析比較簡單靶端，這塊代碼是作者手工編寫的，而不是使用像Lex的詞法分析生成器工具自動(dòng)生成的脏榆。要閱讀其源碼须喂，不得不提到幾個(gè)重要函數(shù)：

int sqlite3_prepare(xxxx);
int sqlite3_prepare_v2(xxxx);
int sqlite3_prepare_v3(xxxx);

這幾個(gè)接口均接受輸入一組SQL語句坞生，并將編譯后的結(jié)果記錄到sqlite3_stmt結(jié)構(gòu)中是己。
經(jīng)過幾個(gè)核心函數(shù)調(diào)用后，調(diào)用到編譯的核心函數(shù)sqlite3RunParser：

SQL詞法分析-prepare

詞法分析的層次

?sqlite3RunParser函數(shù)是個(gè)非常重要的函數(shù)，其實(shí)現(xiàn)了對SQL語句的編譯逆皮，即詞法电谣、語法分析的全過程剿牺。根據(jù)前面文章介紹牢贸，詞法分析器從輸入的字符串自左向右逐個(gè)將輸入的字串流分割成一個(gè)個(gè)單詞符號潜索，并輸入給語法分析器進(jìn)行語法分析竹习。顯然整陌，sqlite3RunParser的執(zhí)行過程也應(yīng)該是這樣的泌辫。

Parse過程

sqlite3RunParser函數(shù)實(shí)現(xiàn)：

while( 1 ){
      ...
      //詞法分析得到token
      n = sqlite3GetToken((u8*)zSql, &tokenType);
      ...
      //將一個(gè)個(gè)token輸入到語法分析器宾毒，驅(qū)動(dòng)語法分析器進(jìn)行語法分析
      sqlite3Parser(pEngine, tokenType, pParse->sLastToken, pParse);
      ...
    }
  }

SQLite詞法分析源碼

詞法分析函數(shù)的輸入輸出

?從源碼注釋上看，詞法分析器函數(shù)sqlite3GetToken接受輸入一個(gè)SQL語句谐岁，不斷的調(diào)用該函數(shù)幢竹，逐步的返回token距SQL語句起始點(diǎn)的長度焕毫，并且每次調(diào)用將得到的token類型保存到第二個(gè)參數(shù)tokenType中咬荷。

** Return the length (in bytes) of the token that begins at z[0]. 
** Store the token type in *tokenType before returning.
*/
int sqlite3GetToken(const unsigned char *z, int *tokenType)
{
  int i, c;
  switch( aiClass[*z] ){  /* Switch on the character-class of the first byte
                          ** of the token. See the comment on the CC_ defines
                          ** above. */
      //空格
    case CC_SPACE: {
     ...
      for(i=1; sqlite3Isspace(z[i]); i++){}
      *tokenType = TK_SPACE;
      return i;
    }
  //左括號
    case CC_LP: {
      *tokenType = TK_LP;
      return 1;
    }
  //右括號
    case CC_RP: {
      *tokenType = TK_RP;
      return 1;
    }
    ...
  //字母或下劃線
    case CC_KYWD: {
      for(i=1; aiClass[z[i]]<=CC_KYWD; i++){}
      if( IdChar(z[i]) ){
        /* This token started out using characters that can appear in keywords,
        ** but z[i] is a character not allowed within keywords, so this must
        ** be an identifier instead */
        i++;
        break;
      }
      *tokenType = TK_ID;
      return keywordCode((char*)z, i, tokenType);
    }
...
  }
  while( IdChar(z[i]) ){ i++; }
  *tokenType = TK_ID;
  return i;
}

?上面簡化了的詞法分析函數(shù)幸乒，代碼比較簡單罕扎，對于輸入的字符串流逐個(gè)字符進(jìn)行分析腔召，字符被分為若干大類臀蛛，通過查aiClass表，非晨颓停快速高效的得到當(dāng)前字符類型舔琅。代碼邏輯很清晰备蚓，比如： case CC_SPACE: 檢測到空格輸入囱稽，把相鄰的空格全部過濾掉后虚循，返回一個(gè)空格的類型TK_SPACE(TK_SPACE是怎么得來的，后面介紹铺遂，go ahead);case CC_KYWD: 檢測到字母或下劃線，則繼續(xù)讀入撤逢，直到讀到下一個(gè)特征字符后初狰，將識別到的一個(gè)詞組經(jīng)keywordCode函數(shù)處理后返回互例。

Token識別知識鋪墊

?如上述對詞法分析函數(shù)的解析媳叨，它從字符串流不斷的提取出關(guān)鍵字武福、特征字痘番、運(yùn)算符等汞舱，轉(zhuǎn)換成了一個(gè)叫做tokenType的數(shù)后返回兵拢，這個(gè)數(shù)字背后的邏輯基礎(chǔ)是什么说铃？單詞符號和數(shù)字之間的對應(yīng)關(guān)系是怎樣的呢腻扇？
?首先幼苛，可以觀察到，sqlite3GetToken函數(shù)返回的tokenType取值是一組TK_開頭的宏墙杯，這組宏定義在parse.h頭文件中高镐，意識到這點(diǎn)特征是非常重要的一步畸冲。而且TK_后接的字符串又正好是SQL語句的關(guān)鍵字，是否有想到些什么梧油？

parse.h中定義的tokenType值
#define TK_SEMI                             1
#define TK_EXPLAIN                          2
#define TK_QUERY                            3
#define TK_PLAN                             4
#define TK_BEGIN                            5
#define TK_TRANSACTION                      6
#define TK_DEFERRED                         7
...

? 要詳細(xì)解釋這些現(xiàn)象背后的緣由儡陨，請關(guān)注后面語法分析章節(jié)迄委。這里大致說明一下叙身，SQLite使用的語法分析器生成器(lemon)會根據(jù)語法規(guī)則文件給所有的終結(jié)符信轿、非終結(jié)符分配唯一的數(shù)字特征ID财忽，在語法分析的過程中使用這些數(shù)字表達(dá)一些規(guī)則即彪。parse.h即為其產(chǎn)物隶校，它記錄了SQL語句中的終結(jié)符的數(shù)字ID深胳，而它的另一核心產(chǎn)物則是語法分析器parse.c,也就是說舞终，語法分析器期望從詞法分析器得到一組數(shù)組特征ID作為輸入而非單詞。因此詞法分析器的核心任務(wù)除了分詞外纷宇，還需要將分好的詞轉(zhuǎn)成語法分析器能認(rèn)識的ID呐粘。

Token的Type轉(zhuǎn)換方法

? 對于特征符號的 type轉(zhuǎn)換直接代碼寫死作岖，非常容易痘儡。對于詞組的tokenType怎么獲取沉删，需要依賴核心函數(shù)keywordCode。下面分析該函數(shù)的源碼實(shí)現(xiàn)：

/* Check to see if z[0..n-1] is a keyword. If it is, write the
** parser symbol code for that keyword into *pType.  Always
** return the integer n (the length of the token). */
static int keywordCode(const char *z, int n, int *pType){
  int i, j;
  const char *zKW;
  if( n>=2 ){
    i = ((charMap(z[0])*4) ^ (charMap(z[n-1])*3) ^ n) % 127;
    for(i=((int)aKWHash[i])-1; i>=0; i=((int)aKWNext[i])-1){
      if( aKWLen[i]!=n ) continue;
      j = 0;
      zKW = &zKWText[aKWOffset[i]];
#ifdef SQLITE_ASCII
      while( j<n && (z[j]&~0x20)==zKW[j] ){ j++; }
#endif
#ifdef SQLITE_EBCDIC
      while( j<n && toupper(z[j])==zKW[j] ){ j++; }
#endif
      if( j<n ) continue;
      ...
      *pType = aKWCode[i];
      break;
    }
  }
  return n;
}

什么鬼？(charMap(z[0])4) ^ (charMap(z[n-1])3) ^ n) % 127殴穴；x&^K%&$^%*@#....?完全無法理解＞⒐弧Ｐ莅磨取！這是什么原理顷扩？
冷靜一下隘截，看下源文件注釋：

/***** This file contains automatically generated code ******
** 這個(gè)文件中包含了自動(dòng)生成的代碼
** The code in this file has been automatically generated by
** 這段代碼是通過mkkeywordhash.c自動(dòng)生成的
** sqlite/tool/mkkeywordhash.c

mkkeywordhash.c黑幕

編譯調(diào)試

?這個(gè)文件直接編譯可以得到完整的可執(zhí)行程序婶芭，使用命令：

gcc mkkeywordhash.c -o mkkeywordhash

從Main函數(shù)開始閱讀，下面分析其實(shí)現(xiàn)宰掉。

1. 初步壓縮呵哨，刪除不支持的關(guān)鍵字

/* Remove entries from the list of keywords that have mask==0 */
  for(i=j=0; i<nKeyword; i++){
    if( aKeywordTable[i].mask==0 ) continue;
    if( j<i ){
      aKeywordTable[j] = aKeywordTable[i];
    }
    j++;
  }
  nKeyword = j;

該段函數(shù)實(shí)現(xiàn)對關(guān)鍵字表的初步壓縮赁濒，對于mask==0的數(shù)組字段進(jìn)行刪除，之所以有這樣的操作孟害，是因?yàn)镾QLite支持編譯時(shí)裁剪優(yōu)化拒炎，當(dāng)有些SQL功能不需要支持時(shí)，沒必要保留在關(guān)鍵字查找表中挨务，影響表的空間大小從而影響到內(nèi)存和執(zhí)行效率击你。該部分代碼執(zhí)行完畢后，將得到一個(gè)長度為nKeyword 的數(shù)組aKeywordTable谎柄，這部分包含的key即當(dāng)前編譯的SQL支持的命令范圍鸿摇。

2. 對明確支持的關(guān)鍵字初始化len糙臼、hash、id

 /* Fill in the lengths of strings and hashes for all entries. */
  for(i=0; i<nKeyword; i++){
    Keyword *p = &aKeywordTable[i];
    p->len = (int)strlen(p->zName);
    assert( p->len<sizeof(p->zOrigName) );
    memcpy(p->zOrigName, p->zName, p->len+1);
    totalLen += p->len;
    p->hash = (charMap(p->zName[0])*4) ^
              (charMap(p->zName[p->len-1])*3) ^ (p->len*1);
    p->id = i+1;
  }

aKeywordTable數(shù)組中的每一項(xiàng)代表SQL的一個(gè)關(guān)鍵字，關(guān)鍵字的名字記錄在zName字段中，作者使用該哈希函數(shù)為關(guān)鍵字進(jìn)行哈希(算法：關(guān)鍵字的第一個(gè)字符*4)^(關(guān)鍵字的最后一個(gè)字符*3)^(關(guān)鍵字名字的長度))：

(charMap(p->zName[0])*4) ^(charMap(p->zName[p->len-1])*3) ^ (p->len*1)
從aKeywordTable中的關(guān)鍵字看到，首尾字符已經(jīng)可以獲得很少的哈希沖突了

同時(shí)，在代碼里有一句斷言需要提一下： assert( p->len<sizeof(p->zOrigName) ); zOrigName和zName之間是有什么關(guān)聯(lián)？這里暫時(shí)看不出來抒和，其實(shí)zName存著的是關(guān)鍵字字串壓縮后的結(jié)果，而zOrigName存著的是原始的key串员魏，下面會看到壓縮的過程碌补。

3. 找出某些關(guān)鍵字是另外關(guān)鍵字的一部分的情況袜啃，為再次壓縮準(zhǔn)備

/* Sort the table from shortest to longest keyword */
  qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare1);

  /* Look for short keywords embedded in longer keywords */
  for(i=nKeyword-2; i>=0; i--){
    Keyword *p = &aKeywordTable[i];
    //從最長的key串開始（數(shù)組下標(biāo)nKeyword-1），依次檢查該子串是否完全包含 
    // Keyword  p,顯然pOther 必須要比p長，所以j>i。
    for(j=nKeyword-1; j>i && p->substrId==0; j--){
      Keyword *pOther = &aKeywordTable[j];
      if( pOther->substrId ) continue;
      if( pOther->len<=p->len ) continue;
      for(k=0; k<=pOther->len-p->len; k++){
        //pOther的name長度大于p坤次，要檢查p是不是pOther完全子串滑绒，只需要從
        //pOther起始點(diǎn)到pOther->len-p->len(==k)比較是否相等即可
        if( memcmp(p->zName, &pOther->zName[k], p->len)==0 ){
          p->substrId = pOther->id;
          p->substrOffset = k;
          break;
        }
      }
    }
  }

首先，將key數(shù)組排序，排序算法非常簡單，就是按長度排序，長度相同的按字符串比較大小排序。keywordCompare1函數(shù)不再贅述。
然后，從字符串最長的倒敘查找比其短的的字符串，是否是它的子串。比如SET是OFFSET子串，則將SET的substrId 設(shè)置為OFFSET的id，并記錄SET在OFFSET中的偏移量substrOffset =3；這樣在后面的字符串壓縮中，SET和OFFSET就可以完全合并了鼻忠。合并算法后面介紹，go ahead篡殷！

3. 找出關(guān)鍵字名字的最長后綴劲弦，為更進(jìn)一步的壓縮準(zhǔn)備

  /* Compute the longestSuffix value for every word */
  for(i=0; i<nKeyword; i++){
    Keyword *p = &aKeywordTable[i];
    //已經(jīng)是別的字串的子串了，后面會被合并掉，不需要尋找最長后綴
    if( p->substrId ) continue;
    for(j=0; j<nKeyword; j++){
      Keyword *pOther;
      if( j==i ) continue;
      pOther = &aKeywordTable[j];
       //已經(jīng)是別的字串的子串了雳灵，也不需要用于比對最長后綴
      if( pOther->substrId ) continue;
      for(k=p->longestSuffix+1; k<p->len && k<pOther->len; k++){
        if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
          p->longestSuffix = k;
        }
      }
    }
  }
/* Sort the table into reverse order by length */
  qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare2);

最長后綴的意圖，是找出有相交但不完全包含的兩個(gè)字符串的集和中瓤狐，相交最長值為最長后綴拦宣，比如：abcde 和defgh、cdefg腻窒、bcdefgei三個(gè)字串都是相交但又非完全包含，和defgh相交的長度為2,即de;和cdefg相交的長度為3,即cde;和bcdefgei相交的長度為4,即bcde儡毕。因此旬痹，abcde 的最長后綴值為4。
達(dá)到這樣的意圖耸别，只需要對每個(gè)關(guān)鍵字兜看，都要遍歷其他所有的關(guān)鍵字弧轧，尋找該關(guān)鍵字的最長后綴值。找完后排序擂橘。

4. 字符串壓縮核心算法

將所有的關(guān)鍵字緊密排列到一起，并計(jì)算每個(gè)關(guān)鍵字在整個(gè)字符串中的偏移

//運(yùn)行到這里彤避，aKeywordTable是按照最長后綴排序過的數(shù)組
  /* Fill in the offset for all entries */
  nChar = 0;
  for(i=0; i<nKeyword; i++){
    Keyword *p = &aKeywordTable[i];
    //已經(jīng)計(jì)算好了offset或是其他字串的子串娄帖，暫不處理
    if( p->offset>0 || p->substrId ) continue;
    p->offset = nChar;
    nChar += p->len;
    //p為當(dāng)前有最長后綴的子串佩耳，子串長度為p->len挂捅，尋找和后綴重疊但不全包含的字 
    //符串進(jìn)行拼接，因此比對從p->len-1開始舵揭，不斷尋找后綴匹配的串耕漱，找不到則k--,
    //因?yàn)閍KeywordTable是排序的最長后綴串寞宫，因此該循環(huán)中一般一定能找到一個(gè)串
    for(k=p->len-1; k>=1; k--){
      //遍歷比該串還短的子串，尋找最長后綴匹配
      for(j=i+1; j<nKeyword; j++){
        Keyword *pOther = &aKeywordTable[j];
        if( pOther->offset>0 || pOther->substrId ) continue;
        if( pOther->len<=k ) continue;
        //找打p串后綴和pOther前綴重合的串，進(jìn)行合并
        if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
          //other將合入p钾麸，下次循環(huán)找other的后綴重疊串涉瘾，因此other賦值p
          p = pOther;
          //other串開始o(jì)ffset等于當(dāng)前串尾向前減去重疊部分
          p->offset = nChar - k;
          //pOther合并后總串的長度改變
          nChar = p->offset + p->len;
          //合并壓縮后，zName就只剩未重疊部分朋蔫，重疊部分被壓縮到前面的串中
          //壓縮后雀鹃，zName變短，長度等于原長度-重疊部分屏积，重疊長度k記錄到prefix 
          p->zName += k;
          p->len -= k;
          p->prefix = k;
          j = i;
          k = p->len;
        }
      }
    }
  }
  //對于完全子串括眠，其offset等于父串(完全包含它的串)在整個(gè)字串中的offset+該子串在父串中的offset
  for(i=0; i<nKeyword; i++){
    Keyword *p = &aKeywordTable[i];
    if( p->substrId ){
      p->offset = findById(p->substrId)->offset + p->substrOffset;
    }
  }
//按offset偏移從小到大排序
/* Sort the table by offset */
  qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare3);

這點(diǎn)代碼比較難理解缩幸，下面用事例描述這個(gè)過程，以幫助理解這段代碼：

1. 假設(shè)有6個(gè)字符串，分別為“abc”媳板、“bcd”、“cde”铅忿、“def”、“efg”蔚晨、“fgh”铭腕，這6個(gè)字符串之間兩兩之間不互相完全包含。要把這些字符串存起來身堡，需要占用abcbcdcdedefefgfgh共18個(gè)字節(jié)，這是非常浪費(fèi)空間的。因?yàn)槲覀儼l(fā)現(xiàn)他們之間兩兩重疊的部分肠骆，實(shí)際可以壓縮起來的。
2. 將6個(gè)字符串前后重合部分合并起來塞耕，字符串變成了tmp = "abcdefgh"蚀腿，這時(shí)我們只需要知道abc是tmp中開始0偏移3的串，bcd是tmp中開始1偏移3的串扫外，cde是tmp中開始2偏移3的串...依次類推莉钙。
3. 對于完全包含的子串，比如有字符串bc,要用tmp描述筛谚，只需要指導(dǎo)bc完全包含在abc或者bcd之1中磁玉，假定選擇abc，那bc是abc的子串驾讲，其在abc中偏移1蚊伞。此時(shí)，bc在tmp中的描述就變成了abc在tmp中的偏移0加bc在abc中的偏移1吮铭，即在tmp中偏移1时迫，長度2。

上述代碼的核心邏輯就是按照這樣的原理進(jìn)行壓縮的谓晌。

經(jīng)過這種壓縮算法壓縮后别垮，aKeywordTable數(shù)組中的keywork的zName就變小了，而aKeywordTable又是一個(gè)按照offset排序過得數(shù)組扎谎，此時(shí)只要for循環(huán)碳想，把非完全字串（substrId ==0）的zName拼接在一起就得到了壓縮后的總字符串zKWText:

/* zKWText[] encodes 834 bytes of keyword text in 554 bytes */
/*   REINDEXEDESCAPEACHECKEYBEFOREIGNOREGEXPLAINSTEADDATABASELECT       */
/*   ABLEFTHENDEFERRABLELSEXCEPTRANSACTIONATURALTERAISEXCLUSIVE         */
/*   XISTSAVEPOINTERSECTRIGGEREFERENCESCONSTRAINTOFFSETEMPORARY         */
/*   UNIQUERYWITHOUTERELEASEATTACHAVINGROUPDATEBEGINNERECURSIVE         */
/*   BETWEENOTNULLIKECASCADELETECASECOLLATECREATECURRENT_DATEDETACH     */
/*   IMMEDIATEJOINSERTMATCHPLANALYZEPRAGMABORTVALUESVIRTUALIMITWHEN     */
/*   WHERENAMEAFTEREPLACEANDEFAULTAUTOINCREMENTCASTCOLUMNCOMMIT         */
/*   CONFLICTCROSSCURRENT_TIMESTAMPRIMARYDEFERREDISTINCTDROPFAIL        */
/*   FROMFULLGLOBYIFISNULLORDERESTRICTRIGHTROLLBACKROWUNIONUSING        */
/*   VACUUMVIEWINITIALLY                                                */

5. 計(jì)算最優(yōu)哈希表大小及哈希值

  /* Figure out how big to make the hash table in order to minimize the
  ** number of collisions */
  bestSize = nKeyword;
  bestCount = nKeyword*nKeyword;
  for(i=nKeyword/2; i<=2*nKeyword; i++){
    for(j=0; j<i; j++) aKWHash[j] = 0;
    for(j=0; j<nKeyword; j++){
      h = aKeywordTable[j].hash % i;
      aKWHash[h] *= 2;
      aKWHash[h]++;
    }
    for(j=count=0; j<i; j++) count += aKWHash[j];
    if( count<bestCount ){
      bestCount = count;
      bestSize = i;
    }
  }

  /* Compute the hash */
  for(i=0; i<bestSize; i++) aKWHash[i] = 0;
  for(i=0; i<nKeyword; i++){
    h = aKeywordTable[i].hash % bestSize;
    aKeywordTable[i].iNext = aKWHash[h];
    aKWHash[h] = i+1;
  }

分詞器得到一個(gè)字符串key后，要查字符串對應(yīng)的tokenType毁靶，直接遍歷整個(gè)表查詢并不夠優(yōu)化胧奔。為了提高查詢效率，作者使用哈希索引實(shí)現(xiàn)常數(shù)級的復(fù)雜度预吆，以提高查詢效率龙填。那SQL支持的關(guān)鍵字?jǐn)?shù)目是用戶可裁剪的，如何取哈希表的大小，以求得比較小的哈希碰撞岩遗，從而獲取較高的綜合查詢效率扇商？
?作者將哈希表的范圍限定到關(guān)鍵字?jǐn)?shù)量的一半到其平方值之間，以這個(gè)區(qū)間內(nèi)的值取模宿礁，哪個(gè)數(shù)值會更優(yōu)案铺？哈希碰撞會更小梆靖？設(shè)置一個(gè)“懲罰因子”——此處是取值2（也可以是3,4,5控汉，實(shí)際上任意除1之外的正整數(shù)都可以），每次取模后的結(jié)果都要乘以這個(gè)“懲罰因子”返吻，重復(fù)的次數(shù)與2的冪次方成正比姑子，增長速度是非常快的测僵。對所有模值求和街佑，意味著重復(fù)項(xiàng)越多，最終求得的和越大捍靠。怎么理解舆乔？比如當(dāng)哈希表大小取值為n1時(shí)，如果完全沒有發(fā)生碰撞剂公，aKWHash[n]初始值是0希俩，那么哈希表中所有的值求和count += aKWHash[j];就等于n1；而當(dāng)有一個(gè)元素發(fā)生1次碰撞后纲辽，求和應(yīng)該等于n1+2颜武，一個(gè)元素發(fā)生2次碰撞后求和等于n1+6，三次n1+14....按2的指數(shù)次方增長拖吼。因此鳞上，和的大小很大程度反映了碰撞的激烈程度。隨著哈希表的大小i的增加吊档，最終計(jì)算得到的哈希值會變得一樣的“稀疏”篙议，也就意味著求和的結(jié)果都趨向于i,當(dāng)i使得和最小，則認(rèn)為其實(shí)最優(yōu)的哈希模值怠硼。
?為aKeywordTable中留下來的每一個(gè)key計(jì)算哈希值鬼贱，如果沒有哈希沖突，意味著每個(gè)哈希值都對應(yīng)唯一的aKWHash[h]香璃，由于aKWHash[]數(shù)組默認(rèn)值是0这难，因此每個(gè)關(guān)鍵字的iNext值都是0。如果存在哈希沖突葡秒，則aKWHash[h]中是非零值姻乓。該非零值減1即表示與當(dāng)前關(guān)鍵字產(chǎn)生哈希沖突的關(guān)鍵字的索引值嵌溢。

6. 代碼自動(dòng)生成

?有了上面這些分析，代碼自動(dòng)生成做的工作就比較清晰了蹋岩，它生成了讓我們看不懂的函數(shù)int keywordCode(const char *z, int n, int *pType)及其計(jì)算使用的那些數(shù)組赖草、哈希表等。即zKWText為壓縮后的字符串剪个；aKWHash為keyword的哈希值表秧骑；aKWLen為第i個(gè)key的長度；aKWOffset為第i個(gè)key在zKWText的offset值禁偎，aKWCode是第i個(gè)key的tokenType;在回過頭來看keywordCode實(shí)現(xiàn)腿堤，意圖就十分清晰了阀坏。

static int keywordCode(const char *z, int n, int *pType){
  int i, j;
  const char *zKW;
  if( n>=2 ){
    //根據(jù)詞法分析到的關(guān)鍵字串如暖，計(jì)算其哈希值
    i = ((charMap(z[0])*4) ^ (charMap(z[n-1])*3) ^ n) % 127;
   /*i=((int)aKWHash[i])-1，即i值應(yīng)該是keywork的索引或和keywork索引發(fā)生哈希碰撞的keyword索引忌堂。*/
   //1.哈希無沖突時(shí)盒至，其值就是keywork的索引;
   //2.當(dāng)存在哈希沖突時(shí)，其值是和keyword沖突的索引值+1
   //有沒有哈希碰撞士修，可以檢測aKWNext[i]是不是等于0枷遂，等于0無沖突
  //在此基礎(chǔ)上檢查len和字符串（全轉(zhuǎn)大寫比較）是否相等
    for(i=((int)aKWHash[i])-1; i>=0; i=((int)aKWNext[i])-1){
      if( aKWLen[i]!=n ) continue;
      j = 0;
      zKW = &zKWText[aKWOffset[i]];
#ifdef SQLITE_ASCII
      while( j<n && (z[j]&~0x20)==zKW[j] ){ j++; }
#endif
#ifdef SQLITE_EBCDIC
      while( j<n && toupper(z[j])==zKW[j] ){ j++; }
#endif
      if( j<n ) continue;
     ...
    //條件驗(yàn)證通過后，type則可直接通過索引i拿到并賦值
    *pType = aKWCode[i];
      break;
    }
  }
  return n;

至此棋嘲，SQLite的詞法分析部分的核心代碼分析完畢酒唉，可以看到，作者為了提高執(zhí)行效率和降低內(nèi)存使用率方面沸移，做了非常深入的優(yōu)化痪伦。