開發

用 Go 構建一個 SQL 解析器

廣告
廣告

在本文中,小編將向大家簡單介紹如何在 Go 中構造 LL(1) 解析器,并應用于解析SQL查詢。希望大家能用 Go 對簡單的解析器算法有一個了解和簡單應用。

摘要

本文旨在簡單介紹如何在 Go 中構造 LL(1) 解析器,在本例中用于解析SQL查詢。

為了簡單起見,我們將處理子選擇、函數、復雜嵌套表達式和所有 SQL 風格都支持的其他特性。這些特性與我們將要使用的策略緊密相關。

1分鐘理論

一個解析器包含兩個部分:

  • 詞法分析:也就是“Tokeniser”
  • 語法分析:AST 的創建

詞法分析

讓我們用例子來定義一下。“Tokenising”以下查詢:

SELECT id, name FROM 'users.csv'

表示提取構成此查詢的“tokens”。tokeniser 的結果像這樣:

[]string{"SELECT", "id", ",", "name", "FROM", "'users.csv'"}

語法分析

這部分實際上是我們查看 tokens 的地方,確保它們有意義并解析它們來構造出一些結構體,以一種對將要使用它的應用程序更方便的方式表示查詢(例如,用于執行查詢,用顏色高亮顯示它)。在這一步之后,我們會得到這樣的結果:

query{	Type: "Select",	TableName: "users.csv",	Fields: ["id", "name"],}

有很多原因可能會導致解析失敗,所以同時執行這兩個步驟可能會比較方便,并在出現錯誤時可以立即停止。

策略

我們將定義一個像這樣的解析器:

type parser struct { ?sql ? ? ? ? ? ? string ? ? ? ?// The query to parse ?i ? ? ? ? ? ? ? int ? ? ? ? ? // Where we are in the query ?query ? ? ? ? ? query.Query ? // The "query struct" we'll build ?step ? ? ? ? ? ?step ? ? ? ? ?// What's this? Read on...}// Main function that returns the "query struct" or an errorfunc (p *parser) Parse() (query.Query, error) {}// A "look-ahead" function that returns the next token to parsefunc (p *parser) peek() (string) {}// same as peek(), but advancing our "i" indexfunc (p *parser) pop() (string) {}

直觀地說,我們首先要做的是“peek() 第一個 token”。在基礎的SQL語法中,只有幾個有效的初始 token:SELECT、UPDATE、DELETE等;其他的都是錯誤的。代碼像這樣:

switch strings.ToUpper(parser.peek()) {case "SELECT": ?parser.query.type = "SELECT" // start building the "query struct" ?parser.pop() ?// TODO continue with SELECT query parsing...case "UPDATE": ?// TODO handle UPDATE// TODO other cases...default: ?return parser.query, fmt.Errorf("invalid query type")}

我們基本上可以填寫 TODO 和讓它跑起來!然而,聰明的讀者會發現,解析整個 SELECT 查詢的代碼很快會變得混亂,而且我們有許多類型的查詢需要解析。所以我們需要一些結構。

有限狀態機

FSMs 是一個非常有趣的話題,但我們來這里不是為了講這個,所以不會深入介紹。讓我們只關注我們需要什么。

在我們的解析過程中,在任何給定的點(與其說“點”,不如稱其稱為“節點”),只有少數 token 是有效的,在找到這些 token 之后,我們將進入新的節點,其中不同的 token 是有效的,以此類推,直到完成對查詢的解析。我們可以將這些節點關系可視化為有向圖:

點轉換可以用一個更簡單的表來定義,但是:

我們可以直接將這個表轉換成一個非常大的 switch 語句。我們將使用那個我們之前定義過的 parser.step 屬性:

func (p *parser) Parse() (query.Query, error) { ?parser.step = stepType // initial step ?for parser.i < len(parser.sql) { ? ?nextToken := parser.peek() ? ?switch parser.step { ? ?case stepType: ? ? ?switch nextToken { ? ? ?case UPDATE: ? ? ? ?parser.query.type = "UPDATE" ? ? ? ?parser.step = stepUpdateTable ? ? ?// TODO cases of other query types ? ? ?} ? ?case stepUpdateSet: ? ? ?// ... ? ?case stepUpdateField: ? ? ?// ... ? ?case stepUpdateComma: ? ? ?// ... ? ?} ? ?parser.pop() ?} ?return parser.query, nil}

好了!注意,有些步驟可能會有條件地循環回以前的步驟,比如 SELECT 字段定義上的逗號。這種策略對于基本的解析器非常適用。然而,隨著語法變得復雜,狀態的數量將急劇增加,因此編寫起來可能會變得單調乏味。我建議在編寫代碼時進行測試;更多信息請見下文。

Peek() 實現

記住,我們需要同時實現 peek() 和 pop() 。因為它們幾乎是一樣的,所以我們用一個輔助函數來保持代碼整潔。此外,pop() 應該進一步推進索引,以避免取到空格。

func (p *parser) peek() string { ?peeked, _ := p.peekWithLength() ?return peeked}func (p *parser) pop() string { ?peeked, len := p.peekWithLength() ?p.i += len ?p.popWhitespace() ?return peeked}func (p *parser) popWhitespace() { ?for ; p.i < len(p.sql) && p.sql[p.i] == ' '; p.i++ { ?}}

下面是我們可能想要得到的令牌列表:

var reservedWords = []string{ ?"(", ")", ">=", "<=", "!=", ",", "=", ">", "<", ?"SELECT", "INSERT INTO", "VALUES", "UPDATE", ?"DELETE FROM", "WHERE", "FROM", "SET",}

除此之外,我們可能會遇到帶引號的字符串或純標識符(例如字段名)。下面是一個完整的 peekWithLength() 實現:

func (p *parser) peekWithLength() (string, int) { ?if p.i >= len(p.sql) { ? ?return "", 0 ?} ?for _, rWord := range reservedWords { ? ?token := p.sql[p.i:min(len(p.sql), p.i+len(rWord))] ? ?upToken := strings.ToUpper(token) ? ?if upToken == rWord { ? ? ?return upToken, len(upToken) ? ?} ?} ?if p.sql[p.i] == '\'' { // Quoted string ? ?return p.peekQuotedStringWithLength() ?} ?return p.peekIdentifierWithLength()}

其余的函數都很簡單,留給讀者作為練習。如果您感興趣,可以查看 github 的鏈接,其中包含完整的源代碼實現。

最終驗證

解析器可能會在得到完整的查詢定義之前找到字符串的末尾。實現一個 parser.validate() 函數可能是一個好主意,該函數查看生成的“query”結構,如果它不完整或錯誤,則返回一個錯誤。

測試Go的表格驅動測試模式非常適合我們的情況:

type testCase struct { ?Name ? ? string ? ? ? ? // description of the test ?SQL ? ? ?string ? ? ? ? // input sql e.g. "SELECT a FROM 'b'" ?Expected query.Query ? ?// expected resulting "query" struct ?Err ? ? ?error ? ? ? ? ?// expected error result}

測試實例:

ts := []testCase{ ? ?{ ? ? ?Name: ? ? "empty query fails", ? ? ?SQL: ? ? ?"", ? ? ?Expected: query.Query{}, ? ? ?Err: ? ? ?fmt.Errorf("query type cannot be empty"), ? ?}, ? ?{ ? ? ?Name: ? ? "SELECT without FROM fails", ? ? ?SQL: ? ? ?"SELECT", ? ? ?Expected: query.Query{Type: query.Select}, ? ? ?Err: ? ? ?fmt.Errorf("table name cannot be empty"), ? ?}, ? ?...

像這樣測試測試用例:

for _, tc := range ts { ? ?t.Run(tc.Name, func(t *testing.T) { ? ? ?actual, err := Parse(tc.SQL) ? ? ?if tc.Err != nil && err == nil { ? ? ? ?t.Errorf("Error should have been %v", tc.Err) ? ? ?} ? ? ?if tc.Err == nil && err != nil { ? ? ? ?t.Errorf("Error should have been nil but was %v", err) ? ? ?} ? ? ?if tc.Err != nil && err != nil { ? ? ? ?require.Equal(t, tc.Err, err, "Unexpected error") ? ? ?} ? ? ?if len(actual) > 0 { ? ? ? ?require.Equal(t, tc.Expected, actual[0], ? ? ? ? ?"Query didn't match expectation") ? ? ?} ? ?}) ?}

我使用 verify 是因為當查詢結構不匹配時,它提供了一個 diff 輸出。

深入理解

這個實驗非常適合:

  • 學習 LL(1) 解析器算法
  • 自定義解析無依賴關系的簡單語法

然而,這種方法可能會變得單調乏味,而且有一定的局限性。考慮一下如何解析任意復雜的復合表達式(例如 sqrt(a) =(1 *(2 + 3)))。

要獲得更強大的解析模型,請查看解析器組合符。goyacc 是一個流行的Go實現。

下面是完整的解析器地址:

http://github.com/marianogappa/sqlparser
我還沒有學會寫個人說明!

“分庫分表" ?選型和流程要慎重,否則會失控

上一篇

專訪領英工程副總裁張仁輝:如何馴服算法,打造世界級的職位推薦系統?

下一篇

你也可能喜歡

用 Go 構建一個 SQL 解析器

長按儲存圖像,分享給朋友

ITPUB 每周精要將以郵件的形式發放至您的郵箱


微信掃一掃

微信掃一掃
排球主场论坛