用 Go 构建一个 SQL 解析器

栏目: 数据库 · 发布时间: 5年前

内容简介:本文旨在简单介绍如何在 Go 中构造 LL(1) 解析器,在本例中用于解析SQL查询。为了简单起见,我们将处理子选择、函数、复杂嵌套表达式和所有 SQL 风格都支持的其他特性。这些特性与我们将要使用的策略紧密相关。一个解析器包含两个部分:

女主宣言

在本文中,小编将向大家简单介绍如何在 Go 中构造 LL(1) 解析器,并应用于解析 SQL 查询。希望大家能用 Go 对简单的解析器算法有一个了解和简单应用。

PS:丰富的一线技术、多元化的表现形式,尽在“ 3 60云计算 ”,点关注哦!

摘要

本文旨在简单介绍如何在 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 error
func (p *parser) Parse() (query.Query, error) {}

// A "look-ahead" function that returns the next token to parse
func (p *parser) peek() (string) {}

// same as peek(), but advancing our "i" index
func (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 是有效的,以此类推,直到完成对查询的解析。我们可以将这些节点关系可视化为有向图:

用 Go 构建一个 SQL 解析器

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

用 Go 构建一个 SQL 解析器

我们可以直接将这个表转换成一个非常大的 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

360云计算

由360云平台团队打造的技术分享公众号,内容涉及 数据库、大数据、微服务、容器、AIOps、IoT 等众多技术领域,通过夯实的技术积累和丰富的一线实战经验,为你带来最有料的技术分享

用 Go 构建一个 SQL 解析器


以上所述就是小编给大家介绍的《用 Go 构建一个 SQL 解析器》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Essential C++中文版

Essential C++中文版

[美] Stanley B. Lippman / 侯捷 / 华中科技大学出版社 / 2001-8 / 39.80元

书中以4个面向来表现C++的本质:procedural(程序性的)、generic(泛型的)、object-based(个别对象的)、object-oriented(面向对象的),全书围绕着一系列逐渐繁复的程序问题,以及用以解决这些问题的语言特性。循此方式,读者不只学到C++的函数和结构,也会学习到它们的设计目的和基本原理。一起来看看 《Essential C++中文版》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具