利用goyacc解析sql并生成go struct

刚好需要做一个基于自定义DSL的规则引擎,准备用yacc来解析dsl,需要熟悉一下yacc,因为用的编程语言是golang,所以很自然要用goyacc. 为了熟悉goyacc,决定以练代学,写个小demo,于是很自然的想到了解析sql生成go文件。

然后,发现网上关于goyacc的介绍很少,所以记录一下学习过程。

yacc包含了两部分,语法解析器(Parser)与词法解析器(Lex). 但实际上,它只实现了语法分析,并没有实现词法分析,但它提供了一个词法分析接口,需要你自己实现。

type yyLexer interface {
    Lex(lval *yySymType) int
    Error(s string)
}

下面,我们分别来介绍这两部分。

语法分析

在语法分析里,有两个词terminalnonterminal,翻译为终结符非终结符,分别用%token%type来表示,表示不可拆分和可拆分。实际上,非终结符只是方便人看的,并无实际意义。 比如,我们用伪代码表示的规则

S -> A B ( C | D ) E

A -> F G

D -> H I

这里面,S, A,D就是非终结符,只是为了辅助编写规则用的,B C E F G H I 不可再分,是终结符。

你完全可以用一条规则来表示 F G B (C | (H I)) E

在大多数编译器里,会把终结符称之为token

所以,词法规则(rules)的本质是什么?本质就是一条token数组,表示了token的排列顺序。但是需要注意的是,因为token之间有的关系,所以token数组并不一定只有一条, 比如上文中,就有两条,分别是 F G B C EF G B H I E, 你的输入文本匹配任意一条就可以,但如果任意一条都无法匹配上,则表示输入文本不合法。

每个token都有一个唯一标识,一般我们用一个常量int来表示(其实字符串也可以,但goyacc固定了int类型). 不同的token有不同的数据类型或结构,c语言里,可以用union类型来表示,但是golang没有union类型,所以用的结构体来模拟。这个结构体会给每种类型一个field,不同的token,取的field不同。比如:

type yySymType struct {
    yys       int
    pos       int
    s         string
    i         int64
    express   ExprNode
    statement StmtNode
}

根据token的类别,,从不同的field取值。

那么,我们输入的文本,是如何转换成这一个个的token呢?

这就用到下面需要讲的词法分析器lex

词法分析器

yacc 定义了lex的接口,如前面提到过的 yyLexer, 需要你自己来实现解析方法。yacc会逐次调用 Lex(lval *yySymType) int, 你需要返回解析后的token类型,依次返回的token顺序必须跟rules完全一致,否则会报错. 同时你还需要将解析后的值填充到lval,也就是前面提到的那个模拟的union结构。

每个token都有有一个类型编号,即Lex函数的返回值,token的值则存在lval,lval是用struct实现的unition,token的识别分为 特殊字符识别,关键字识别,字符串识别数字识别,具体代码可以见lexer.go,还是很容易理解的。

AST

ast就是抽象语法树,我们通过前面两步得到了token数组,然后就可以遍历,将其转换成我们自定义的ast,但是yacc提供了更为简便的方法,如下面代码所示,右侧的大括号中定义了该规则关联的动作

CommentNode:
    kwComment  tString  {
            $$=CommentNode{s:$2}
    }

$$ 代表规约后的值, $1,$2依次代表第一项,第二项...

利用goyacc解析mysql 建表语句

一个典型的建表语句如下

CREATE TABLE `shop_order` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT,
  `uuid` varchar(50) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL COMMENT 'uuid,为兼容旧逻辑',
  `user_id` bigint unsigned NOT NULL DEFAULT '0' COMMENT '购买用户id',
  `payment` tinyint unsigned NOT NULL DEFAULT '0' COMMENT '0-no,1-wepay,2-alipay',
  `fee_amount` int unsigned NOT NULL DEFAULT '0' COMMENT '总共需要支付费用',
  `prepare_time` int unsigned NOT NULL DEFAULT '0' COMMENT '发起支付时间,10位时间戳',
  `paid_time` int unsigned NOT NULL DEFAULT '0' COMMENT '回调确认支付时间',
  `goods_detail` text CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci NOT NULL COMMENT '订单商品详情,json数组',
  `status` tinyint unsigned NOT NULL DEFAULT '0' COMMENT '1-待支付,3-待确认,4-已经支付成功,5-支付失败,6-物流中,7-关闭,8-完成',
  `created_ts` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `updated_ts` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  `logistics_id` bigint unsigned NOT NULL DEFAULT '0' COMMENT '物流id',
  `flag` int unsigned NOT NULL DEFAULT '0' COMMENT '01-已计算sold_amount,10-已经评论',
  PRIMARY KEY (`id`),
  KEY `idx_uuid` (`uuid`)
) ENGINE=InnoDB AUTO_INCREMENT=33830785918 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

整体的parser大概如下, 详见

CreateTableStmt:
    CreateTableStmt SEMICOLON {
        $$=$1
    }
    | kwCreate  kwTable  NameNode LPAREN   ColumnsStmt  RPAREN TableOptsStmt  {
      
        //-- 返回结构体---
    }
    | kwCreate  kwTable  NameNode LPAREN   ColumnsStmt TableIndexListStmt RPAREN TableOptsStmt {
        //-- 返回结构体---
    }
    ;

更详细的见这里 parser.y

因为在parser.y里,每个用到的类型都需要在union里声明,我在写v4版本的时候,就是把所有的变量都声明了,虽然看起来清晰,但是非常繁琐v4

%union {
    offset int // offset
    ident string

    fieldType FieldType
    i int
    columnStmt ColumnStmt
    columnsStmt []ColumnStmt
    fieldOptStmt FieldOptStmt
    tableStmt TableStmt
    fieldCommentExpr FieldComment
    fieldTypeExpr FieldTypeExpr
    fieldDefault FieldDefault
    fieldNameIdenList []string
    indexStmt IndexStmt
    indexListStmt []IndexStmt
    tableOptStmt TableOptStmt

}

类型定义在ast.go,可以看出非常繁琐。

于是在v5进行了抽象成了两种基类 ExprNodeStmtNode,具体可以看v5

生成go代码

在获取了sql的ast后,要想生成go代码其实有两个思路

  1. 直接按字符串处理,拼凑出一个完整的go文件

  2. 利用go自带的ast来处理,将sql的ast转换成go的ast,然后利用go自带的go/format来生成go文件

我采用了第二种方案,大概过程在这里gen.go

冲突处理

yacc的语法分析器采用的是LALR分析器,关于它的原理和介绍网上有很多,记得在我们大学学习数据结构的时候,讲到栈,会举一个后缀表达式的例子,其实这个就很像LR.

这里只说我们非常容易碰到的问题,那就是conflict,在output文件里,经常可以看到State 0 conflicts: 1 shift/reduce, 2 reduce/reduce这类的冲突提示,在yacc里,两种情况都会产生冲突:

  1. 同时可以进行多个归约。称为归约/归约冲突。

  2. 满足移进的规则,同时又满足归约的规则。称为移进/归约冲突

具体例子网上可以找出很多,要解决只要还是看写的规则有没有歧义,其实是很好发现的。