用Go构建一个SQL解析器

摘要

本文旨在简单介绍如何在 Go 中构造 LL(1) 解析器，在本例中用于解析SQL查询。

为了简单起见，我们将处理子选择、函数、复杂嵌套表达式和所有 SQL 风格都支持的其他特性。这些特性与我们将要使用的策略紧密相关。

1分钟理论

一个解析器包含两个部分：

  • 词法分析：也就是“Tokeniser”
  • 语法分析：AST 的创建

词法分析

让我们用例子来定义一下。“Tokenising”以下查询：

 
 
 
 
    
  
  
  
  
  1. SELECT id, name FROM 'users.csv' 
    2.

表示提取构成此查询的“tokens”。tokeniser 的结果像这样：

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

语法分析

这部分实际上是我们查看 tokens 的地方，确保它们有意义并解析它们来构造出一些结构体，以一种对将要使用它的应用程序更方便的方式表示查询(例如，用于执行查询，用颜色高亮显示它)。在这一步之后，我们会得到这样的结果：

 
 
 
 
    
  
  
  
  
  1. query{ 
    2.   
  
  
  
  2.     Type: "Select", 
    3.   
  
  
  
  3.     TableName: "users.csv", 
    4.   
  
  
  
  4.     Fields: ["id", "name"], 
    5.   
  
  
  
  5. } 
    6.

有很多原因可能会导致解析失败，所以同时执行这两个步骤可能会比较方便，并在出现错误时可以立即停止。

策略

我们将定义一个像这样的解析器：

 
 
 
 
    
  
  
  
  
  1. type parser struct { 
    2.   
  
  
  
  2.   sql             string        // The query to parse 
    3.   
  
  
  
  3.   i               int           // Where we are in the query 
    4.   
  
  
  
  4.   query           query.Query   // The "query struct" we'll build 
    5.   
  
  
  
  5.   step            step          // What's this? Read on... 
    6.   
  
  
  
  6. } 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8. // Main function that returns the "query struct" or an error 
    9.   
  
  
  
  9. func (p *parser) Parse() (query.Query, error) {} 
    10.   
  
  
  
  10.  
    11.   
  
  
  
  11. // A "look-ahead" function that returns the next token to parse 
    12.   
  
  
  
  12. func (p *parser) peek() (string) {} 
    13.   
  
  
  
  13.  
    14.   
  
  
  
  14. // same as peek(), but advancing our "i" index 
    15.   
  
  
  
  15. func (p *parser) pop() (string) {} 
    16.

直观地说，我们首先要做的是“peek() ***个 token”。在基础的SQL语法中，只有几个有效的初始 token：SELECT、UPDATE、DELETE等;其他的都是错误的。代码像这样：

 
 
 
 
    
  
  
  
  
  1. switch strings.ToUpper(parser.peek()) { 
    2.   
  
  
  
  2.  
    3.   
  
  
  
  3. case "SELECT": 
    4.   
  
  
  
  4.   parser.query.type = "SELECT" // start building the "query struct" 
    5.   
  
  
  
  5.   parser.pop() 
    6.   
  
  
  
  6.   // TODO continue with SELECT query parsing... 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8. case "UPDATE": 
    9.   
  
  
  
  9.   // TODO handle UPDATE 
    10.   
  
  
  
  10.  
    11.   
  
  
  
  11. // TODO other cases... 
    12.   
  
  
  
  12.  
    13.   
  
  
  
  13. default: 
    14.   
  
  
  
  14.   return parser.query, fmt.Errorf("invalid query type") 
    15.   
  
  
  
  15.  
    16.   
  
  
  
  16. } 
    17.

我们基本上可以填写 TODO 和让它跑起来!然而，聪明的读者会发现，解析整个 SELECT 查询的代码很快会变得混乱，而且我们有许多类型的查询需要解析。所以我们需要一些结构。

有限状态机

FSMs 是一个非常有趣的话题，但我们来这里不是为了讲这个，所以不会深入介绍。让我们只关注我们需要什么。

在我们的解析过程中，在任何给定的点(与其说“点”，不如称其称为“节点”)，只有少数 token 是有效的，在找到这些 token 之后，我们将进入新的节点，其中不同的 token 是有效的，以此类推，直到完成对查询的解析。我们可以将这些节点关系可视化为有向图：

点转换可以用一个更简单的表来定义，但是：

我们可以直接将这个表转换成一个非常大的 switch 语句。我们将使用那个我们之前定义过的 parser.step 属性：

 
 
 
 
    
  
  
  
  
  1. func (p *parser) Parse() (query.Query, error) { 
    2.   
  
  
  
  2.   parser.step = stepType // initial step 
    3.   
  
  
  
  3.  
    4.   
  
  
  
  4.   for parser.i < len(parser.sql) { 
    5.   
  
  
  
  5.     nextToken := parser.peek() 
    6.   
  
  
  
  6.  
    7.   
  
  
  
  7.     switch parser.step { 
    8.   
  
  
  
  8.     case stepType: 
    9.   
  
  
  
  9.       switch nextToken { 
    10.   
  
  
  
  10.       case UPDATE: 
    11.   
  
  
  
  11.         parser.query.type = "UPDATE" 
    12.   
  
  
  
  12.         parser.step = stepUpdateTable 
    13.   
  
  
  
  13.  
    14.   
  
  
  
  14.       // TODO cases of other query types 
    15.   
  
  
  
  15.       } 
    16.   
  
  
  
  16.     case stepUpdateSet: 
    17.   
  
  
  
  17.       // ... 
    18.   
  
  
  
  18.     case stepUpdateField: 
    19.   
  
  
  
  19.       // ... 
    20.   
  
  
  
  20.     case stepUpdateComma: 
    21.   
  
  
  
  21.       // ... 
    22.   
  
  
  
  22.     } 
    23.   
  
  
  
  23.  
    24.   
  
  
  
  24.     parser.pop() 
    25.   
  
  
  
  25.   } 
    26.   
  
  
  
  26.  
    27.   
  
  
  
  27.   return parser.query, nil 
    28.   
  
  
  
  28. } 
    29.

好了!注意，有些步骤可能会有条件地循环回以前的步骤，比如 SELECT 字段定义上的逗号。这种策略对于基本的解析器非常适用。然而，随着语法变得复杂，状态的数量将急剧增加，因此编写起来可能会变得单调乏味。我建议在编写代码时进行测试;更多信息请见下文。

Peek() 实现

记住，我们需要同时实现 peek() 和 pop() 。因为它们几乎是一样的，所以我们用一个辅助函数来保持代码整洁。此外，pop() 应该进一步推进索引，以避免取到空格。

 
 
 
 
    
  
  
  
  
  1. func (p *parser) peek() string { 
    2.   
  
  
  
  2.   peeked, _ := p.peekWithLength() 
    3.   
  
  
  
  3.   return peeked 
    4.   
  
  
  
  4. } 
    5.   
  
  
  
  5.  
    6.   
  
  
  
  6. func (p *parser) pop() string { 
    7.   
  
  
  
  7.   peeked, len := p.peekWithLength() 
    8.   
  
  
  
  8.   p.i += len 
    9.   
  
  
  
  9.   p.popWhitespace() 
    10.   
  
  
  
  10.   return peeked 
    11.   
  
  
  
  11. } 
    12.   
  
  
  
  12.  
    13.   
  
  
  
  13. func (p *parser) popWhitespace() { 
    14.   
  
  
  
  14.   for ; p.i < len(p.sql) && p.sql[p.i] == ' '; p.i++ { 
    15.   
  
  
  
  15.   } 
    16.   
  
  
  
  16. } 
    17.

下面是我们可能想要得到的令牌列表：

 
 
 
 
    
  
  
  
  
  1. var reservedWords = []string{ 
    2.   
  
  
  
  2.   "(", ")", ">=", "<=", "!=", ",", "=", ">", "<", 
    3.   
  
  
  
  3.   "SELECT", "INSERT INTO", "VALUES", "UPDATE", 
    4.   
  
  
  
  4.   "DELETE FROM", "WHERE", "FROM", "SET", 
    5.   
  
  
  
  5. } 
    6.

除此之外，我们可能会遇到带引号的字符串或纯标识符(例如字段名)。下面是一个完整的 peekWithLength() 实现：

 
 
 
 
    
  
  
  
  
  1. func (p *parser) peekWithLength() (string, int) { 
    2.   
  
  
  
  2.   if p.i >= len(p.sql) { 
    3.   
  
  
  
  3.     return "", 0 
    4.   
  
  
  
  4.   } 
    5.   
  
  
  
  5.   for _, rWord := range reservedWords { 
    6.   
  
  
  
  6.     token := p.sql[p.i:min(len(p.sql), p.i+len(rWord))] 
    7.   
  
  
  
  7.     upToken := strings.ToUpper(token) 
    8.   
  
  
  
  8.     if upToken == rWord { 
    9.   
  
  
  
  9.       return upToken, len(upToken) 
    10.   
  
  
  
  10.     } 
    11.   
  
  
  
  11.   } 
    12.   
  
  
  
  12.   if p.sql[p.i] == '\'' { // Quoted string 
    13.   
  
  
  
  13.     return p.peekQuotedStringWithLength() 
    14.   
  
  
  
  14.   } 
    15.   
  
  
  
  15.   return p.peekIdentifierWithLength() 
    16.   
  
  
  
  16. } 
    17.

其余的函数都很简单，留给读者作为练习。如果您感兴趣，可以查看 github 的链接，其中包含完整的源代码实现。

最终验证

解析器可能会在得到完整的查询定义之前找到字符串的末尾。实现一个 parser.validate() 函数可能是一个好主意，该函数查看生成的“query”结构，如果它不完整或错误，则返回一个错误。

测试Go的表格驱动测试模式非常适合我们的情况：

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

测试实例：

 
 
 
 
    
  
  
  
  
  1. ts := []testCase{ 
    2.   
  
  
  
  2.     { 
    3.   
  
  
  
  3.       Name:     "empty query fails", 
    4.   
  
  
  
  4.       SQL:      "", 
    5.   
  
  
  
  5.       Expected: query.Query{}, 
    6.   
  
  
  
  6.       Err:      fmt.Errorf("query type cannot be empty"), 
    7.   
  
  
  
  7.     }, 
    8.   
  
  
  
  8.     { 
    9.   
  
  
  
  9.       Name:     "SELECT without FROM fails", 
    10.   
  
  
  
  10.       SQL:      "SELECT", 
    11.   
  
  
  
  11.       Expected: query.Query{Type: query.Select}, 
    12.   
  
  
  
  12.       Err:      fmt.Errorf("table name cannot be empty"), 
    13.   
  
  
  
  13.     }, 
    14.   
  
  
  
  14.     ... 
    15.

像这样测试测试用例：

 
 
 
 
    
  
  
  
  
  1. for _, tc := range ts { 
    2.   
  
  
  
  2.     t.Run(tc.Name, func(t *testing.T) { 
    3.   
  
  
  
  3.       actual, err := Parse(tc.SQL) 
    4.   
  
  
  
  4.       if tc.Err != nil && err == nil { 
    5.   
  
  
  
  5.         t.Errorf("Error should have been %v", tc.Err) 
    6.   
  
  
  
  6.       } 
    7.   
  
  
  
  7.       if tc.Err == nil && err != nil { 
    8.   
  
  
  
  8.         t.Errorf("Error should have been nil but was %v", err) 
    9.   
  
  
  
  9.       } 
    10.   
  
  
  
  10.       if tc.Err != nil && err != nil { 
    11.   
  
  
  
  11.         require.Equal(t, tc.Err, err, "Unexpected error") 
    12.   
  
  
  
  12.       } 
    13.   
  
  
  
  13.       if len(actual) > 0 { 
    14.   
  
  
  
  14.         require.Equal(t, tc.Expected, actual[0], 
    15.   
  
  
  
  15.           "Query didn't match expectation") 
    16.   
  
  
  
  16.       } 
    17.   
  
  
  
  17.     }) 
    18.   
  
  
  
  18.   } 
    19.

我使用 verify 是因为当查询结构不匹配时，它提供了一个 diff 输出。

深入理解

这个实验非常适合：

  • 学习 LL(1) 解析器算法
  • 自定义解析无依赖关系的简单语法

然而，这种方法可能会变得单调乏味，而且有一定的局限性。考虑一下如何解析任意复杂的复合表达式(例如 sqrt(a) =(1 *(2 + 3)))。

要获得更强大的解析模型，请查看解析器组合符。goyacc 是一个流行的Go实现。

下面是完整的解析器地址(或点击阅读原文查看)：http://github.com/marianogappa/sqlparser

 

文章题目：用Go构建一个SQL解析器
文章网址：http://www.mswzjz.cn/qtweb/news14/388914.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能

贝锐智能技术为您推荐以下文章

商城网站知识

分类信息网

网站收录　　 　网站空间　　 　响应式网站设计　　 　四川国泰民安消防　　 　固迪佳新材料　　 　卡多尼人工智　　 　成都服务器运维　　 　专业网站建设　　 　h5响应式网站　　 　营销型网站建设　　 　雅安机房托管　　 　教育培训网站建设方案　　 　成都微信小程序开发　　 　青羊总部基地　　 　成都木托盘　　 　四川平武网站建设　　 　成都未宇聚　　 　微信网站开发　　 　上市企业网站建设方案　　 　广告品牌策划设计