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

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

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

解析目標(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])
  );

這是本文為了方便說明，實現(xiàn)的一個精簡版本。完整版見我們的開源倉庫 cparser。

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

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

表示允許任意長度的 selectStatement 由 ; 號連接，selectList 的寫法也同理。

matchWord 表示匹配任意單詞。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文介紹了如何生成語法樹，并說明了 默認語法樹 的存在，以及我們之所以要一個定制的語法樹，是為了更方便的理解含義。

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

本文介紹的模型，只是為了便于理解而定制的簡化版，了解全部細節(jié)，請訪問 cparser。

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

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

討論地址是：精讀《手寫 SQL 編譯器 - 語法樹》 · Issue #99 · dt-fe/weekly

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