柠芒技术博客

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.Ident 且 Y.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 2024-04-22

Big Image