社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
奇技指南
在本文中，小编将向大家简单介绍如何在 Go 中构造 LL(1) 解析器，并应用于解析SQL查询。希望大家能用 Go 对简单的解析器算法有一个了解和简单应用。
本文来自公众号360云计算。
摘要
本文旨在简单介绍如何在 Go 中构造 LL(1) 解析器，在本例中用于解析SQL查询。
为了简单起见，我们将处理子选择、函数、复杂嵌套表达式和所有 SQL 风格都支持的其他特性。这些特性与我们将要使用的策略紧密相关。
1分钟理论
一个解析器包含两个部分：
词法分析：也就是“Tokeniser”
语法分析：AST 的创建
词法分析
让我们用例子来定义一下。“Tokenising”以下查询：
SELECT id, name FROM 'users.csv'id, name FROM 'users.csv'表示提取构成此查询的“tokens”。tokeniser 的结果像这样：
[]string{"SELECT", "id", ",", "name", "FROM", "'users.csv'"}"SELECT", "id", ",", "name", "FROM", "'users.csv'"}语法分析
这部分实际上是我们查看 tokens 的地方，确保它们有意义并解析它们来构造出一些结构体，以一种对将要使用它的应用程序更方便的方式表示查询(例如，用于执行查询，用颜色高亮显示它)。在这一步之后，我们会得到这样的结果：
query{ Type: "Select", TableName: "users.csv", Fields: ["id", "name"],}
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) {}
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")}
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}// 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++ { }}
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",}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()}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}
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"), }, ...
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") } }) }_, 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官方技术公众号
技术干货|一手资讯|精彩活动
空·
更多精彩内容“阅读原文”
右边给我一朵小花花
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
