用 Go 构建一个 SQL 解析器 |
您所在的位置：网站首页 › go搜索 › 用 Go 构建一个 SQL 解析器 |
用 Go 构建一个 SQL 解析器
|
女主宣言 在本文中，小编将向大家简单介绍如何在 Go 中构造 LL(1) 解析器，并应用于解析SQL查询。希望大家能用 Go 对简单的解析器算法有一个了解和简单应用。 PS：丰富的一线技术、多元化的表现形式，尽在“360云计算”，点关注哦！ 摘要 本文旨在简单介绍如何在 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{ "(", ")", ">=", "", " |
【本文地址】