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.

前言

?對于非計算機專業(yè)的同學，在學習SQLite源碼時肯定也會有一個很大的疑問，SQL是如何被解析和執(zhí)行的？大家應(yīng)該都明白，SQL雖然非常精簡和易讀，但其語句是可變長的，同時又支持許多表達式、函數(shù)等復(fù)雜特性，如果僅用if...else...完美的覆蓋SQL的解析，那幾乎是不可能的。因此你可能會急迫的去源碼里尋找答案，并且很容易的找到兩個關(guān)鍵函數(shù)sqlite3RunParser、sqlite3Parser，代碼并不算長，你喜出望外，意識到自己終于要揭開SQL解析的神秘面紗了，但待你定下神來一句一行的想去讀懂這兩個函數(shù)時，卻絞盡腦汁，終究看不懂這一堆亂七八糟的東西...
?我并不例外，看了兩天這塊代碼，網(wǎng)上查資料，這方面的信息少之又少，終究沒能找到一篇可以讓我理解為什么的文章，還好SQLite的注釋非常詳細：the parse.c file generated by lemon and the tokenize.c file are concatenated 。讓我如此郁悶的代碼，原來是被一個叫l(wèi)emon的程序自動生成的，再查lemon，語法分析、LALR(1)、自動生成、編譯器的編譯器、Lex/Yacc、Bison...一堆的關(guān)鍵詞都指向了計算機專業(yè)核心專業(yè)課程--編譯原理，那么只能從這里尋求突破了。

編譯原理

?程序語言是向人以及計算機描述計算過程的符號，一個程序語句，在可以被運行之前，它首先需要被翻譯成一種能夠被計算機執(zhí)行的形式。完成這項翻譯工作的軟件系統(tǒng)稱為編譯器（compiler）。而編譯原理正是編譯器的設(shè)計和實現(xiàn)的理論基礎(chǔ)。SQL(Structured Query Language)，既然也是一個可以被計算機識別的語言，毫無懸念，可以基于編譯原理指導(dǎo)完成解析。

1.編譯過程

?大道至簡，科學的產(chǎn)生就是先從具體到抽象得到基本原理的過程，而技術(shù)的應(yīng)用則是以基本原理所描述的模型為基礎(chǔ)，尋求對自然事物的科學描述的過程。因此，計算機語言的解析過程和自然語言的翻譯過程必然是高度一致的。我們從如下一個英文句子的翻譯過程中，理解一下計算機語言的編譯過程。

The compiler can translate a program from source language to target language.
1.識別句子中的每一個單詞 =>詞法分析
2.分析句子的語法結(jié)構(gòu) =>語法分析
3.根據(jù)句子的結(jié)構(gòu)進行初步翻譯 =>中間代碼生成
4.對譯文進行修飾 =>優(yōu)化
5.寫出最后的譯文 =>目標代碼產(chǎn)生

2.詞法分析

2.1 詞法分析的職責和流程

?詞法分析器的主要任務(wù)是讀入源程序的輸入字符、將它們組成詞素，生成并輸出一個詞法單元序列，每個詞法單位對應(yīng)一個詞素。這個詞法單元序列被輸出到語法分析器中進行語法分析。詞法分析器通常還要和符號表進行交互，當詞法分析器發(fā)現(xiàn)一個標識符的詞素時，它將這個詞素添加到符號表中。在某些情況下，詞法分析器會從符號表中讀取有關(guān)標識符種類的信息，以確定向語法分析器傳送哪個詞法單元。

詞法分析器在編譯器中的位置

?詞法分析器的大概工作過程為：掃描器調(diào)用預(yù)處理子程序，將源程序輸入到輸入緩沖區(qū)中，預(yù)處理子程序讀取輸入緩沖區(qū)數(shù)據(jù)，剔除無用的空白、跳格、回車等編輯性字符、給出句末符等，并將處理后的更規(guī)范的文本輸入到掃描緩沖區(qū)。掃描器從掃描緩沖區(qū)中讀入字符并根據(jù)詞法規(guī)則進行分詞，輸出單詞符號。

詞法分析器結(jié)構(gòu)

2.2 詞法分析的形式化處理

?如何讓計算機自動的進行詞法分析，甚至如何讓計算機能夠按照詞法規(guī)則自動的生成詞法分析器，都需要對詞法分析過程進行形式化處理和分析。為了描述程序中合法的單詞，引入正規(guī)集和正規(guī)式（正規(guī)表達式or正則表達式）的概念(集合論知識），利用正則模式構(gòu)造一段代碼，這段代碼能夠檢查輸入字符串并在輸入的前綴中找出一個和模式匹配的詞素，這個過程使用狀態(tài)轉(zhuǎn)移圖可以非常形象的表達。
?作為構(gòu)造詞法分析器的一個中間步驟，將正則模式轉(zhuǎn)換成具有特定風格的流圖，稱為“狀態(tài)轉(zhuǎn)換圖”。狀態(tài)轉(zhuǎn)換圖有一組被稱為“狀態(tài)”的節(jié)點或者圓圈。詞法分析器在掃描輸入串的過程中尋找和某個模式匹配的詞素，而轉(zhuǎn)換圖中的每個狀態(tài)代表一個可能在這個過程中出現(xiàn)的情況。狀態(tài)圖的邊從圖的一個狀態(tài)指向另外一個狀態(tài)，每條邊的標號包含了一個或多個符號。通過這樣的狀態(tài)轉(zhuǎn)換圖，詞法分析器就可以非常容易的被寫出來。

狀態(tài)轉(zhuǎn)換圖

?如何實現(xiàn)該狀態(tài)轉(zhuǎn)換圖，自動機理論中有完善的形式化描述策略，即確定性有限自動機(DFA),確定性有限自動機要求有唯一的初態(tài)，且從一個狀態(tài)開始，識別一個新的字符后，一定可以到達一個確定的狀態(tài)，即其狀態(tài)轉(zhuǎn)移函數(shù)時一個單值的部分映射，因此實現(xiàn)起來非常簡單，大概過程包含：

1. 定義初始狀態(tài)值，并定義一個包含所有狀態(tài)和輸入符號的二維表。
2. 從初始狀態(tài)開始，循環(huán)讀入一個符號，并根據(jù)當前狀態(tài)和讀入的符號查詢二維表，跳轉(zhuǎn)至最新狀態(tài)。
3. 循環(huán)上述步驟直至遇到終態(tài)結(jié)束。

?但由于確定性有限自動機描述的狀態(tài)轉(zhuǎn)換過于基礎(chǔ)，似乎和實際的需求還有一些差別，計算機科學家們定義了另外一種看上去更一般化的有限自動機--非確定性有限自動機（NFA）。其要求初態(tài)不再唯一，可以有多個。同時其狀態(tài)轉(zhuǎn)移函數(shù)不再是單值映射，其允許在輸入一個字（由字符擴展到字）后，可以存在到達多種狀態(tài)的可能。這樣一來，從感官上我們會感覺NFA的識別能力似乎更加強大，實現(xiàn)起來會更加復(fù)雜，因為定義上看DFA只是NFA的一個特例。但經(jīng)過理論學家的研究和證明，NFA和DFA的識別能力是相等的，并且研究出了NFA化簡DFA的“套路”，這樣，人民們可以非常容易的用NFA描述問題，再用確定的理論方法轉(zhuǎn)成DFA進行計算機處理?；谶@些理論依據(jù)，現(xiàn)在人們已經(jīng)比較容易的開發(fā)出詞法分析器生成器，比如Lex。

2.3 SQLite中的詞法分析

?雖然像Lex這樣的詞法分析器生成器已經(jīng)存在，但由于SQLite中的SQL語句分詞比較簡單，其并未使用詞法分析生成器來自動生成詞法分析器，而是作者自己手工編寫實現(xiàn)的代碼，因此上述的知識點描述，僅用于求解為什么、如何做的問題，對源碼的理解并無影響。關(guān)于SQLite的詞法分析是怎樣的邏輯，我們后續(xù)文章詳細介紹。

3.語法分析

3.1 語法分析的理論體系

?講到語法分析，不得不提到喬姆斯基的形式語言體系。喬姆斯基，這個本世紀最偉大的語言學家、哲學家，一個地地道道的政治憤青,點我了解CHOMSKY ，最初基于對自然語言研究的動機提出了一套完整的語言體系，但卻意外的深刻影響了現(xiàn)代計算機程序設(shè)計語言的發(fā)展，成為編譯理論和方法的基礎(chǔ)。
?喬姆斯基把文法分為了四種類型：0型，1型，2型，3型，詳細的形式化定義網(wǎng)上或者龍書自行查詢，下面是一些對比和簡介：

用一張圖來描述這幾種文法的關(guān)系：

喬姆斯基語言體系

3.2 程序設(shè)計語言使用文法

?非常遺憾的是，程序設(shè)計語言既不是上下文無關(guān)文法，又不是上下文有關(guān)文法。比如，計算機科學家已經(jīng)證明形如如下定義的文法，只能用0型文法分析：

分析：這個語言模式描述了是終結(jié)符a,b組成的字符串，中間的C也是一個終結(jié)符，該語言模式實際上是要求了前后一致、前后匹配。但這個模式在程序設(shè)計語言中有著非常廣泛的存在：比如 在很多計算機程序涉及語言中要求變量要先定義后使用；有些程序設(shè)計語言要求函數(shù)調(diào)用的形參和實參要保持個數(shù)、順序和類型完全一致；而這些約束實際上就是C模式。即想要用文法描述這類前后相關(guān)的約束，上下文無關(guān)文法做不到，甚至上下文有關(guān)文法也很難做到。但對于現(xiàn)今的程序設(shè)計語言，均使用上下文無關(guān)文法用來描述它所能描述的文法，因為上下文無關(guān)文法非常成熟高效，且能描述程序設(shè)計語言中大部分的約束。而對于它無法描述的約束，通常放到語義分析的過程中去做【權(quán)衡思想】。
?通過上面的介紹，我們已經(jīng)知道程序設(shè)計語言語法設(shè)計實現(xiàn)的理論基礎(chǔ)是上下文無關(guān)文法，主要得益于該文法的恰當?shù)恼Z言描述能力、成熟高效的計算機處理策略（下推自動機-push-down automata, PDA）。對于下推自動機，是有完整的定義和實現(xiàn)策略的，可網(wǎng)上查詢了解，其主要是依賴棧來實現(xiàn)，區(qū)別于有限自動機，其核心多了一個有窮的可推入棧的字母表，即可推入堆棧的符號集合，在語法分析源碼分析時，將會看到其真正的面目。

3.3 上下文無關(guān)文法的實現(xiàn)方法

?談實現(xiàn)方法前，先看一下句子、句型和語言的基本定義：

文法分析基礎(chǔ)定義

?語法分析的任務(wù)便是分析一個文法句子的結(jié)構(gòu)，按照文法產(chǎn)生式的規(guī)則識別輸入符號串是否是一個合法的句子。語法分析的方法大致可以分為兩類：

規(guī)約：根據(jù)文法產(chǎn)生式規(guī)則，把串中出現(xiàn)的產(chǎn)生式的右部替換成左部符號
推導(dǎo)：根據(jù)文法產(chǎn)生式規(guī)則，把串中出現(xiàn)的產(chǎn)生式的左部替換成右部符號

3.4 語法分析事例

3.3.1 自上而下的語法分析
?如下圖所示，自上而下分析從文法的開始符號，即樹的根節(jié)點S出發(fā)，向下推導(dǎo)，讓它去跟輸入串x*y從左到右匹配。S只有一個候選，將S擴展為x A y，輸入x，終結(jié)符匹配成功，繼續(xù)往下推導(dǎo)。輸入*號，此時規(guī)則要求匹配A，A是一個非終結(jié)符，有兩個候選式，選擇第一個候選式擴展兩個*號，第一個*號匹配輸入，繼續(xù)調(diào)用詞法分析器得到輸入y，此時語法規(guī)則要求輸入是一個*號，匹配失敗，該層匹配結(jié)束。那是不是意味著句子非法呢？其實不然，主要是A有兩個候選式，此時應(yīng)該回溯到A的開始處，選擇第2個候選，逐步推導(dǎo)下去，匹配成功。

自上而下分析

?在分析過程中，我們可以發(fā)現(xiàn)自上而下分析方法存在的問題：分析過程中，當一個非終結(jié)符用一個候選式匹配成功時，這種匹配可能是暫時的，一旦遇到錯誤，將不得不回溯。除此之外，自上而下分析方法還有一種文法左遞歸問題，導(dǎo)致語法樹會無限擴展下去而陷入死循環(huán)，沒法讀入串進行分析。LL(自左到右，最左推導(dǎo))分析法主要研究的問題就是如何消除回溯和左遞歸。

文法左遞歸問題

3.3.2 自下而上的語法分析
?如下圖所示，給定算數(shù)表達式文法G，開始符號是非終結(jié)符E，它有六個候選。從左到右輸入，輸入i，規(guī)約成E，輸入串變成了E*i+i,接著輸入*,沒有匹配，繼續(xù)移進。然后繼續(xù)輸入i，i規(guī)約成E，語法變成E*E+i。而E*E又可以規(guī)約為E,產(chǎn)生式變?yōu)镋+i，如此繼續(xù)下去，最后規(guī)約得到E，匹配成功。

自下而上分析

?在分析過程中很容易發(fā)現(xiàn)，該分析方法非常適合使用棧進行分析，其核心問題是識別可歸約串。雖然例子中未涉及到該分析方法的問題，但并不是說這個分析法是完美的。自下而上分析方法會有移進-規(guī)約沖突和規(guī)約-規(guī)約沖突。LR（從左到右掃描輸入串、自下而上進行規(guī)約）分析法及其各種變種（SLR、LR(1)、LALR(1))就是研究如何進行自下而上分析法如何設(shè)計的。

3.5 SQLite 語法分析方法

?SQLite中SQL語句的語法分析使用的是LALR(1)[look ahead LR(1)]分析法實現(xiàn)的 ，LALR技術(shù)得到的分析表比LR方法的分析表會小很多(因為其多了一步同心集的合并操作),因此會更加簡潔高效。SQLite其語法分析器是一個名字為lemon的程序根據(jù)輸入語法規(guī)則自動生成的代碼，我們將在后面的學習中分析lemon程序的工作原理。

4.中間代碼生成

?SQLite中的中間代碼生成部分帶真正了解了SQL如何被解析后，單獨開啟章節(jié)介紹。

5.優(yōu)化

?SQLite中的優(yōu)化部分帶真正了解了SQL如何被解析后，單獨開啟章節(jié)介紹。

6.目標代碼生成

?SQLite中的目標代碼生成部分帶真正了解了SQL如何被解析后，單獨開啟章節(jié)介紹。