摘要：經(jīng)過連續(xù)幾期的介紹，手寫編譯器系列進(jìn)入了智能提示模塊，前幾期從詞法到文法語法，再到構(gòu)造語法樹，錯誤提示等等，都是為智能提示做準(zhǔn)備。

詞法、語法、語義分析概念都屬于編譯原理的前端領(lǐng)域，而這次的目的是做 具備完善語法提示的 SQL 編輯器，只需用到編譯原理的前端部分。

經(jīng)過連續(xù)幾期的介紹，《手寫 SQL 編譯器》系列進(jìn)入了 “智能提示” 模塊，前幾期從 詞法到文法、語法，再到構(gòu)造語法樹，錯誤提示等等，都是為 “智能提示” 做準(zhǔn)備。

由于智能提示需要對詞法分析、語法分析做深度定制，所以我們沒有使用 antlr4 等語法分析器生成工具，而是創(chuàng)造了一個 JS 版語法分析生成器 syntax-parser。

這次一口氣講完如何從 syntax-parser 到做一個具有智能提示功能的 SQL 編輯器。

從語法解析、智能提示和 SQL 編輯器封裝三個層次來介紹，這三個層次就像俄羅斯套娃一樣具有層層遞進(jìn)的關(guān)系。

為了更清晰展現(xiàn)邏輯層次，同時滿足解耦的要求，筆者先從智能提示整體設(shè)計架構(gòu)講起。

syntax-parser 是一個 JS 版的語法分析器生成器，除了類似 antlr4 基本語法分析功能外，還支持專門為智能提示優(yōu)化的功能，后面會詳細(xì)介紹。整體架構(gòu)設(shè)計如下圖所示：

首先需要實(shí)現(xiàn) SQL 語法，我們利用語法分析器生成器 syntax-parser，生成一個 SQL 語法分析器，這一步其實(shí)是利用 syntax-parser 能力完成了 sql lexer 與 sql parser。

為了解析語法樹含義，我們需要在 sql parser 基礎(chǔ)之上編寫一套 sql reader，包含了一些分析函數(shù)解析語法樹的語義。

利用 monaco-editor 生態(tài)，利用 sql reader 封裝 monaco-editor 插件，同時實(shí)現(xiàn) 用戶 <=> 編輯器 間的交互，與 編輯器 <=> 語義分析器 間的交互。

syntax-parser 分為詞法分析、語法分析兩步。詞法分析主要利用正則構(gòu)造一個有窮自動機(jī)，大家都學(xué)過的 “編譯原理” 里有更完整的解讀，或者移步 精讀《手寫 SQL 編譯器 - 詞法分析》，這里主要介紹語法分析。

詞法分析的輸入是語法分析輸出的 Tokens。Tokens 就是一個個單詞，Token 結(jié)構(gòu)存儲了單詞的值、位置、類型。

我們需要構(gòu)造一個執(zhí)行鏈條消費(fèi)這些 Token，也就是可以執(zhí)行文法掃描的程序。我們用四種類型節(jié)點(diǎn)描述文法，如下圖所示：

如果不了解文法概念，可以閱讀 精讀《手寫 SQL 編譯器 - 文法介紹》

能消耗 Token 的只有 MatchNode 節(jié)點(diǎn)，ChainNode 節(jié)點(diǎn)描述先后關(guān)系（比如 expr -> name id），TreeNode 節(jié)點(diǎn)描述并列關(guān)系（比如 factor -> num | id），F(xiàn)unctionNode 是函數(shù)節(jié)點(diǎn)，表示還未展開的節(jié)點(diǎn)（如果把文法匹配比做迷宮探險，那這是個無限迷宮，無法窮盡展開）。

如何用 syntax-parser 描述一個文法，可以訪問文檔，現(xiàn)在我們已經(jīng)描述了一個文法樹，應(yīng)該如何解析呢？

我們先找到一個非終結(jié)符作為根節(jié)點(diǎn)，深度遍歷所有非終結(jié)符節(jié)點(diǎn)，遇到 MatchNode 時如果匹配，就消耗一個 Token 并繼續(xù)前進(jìn)，否則文法匹配失敗。

遇到 ChainNode 會按照順序執(zhí)行其子節(jié)點(diǎn)；遇到 FunctionNode（非終結(jié)符節(jié)點(diǎn)）會執(zhí)行這個函數(shù)，轉(zhuǎn)換為一個非 FunctionNode 節(jié)點(diǎn)，如下圖所示：

遇到 TreeNode 節(jié)點(diǎn)時保存這個節(jié)點(diǎn)運(yùn)行狀態(tài)并繼續(xù)執(zhí)行，在 MatchNode 匹配失敗時可以還原到此節(jié)點(diǎn)繼續(xù)嘗試下個節(jié)點(diǎn)，如下圖所示：

這樣就具備了最基本的語法分析功能，如需更詳細(xì)閱讀，可以移步 精讀《手寫 SQL 編譯器 - 語法分析》。

我們還做了一些優(yōu)化，比如 First 集優(yōu)化與路徑緩存優(yōu)化。限于篇幅，分布在以下幾篇文章：

精讀《手寫 SQL 編譯器 - 回溯》

精讀《手寫 SQL 編譯器 - 語法樹》

精讀《手寫 SQL 編譯器 - 錯誤提示》

精讀《手寫 SQL 編譯器 - 性能優(yōu)化之緩存》

SQL 編輯器重點(diǎn)在于如何做輸入提示，也就是如何在用戶光標(biāo)位置給出恰當(dāng)?shù)奶崾?。這就是我們定制 SQL 編輯器的原因，輸入提示與語法檢測需要分開來做，而語法樹并不能很好解決輸入提示的問題。

為了找到一個較為完美的語法提示方案，通過查閱大量資料，我決定將光標(biāo)作為一個 Token 考慮來實(shí)現(xiàn)智能提示。

我們用 | 表示光標(biāo)所在位置，那么下面的 SQL 應(yīng)該如何處理？

select | from b;

從語法角度來看，它是錯的，因?yàn)閷?shí)際上是一個不完整語句 "select from b;"

從提示角度來看，它是對的，因?yàn)檫@是一個正確的輸入過程，光標(biāo)位置再輸入一個單詞就正確了。

你會發(fā)現(xiàn)，從語法和提示角度來看同一個輸入，結(jié)果往往是矛盾的，所以我們需要分兩條線程分別處理語法與提示。

但輸入錯誤時，我們是無法構(gòu)造語法樹的，而智能提示的時機(jī)往往都是語句語法錯誤的時機(jī)，用過 AST 工具的人都知道?？墒菦]有語法樹，我們怎么做到智能的提示呢？試想如下語句：

select c.| from (
  select * from dt;
) c;

面對上面這個語句，很顯然 c. 沒有寫完，一般的語法樹解析器提示你語法錯誤。你可能想到這幾種方案：

字符串匹配方式強(qiáng)行提示。但很顯然這樣提示不準(zhǔn)確，沒有完整語法樹，是無法做精確解析的。而且當(dāng)語法復(fù)雜時，字符串解析方案幾乎無從下手。

把光標(biāo)位置用一個特殊的字符串補(bǔ)上，先構(gòu)造一個臨時正確的語句，生成 AST 后再找到光標(biāo)位置。

一般我們會采取第二種方案，看上去相對靠譜。處理過程是這樣的：

select c.$my_custom_symbol$ from ...

之后在 AST 中找到 $my_custom_symbol$ 字符串，對應(yīng)的節(jié)點(diǎn)就是光標(biāo)位置。實(shí)際上這可以解決大部分問題，除了關(guān)鍵字。

這種方案唯有關(guān)鍵字場景不兼容，試想一下：

select a |from b;
# select a $my_custom_symbol$ b;

你會發(fā)現(xiàn)，“補(bǔ)全光標(biāo)文字” 法，在關(guān)鍵字位置時，會把原本正確的語句變成錯誤的語句，根本解析不出語法樹。

我們在 syntax-parser 解析引擎層就解決了這個問題，解決方案是 連同光標(biāo)位置一起解析。

我們做兩個基本假設(shè)：

需要自動補(bǔ)全的位置分為 “關(guān)鍵字” 與 “非關(guān)鍵字”。

“非關(guān)鍵字” 位置基本都是由字符串構(gòu)成的。

關(guān)鍵字：

因此針對第一種假設(shè)，syntax-parser 內(nèi)置了 “關(guān)鍵字提示” 功能。因?yàn)?syntax-parser 可以拿到你配置的文法，因此當(dāng)給定光標(biāo)位置時，可以拿到當(dāng)前位置前一個 Token，通過回溯和平行嘗試，將后面所有可能性提示出來，如下圖：

輸入是 select a |，灰色部分是已經(jīng)匹配成功的部分，而我們發(fā)現(xiàn)光標(biāo)位置前一個 Token 正是紅色標(biāo)識的 word，通過嘗試運(yùn)行推導(dǎo)，我們發(fā)現(xiàn)，桔紅色標(biāo)記的 "," 和 "from" 都是 word 可能的下一個確定單詞，這種單詞就是 SQL 語法中的 “關(guān)鍵字”，syntax-parser 會自動告訴你，光標(biāo)位置可能的輸入是 [",", "from"]。

所以關(guān)鍵字的提示已經(jīng)在 syntax-parser 層內(nèi)置解決了！而且無論語法正確與否，都不影響提示結(jié)果，因?yàn)樗惴ㄊ?“尋找光標(biāo)位置前一個 Token 所有可能的下一個 Token”，這可以完全由詞法分析器內(nèi)置支持。

非關(guān)鍵字：

針對非關(guān)鍵字，我們解決方案和用特殊字符串補(bǔ)充類似，但也有不同：

在光標(biāo)位置插入一個新 Token，這個 Token 類型是特殊的 “光標(biāo)類型”。

在 word 解析函數(shù)加一個特殊判斷，如果讀到 “光標(biāo)類型” Token，也算成功解析，且消耗 Token。

因此 syntax-parser 總是返回兩個 AST 信息：

{
  "ast": {},
  "cursorPath": []
}

分別是語法樹詳細(xì)信息，與光標(biāo)位置在語法樹中的訪問路徑。

對于 select a | 的情況，會生成三個 Tokens：["select", "a", "cursor"]，對于 select a| 的情況，會生成兩個 Tokens：["select", "a"]，也就是光標(biāo)與字符相連時，不會覆蓋這個字符。

cursorPath 的生成也比 “字符串補(bǔ)充” 方案更健壯，syntax-parser 生成的 AST 會記錄每一個 Token 的位置，最終會根據(jù)光標(biāo)位置進(jìn)行比對，進(jìn)而找到光標(biāo)對應(yīng)語法樹上哪個節(jié)點(diǎn)。

對 .| 的處理：

可能你已經(jīng)想到了，.| 情況是很通用的輸入場景，比如 user. 希望提示出 user 對象的成員函數(shù)，或者 SQL 語句表名存在項(xiàng)目空間的情況，可能 tableName 會存在 .| 的語法。

.| 狀況時，語法是錯誤的，此時智能提示會遇到挑戰(zhàn)。根據(jù)查閱的資料，這塊也有兩種常見處理手法：

在 . 位置加上特殊標(biāo)識，讓語法解析器可以正確解析出語法樹。

抹去 .，先讓語法正確解析，再分析語法樹拿到 . 前面 Token 的屬性，推導(dǎo)出后面的屬性。

然而這兩種方式都不太優(yōu)雅，syntax-parser 選擇了第三種方式：隔空打牛。

通過抽象，我們發(fā)現(xiàn)，無論是 user.name 還是 udf:count() 這種語法，都要求在某個制定字符打出時（比如 . 或 :），提示到這個字符后面跟著的 Token。

此時光標(biāo)焦點(diǎn)在 . 而非之后的字符上，那我們何不將光標(biāo)偷偷移到 . 之后，進(jìn)行空光標(biāo) Token 補(bǔ)位呢！這樣不但能完全復(fù)用之前的處理思想，還可以拿到我們真正想拿到的位置：

select a(.|) from b;
# select a. (|) from b

對比后發(fā)現(xiàn)，第一行擁有 4 個 Token，語法錯誤，而經(jīng)過修改的第二行擁有 5 個 Token（一個光標(biāo)補(bǔ)位），語法正確，且光標(biāo)所在位置等價于第一行我們希望提示的位置，此問題得以解決。

我們擁有了內(nèi)置 “智能提示” 功能的語法解析器，定制了一套自定義的 SQL 詞法、文法描述，便完成了 sql-lexer 與 sql-parser 這一層。由于 SQL 文法完善工作非常龐大，且需要持續(xù)推進(jìn)，這里舉流計算中，申明動態(tài)維表的例子：

CREATE TABLE dwd_log_pv_wl_ri(
  PRIMARY KEY(rowkey),
  PERIOD FOR SYSTEM_TIME
) WITH ()

要支持這種語法，我們在非終結(jié)符 tableOption 下增加兩個分支即可：

const tableOption = () =>
  chain([
    chain(stringOrWord, dataType)(),
    chain("primary", "key", "(", primaryKeyList, ")")(),
    chain("period", "for", "system_time")()
  ])();

sql-reader：

為了方便解析 SQL 語法樹，我們在 sql-reader 內(nèi)置了幾個常用方法，比如：

找到距離光標(biāo)位置最近的父節(jié)點(diǎn)。比如 select a, b, | from d 會找到這個 selectStatement。

根據(jù)表源找到所有提供的字段。表源是指 from 之后跟的語法，不但要考慮嵌套場景，別名，分組，方言，還要追溯每個字段來源于哪張表（針對 join 或 union 的情況）。

有了 sql-reader，我們可以保證在這種層層嵌套 + 別名混淆 + select * 這種復(fù)雜的場景下，仍然能追溯到字段的最原始名稱，最原始的表名：

這樣上層業(yè)務(wù)拓展時，可以拿到足夠準(zhǔn)、足夠多的信息，具有足夠好的拓展型。

monaco-editor plugin：

我們也支持了更上層的封裝，Monaco Editor 插件級別的，只需要填一些參數(shù)：獲取表名、獲取字段的回調(diào)函數(shù)就能 Work，統(tǒng)一了內(nèi)部業(yè)務(wù)的調(diào)用方式：

import { monacoSqlAutocomplete } from "@alife/monaco-sql-plugin";

// Get monaco and editor.

monacoSqlAutocomplete(monaco, editor, {
  onInputTableField: async tableName => { // ...},
  onInputTableName: async () => { // ... },
  onInputFunctionName: async () => { // ... },
  onHoverTableName: async cursorInfo => { // ... },
  onHoverTableField: (fieldName, extra) => { // ... },
  onHoverFunctionName: functionName => { // ... }
});

比如實(shí)現(xiàn)了 onInputTableField 接口，我們可以拿到當(dāng)前表名信息，輕松實(shí)現(xiàn)字段提示：

你也許會看到，上圖中鼠標(biāo)位置有錯誤提示（紅色波浪線），但依然給出了正確的推薦提示。這得益于我們對 syntax-parser 內(nèi)部機(jī)制的優(yōu)化，將語法檢查與智能提示分為兩個模塊獨(dú)立處理，經(jīng)過語法解析，雖然拋出了語法錯誤，但因?yàn)橛辛斯鈽?biāo)的加入，最終生成了語法樹。

再比如實(shí)現(xiàn)了 onHoverFunctionName，可以自定義鼠標(biāo) hover 在函數(shù)時的提示信息：

showImg("https://segmentfault.com/img/remote/1460000017490085");

而你只需要實(shí)現(xiàn) onInputTableField，告訴程序每個表可以提供哪些字段，整個流程就會嚴(yán)格的層層檢查表名提供對原始字段與 selectList 描述的輸出字段，找到映射關(guān)系并逐級傳遞、校驗(yàn)，最終 Merge 后一直冒泡到當(dāng)前光標(biāo)位置所在語句，形成輸入建議。

整個智能提示的封裝鏈條如下：

syntax-parser -> sql-parser -> monaco-editor-plugin

對應(yīng)關(guān)系是：

語法解析器生成器 -> SQL 語法解析器 -> 編輯器插件

這樣邏輯層次清晰，解耦，而且可以從任意節(jié)點(diǎn)切入，進(jìn)行自定義，比如：

從 syntax-parser 開始使用

從最底層開始使用，也許有兩個目的：

上層封裝的 sql-parser 不夠好用，我重寫一個 sql-parser" 以及 monaco-editor-plugin"。

我的場景不是 SQL，而是流程圖語法、或 Markdown 語法的自動提示。

針對這種情況，首先將目標(biāo)文法找到，轉(zhuǎn)化成 syntax-parser 的語法，比如：

chain(word, "=>", word);

再仿照 sql-parser -> monaco-editor-plugin 的結(jié)構(gòu)把上層封裝依次實(shí)現(xiàn)。

從 sql-parser 開始使用

也許你需要的僅僅是一顆 SQL 語法樹？或者你的輸出目標(biāo)不是 SQL 編輯器而是一個 UI 界面？那可以試試直接使用 sql-parser。

sql-parser 不僅可以生成語法樹，還能找到當(dāng)前光標(biāo)位置所在語法樹的節(jié)點(diǎn)，找到 SQL 某個語法返回的所有字段列表等功能，基于它，甚至可以做 UI 與 SQL 文本互轉(zhuǎn)的應(yīng)用。

從 monaco-editor-plugin 開始使用

也許你需要支持自動提示的 SQL 編輯器，那太棒了，直接用 monaco-editor-plugin 吧，根據(jù)你的業(yè)務(wù)場景或個人喜好，實(shí)現(xiàn)一個定制的 monaco-editor 交互插件。

目前我們只開源最底層的 syntax-parser，這也是業(yè)務(wù)無關(guān)的語法解析引擎生成器，期待您的使用與建議！

討論地址是：精讀《手寫 SQL 編譯器 - 智能提示》 · Issue #118 · dt-fe/weekly

如果你想?yún)⑴c討論，請點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。前端精讀 - 幫你篩選靠譜的內(nèi)容。