• 【理上网来喜迎十九大】外媒记者:全面依法治国为中国经济增长保驾护航 2019-07-05
  • “重庆造”国际一类新药 获批同时进入中美临床试验 2019-07-05
  • 企业服务行业跨越式发展 2018年神州顺利办聚焦企业人、财、物 2019-07-03
  • 土地不是劳动成果,而是一种自然资源,就像空气、阳光不是劳动成果而是自然资源一样,所以土地不具有价值,买房只应支付房屋费,不应该支付土地费。 2019-07-03
  • 阳泉市旅发委对全市挂牌督办建设项目进行督导 2019-07-03
  • “忻州工匠”“忻州技能标兵”评选活动启动 2019-07-02
  • 世界杯赞助商集体亮相球迷广场 海信站C位夺眼球 2019-07-01
  • 吃鸡蛋常犯8个错,这些技巧9成人不知道 2019-07-01
  • 父亲为监视孩子盗监控探头 不料IP未改反被“监控” 2019-06-29
  • 最高降7.02万 阿尔法·罗密欧全系调价 2019-06-28
  • 讲法治说情操 江北党员干部听“老马”宣讲“两会”精神 2019-06-23
  • 招聘启事丨西部网诚聘新媒体编辑记者、实习编辑等人员 2019-06-23
  • 南方日报:治理软件不止于“黑名单” 2019-06-21
  • 端午节遇上父亲节长沙楼市上演“宫心计” ——凤凰网房产长沙 2019-06-14
  • 美说唱歌手在迈阿密购买摩托遭遇中枪 疑似身亡说唱中枪-国际博览 2019-06-14
  • 开发

    黑龙江11选五任选开奖:用 Go 构建一个 SQL 解析器

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

    摘要

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

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

    1分钟理论

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

    • 词法分析:也就是“Tokeniser”
    • 语法分析:AST 的创建

    词法分析

    让我们用例子来定义一下?!癟okenising”以下查询:

    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实现。

    下面是完整的解析器地址:

    //github.com/marianogappa/sqlparser
    我还没有学会写个人说明!

    “分库分表" ?选型和流程要慎重,否则会失控

    上一篇

    专访领英工程副总裁张仁辉:如何驯服算法,打造世界级的职位推荐系统?

    下一篇

    你也可能喜欢

    用 Go 构建一个 SQL 解析器

    长按储存图像,分享给朋友

    ITPUB 每周精要将以邮件的形式发放至您的邮箱


    微信扫一扫

    微信扫一扫
  • 【理上网来喜迎十九大】外媒记者:全面依法治国为中国经济增长保驾护航 2019-07-05
  • “重庆造”国际一类新药 获批同时进入中美临床试验 2019-07-05
  • 企业服务行业跨越式发展 2018年神州顺利办聚焦企业人、财、物 2019-07-03
  • 土地不是劳动成果,而是一种自然资源,就像空气、阳光不是劳动成果而是自然资源一样,所以土地不具有价值,买房只应支付房屋费,不应该支付土地费。 2019-07-03
  • 阳泉市旅发委对全市挂牌督办建设项目进行督导 2019-07-03
  • “忻州工匠”“忻州技能标兵”评选活动启动 2019-07-02
  • 世界杯赞助商集体亮相球迷广场 海信站C位夺眼球 2019-07-01
  • 吃鸡蛋常犯8个错,这些技巧9成人不知道 2019-07-01
  • 父亲为监视孩子盗监控探头 不料IP未改反被“监控” 2019-06-29
  • 最高降7.02万 阿尔法·罗密欧全系调价 2019-06-28
  • 讲法治说情操 江北党员干部听“老马”宣讲“两会”精神 2019-06-23
  • 招聘启事丨西部网诚聘新媒体编辑记者、实习编辑等人员 2019-06-23
  • 南方日报:治理软件不止于“黑名单” 2019-06-21
  • 端午节遇上父亲节长沙楼市上演“宫心计” ——凤凰网房产长沙 2019-06-14
  • 美说唱歌手在迈阿密购买摩托遭遇中枪 疑似身亡说唱中枪-国际博览 2019-06-14
  • 七星彩走势图下期预测号码 竞彩足球比分点球算吗 江苏e球彩总进球走势 连码有二打一生肖 今日福彩中心3d开机号码 欢乐生肖开奖结果 玩3d怎么买赚钱的方法 江苏11选5任5奖金多少 安徽快3遗漏数据 山西快乐10分钟技巧 3d怎么看组三组六 青海快三推荐预测号 合肥2019彩票中奖信息 京东彩票投注时间 七乐彩走势图预测