Golang的AST及表达式解析实战(一)

前言

在日常的开发任务需求中有许多规则化的事务描述, 给定一组规则, 如果此规则满足则执行对应的触发的动作。而规则中会定义可枚举的特征字段, 操作符等。通过配置化的方式可以极大节约开发成本及维护成本。所以本期我们就来看一下如何实现一个基于golang的表达式解析工具。

什么是AST？

根据维基百科的介绍：在计算机科学中，抽象语法树(AST) ，或者仅仅是语法树，是用编程语言编写的源代码的抽象语法结构的树状表示。树的每个节点都表示源代码中出现的一个构造。

如何生成AST？

golang的编译核心过程如下:

通过前置的词法分析和语法分析, 可以将源文件构建为AST:

golang的AST结构

可以参考我们之前的分析:BFE负载均衡源码--最小连接数算法及实现 中的描述, 另外也可以尝试用使用: golang可视化ast 做分析。

Node

golang中的AST结构由不同的Node节点组成, 所有实现Pos(), End()方法的都是Node, 接口定义如下:

type Node interface {
   Pos() token.Pos
   End() token.Pos
}

Node有如下几种类型:

Node	含义
Comments	注释, 比如: //, /* some comments */
Declarations	声明, 比如: type, var, const等
Statements	流程控制或表达式语句, 比如: if, return
File	一个源代码文件
Package	一组源代码文件
Expr	表达式, 比如: CallExpr

我们分析一个最简单的源文件:

package main

import (
    "fmt"
)

func main() {
    fmt.Printf("Hello, Golang\n")
}

其AST表达如下:

*ast.File {
     1  .  Doc: nil
     2  .  Package: foo:1:1
     3  .  Name: *ast.Ident {
     4  .  .  NamePos: foo:1:9
     5  .  .  Name: "main"
     6  .  .  Obj: nil
     7  .  }
     8  .  Decls: []ast.Decl (len = 2) {
     9  .  .  0: *ast.GenDecl {
    10  .  .  .  Doc: nil
    11  .  .  .  TokPos: foo:3:1
    12  .  .  .  Tok: import
    13  .  .  .  Lparen: foo:3:8
    14  .  .  .  Specs: []ast.Spec (len = 1) {
    15  .  .  .  .  0: *ast.ImportSpec {
    16  .  .  .  .  .  Doc: nil
    17  .  .  .  .  .  Name: nil
    18  .  .  .  .  .  Path: *ast.BasicLit {
    19  .  .  .  .  .  .  ValuePos: foo:4:2
    20  .  .  .  .  .  .  Kind: STRING
    21  .  .  .  .  .  .  Value: ""fmt""
    22  .  .  .  .  .  }
    23  .  .  .  .  .  Comment: nil
    24  .  .  .  .  .  EndPos: -
    25  .  .  .  .  }
    26  .  .  .  }
    27  .  .  .  Rparen: foo:5:1
    28  .  .  }
    29  .  .  1: *ast.FuncDecl {
    30  .  .  .  Doc: nil
    31  .  .  .  Recv: nil
    32  .  .  .  Name: *ast.Ident {
    33  .  .  .  .  NamePos: foo:7:6
    34  .  .  .  .  Name: "main"
    35  .  .  .  .  Obj: *ast.Object {
    36  .  .  .  .  .  Kind: func
    37  .  .  .  .  .  Name: "main"
    38  .  .  .  .  .  Decl: *(obj @ 29)
    39  .  .  .  .  .  Data: nil
    40  .  .  .  .  .  Type: nil
    41  .  .  .  .  }
    42  .  .  .  }
    43  .  .  .  Type: *ast.FuncType {
    44  .  .  .  .  Func: foo:7:1
    45  .  .  .  .  Params: *ast.FieldList {
    46  .  .  .  .  .  Opening: foo:7:10
    47  .  .  .  .  .  List: nil
    48  .  .  .  .  .  Closing: foo:7:11
    49  .  .  .  .  }
    50  .  .  .  .  Results: nil
    51  .  .  .  }
    52  .  .  .  Body: *ast.BlockStmt {
    53  .  .  .  .  Lbrace: foo:7:13
    54  .  .  .  .  List: []ast.Stmt (len = 1) {
    55  .  .  .  .  .  0: *ast.ExprStmt {
    56  .  .  .  .  .  .  X: *ast.CallExpr {
    57  .  .  .  .  .  .  .  Fun: *ast.SelectorExpr {
    58  .  .  .  .  .  .  .  .  X: *ast.Ident {
    59  .  .  .  .  .  .  .  .  .  NamePos: foo:8:2
    60  .  .  .  .  .  .  .  .  .  Name: "fmt"
    61  .  .  .  .  .  .  .  .  .  Obj: nil
    62  .  .  .  .  .  .  .  .  }
    63  .  .  .  .  .  .  .  .  Sel: *ast.Ident {
    64  .  .  .  .  .  .  .  .  .  NamePos: foo:8:6
    65  .  .  .  .  .  .  .  .  .  Name: "Printf"
    66  .  .  .  .  .  .  .  .  .  Obj: nil
    67  .  .  .  .  .  .  .  .  }
    68  .  .  .  .  .  .  .  }
    69  .  .  .  .  .  .  .  Lparen: foo:8:12
    70  .  .  .  .  .  .  .  Args: []ast.Expr (len = 1) {
    71  .  .  .  .  .  .  .  .  0: *ast.BasicLit {
    72  .  .  .  .  .  .  .  .  .  ValuePos: foo:8:13
    73  .  .  .  .  .  .  .  .  .  Kind: STRING
    74  .  .  .  .  .  .  .  .  .  Value: ""Hello, Golang\n""
    75  .  .  .  .  .  .  .  .  }
    76  .  .  .  .  .  .  .  }
    77  .  .  .  .  .  .  .  Ellipsis: -
    78  .  .  .  .  .  .  .  Rparen: foo:8:30
    79  .  .  .  .  .  .  }
    80  .  .  .  .  .  }
    81  .  .  .  .  }
    82  .  .  .  .  Rbrace: foo:9:1
    83  .  .  .  }
    84  .  .  }
    85  .  }
    86  .  Scope: *ast.Scope {
    87  .  .  Outer: nil
    88  .  .  Objects: map[string]*ast.Object (len = 1) {
    89  .  .  .  "main": *(obj @ 35)
    90  .  .  }
    91  .  }
    92  .  Imports: []*ast.ImportSpec (len = 1) {
    93  .  .  0: *(obj @ 15)
    94  .  }
    95  .  Unresolved: []*ast.Ident (len = 1) {
    96  .  .  0: *(obj @ 58)
    97  .  }
    98  .  Comments: nil
    99  }

ast.Expr 表达式节点

基于我们上述实例代码, 包含:

• ast.CallExpr节点, 表示函数调用节点, 节点下有Fun表示函数名称信息, Args表示参数信息。
• ast.Ident和ast.BasicLit， 这两个节点通过构成一个页子节点的最小表示对象, 比如age > 10这个语句的AST为:

X: *ast.BinaryExpr {
     2  .  .  X: *ast.Ident {
     3  .  .  .  NamePos: -
     4  .  .  .  Name: "age"
     5  .  .  }
     6  .  .  OpPos: -
     7  .  .  Op: >
     8  .  .  Y: *ast.BasicLit {
     9  .  .  .  ValuePos: -
    10  .  .  .  Kind: INT
    11  .  .  .  Value: "10"
    12  .  .  }
    13  .  }

Ident为表达式基本操作字段, BasicLit为字段对应的比较值。

ast.Stmt 流程控制节点

• ast.BlockStmt, 表示一个中断节点, 在此case中是由一个fmt.Printf()函数结束了整个流程
• ast.ExprStmt, 在此case中表示有一个函数和对应的参数组成的此流程

总结

我们了解了AST的一些基础知识, 并且基于实际用例看到了golang构建的AST语法树, 通过这些知识我们可以以此来构建我们的表达式解析工具。

golang spec参考手册译文

golang spec参考手册官网