曹大在我学围棋的时候带我第一次领略了Ast的强大。转载本文请联系码农桃花源公众号。大家好，我是小X，曹达最近开了围棋课程，小X跟曹达一起围棋。本系列将讨论从课程中学到的一些有启发性的东西，拨开乌云，带你回到Go。抽象语法树是编译过程中的中间产物，一般简单看懂就够了。但是我们可以直接使用Go语言的整个parser和ast包，在某些场景下是非常强大的。什么是AST？我从维基百科摘录了一段话：在计算机科学中，抽象语法树（AbstractSyntaxTree，简称AST），简称语法树，是对源代码语法结构的一种抽象表示。它以树的形式表示编程语言的语法结构，树上的每个节点代表源代码中的一个结构。核心是ast可以用树的形式来表示代码结构。使用树结构，您可以遍历它并做很多事情。假设一个场景假设一个场景：我们可以从司机平台的一个接口获取司机的各种特征，比如：年龄、订单数、收入、每天的驾驶时间、驾驶年龄、平均速度、投诉数量……数据一般使用json传递。司机平台的运营小姐姐经常需要从事一些活动，比如挑选：1万单以上，5年以上驾龄的老司机，每天开车3小时以内，高效司机，收入在40岁以上且平均速度超过70岁的“狂野”车手超过500人……这些规则不是固定的，经常变化，但始终是车手特征的组合。为了简化，我们选取??2个特征，用一个Driver结构体来表示：typeDriverstruct{OrdersintDrivingYearsint}为了配合运营进行活动，我们需要根据运营给定的规则来判断一个司机是否符合要求。如果公司人多，可以安排一个rd来服务运营小姐。每次做活动都手动修改代码也不是不可能。而且其实很简单，我们来写个示例代码：//从第三方获取驱动特征，json表示funcgetDriverRemote()[]byte{return[]byte(`{"orders":100000,"driving_years":18}`)}//判断是否是老司机funcisOldDriver(d*Driver)bool{ifd.Orders>10000&&d.DrivingYears>5{returntrue}returnfalse}funcmain(){bs:=getDriverRemote()vardDriverjson.Unmarshal(bs,&d)fmt.Println(isOldDriver(&d))}直接看main函数：getDriverRemote模拟从第三方RPC获取一个司机的特征数据，用json表示。然后json.Unmarshal反序列化Driver结构。最后调用isOldDriver函数判断驱动是否符合运行规则。isOldDriver通过if语句根据Driver结构体的两个字段来判断驱动是否为旧驱动。这真的很简单。但是，每次更新规则，都要经过一个完整的在线流程，相当麻烦。有更容易的方法吗？它可以让我们直接解析运营小姐姐给我们的一个字符串表示的规则，直接返回一个bool值表示是否满足条件。是的！接下来就是本文的核心内容，如何使用ast来完成同样的功能。直观理解如何使用ast解析规则利用ast包提供的一些函数，我们可以很方便的将如下规则字符串：orders>10000&&driving_years>5解析成这样的二叉树：RuleBinaryTree其中，ast.BinaryExpr表示一个二叉树由三部分X和Y以及符号OP组成的元表达式。顶部的BinaryExpr表示规则左右两部分的AND。显然，左半部分是：orders>10000，右半部分是：driving_years>5。神奇的是，左半部分和右半部分恰好又是一个二元表达式。左半部分的orders>10000其实就是最小的叶子节点，可以算出一个bool值。拆开后可以分为X、Y、OP。X是订单，OP是“>”，Y是“10000”。其中，X代表一个标识符，类型是ast.Ident，Y代表一个基本类型的字面量，比如int类型，string类型……，类型是ast.BasicLit。右半部分的driving_years>18可以这样拆分。然后从json中取出这个驱动的order字段的值为100000，大于10000，所以左半部分计算为true。同样，右半部分也计算为真。最后再计算最外层的“&&”，结果依然成立。至此，我们就可以直接根据规则字符串计算出结果了。如果写成程序，就是一个dfs遍历过程。如果不是叶子节点，就是二元表达式节点，必须有X、Y、OP部分。递归遍历X。如果X是叶节点，则结束递归，计算X的值……这里是ast包打印的另一棵抽象语法树：上面Go打印ast，1,2,3代表最外层二元表达式；4、5、6代表左边的二进制表达式。结合这张图，再参考ast包的相关结构代码，就很清楚了。比如ast.BinaryExpr的代码如下：//ABinaryExprnoderepresentsabinaryexpression.BinaryExprstruct{XExpr//leftoperandOpPostoken.Pos//positionofOpOptoken.Token//operatorYExpr//rightoperand}它有X,Y,OP,甚至解析出Op的位置，用OpPos表示。如果你对实现还有兴趣，那么继续看下面的原理分析部分，否则可以直接跳到最后的结论。原理分析还是用上面的例子，我们直接写一个表达式：orders>10000&&driving_years>5然后用ast解析规则判断真假。funcmain(){m:=map[string]int64{"orders":100000,"driving_years":18}rule:=`orders>10000&&driving_years>5`fmt.Println(Eval(m,rule))}为简单起见，我们直接使用map而不是json，道理是一样的，只是为了方便。Eval函数判断规则为真还是假：//Eval:计算expr的值funcEval(mmap[string]int64,exprstring)(bool,error){exprAst,err:=parser.ParseExpr(expr)iferr!=nil{returnfalse,err}//打印astfset:=token.NewFileSet()ast.Print(fset,exprAst)returnjudge(exprAst,m),nil}先把表达式解析成Expr，然后调用判断函数计算结果：//dfsfuncjudge(bopast.Node,mmap[string]int64)bool{//leafnodeifisLeaf(bop){//Assertedintoabinaryexpressionexpr:=bop.(*ast.BinaryExpr)x:=expr.X.(*ast.Ident)//左y:=expr.Y.(*ast.BasicLit)//右//如果是“>”符号ifexpr.Op==token.GTR{left:=m[x.Name]right,_:=strconv.ParseInt(y.Value,10,64)returnleft>right}returnfalse}//如果不是叶子节点，则一定是二进制表达式（我们只处理二进制expressionsatpresent)expr,ok:=bop.(*ast.BinaryExpr)if!ok{println("thiscannotbetrue")returnfalse}//递归计算左节点和右节点的值switchexpr.Op{casetoken.LAND:returnjudge(expr.X,m)&&judge(expr.Y,m)casetoken.LOR:returnjudge(expr.X,m)||judge(expr.Y,m)}println("unsupportedoperator")returnfalse}judge使用dfs递归地评估表达式。递归终止条件是叶子节点：//判断是否是叶子节点funcisLeaf(bopast.Node)bool{expr,ok:=bop.(*ast.BinaryExpr)if!ok{returnfalse}//最小的二进制表达式单元，左节点为标识符，右节点为值_,okL:=expr.X.(*ast.Ident)_,okR:=expr.Y.(*ast.BasicLit)ifokL&&okR{returntrue}returnfalse}总结今天这篇文章主要讲的是如何使用ast包和parser包来解析一个二进制表达式，见识其威力，用它来做一个非常简单的规则引擎。事实上，你可以用ast包做更多有趣的事情。比如把thrift文件批量转成proto文件，解析sql语句，做一些审计……想了解更多可以看曹达的文章[1]。按照曹达自己的说法，他30分钟就可以搞定。几天之内就完成了一个项目的API编写，很霸气！不接受就喷他...
