您现在的位置是：亿华云 > 域名

用 Go 构建一个 SQL 解析器

亿华云2025-10-03 07:03:49【域名】2人已围观

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

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

摘要

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

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

1分钟理论

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

词法分析：也就是析器“Tokeniser”

语法分析：AST 的创建

词法分析

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

SELECT id,建个L解 name FROM users.csv

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

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

语法分析

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

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" well build step step // Whats 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 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

) {

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)

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"