规则引擎的设计与实现

认识规则引擎

定义

规则引擎是一种嵌入在应用程序中的组件，实现了将业务决策从应用程序代码中分离出来，并使用预定义的语义模块编写业务决策。接受数据输入，解释业务规则，并根据业务规则做出业务决策

优点

• 解决了开发人员重复编码的问题

• 业务决策与服务本身解耦，提高了服务的可维护性

• 缩短开发路径，提高效率

组成部分

• 数据输入

  • 支持接受使用预定义的语义编写的规则作为决策集

    • 比如：“price > 500”

  • 接受业务的数据作为执行过程中的参数

    • 比如价格、标签等

• 规则理解

  • 能够按预先定义的词法、语法、优先级、运算符等正确理解业务规则所表达的语义

• 规则执行

  • 根据执行时输入的参数对策略集中的规则进行正确的解释和执行

  • 对规则执行过程中的数据类型进行检查，确保执行结果的正确性

应用场景

• 风控对抗

• 活动策略运营

• 数据分析和清洗

编译原理基本概念

编译原理

• 理解

• 执行

• 输入输出

词法分析 Lexical Analysis

概念

将源代码字符串转化为词法单元 (Token) 的过程

有限自动机（Finite-State Automaton）

有限自动机就是一个状态机，它的状态数量是有限的。该状态机在任何一个状态，基于输入的字符，都能做出一个正确的转换

也就是一个多对一的转换

语法分析 Syntax Analysis

概念

在词法分析的基础上识别表达式的语法结构

抽象语法树 Abstract Syntax Tree

树的结构

表达式的语法结构可以用树来表示，其每个节点（字数）是一个语法单元，这个单元的构成规则就叫 “语法”。每个节点还可以有下级节点。

上下文无关语法 Context-Free Grammar

语言句子无需考虑上下文，就可以判断正确性。

举个栗子：

······
r := a > b //Context-Free Grammar
······

产生式：一个表达式可以由另外已知类型的表达式或者符号推导产生

上下文无关语法可以使用巴科斯范式 (BNF) 来表示

简单介绍 bnf

exp : add ;
add : add '+' mul | mul ;                   //加法表达式 a + b + c  a + b * c
mul : mul '*' pri | pri ;                   //乘法表达式 a * b * c
pri : string | bool | number | identifier ; //基础表达式 weight | 20 | "abcde"

• 内置符号：字面量(string, bool, number) 标识符、运算符

• 一个基础表达式可以由 常量(string, bool, number) 或标识符 (identifier) 组成

• 一个乘法表达式可以由 基础表达式 或者 乘法表达式 * 基础表达式 组成

• ……

这里面蕴含了递归的思想，即自己调用自己直到遇见终止条件

这里面也包含了优先级的思想，在回溯的过程中 ‘*’ 比 ‘+’ 优先触发

递归下降算法 Recursive Descent Parsing

• 自顶向下构造语法树

• 不断地对 Token 进行语法展开，展开过程中可能会遇到递归的情况

类型检查

类型综合

根据子表达式的类型构造出父表达式的类型

例如：

表达式 A + B 的类型是根据 A 和 B 的类型定义的

编译时检查 & 运行时检查

类型检查可以发生在表达式的编译阶段，即在构造语法树的阶段；可以以发生在执行阶段

• 编译时：需要提前声明参数的类型，在构建语法树构成中进行类型检查

  int1 : int;
  str1 : string;
  

• 执行时：可以根据执行时的参数输入的值的类型，在执行过程中检查

  int1 : 108;
  str1 : "300";
  

  

• 出现问题抛出异常

设计规则引擎

设计目标

设计一个规则引擎，支持特定的词法、运算符、数据类型和优先级，支持基于以上预定义语法的规则表达式的编译和执行

词法

• 参数：由字母数字下划线组成 eg: _ab2, user_name

• 布尔值：true, false

• 字符串：“abcde”, ‘abcde’

• 十进制 int：1234

• 十进制 float：123.4

• 预定义运算符：+, -

数据类型

• 字符串

• 布尔值

• 十进制 int

• 十进制 float

运算符

• 一元运算符：+, -

• 二元运算符：+, -, *, /, <, >, <=, >=, ==, !=

• 逻辑运算符：&&, ||, !

• 括号：()

优先级

词法分析

所有情况

• 参数：由字母数字下划线组成 eg: _ab2, user_name

• 布尔值：true, false

• 字符串：“abcde”, ‘abcde’

• 十进制 int：1234

• 十进制 float：123.4

• 一元运算符：+, -

• 二元运算符：+, -, *, /, <, >, <=, >=, ==, !=

• 逻辑运算符：&&, ||, !

• 括号：()

设计状态机

语法分析

expr: logOr EOF;
logOr: logOr '||' logAnd | logAnd;
logAnd: logAnd '&&' logNot | logNot;
logNot: '!' logNot | cmp;
cmp: cmp '>' 'add' | cmp '>=' add | cmp '<=' add | cmp '==' add | cmp '!=' add | cmp '!=' add | add;
add: add '+' mul | add '-' mul | mul;
mul: mul '*' pri | mul '/' pri | mul '%' pri | pri;
pri: BooleanLiteral | IntegerLiteral | FloatLiteral | StringLiteral | Identifier | '('expr')';'

优先级的表达

type precedence struct {
    validSymbol []Symbol       //当前优先级支持的运算符类型
    nextPrecedence *precedence //更高优先级
    planner planner            //当前优先级的处理函数
}

语法树结构

二叉树

• 一元运算符：左子树为空，右子树为右操作数

• 二元运算符：左子树为左操作数，右子树为右操作数

• 括号：左子树为空，右子树为内部表达式的 AST

语法树执行与类型检查

语法树的执行

• 预先定义每种操作符的执行逻辑

• 对抽象语法树进行后序遍历

类型检查

• 检查时机：执行时检查

• 检查方式：在一个节点的左右子节点执行完成后，分别校验左右子节点的类型是否符合对应操作符的类型检查预设规则

  • 例如

  • ‘>’ 要求左右子节点的值都存在且为 int 或 float

  • ‘!’ 要求左节点为空且右节点的值为 bool

实现规则引擎

示例项目：GitHub - qimengxingyuan/young_engine: 简单的规则引擎

目录结构

.
├── README.md
├── compiler.go
├── compiler_test.go
├── compiler
│   ├── lexical.go 
│   ├── parser.go   # 语法分析
│   ├── parser_test.go
│   ├── planner.go  # 构建语法树
│   ├── scanner.go  # 词法分析
│   └── scanner_test.go
├── executor
│   ├── ast.go      # 抽象语法树定义
│   ├── operator.go # 语法树执行
│   ├── svg.go      # 可视化打印语法树 - 辅助工具
│   ├── symbol.go   # 符号定义
│   ├── type.go     # 类型定义
│   └── type_checker.go # 类型检查
└── token
    ├── kind.go      # token类型
    ├── kind_test.go
    ├── lexer.go     # 词法定义
    └── token.go     # token定义

重点关注3个文件夹

• compiler 目录 => 实现词法分析和语法分析

• executor 目录 => 语法树的定义与执行

• token 目录 => token 定义

词法分析

相当于全局扫描的过程

func (scanner *Scanner) Lexer() ([]token.Token, error) {
    tokens := make([]token.Token, 0)

    var err error
    var tok token.Token
    for {
        tok, err = scanner.Scan()
        tokens = append(tokens, tok)
        if err != nil || tok.Kind == token.Eof {
            break
        }
    }

    return tokens, err
}

进行简单的while循环，出现异常或者 scan 到了 Eof 就终止并且返回 tokens 和 err

其中:

scanner.Scan() 方法是由 switch-case 逻辑构成的

case 的先后顺序决定了各个 token 的优先级

语法分析

• balance 检查 -> ()[]{} 是否只存在一边

• next token 检查 -> 后面是否存在token，后面的token能否被前面的token接受？

• ……

确保语法树构建时不会报错

我的理解

• 规则引擎使用的意义

  • 更高效地对接用户与后端

    • 更快速地分析数据

  • 语法简单，可以很方便的使用

  • 相当于是自己造轮子

• 怎么保证规则引擎的全面性