精讀《手寫 SQL 編譯器 - 詞法分析》

wuyangnju 發布于2019-08-22 18:35 / 1019人閱讀

摘要：解析可以分為如下四步詞法分析，將字符串拆分成包含關鍵詞識別的字符段。涉及到語意處理就要考慮上下文，而這都不是詞法分析階段要考慮的。更多討論討論地址是精讀手寫編譯器詞法分析如果你想參與討論，請點擊這里，每周都有新的主題，周末或周一發布。

1 引言

因為工作關系，需要開發支持眾多方言的 SQL 編輯器，所以復習了一下編譯原理相關知識。

相比編譯原理專家，我們只需要了解部分編譯原理即可實現 SQL 編輯器，所以這是一篇寫給前端的編譯原理文章。

解析 SQL 可以分為如下四步：

詞法分析，將 SQL 字符串拆分成包含關鍵詞識別的字符段（Tokens）。

語法分析，利用自頂向下或自底向上的算法，將 Tokens 解析為 AST，可以手動，也可以自動。

錯誤檢測、恢復、提示推斷，都需要利用語法分析產生的 AST。

語義分析，做完這一步就可以執行 SQL 語句了，不過對前端而言，不需要深入到這一步，可以跳過。

2 精讀

詞法分析就像刀削面的過程，拿著一段字符串（面條）一端不斷下刀，當面條被切完也就完成了詞法分析，所以詞法分析是字符串 -> 一堆字符段的過程。

流程很簡單，難點就在下刀的分寸了，每次砍幾厘米呢？

回到詞法分析，為了準備切分，我們需要定義 SQL 的 Token 有哪些類型，即 Token 分類。

Token 分類

SQL 的 Token 可以分為如下幾類：

注釋。

關鍵字（SELECT、CREATE）。

操作符（+、-、>=）。

開閉合標志（(、CASE）。

占位符（?）。

空格。

引號包裹的文本、數字、字段。

方言語法（${variable}）。

可以看到，在詞法分析階段，我們的 Tokens 不需要關心關鍵詞是什么，只要識別是不是關鍵詞即可，因為關鍵詞的辨認會留到語法分析時處理。涉及到語意處理就要考慮上下文，而這都不是詞法分析階段要考慮的。

同樣，操作符、空格、文本、占位符等構成了 SQL 語句的其他部分，最后通過開閉合標志比如左括號和右括號，讓 SQL 支持子語句。

再強調一次，雖然 SQL 支持子語句，但并不是放在任何位置都是合理的，其他類型 Token 同理，但是詞法分析不需要考慮 Token 是否合理，只要切分即可。

用正則逐段分詞

像大多數語言一樣，SQL 為了方便人類閱讀，采用從左到右的書寫方式，因此分詞方向也從左到右。

我們為每個 Token 類型寫一個函數，比如匹配空格的匹配函數：

function getTokenWhitespace(restStr: string) {
  const matches = restStr.match(/^(s+)/);

  if (matches) {
    return { type, value: matches[1] };
  }
}

restStr 表示掐去頭部剩下的 SQL 字符串，所有匹配函數都拿 restStr 進行匹配，已經匹配的不需要再處理。

通過正則 /^(s+)/ 匹配到第一個以空格開頭的空格（讀起來有點別扭），匹配時必須保證以你要匹配的內容開頭，而且只匹配一次，這樣才不會在切詞時發生遺漏。

同理匹配 /**/ 類型注釋時，也能通過正則輕而易舉的實現：

function getTokenBlockComment(restStr: string) {
  const matches = restStr.match(/^(/*[^]*?(?:*/|$))/);

  if (matches) {
    return { type, value: matches[1] };
  }
}

其中 (?:*/) 表示匹配到以 */ 結尾處，而 (?:*/|$) 后面的 |$ 表示或者直接匹配到結尾（如果一直沒有遇到 */ 那后面全部當作注釋）。

所以只要 Token 分類得當，并且能為每一個分類寫一個頭匹配正則，分詞功能就實現了 90%。

方言拓展

為了支持某些方言，需要從分詞時就開始做考慮。比如 ${variable} 作為一種變量用法時，我們需要在普通字段的正則匹配中，加入一項 ${[a-zA-Z0-9]+} 匹配。

如果要支持純中文作為字段，可以再補充 |u4e00-u9fa5。

分詞主流程

有了一個個分詞函數，再補充一個不斷匹配、切割字符串、再匹配的主函數即可，這一步更簡單：

while (sqlStr) {
  token =
    getTokenWhitespace(sqlStr, token) | getTokenBlockComment(sqlStr, token);

  sqlStr = sqlStr.substring(token.value.length);

  tokens.push(token);
}

上面的函數每取一次 Token，都將取到的 Token 長度丟掉，繼續匹配剩下的字符串，直到字符串被切分完為止。

有些特殊情況需要拿到上次的 Token 才能判斷下一個 Token 該如何切割，所以將 Token 傳給每一個下一步 Match 函數。

最后，執行這個主函數，分詞就完成了！

3 總結

分詞比較簡單，到這里就全部結束了。后面即將進入深水區語法分析，敬請期待。

4 更多討論

討論地址是：精讀《手寫 SQL 編譯器 - 詞法分析》 · Issue #93 · dt-fe/weekly

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

云服務器 GPU云服務器 flex詞法分析語言簡單詞法分析器c語言 sql預編譯詞法

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96025.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 引言文法用來描述語言的語法規則，所以不僅可以用在編程語言上，也可用在漢語、英語上。 2 精讀我們將一塊語法規則稱為產生式，使用 Left → Right 表示任意產生式，用 Left => Right 表示產生式的推導過程，比如對...

TNFE 2019-08-22 18:45 評論0 收藏0