Strcpy

Go抽象语法树(AST)实用指南 (二)

源代码/数据集已上传到 Github - posts

grade == “四(3)班” && age > 10

AST 抽象语法树在表达式解析上面也有不错的表现。通常在规则引擎场景可以得到充分的发挥。
比如一段表达式

1
grade == 四(3)班 && age > 10

这个表达式,对于人来说是非常容易理解的。年级是四(3)班,年纪大于10。

但是计算机来说,传入一段字符串表达式,理解起来可能并不是这么容易。

好在Golang提供了表达式解析的能力,我们可以通过查看解析后的数据,理解ast如果解析这串表达式。

解析表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 0  *ast.BinaryExpr {
1 . X: *ast.BinaryExpr {
2 . . X: *ast.Ident {
3 . . . NamePos: -
4 . . . Name: "grade"
5 . . . Obj: *ast.Object {
6 . . . . Kind: bad
7 . . . . Name: ""
8 . . . }
9 . . }
10 . . OpPos: -
11 . . Op: ==
12 . . Y: *ast.BasicLit {
13 . . . ValuePos: -
14 . . . Kind: STRING
15 . . . Value: "\"四(3)班\""
16 . . }
17 . }
18 . OpPos: -
19 . Op: &&
20 . Y: *ast.BinaryExpr {
21 . . X: *ast.Ident {
22 . . . NamePos: -
23 . . . Name: "age"
24 . . . Obj: *(obj @ 5)
25 . . }
26 . . OpPos: -
27 . . Op: >
28 . . Y: *ast.BasicLit {
29 . . . ValuePos: -
30 . . . Kind: INT
31 . . . Value: "10"
32 . . }
33 . }
34 }

分析表达式解析结果

通过AST抽象语法树可以看到,表达式已经被准确地解析出来了。正如我们理解的,优先解析了最外层的 &&&& 前后的两个判断条件各自成为一个二进制节点。二进制节点

实现一个变量解析器(二元表达式)

有这么一个场景,用户发起了请求,传递了如下参数

1
2
3
4
5
{
"grade":"\"四(3)班\"",
"name":"小明",
"age": 10
}

需要用上面提到的表达式去判断是否符合条件。从抽象语法树上可以知道,不管在哪个层级,都是 X op Y的形式。所以可以通过递归的方式进行递归,直到根节点。

判断是否是根节点

只有到根节点了,才能进行判断最终值。个节点是一个*ast.BinaryExpr节点,它符合X.Type == *ast.IdentY.Type == *ast.BasicLit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isLeaf(node ast.Node) bool {
expr, ok := node.(*ast.BinaryExpr)
if !ok {
return false
}

_, okL := expr.X.(*ast.Ident)
_, okR := expr.Y.(*ast.BasicLit)
if okL && okR {
return true
}

return false
}

递归判断结果值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func judge(node ast.Node, m map[string]interface{}) bool {
if isLeaf(node) {
// 断言成二元表达式
expr := node.(*ast.BinaryExpr)
x := expr.X.(*ast.Ident) // 左边
y := expr.Y.(*ast.BasicLit) // 右边

// 仅处理表达式
switch expr.Op {
case token.GTR:
left := cast.ToFloat64(m[x.Name])
right := cast.ToFloat64(y.Value)
return left > right

case token.EQL:
left, _ := m[x.Name]
right := y.Value
switch y.Kind {
case token.INT:
return cast.ToInt64(left) == cast.ToInt64(right)
case token.FLOAT:
return cast.ToFloat64(left) == cast.ToFloat64(right)
case token.IMAG:
return cast.ToFloat64(left) == cast.ToFloat64(right)
case token.CHAR:
return cast.ToInt(left) == cast.ToInt(right)
case token.STRING:
return cast.ToString(left) == cast.ToString(right)
}
return false
}

return false
}

// 不是叶子节点那么一定是 binary expression(我们目前只处理二元表达式)
expr, ok := node.(*ast.BinaryExpr)
if !ok {
return false
}

// 递归地计算左节点和右节点的值
switch expr.Op {
case token.LAND:
return judge(expr.X, m) && judge(expr.Y, m)
case token.LOR:
return judge(expr.X, m) || judge(expr.Y, m)
}
return false
}

测试用例

1
`grade == "四(三)班" && age > 9`
1
`grade == "四(三)班" && age == 9`
1
`grade == "四(三)班" && age > 10`
1
`grade == "四(三)班" && age < 11`
1
`grade == "四(二)班" && age > 9`
1
`grade == "四(二)班" || age > 9`

扩展

案例一

当传入的参数为如下,该如何解析grade.group

1
2
3
4
5
6
7
{
"grade":{
"group":"\"四(三)班\""
},
"name":"小明",
"age":10,
}

案例二

当传入的参数为如下,又该如何解析

1
2
3
4
5
{
"jump": 160,
"name":"小明",
"age":10,
}

rule: jump > 150 && jump / age > 16


edit this page last updated at 2022-01-27

Big Image