摘要：返回的語(yǔ)法樹(shù)作為結(jié)果被傳遞到文法中，其結(jié)果可能是。每個(gè)元素的子節(jié)點(diǎn)全部執(zhí)行完畢，才會(huì)生成當(dāng)前節(jié)點(diǎn)的語(yǔ)法樹(shù)。更多討論討論地址是精讀手寫(xiě)編譯器語(yǔ)法樹(shù)如果你想?yún)⑴c討論，請(qǐng)點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。

重回 “手寫(xiě) SQL 編輯器” 系列。之前幾期介紹了 詞法、文法、語(yǔ)法的解析，以及回溯功能的實(shí)現(xiàn)，這次介紹如何生成語(yǔ)法樹(shù)。

基于 《回溯》 一文介紹的思路，我們利用 JS 實(shí)現(xiàn)一個(gè)微型 SQL 解析器，并介紹如何生成語(yǔ)法樹(shù)，如何在 JS SQL 引擎實(shí)現(xiàn)語(yǔ)法樹(shù)生成功能！

解析目標(biāo)是：

select name, version from my_table;

文法：

const root = () => chain(selectStatement, many(";", selectStatement));

const selectStatement = () => chain("select", selectList, fromClause);

const selectList = () => chain(matchWord, many(",", matchWord));

const fromClause = () => chain("from", matchWord);

const statement = () =>
  chain(
    "select",
    selectList,
    "from",
    chain(tableName, [whereStatement, limitStatement])
  );

這是本文為了方便說(shuō)明，實(shí)現(xiàn)的一個(gè)精簡(jiǎn)版本。完整版見(jiàn)我們的開(kāi)源倉(cāng)庫(kù) cparser。

root 是入口函數(shù)，many() 包裹的文法可以執(zhí)行任意次，所以

chain(selectStatement, many(";", selectStatement));

表示允許任意長(zhǎng)度的 selectStatement 由 ; 號(hào)連接，selectList 的寫(xiě)法也同理。

matchWord 表示匹配任意單詞。

語(yǔ)法樹(shù)是人為對(duì)語(yǔ)法結(jié)構(gòu)的抽象，本質(zhì)上，如果我們到此為止，是可以生成一個(gè) 基本語(yǔ)法樹(shù) 的，這個(gè)語(yǔ)法樹(shù)是多維數(shù)組，比如：

const fromClause = () => chain("from", matchWord);

這個(gè)文法生成的默認(rèn)語(yǔ)法樹(shù)是：["from", "my_table"]，只不過(guò) from my_table 具體是何含義，只有當(dāng)前文法知道（第一個(gè)標(biāo)志無(wú)含義，第二個(gè)標(biāo)志表示表名）。

fromClause 返回的語(yǔ)法樹(shù)作為結(jié)果被傳遞到文法 selectStatement 中，其結(jié)果可能是：["select", [["name", "version"]], ["from", "my_table"]]。

大家不難看出問(wèn)題：當(dāng)默認(rèn)語(yǔ)法樹(shù)聚集在一起，就無(wú)法脫離文法結(jié)構(gòu)多帶帶理解語(yǔ)法含義了，為了脫離文法結(jié)構(gòu)理解語(yǔ)法樹(shù)，我們需要將其抽象為一個(gè)有規(guī)可循的結(jié)構(gòu)。

通過(guò)上面的分析，我們需要對(duì) chain 函數(shù)提供修改局部 AST 結(jié)構(gòu)的能力：

const selectStatement = () =>
  chain("select", selectList, fromClause)(ast => ({
    type: "statement",
    variant: "select",
    result: ast[1],
    from: ast[2]
  }));

我們可以通過(guò)額外參數(shù)對(duì)默認(rèn)語(yǔ)法樹(shù)進(jìn)行改造，將多維數(shù)組結(jié)構(gòu)改變?yōu)閷?duì)象結(jié)構(gòu)，并增加 type variant 屬性標(biāo)示當(dāng)前對(duì)象的類(lèi)型、子類(lèi)型。比如上面的例子，返回的對(duì)象告訴使用者：“我是一個(gè)表達(dá)式，一個(gè) select 表達(dá)式，我的結(jié)果是 result，我的來(lái)源表是 from”。

那么，chain 函數(shù)如何實(shí)現(xiàn)語(yǔ)法樹(shù)功能呢？

對(duì)于每個(gè)文法（每個(gè) chain 函數(shù)），其語(yǔ)法樹(shù)必須等待所有子元素執(zhí)行完，才能生成。所以這是個(gè)深度優(yōu)先的運(yùn)行過(guò)程。

下圖描述了 chain 函數(shù)執(zhí)行機(jī)制：

生成結(jié)構(gòu)中有四個(gè)基本結(jié)構(gòu)，分別是 Chain、Tree、Function、Match，足以表達(dá)語(yǔ)法解析需要的所有邏輯。（不包含 可選、多選 邏輯）。

每個(gè)元素的子節(jié)點(diǎn)全部執(zhí)行完畢，才會(huì)生成當(dāng)前節(jié)點(diǎn)的語(yǔ)法樹(shù)。實(shí)際上，每個(gè)節(jié)點(diǎn)執(zhí)行完，都會(huì)調(diào)用 callParentNode 訪問(wèn)父節(jié)點(diǎn)，執(zhí)行到了這個(gè)函數(shù)，說(shuō)明子元素已成功執(zhí)行完畢，補(bǔ)全對(duì)應(yīng)節(jié)點(diǎn)的 AST 信息即可。

對(duì)于修改局部 AST 結(jié)構(gòu)函數(shù)，需等待整個(gè) ChainNode 執(zhí)行完畢才調(diào)用，并將返回的新 AST 信息存儲(chǔ)下來(lái)，作為這個(gè)節(jié)點(diǎn)的最終 AST 信息并傳遞給父級(jí)（或者沒(méi)有父級(jí)，這就是根結(jié)點(diǎn)的 AST 結(jié)果）。

本文介紹了如何生成語(yǔ)法樹(shù)，并說(shuō)明了 默認(rèn)語(yǔ)法樹(shù) 的存在，以及我們之所以要一個(gè)定制的語(yǔ)法樹(shù)，是為了更方便的理解含義。

同時(shí)介紹了如何通過(guò) JS 運(yùn)行一套完整的語(yǔ)法解析器，以及如何提供自定義 AST 結(jié)構(gòu)的能力。

本文介紹的模型，只是為了便于理解而定制的簡(jiǎn)化版，了解全部細(xì)節(jié)，請(qǐng)?jiān)L問(wèn) cparser。

最后說(shuō)一下為何要做這個(gè)語(yǔ)法解析器。如今有許多開(kāi)源的 AST 解析工具，但筆者要解決的場(chǎng)景是語(yǔ)法自動(dòng)提示，需要在語(yǔ)句不完整，甚至錯(cuò)誤的情況，給出當(dāng)前光標(biāo)位置的所有可能輸入。所以通過(guò)完整重寫(xiě)語(yǔ)法解析器內(nèi)核，在解析的同時(shí)，生成語(yǔ)法樹(shù)的同時(shí)，也給出光標(biāo)位置下一個(gè)可能輸入提示，在通用錯(cuò)誤場(chǎng)景自動(dòng)從錯(cuò)誤中恢復(fù)。

目前在做性能優(yōu)化，通用 SQL 文法還在陸續(xù)完善中，目前僅可當(dāng)學(xué)習(xí)參考，不要用于生產(chǎn)環(huán)境。

討論地址是：精讀《手寫(xiě) SQL 編譯器 - 語(yǔ)法樹(shù)》 · Issue #99 · dt-fe/weekly

如果你想?yún)⑴c討論，請(qǐng)點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。