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

Caicloud 發布于2019-08-23 11:31 / 2419人閱讀

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

1 引言

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

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

解析目標是：

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])
  );

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

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

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

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

matchWord 表示匹配任意單詞。

語法樹是人為對語法結構的抽象，本質上，如果我們到此為止，是可以生成一個 基本語法樹 的，這個語法樹是多維數組，比如：

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

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

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

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

2 精讀

通過上面的分析，我們需要對 chain 函數提供修改局部 AST 結構的能力：

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

我們可以通過額外參數對默認語法樹進行改造，將多維數組結構改變為對象結構，并增加 type variant 屬性標示當前對象的類型、子類型。比如上面的例子，返回的對象告訴使用者：“我是一個表達式，一個 select 表達式，我的結果是 result，我的來源表是 from”。

那么，chain 函數如何實現語法樹功能呢？

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

下圖描述了 chain 函數執行機制：

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

每個元素的子節點全部執行完畢，才會生成當前節點的語法樹。實際上，每個節點執行完，都會調用 callParentNode 訪問父節點，執行到了這個函數，說明子元素已成功執行完畢，補全對應節點的 AST 信息即可。

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

3 總結

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

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

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

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

目前在做性能優化，通用 SQL 文法還在陸續完善中，目前僅可當學習參考，不要用于生產環境。

4 更多討論

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

如果你想參與討論，請點擊這里，每周都有新的主題，周末或周一發布。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/97073.html

精讀《手寫 SQL 編譯器 - 智能提示》

摘要：經過連續幾期的介紹，手寫編譯器系列進入了智能提示模塊，前幾期從詞法到文法語法，再到構造語法樹，錯誤提示等等，都是為智能提示做準備。 1 引言詞法、語法、語義分析概念都屬于編譯原理的前端領域，而這次的目的是做具備完善語法提示的 SQL 編輯器，只需用到編譯原理的前端部分。經過連續幾期的介紹，《手寫 SQL 編譯器》系列進入了智能提示模塊，前幾期從詞法到文法、語法，再到構造語法...

ztyzz 2019-08-23 14:15 評論0 收藏0
精讀《syntax-parser 源碼》

摘要：引言是一個版語法解析器生成器，具有分詞語法樹解析的能力。實現函數用鏈表設計函數是最佳的選擇，我們要模擬調用棧了。但光標所在的位置是期望輸入點，這個輸入點也應該參與語法樹的生成，而錯誤提示不包含光標，所以我們要執行兩次。 1. 引言 syntax-parser 是一個 JS 版語法解析器生成器，具有分詞、語法樹解析的能力。通過兩個例子介紹它的功能。第一個例子是創建一個詞法解析器 my...

yuanxin 2019-08-23 15:37 評論0 收藏0
精讀《手寫 SQL 編譯器 - 錯誤提示》

摘要：總結做語法解析器錯誤提示功能時，再次刷新了筆者三觀，原來我們以為的必然，在編譯器里對應著那么多可能。語法解析器為了讓報錯符合人們的第一直覺，對錯誤信息做了過濾，只保留剩余數最短的那條錯誤信息。 1 引言 showImg(https://segmentfault.com/img/remote/1460000016244315?w=1522&h=272); 編譯器除了生成語法樹之外，還要在...

王陸寬 2019-08-23 11:41 評論0 收藏0