SQLite 的 SQL 語言剖析器是使用稱為「Lemon」的程式碼產生器程式產生的。Lemon 程式會讀取輸入語言的語法,並產生 C 程式碼來實作該語言的剖析器。
Lemon 沒有自己的原始碼儲存庫。相反地,Lemon 由 SQLite 原始碼樹中的幾個檔案組成
lemon.html → Lemon 的原始詳細使用文件和程式設計師參考。
lemon.c → 讀取語法檔案並產生對應剖析器 C 程式碼的工具程式原始碼。
lempar.c → 產生剖析器 C 程式碼的範本。「lemon」工具程式會讀取此範本,並插入額外程式碼以產生剖析器。
Lemon 會產生 LALR(1) 剖析器。它的運作方式類似於較為常見的工具 Yacc 和 Bison,但 Lemon 加入了一些重要的改進,包括
語法語法較不容易出錯 - 使用符號名稱表示語意值,而不是 Yacc 的「$1」樣式位置標記。
在 Lemon 中,分詞器會呼叫解析器。Yacc 則相反,解析器會呼叫分詞器。Lemon 的方法是可重入且執行緒安全的,而 Yacc 使用全域變數,因此兩者都不是。可重入性對 SQLite 來說特別重要,因為有些 SQL 陳述會對解析器進行遞迴呼叫。例如,在分析 CREATE TABLE 陳述時,SQLite 會遞迴呼叫解析器,以產生 INSERT 陳述,在 sqlite_schema 表中建立新項目。
Lemon 有非終端破壞者的概念,可用於在語法錯誤或其他中止分析後回收記憶體或其他資源。
SQLite 中有兩個地方使用 Lemon。
Lemon 的主要用途是建立 SQL 語言解析器。語法檔案 (parse.y) 由 Lemon 編譯成 parse.c 和 parse.h。parse.c 檔案會併入 合併 中,而不會進一步修改。
Lemon 也用於產生 FTS5 擴充功能中查詢模式表達式的解析器。在此情況下,輸入語法檔案是 fts5parse.y。
將程式碼產生器工具作為專案一部分寄存的其中一個優點是,這些工具可以最佳化,以滿足整體專案的特定需求。Lemon 已從此效應中受益。多年來,Lemon 剖析器產生器已擴充並增強,以提供新的功能和改善 SQLite 的效能。專門設計給 SQLite 使用的 Lemon 的一些特定增強功能包括
Lemon 有「後備」權杖的概念。SQL 語言包含大量關鍵字,而這些關鍵字有潛力與識別名稱發生衝突。Lemon 有能力指定一些關鍵字為能夠「後備」到識別名稱。如果關鍵字出現在輸入權杖串流中,而其脈絡在其他情況下會是語法錯誤,則權杖會在語法錯誤發生之前自動轉換為其後備。此功能讓剖析器能夠非常寬容地處理用作識別名稱的保留字,而這是在 SQL 語言中經常出現的問題。
為了支援 SQLite 的 100% MC/DC 測試 目標,Lemon 產生的剖析器程式碼沒有無法到達的分支,且包含額外的(編譯時選擇)儀器,有助於測量測試範圍。
Lemon 支援語法檔案規則的條件編譯,因此可以根據編譯時選項產生不同的剖析器。
作為效能最佳化,Lemon 輸入語法的簡化動作允許包含「/*A-覆寫-Z*/」形式的註解,以表示規則右手邊的語意值「A」允許直接覆寫左手邊的語意值「Z」。此簡單最佳化減少了用於剖析輸入語法的下推自動機中的堆疊操作數量,因此改善了剖析器的效能。它也讓產生的程式碼更小一些。
SQL 語句的剖析是任何 SQL 資料庫引擎中 CPU 週期的重要消耗者。持續優化 SQLite 的努力讓開發人員花費大量時間調整 Lemon 以產生更快的剖析器。這些努力讓 Lemon 剖析器產生器的所有使用者受益,不只是 SQLite。但如果 Lemon 是單獨維護的工具,要對 SQLite 和 Lemon 進行協調變更會更加困難,因此無法完成這麼多的最佳化。因此,剖析器產生器工具包含在 SQLite 的原始碼樹中,事實證明對工具本身和 SQLite 來說都是淨收益。
Lemon 最初是由 D. Richard Hipp(也是 SQLite 的創建者)編寫的,當時他在 1987 年至 1992 年間就讀於杜克大學研究所。Lemon 的原始建立日期已不可考,但可能約在 1990 年左右。Lemon 會產生 LALR(1) 剖析器。有一個名為「Lime」的伴隨 LL(1) 剖析器產生器工具,但 Lime 的原始碼已遺失。
Lemon 原始碼最初寫成獨立的原始碼檔案,後來才合併成單一的「lemon.c」原始碼檔案。
Lemon 和 SQLite 的作者(Hipp)表示,透過研究 John Ousterhout 的 Tcl 原始原始碼,大幅提升了他的 C 程式設計技巧。Hipp 在 1993 年發現並研究 Tcl。Lemon 是在當時之前編寫的,而 SQLite 是在之後。這兩個產品的編碼風格有明顯的差異,SQLite 顯得更簡潔、更易讀,而且更容易維護。