關於SQL解析，為何程式語言解析器ANTLR更勝一籌？
相對於其他程式語言來說，SQL是比較簡單的。不過，它依然是一門完善的程式語言，因此對SQL的語法進行解析，與解析其他程式語言（如：Java語言、C語言、Go語言等）並無本質區別。
一、概念
談到SQL解析，就不得不談一下文字識別。文字識別是根據給定的規則把輸入文字的各個部分識別出來，再按照特定的資料格式輸出。以樹形結構輸出是最常見的方式，這就是通常所說的抽象語法樹（AST）。
作為一個開發者，文字識別每天都和我們打交道。在編寫完程式碼之後，編譯器在編譯時首先需要根據程式的語法對程式碼做解析，即文字識別，並生成中間程式碼。
SQL解析和程式程式碼解析類似，它按照SQL語法對SQL文字進行解析，識別出文本中各個部分然後以抽象語法樹的形式輸出。SQL也是一門程式語言，它並不比其他程式語言的語法簡單。一個複雜的建表語句佔用20多k位元組也是正常的。
無論是對SQL進行解析，還是對其他程式語言的語法進行解析，都需要專門的解析器。從零開發則需要較長的時間，而且各種資料庫的SQL方言不盡相同，這並不是一套能夠完全通用的SQL解析引擎。在各種第三方類庫十分完善的現今，找尋一個利器，比從零開發這種刀耕火種的方式好得多。開源的SQL解析器有JSQLParser、FDB和Druid等，用於語法解析的主要有ANTLR、JavaCC等。
JSQLParser是一個通用的SQL解析器，它提供一站式的SQL解析能力，將SQL轉化為語法樹，並提供樹訪問介面供程式遍歷語法樹。雖然使用便利，但它也有一些缺點：
-
無法根據所需的語法生成解析器。對於資料分片所需要的語法來說，它不如ANTLR這樣能夠根據自己需求書寫語法規則的方式輕量級；
-
只支援部分常用的標準SQL語法，像ALTER TABLE、ALTER INDEX、DCL以及各類資料庫的方言支援的力度不足；
-
它採用Visitor模式將抽象語法樹完全封裝，外圍程式無法直接訪問抽象語法樹，在無需完全遍歷樹時，程式碼比較繁瑣。
FDB和Driuid與JSQLParser同類型。它們無需自定義SQL語法，可以拿來即用，但缺乏自定義語法的靈活度。
相對來說，ANTLR則好一些。它並非為SQL解析專門定製的解析器，而是通用的程式語言解析器。它只需編寫名為G4的語法檔案，即可自動生成解析的程式碼，並且以統一的格式輸出，處理起來非常簡單。由於G4檔案是通過開發者自行定製的，因此由ANTLR所生成的程式碼也更加簡潔和個性化。在編寫僅適用於資料分片的語法規則時，可以簡化大量無需關注的SQL語法。對於SQL審計等SQL解析的需求，完全可以用ANTRL編寫另外一份語法規則，可以達到因地制宜的效果。JavaCC與ANTLR類似，都屬於自定義語法型別的解析器。
無論採用哪種解析器，解析過程都是一致的，它分為詞法解析（Lexer）和語法解析（Parser）兩部分。
1、詞法解析
先通過詞法解析器將SQL拆分為一個個不可再分的詞法單元（Token）。在SQL語法中，通常將詞法單元分為關鍵字、識別符號、字面量、運算子和分界符。
-
關鍵字： 資料庫引擎所用到的特殊詞，為保留字元，不能用做識別符號；
-
識別符號： 在SQL語法中是表名稱、列名稱等。對應於程式語言則是包名、類名、方法名、變數名、屬性名等等；
-
字面量： 包括字串和數值；
-
運算子： 包括加減乘除、位運算、邏輯運算等；
-
分界符： 逗號、分號、括號等。
詞法解析器每次讀取一個字元，在當前字元與之前的字元所屬分類不一致時，即完成一個詞法單元的識別。例如，讀取SELECT時，第一個字元是 ’ S’，滿足關鍵字和標示符的規則，第二個字元’E’也同樣滿足，以此類推，直到第7個字元是空格時，則不滿足該規則，那麼就完成了一個詞法單元的識別。SELECT既是SQL規範定義的關鍵字，又同時滿足識別符號規則，因此當一個詞法單元是識別符號時，解析器需要有優先順序的判斷，需要先確定它是否為關鍵字。其他的規則相對簡單，如：以數字開頭的字元則根據數值規則的字面量讀取字元；以雙引號或單引號開頭的則根據字串規則的字面量讀取字元；運算子或分界符就更易識別。舉例說明，以下SQL：
SELECT id, name FROM product WHERE id > 10;
識別之後的詞法單元為：
-
關鍵字： SELECT、FROM、WHERE
-
識別符號： id、name、product
-
字面量： 10
-
運算子： >
-
分界符： ,和;
2、語法解析
語法解析器每次從詞法解析器中獲取一個詞法單元。如果滿足規則，則繼續下一個詞法單元的提取和匹配，直至字串結束；若不滿足規則，便提示錯誤並結束本次解析。
語法解析難點在於規則的迴圈處理以及分支選擇，還有遞迴呼叫和複雜的計算表示式等。
在處理迴圈規則時，當匹配完成一個規則時，匹配規則需要迴圈地再次匹配當前規則，當其不再是當前的規則定義時，才可以繼續進行後續規則的匹配。以CREATE TABLE語句為例。每張表可以包含多列，每個列都可能需要定義名稱、型別、精度等引數。
當一個規則中存在多條分支路徑時，則需要超前搜尋，語法解析器必須和每個可能的分支進行匹配來確定正確的路徑。以ALTER TABLE語句為例。
修改表名語法為：
ALTER TABLE oldTableName RENAME TO newTableName;
刪除列的語法為：
ALTER TABLE tableName DROP COLUMN columnName;
兩個語句均以ALTER TABLE開頭，它們合併在一起的語法為：
ALTER TABLE tableName (RENAME TO newTableName | DROP COLUMN columnName);
匹配完成tableName之後的2個分支選項，需要超前搜尋來確定正確的分支。
在選擇分支時，可能會出現一個分支是另一個分支的子集。此時，當成功匹配短路徑時，需要進一步匹配長路徑，在無法匹配長路徑時，再選取短路徑，這稱之為貪婪匹配。如果不使用貪婪匹配的演算法，則最長的分支規則便永遠不能被匹配了。
當詞法單元不滿足一個可選規則時，則需要與下個規則做匹配，直至匹配成功或與下個非可選規則匹配失敗。在CREATE TABLE語句中，定義列時存在很多可選項，比如是否為空、是否主鍵、是否存在約束條件等。
語法解析器最終將SQL轉換為抽象語法樹。例如以下SQL：
SELECT id, name FROM t_user WHERE status = 'ACTIVE' AND age > 18
解析之後的為抽象語法樹見下圖：
為了便於理解，抽象語法樹中的關鍵字的Token用綠色表示，變數的Token用紅色表示，灰色表示需要進一步拆分。
語法解析要比詞法解析複雜一些，詞法解析的規則相對簡單，定義好詞法單元的規則即可，極少出現分支選擇；而且只需超前搜尋一個字元即可確定詞法單元。但它卻是解析的基礎，如果分詞出現錯誤，語法解析則很難正確處理。
生成抽象語法樹的第三方工具有很多，ANTLR是不錯的選擇。它將開發者定義的規則生成抽象語法樹的Java程式碼並提供訪問者介面。相比於程式碼生成，手寫抽象語法樹在執行效率方面會更加高效，但是工作量也比較大。在效能要求高的場景中，可以考慮定製化抽象語法樹。
二、ANTLR
1、介紹
ANTLR是Another Tool for Language Recognition的簡寫，是一個用Java語言編寫的識別器工具。它能夠自動生成解析器，並將使用者編寫的ANTLR語法規則直接生成目標語言的解析器，它能夠生成Java、Go、C等語言的解析器客戶端。
ANTLR所生成的解析器客戶端將輸入的文字生成抽象語法樹，並提供遍歷樹的介面，以訪問文字的各個部分。ANTLR的實現與前文所講述的詞法分析與語法分析是一致的。詞法分析器根據語法規則做詞法單元的拆分；語法分析器對詞法單元做語義分析，並對規則進行優化以及消除左遞迴等操作。
2、ANTLR語法規則
ANTLR語法規則的主要工作是定義詞法解析規則和語法解析規則。ANTLR約定詞法解析規則以大寫字母開頭，語法解析規則以小寫字母開頭。下面簡單介紹一下ANTLR的規則。
首先需要定義Grammar型別及名稱，名稱必須和檔名一樣。有Lexer、Parser、Tree和Combine這4種語法型別。
-
Lexer定義詞法分析規則；
-
Parser 定義語法分析規則；
-
Tree用於遍歷語法分析樹；
-
Combine既可以定義語法分析規則，也可定義詞法分析規則，規則名稱遵循上述規則；
-
Import 用於匯入語法規則。使用Import語法規則分類，可以使語法規則更加清晰；並且可以採用面向物件的思想設計規則檔案，使其具有多型及繼承的思想。值得注意的是，當前規則的優先順序高於匯入規則。
規則名稱及內容以冒號分隔，分號結尾。例如：
NUM:[0-9]+;
規則的名稱是NUM，以大寫字母開頭，因此是詞法分析的規則；規則的內容是[0-9]+，表示所有的整數。
ANTLR規則基於BNF正規化，用’|’表示分支選項，’*’表示匹配前一個匹配項0次或者多次，’+’ 表示匹配前一個匹配項至少一次。
語法其它部分，讀者感興趣的話請查閱官方文件。
ANTLR生成SQL解析器，首先就是要定義SQL的詞法解析器和語法解析器，下面一一介紹。
3、ANTLR的詞法解析
與之前的SQL解析原理相同，ANTLR的詞法解析同樣是將SQL拆分為詞法單元。ANTLR解析詞法規則時，並不理解規則的具體含義，不清楚哪些規則是關鍵字定義，哪些規則是識別符號定義，它會根據讀取順序為每個規則編號，編號靠前的規則將優先匹配，匹配成功則直接返回該詞法單元。在設計詞法拆分規則時，需要將識別符號規則放置在關鍵字規則之後，確保關鍵字匹配失敗後，再去匹配識別符號。
ANTLR採用狀態轉換表實現字元的匹配。它將詞法拆分規則轉換為表格，每次讀取一個字元，根據當前字元型別及當前狀態查詢該表，並判斷讀入字元是否匹配規則。如果規則匹配，則接受該字元，並繼續讀取下個字元；如果規則不匹配，則拒絕接受該字元。此時，若當前狀態是成功匹配某一詞法單元的可接受狀態，則返回該詞法單元；反之則提示錯誤。以此類推，如果接受該字元，則繼續讀取下一字元。直至成功返回一個詞法單元或匹配失敗提示錯誤。
舉例說明，以下是一個簡易的查詢語句詞法拆分規則：
lexer grammar SelectLexer; SELECT: [Ss] [Ee] [Ll] [Ee] [Cc] [Tt]; FROM: [Ff] [Rr] [Oo] [Mm]; WHERE: [Ww] [Hh] [Ee] [Rr] [Ee]; LEFT: [Ll][Ee][Ff][Tt]; RIGHT: [Rr][Ii][Gg][Hh][Tt]; INNER: [Ii][Nn][Nn][Ee][Rr]; JOIN: [Jj] [Oo] [Ii] [Nn]; ON : [Oo][Nn]; BETWEEN: [Bb] [Ee] [Ee] [Rr] [Ee]; AND: [Aa] [Nn] [Dd]; OR:[Oo][Rr]; GROUP: [Gg] [Rr] [Oo] [Uu] [Pp]; BY:[Bb] [Yy]; ORDER: [Oo] [Rr] [Dd] [Ee] [Rr]; ASC:[Aa][Ss][Cc]; DESC:[Dd][Ee][Ss][Cc]; IN: [Ii][Nn]; ID: [a-zA-Z0-9]+; WS: [ \t\r\n] + ->skip;
它定義了大小寫不敏感的從SELECT到IN的關鍵字規則以及識別符號規則ID，識別符號規則放在最後。WS規則表示遇到空格、製表符、換行符跳過。輸入字元中任何字元，在詞法分析器中都要找到對應的規則，否則會提示失敗。如果去掉WS規則，對於包含空格的SQL將會得到以下的錯誤提示。
錯誤原因是第1行的第6、第10以及第11個字元是回車換行符，詞法規則找不到對應的規則。
4、ANTLR的語法解析
ANTLR的語法解析用於定義組成語句的短語規則。語法規則由各個資料庫廠商提供，因此，在SQL解析時，只需要將它們轉換為ANTLR的語法規則即可。需要注意的是，SQL表示式的規則定義十分複雜。不僅包括常見的數學表示式和布林表示式，還包括函式呼叫以及各資料庫的私有日期表示式、Window函式、Case語句等。
ANTLR同樣採用狀態轉換表的方式檢查詞法單元是否滿足語法規則。語法分析器呼叫詞法分析器獲取詞法單元並其檢查是否符合規則。當遇到多個選項分支時，則採用貪婪匹配原則，優先走完最長路徑的分支。如果分支中有多個規則滿足條件，按順序匹配。
以如下規則舉例說明：
grammar Test; ID: [a-zA-Z0-9]+; WS: [ \t\r\n] + ->skip; testAll:test1 |test2|test3|test21; test1:ID; test2:ID ID; test21:ID ID; test3:ID ID ID; test4:test1+;
使用testAll規則做如下測試：
-
當輸入的引數為“a1 a2 a3”時，使用test3分支，而並未使用(test1 a1) (test1 a2) (test1 a3)或(test2 a1 a2) (test1 a3)這種匹配模式；
-
當輸入的引數為“a1 a2”時，雖然test21規則也能夠匹配，但前面有test2規則匹配，因此使用test2規則；
-
當輸入的引數為“a1 a2 #”，由於無法匹配‘#’，因此提示錯誤。
5、分片上下文提取
完成了SQL解析之後，最後一步便是對資料分片所需的上下文進行提取。它通過對SQL的理解，以訪問抽象語法樹的方式去提煉分片所需的上下文，並標記有可能需要改寫的位置。供分片使用的解析上下文包含查詢選擇項（Select Items）、表資訊（Table）、分片條件（Sharding Condition）、自增主鍵資訊（Auto increment Primary Key）、排序資訊（Order By）、分組資訊（Group By）以及分頁資訊（Limit、Rownum、Top）等。
三、Sharding-Sphere中的SQL解析
SQL解析作為分庫分表類產品的核心，其效能和相容性是最重要的衡量指標。
Sharding-Sphere的前身，Sharding-Sphere在1.4.x之前的版本使用Druid作為SQL解析器。經實際測試，它的效能遠超其它解析器。
從1.5.x版本開始，Sharding-Sphere採用完全自研的SQL解析引擎。由於目的不同，Sharding-Sphere並不需要將SQL轉為一顆完全的抽象語法樹，也無需通過訪問器模式進行二次遍歷。它採用對SQL“半理解”的方式，僅提煉資料分片需要關注的上下文，因此SQL解析的效能和相容性得到了進一步的提高。
在最新的3.x版本中，Sharding-Sphere嘗試使用ANTLR作為SQL解析的引擎，並計劃根據 DDL->TCL->DAL–>DCL->DML–>DQL這個順序 ，依次替換原有的解析引擎。使用ANTLR的原因是希望Sharding-Sphere的解析引擎能夠更好地對SQL進行相容。對於複雜的表示式、遞迴、子查詢等語句，雖然Sharding-Sphere的分片核心並不關注，但是會影響對於SQL理解的友好度。自研的SQL解析引擎為了效能的極致，對這些方便並未處理，使用時會直接報錯。
經過例項測試，ANTLR解析SQL的效能比自研的SQL解析引擎慢3倍左右。為彌補差距，Sharding-Sphere將使用Prepared Statement的SQL解析的語法樹放入快取。因此建議採用PreparedStatement這種SQL預編譯的方式提升效能。Sharding-Sphere會提供配置項，將兩種解析引擎共存，交由使用者抉擇SQL解析的相容性與效能。
有關Sharding-Sphere的延伸閱讀：