parser的故事

2016-07-07

这几天优化TiDB，我们的内存管理还不太理想，有大量的开销花在了GC上面，其中造成对象分配最多的，就是SQL的parser。所以今天想讲讲关于parser的故事。

TiDB中SQL的parser是利用的lex&yacc实现的。也就是走的parser generator的方式，这里可以看到代码。手写一个parser.y文件，然后用了一个叫goyacc的工具，它会根据我们定义的.y文件生成parser.go。但是对于做优化来说，生成的代码总是不那么容易控制。

一般来讲实现parser的主要形式有三类：纯手写parser，YACC工具，parser combinator。

纯手写parser的事情，我只在许多年以前，写自己的第一个scheme解释器的时候干过。还好lisp的语法足够简单，没有造成太大困扰。纯手写parser的主要问题是枯燥，工作量大。本来parser其实没有什么太高深的事情，简单的递归下降可以处理很多东西了。好处是性能可以做到比较极致，据说lua的parser早期是用工具做，后面考虑到性能就手写了，类似的例子还有一些。

如果想把性能优化做到极致，手写parser是一个方案。我搜索了一下Go的开源项目涉及到SQL的parser的实现，Cockroach跟我们一样用的yacc，想必会遇到我们同样的问题。InfluxDB是手写的。纯手写parser是这种样子的：

// ParseStatement parses an InfluxQL string and returns a Statement AST object.
func (p *Parser) ParseStatement() (Statement, error) {
    // Inspect the first token.
    tok, pos, lit := p.scanIgnoreWhitespace()
    switch tok {
    case SELECT:
        return p.parseSelectStatement(targetNotRequired)
    case DELETE:
        return p.parseDeleteStatement()
    case SHOW:
        return p.parseShowStatement()
    case CREATE:
        return p.parseCreateStatement()
    case DROP:
        return p.parseDropStatement()

先看哪些Statement，再具体到某一种，比如Select的Statement，再对应到解析它的格式的函数。

yacc是我们现在使用的方案。这种方案的缺点，yacc有一定的学习门槛；生成代码方案不那么可控，可读性基本为零；还有现在的问题，性能。哦，据说还有灵活性比较差，特定复杂的语法是处理不了的。

说下yacc的基本原理。在.y文件中其实是定义了一套语法规则，yacc工具会根据这套规则生成一张表。比如在生成的parser.go文件中，有一张名叫yyParseTab的表。生成的代码做解析时会根据这张表决定走到对应的解析规则。就白了就是状态机，模式匹配这些东西。

最后一类实现方式叫做parser combinator，是我比较喜欢的。如果自己从头实现，估计会采用这种方式。parser是一个接受输入，返回特定结果的函数。如果我们有许许多多不同的parser，每一类parser只处理一个非常简单的工作，这类parser是比较好写的。然后定义combinator，combinator接受parser作为输入，生成新的parser作为输出。利用高阶函数，combinator可能非常灵活而又功能强大。跟纯手写parser相比，它没有那么多工作量，而跟生成器相比，它是灵活并且可调试的。

最早知道parser combinator是从王垠那里，那么就拿他的代码为例子说下吧。仅用这几行代码就实现了一个lisp的parser：

(:: $open
    (@or (@~ "(") (@~ "[")))
(:: $close
    (@or (@~ ")") (@~ "]")))
(:: $non-parens
    (@and (@! $open) (@! $close)))
(::= $parens 'sexp
    (@seq $open (@* $sexp) $close))
(:: $sexp
    (@+ (@or $parens $non-parens)))
(:: $program $sexp)

其中@or @and @+ 这些都是combinator，是高阶函数。(@~ "(")生成了一个只能解析(的parser函数，而用@or组合起来，得到的$open就是一个可以解析(或者[的parser。@+是将parser重复多次，比如多个sexp。

回到最初的地方，parser的优化问题。给个十天半个月的，我大概可以写一个基本的parser出来，能解析80%的SQL语法。但是后面填坑就复杂了，还有跟现在的ast结构定义的兼容问题。TiDB已经beta版本了，干这种事情明显不值得。

我想了一个简单的优化方法：给yyParse传一个分配器进去。这个分配器非常简单，就是一块array。yyParse里面解析出ast对象直接从这块array里面划。每个session绑定一个parser对象，里面有分配器。因为每个session里面，上一个SQL执行完成之前，下一个SQL是不会执行的，所以不用担心会出问题。哈，太晚了，明天去改代码吧！