用 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
Image placeholder
winske
未设置
  19人点赞

没有讨论,发表一下自己的看法吧

推荐文章
如何基于 Kafka 构建一个关系型数据库

在这篇文章里,我将分享如何通过扩展KCache(https://github.com/rayokota/kcache)来实现一个全功能的关系型数据库,我把这个数据库叫作KarelDB(https://

微服务架构中如何构建一个数据报告服务?

场景描述在微服务架构中,每个微服务负责自己的数据库,微服务A是不允许直接连接微服务B的数据库进行操作的。现在有2个微服务,一个是订单服务,一个是用户服务。有一个数据报告的需求:生成一份包含用户信息的订

GORM 中文文档_4.5. 原生 SQL 和 SQL 生成器

运行原生SQL 执行原生SQL时不能通过链式调用其他方法 db.Exec("DROPTABLEusers;") db.Exec("UPDATEordersSETshipped_at=?WHEREidI

【Golang+MySQL】记一次 MySQL 数据库迁移(一)

【Golang+mysql】记一次mysql数据库迁移(一)文章地址:https://github.com/stayfoo/stayfoo-hub一、准备目标: 腾讯云CVM自建mysql数据迁移到腾

SQL 查询语句的执行顺序解析

代理搭建-shadowsockshttps://www.jetbrains.com/shop/eform/opens...https://blog.csdn.net/lianghecai5217131

TPC-C解析系列03_TPC-C基准测试之SQL优化

TPC-C是一个非常严苛的基准测试模型,考验的是一个完备的关系数据库系统全链路的能力。这也是为什么在TPC-C的榜单前列,出现的永远只是大家熟知的那几家在业界有着几十年积累、从关系数据库理论开始发展就

03.2. Go 搭建一个 Web 服务器

前面小节已经介绍了Web是基于http协议的一个服务,Go语言里面提供了一个完善的net/http包,通过http包可以很方便的就搭建起来一个可以运行的Web服务。同时使用这个包能很简单地对Web的路

使用Go语言在MacOS创建一个自定义的命令行工具

原文链接:https://idoubi.cc/posts/create-a-cli-tool-in-macos/ 使用MacOS做开发的朋友都知道,我们一般会使用Homebrew做软件包管理,经常会用

MySQL 性能优化:8 种常见 SQL 错误用法!

1、LIMIT语句分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般DBA想到的办法是在type,name,create_time字段上加组合索引。这样条件排序都

为什么SQL正在击败NoSQL,这对未来的数据意味着什么

导读:经过多年的沉寂之后,今天的SQL正在复出。缘由如何?这对数据社区有什么影响?看看本文的分析。以下为译文。自从可以利用计算机做事以来,我们一直在收集的数据以指数级的速度在增长,因此对于数据存储、处

Oracle/云MySQL/MsSQL“大迁移”真相及最优方案

最近一段时间碰到一些数据迁移的项目,如:Oracle迁移到MySQL,MsSQL迁移到MySQL,云MySQL迁移到本地MySQL。对于这方面做了系统的整理。包括:迁移方案的选择、如何跳出迁移遇到的坑

一条SQL语句在MySQL中如何执行的

前两天发了一条SQL慢的原因有哪些,在那篇文章我没有说到优化器之类的,我觉得如果配合一条SQL是如何执行的,会更好,所以特地找了一篇。来源:JavaGuide  |作者:木木匠本篇文章会分析一个sql

SQL 已死,但 SQL 将永存!

在SQL被引入的47年中,它经历了许多数据库的诞生和消亡,也经历了许多数据处理方式的诞生和消亡。以下为译文:四十七年前,两位年轻的IBM研究人员在数据库上提出了一种新的语言,这是一种关系型语言,它奉行

SQL Server 2014的数据库引擎新增功能(参考sqlserver官方文档)

SQLServer2014数据库引擎引入了一些新功能和增强功能,这些功能可以提高设计、开发和维护数据存储系统的架构师、开发人员和管理员的能力和工作效率。  以下是 数据库引擎已增强的方面。数据库引擎功

mysql 进行update时,要更新的字段中有单引号或者双引号导致不能批量生成sql的问题

前言将数据从一张表迁移到另外一张表的过程中,通过mysql的concat方法批量生成sql时遇到了一个问题,即进行UPDATE更新操作时如果原表中的字段中包含单引号'或者双引号",那么就会生成不正确的

symfony 创建一个 flash 提示框

给大家介绍下flash,flash还是比较不错的。于是记录下来。 首先还是在我的baseController中建立一个方法 /** *@authorgf * *flash提示 * *@par

通过 Laravel 创建一个 Vue 单页面应用(一)

使用laravel创建一个Vue单页面应用(SPA)可以构建一个整洁的由API驱动的应用。在此教程中,我们将学习如何构建并运行一个以Vue路由为前端,laravel为后端的SPA应用。首先我们将注意

通过 Laravel 创建一个 Vue 单页面应用(三)

我们将通过演示在vue-router进入一个路由之前,如何异步加载数据来继续使用Laravel构建我们的VueSPA。 之前在通过Laravel创建一个Vue单页应用(二)中完成了UsersInde

使用 Vue.js 和 Iris 共建一个简单的 Todo MVC 应用

本文用Golang的Iris框架作为后端服务,vuejs渲染前端UI,用websocket通信。基于监听hash变化director.js库实现简单路由,axios库与后方沟通,netoffos.j

使用 Vue.js 和 Iris 共建一个简单的 Todo MVC 应用

数据服务 packagetodo import"sync" //Item条目数据 typeItemstruct{ SessionIDstring`json:"-"` IDint64`json:"i

怎么新建一个react项目

怎么新建一个react项目现在比较流行和常用的方式就是利用create-react-app脚手架来帮我们搭建一个初始的react项目,准备工作安装node环境,这个去百度搜索下node安装,在命令行中

建一个5G基站,到底要花多少钱?

自从国内5G正式宣布商用之后,全国各地的5G网络建设速度明显加快了。5G基站的身影,出现在越来越多的城市、角落。5G信号的覆盖范围,也在不断扩大。这意味着,5G的投资已经全面启动,并且在不断增加。一直

使用 Go Wails 框架来构建桌面应用(Go+Vue.js)

众所周知,Go主要用于构建API、web后端和CLI工具。但有趣的是,Go可以用在我们没有预料到的地方。 例如,我们可以使用Wails框架用Go和Vue.js构建一个桌面应用程序。 这是一个新框架,

基于Go的语义解析开源库FMR,“屠榜”模型外的NLP利器

如何合理地表示语言的内在意义?这是自然语言处理业界中长久以来悬而未决的一个命题。 在2013年分布式词向量表示(DistributedRepresentation)出现之前,one-hot是最常用的

基于Go的语义解析开源库FMR,“屠榜”模型外的NLP利器

(由AI科技大本营付费 下载自视觉中国)作者|刘占亮一览群智技术副总裁编辑|Jane出品|AI科技大本营( ID:rgznai100)如何合理地表示语言的内在意义?这是自然语言处理业界中长久以来悬而未