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í)行的饺窿？大家應該都明白鲫咽，SQL雖然非常精簡和易讀姨伤，但其語句是可變長的劫恒，同時又支持許多表達式贩幻、函數等復雜特性，如果僅用if...else...完美的覆蓋SQL的解析两嘴，那幾乎是不可能的段直。因此你可能會急迫的去源碼里尋找答案，并且很容易的找到兩個關鍵函數sqlite3RunParser溶诞、sqlite3Parser，代碼并不算長决侈，你喜出望外螺垢，意識到自己終于要揭開SQL解析的神秘面紗了，但待你定下神來一句一行的想去讀懂這兩個函數時赖歌，卻絞盡腦汁枉圃，終究看不懂這一堆亂七八糟的東西...
?我并不例外，看了兩天這塊代碼庐冯，網上查資料孽亲，這方面的信息少之又少，終究沒能找到一篇可以讓我理解為什么的文章展父，還好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...一堆的關鍵詞都指向了計算機專業(yè)核心專業(yè)課程--編譯原理吼虎，那么只能從這里尋求突破了犬钢。

編譯原理

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

1.編譯過程

?大道至簡肺魁，科學的產生就是先從具體到抽象得到基本原理的過程电湘，而技術的應用則是以基本原理所描述的模型為基礎，尋求對自然事物的科學描述的過程鹅经。因此寂呛，計算機語言的解析過程和自然語言的翻譯過程必然是高度一致的。我們從如下一個英文句子的翻譯過程中瘾晃，理解一下計算機語言的編譯過程贷痪。

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

2.詞法分析

2.1 詞法分析的職責和流程

?詞法分析器的主要任務是讀入源程序的輸入字符、將它們組成詞素蹦误，生成并輸出一個詞法單元序列劫拢，每個詞法單位對應一個詞素。這個詞法單元序列被輸出到語法分析器中進行語法分析强胰。詞法分析器通常還要和符號表進行交互舱沧，當詞法分析器發(fā)現一個標識符的詞素時，它將這個詞素添加到符號表中偶洋。在某些情況下熟吏，詞法分析器會從符號表中讀取有關標識符種類的信息，以確定向語法分析器傳送哪個詞法單元玄窝。

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

?詞法分析器的大概工作過程為：掃描器調用預處理子程序牵寺，將源程序輸入到輸入緩沖區(qū)中，預處理子程序讀取輸入緩沖區(qū)數據恩脂，剔除無用的空白缸剪、跳格、回車等編輯性字符东亦、給出句末符等杏节，并將處理后的更規(guī)范的文本輸入到掃描緩沖區(qū)唬渗。掃描器從掃描緩沖區(qū)中讀入字符并根據詞法規(guī)則進行分詞，輸出單詞符號奋渔。

詞法分析器結構

2.2 詞法分析的形式化處理

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

狀態(tài)轉換圖

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

1. 定義初始狀態(tài)值压固，并定義一個包含所有狀態(tài)和輸入符號的二維表。
2. 從初始狀態(tài)開始靠闭，循環(huán)讀入一個符號帐我，并根據當前狀態(tài)和讀入的符號查詢二維表，跳轉至最新狀態(tài)愧膀。
3. 循環(huán)上述步驟直至遇到終態(tài)結束拦键。

?但由于確定性有限自動機描述的狀態(tài)轉換過于基礎，似乎和實際的需求還有一些差別檩淋，計算機科學家們定義了另外一種看上去更一般化的有限自動機--非確定性有限自動機（NFA）芬为。其要求初態(tài)不再唯一萄金，可以有多個。同時其狀態(tài)轉移函數不再是單值映射媚朦，其允許在輸入一個字（由字符擴展到字）后氧敢，可以存在到達多種狀態(tài)的可能。這樣一來询张，從感官上我們會感覺NFA的識別能力似乎更加強大孙乖，實現起來會更加復雜，因為定義上看DFA只是NFA的一個特例份氧。但經過理論學家的研究和證明唯袄，NFA和DFA的識別能力是相等的，并且研究出了NFA化簡DFA的“套路”蜗帜，這樣恋拷，人民們可以非常容易的用NFA描述問題，再用確定的理論方法轉成DFA進行計算機處理钮糖∶仿樱基于這些理論依據，現在人們已經比較容易的開發(fā)出詞法分析器生成器店归，比如Lex阎抒。

2.3 SQLite中的詞法分析

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

3.語法分析

3.1 語法分析的理論體系

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

用一張圖來描述這幾種文法的關系：

喬姆斯基語言體系

3.2 程序設計語言使用文法

?非常遺憾的是塞关，程序設計語言既不是上下文無關文法，又不是上下文有關文法子巾。比如帆赢，計算機科學家已經證明形如如下定義的文法，只能用0型文法分析：

分析：這個語言模式描述了是終結符a,b組成的字符串线梗，中間的C也是一個終結符椰于，該語言模式實際上是要求了前后一致、前后匹配仪搔。但這個模式在程序設計語言中有著非常廣泛的存在：比如 在很多計算機程序涉及語言中要求變量要先定義后使用瘾婿；有些程序設計語言要求函數調用的形參和實參要保持個數、順序和類型完全一致烤咧；而這些約束實際上就是C模式偏陪。即想要用文法描述這類前后相關的約束，上下文無關文法做不到煮嫌，甚至上下文有關文法也很難做到笛谦。但對于現今的程序設計語言，均使用上下文無關文法用來描述它所能描述的文法昌阿，因為上下文無關文法非常成熟高效饥脑，且能描述程序設計語言中大部分的約束。而對于它無法描述的約束宝泵，通常放到語義分析的過程中去做【權衡思想】好啰。
?通過上面的介紹轩娶，我們已經知道程序設計語言語法設計實現的理論基礎是上下文無關文法儿奶，主要得益于該文法的恰當的語言描述能力、成熟高效的計算機處理策略（下推自動機-push-down automata, PDA）鳄抒。對于下推自動機闯捎，是有完整的定義和實現策略的椰弊，可網上查詢了解，其主要是依賴棧來實現瓤鼻，區(qū)別于有限自動機秉版，其核心多了一個有窮的可推入棧的字母表，即可推入堆棧的符號集合茬祷，在語法分析源碼分析時清焕，將會看到其真正的面目。

3.3 上下文無關文法的實現方法

?談實現方法前祭犯，先看一下句子秸妥、句型和語言的基本定義：

文法分析基礎定義

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

規(guī)約：根據文法產生式規(guī)則，把串中出現的產生式的右部替換成左部符號
推導：根據文法產生式規(guī)則戏售，把串中出現的產生式的左部替換成右部符號

3.4 語法分析事例

3.3.1 自上而下的語法分析
?如下圖所示侨核，自上而下分析從文法的開始符號，即樹的根節(jié)點S出發(fā)灌灾，向下推導搓译，讓它去跟輸入串x*y從左到右匹配。S只有一個候選锋喜，將S擴展為x A y些己，輸入x，終結符匹配成功嘿般，繼續(xù)往下推導段标。輸入*號，此時規(guī)則要求匹配A炉奴，A是一個非終結符逼庞，有兩個候選式，選擇第一個候選式擴展兩個*號瞻赶，第一個*號匹配輸入赛糟，繼續(xù)調用詞法分析器得到輸入y派任，此時語法規(guī)則要求輸入是一個*號，匹配失敗璧南，該層匹配結束掌逛。那是不是意味著句子非法呢？其實不然司倚，主要是A有兩個候選式豆混，此時應該回溯到A的開始處，選擇第2個候選动知，逐步推導下去崖叫，匹配成功。

自上而下分析

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

文法左遞歸問題

3.3.2 自下而上的語法分析
?如下圖所示阔墩，給定算數表達式文法G嘿架，開始符號是非終結符E，它有六個候選啸箫。從左到右輸入耸彪，輸入i，規(guī)約成E忘苛，輸入串變成了E*i+i,接著輸入*,沒有匹配蝉娜，繼續(xù)移進。然后繼續(xù)輸入i扎唾，i規(guī)約成E召川，語法變成E*E+i。而E*E又可以規(guī)約為E,產生式變?yōu)镋+i胸遇，如此繼續(xù)下去荧呐，最后規(guī)約得到E，匹配成功。

自下而上分析

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

3.5 SQLite 語法分析方法

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

4.中間代碼生成

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

5.優(yōu)化

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

6.目標代碼生成

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