规则引擎与设计实现

本文来源于第五届字节跳动青训营活动，已收录到规则引擎与设计实现 | 青训营笔记 - 掘金 (juejin.cn) ，主要记录了对规则引擎的学习

规则引擎与设计实现

规则引擎的组成部分及应用场景

规则引擎的核心原理——编译原理的相关概念

设计并实现一个规则引擎——YoungEngine

实现一个Web版规则引擎

1. 认识规则引擎

规则引擎的定义

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

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

  业务决策与服务本身解耦，提高服务的可维护性，缩短开发路径，提高效率

组成部分

• 数据输入
  • 支持接受使用预定义的语义编写的规则作为策略集。比如“price > 500”
  • 接受业务的数据作为执行过程中的参数。比如价格、标签等
• 规则理解
  • 能够按照预先定义的词法、语法、优先级、运算符等正确理解业务规则所表达的语义。
• 规则执行
  • 根据执行时输入的参数对策略集中的规则进行正确的解释和执行。
  • 同时对规则执行过程中的数据类型进行检查，确保执行结果的正确。

应用场景

• 风控对抗。快速识别和对抗，以实现最好的风控识别效果。
• 活动策略运营。提高运营策略的迭代效率，方便新玩法的探索和效果验证。
• 数据分析和清洗。方便快捷地产出所需要的数据。

2.编译原理基本概念

规则引擎和编译原理具有一定的关联性。它们都有理解、执行、输入输出的流程。

• 理解：词法分析、语法分析
• 执行：抽象语法树
• 输入输出：参数注入、类型检查

词法分析 Lexicel Analysis

词法分析就是把源代码字符串转换为词法单元（Token）的过程。

• 识别Token：有限自动机（Finite-State Automaton）

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

语法分析 Syntax Analysis

语法分析就是在词法分析的基础上，识别表达式的语法结构的过程。

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

抽象语法树 Abstract Syntax Tree

• 上下文无关语法 Context-Free Grammar

  语言句子无需考虑上下文，就可以判断正确性。可以使用巴克斯范式（BNF）来表达。

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

  内置符号：字面量（string、bool、number）标识符、运算符。

  一个基础表达式可以由常量（string、bool、number）或标识符（identifier），一个乘法表达式可以由基础表达式或者乘法表达式+基础表达式组成。

• 递归下降算法 Recursive Descent Parsing

  递归下降算法就是自顶向下构造语法树，不断地对Token进行语法展开（下降），展开过程中可能会遇到递归的情况。

类型检查

• 类型综合

  根据表达式的类型构造出父表达式的类型。例如，表达式A+B的类型是根据A和B的类型定义的。

• 编译时检查和运行时检查

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

  • 编译时：需要提前声明参数的类型，在构建语法树过程中进行类型检查
  • 执行时：可以根据执行时的参数输入的值类型，在执行过程中进行类型检查

3.设计一个规则引擎

设计目标

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

• 词法（合法Token）：参数、布尔值、字符串、十进制int、十进制float、预定义运算符的规定写法
• 数据类型：字符串、布尔值、十进制int、十进制float
• 运算符：一元运算符、二元运算符、逻辑操作符、括号
• 优先级：各种运算符的优先级定义

词法分析

• 设计词法分析的状态机

语法分析

• 优先级的表达
• 语法树结构

语法树的执行与类型检查

• 语法树执行

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

  对抽象语法树进行后缀遍历执行，即

  • 先执行左子树，得到左节点的值
  • 再执行右子树，得到右节点的值
  • 最后根据根节点的操作符执行得到根节点的值

• 类型检查

  检查时机：执行时检查

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

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

4.规则引擎的实现

可参考qimengxingyuan/young_engine: 简单的规则引擎 实现。

参考资料

【后端专场 学习资料三】第五届字节跳动青训营