萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 資料庫 >> MS SQL 資料庫

Mixer SQL 詞法分析器設計:基於狀態機的 Go 實現

前言

在開發 Mixer 數據庫代理時,我們需要在 Proxy 層實現自定義路由、SQL 黑名單、防 SQL 注入等功能。這些功能的核心基石在於對用戶發送的 SQL 語句進行解析,而這正是令我最頭疼的詞法分析與語法分析環節。

目前我僅實現了一個簡易的詞法分析器,能將 SQL 語句分解為多個 Token。至於從 Token 進一步進行語法分析、構建 SQL 的抽象語法樹(AST),我尚無經驗(編譯原理基礎薄弱),急需高手協助。因此,本文僅簡要介紹 Mixer 的詞法分析實現。

Tokenize:詞法分析的幾種路徑

在眾多場景中,詞法分析通常有以下幾種實現方式:

  • 使用成熟工具(如 Lex):MySQL Proxy 採用此方式。但學習成本高、生成代碼可讀性差、代碼量大,且可能較慢。MySQL 自身也選擇自行實現詞法分析模組。
  • 正則表達式:性能是主要考量,且複雜度不亞於使用 Lex 類工具。
  • 狀態機:我認為這是自己動手實現詞法解析的最佳方式。對於 SQL 詞法解析,採用狀態機自行編寫難度不大,故 Mixer 採用此方案自主實現。

狀態機實現模式

傳統狀態機常採用 state + action + switch 模式:

switch state {
case state1:
    state = action1()
case state2:
    state = action2()
case state3:
    state = action3()
}

若狀態過多,case 語句會膨脹。可透過「狀態函數」簡化:每個狀態函數執行當前動作並直接返回下一個狀態函數。

type stateFn func(*Lexer) stateFn

for state := startState; state != nil {
    state = state(lexer)
}

核心任務便是實現各個狀態函數及其對應的下一狀態函數。

Mixer Lexer 核心邏輯

Mixer 的詞法分析主要參考 Go 標準庫 template/parse 的實現,代碼位於 parser 模組。Lexer 需對外提供 NextToken 方法,供後續語法分析獲取 Token。

func (l *Lexer) NextToken() (Token, error) {
    for {
        select {
        case t := <-l.tokens:
            return t, nil
        default:
            if l.state == nil {
                return Token{TK_EOF, ""}, l.err
            }
            l.state = l.state(l)
            if l.err != nil {
                return Token{TK_UNKNOWN, ""}, l.err
            }
        }
    }
}

tokens 是一個 Channel,每個狀態解析出的 Token 會發送到此 Channel,NextToken 從中取值;若 Channel 為空,則再次調用狀態函數繼續解析。得益於 Go 的協程與 Channel 機制,實現一個詞法解析器變得相當輕鬆,剩下的工作便是編寫針對 SQL 的各類狀態函數。

待完善項目

Mixer 的詞法分析仍有不足,例如對科學計數法數值的解析不完善。後續計劃參考 MySQL 官方詞法分析模組進一步完善。

copyright © 萬盛學電腦網 all rights reserved