利用goyacc解析sql并生成go struct

Posted on Tagged , , , , , , 有0条评论

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

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

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

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

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

语法分析

在语法分析里，有两个词terminal和nonterminal，翻译为终结符和非终结符，分别用%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 E和F 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进行了抽象成了两种基类 ExprNode和StmtNode，具体可以看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. 满足移进的规则，同时又满足归约的规则。称为移进/归约冲突

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