初接触编译器文法 - 创造一个简单的规则引擎
目录
日常用到的编程语言可以实现不同的业务,当业务繁杂多变时,代码会因为分支逐渐增加而变得冗余难读。规则引擎可以缓解这些问题,规则引擎可以是动态解析的,并且相比于编程语言,规则语言对编码职能以外的人员也能有很好的可读性,使得他们能避免代码的学习成本,自行编辑业务规则。
硬编码业务带来的成本
复杂的业务总是伴随着很多的分支,这些分支都直接写死在代码里,需求变更时,就要对代码进行改动。
下方的例子描述了不同客户的优惠折扣(新用户、铜牌用户、白银客户、黄金客户):
if (level === 'gold') {
// discount 75%
} else if (level === 'silver') {
// discount 85%
} else if (level === 'bronze') {
// discount 90%
} else if (is_new === true) {
// discount 95%
} else (...) {
// no discount
}
如果想把白银客户的折扣改成 80%,或者增加 白金客户…随着分支越来越复杂,代码逐渐难读,而且代码每次改动后,就要重新部署。
而核心的业务只是类似如下的规则描述,输入一个客户的身份,输出折扣:
( level == 'gold' ) => 75
( level == 'silver' ) => 85
( level == 'bronze' ) => 85
( is_new == true ) => 95
这份描述比 if 分支简洁多了,它按顺序执行这些规则,如果遇到满足则立即返回折扣。但是编程语言不认得这些语法,所以要自己实现一个规则引擎让这份描述跑起来。
虽然现在已经有很多好用的规则引擎(像 Drools),但都是面向通用的业务,也需要新语言的学习成本。这种成本我觉得在学习微信小程序“原创语言” WXS 的时候可以感受到。
在一些极端的情况下,可以自行实现一个规则引擎,创造一门规则描述语言。
创造一个简单的规则引擎
程序语言的解释都遵循编译器的基本流程:词法分析、语法分析、语义分析。建立一门新的规则语言也要实现这些过程,但是规则引擎因应业务需要,它可以是动态解释的,边解释边运行,就像 js 和 python 的解释器。
现在试试用上方的规则描述作为参考,做一个简单的规则解释器,让这份规则描述输出结果:
// 预设变量: level、is_new
( level == 'gold' ) => 75
( level == 'silver' ) => 85
( level == 'bronze' ) => 85
( is_new == true ) => 95
数据类型和文法
文法用于约束语言的结构,这里假定 ->
标志,意思是「可以有这种形式」。
例:
coord -> (x,0)
x -> 1
代表
1
会被认定为 x,(1,0)
会被认定为 coord。
规则引擎的类型应尽量简单易懂,这里我们只定义3种最简单的类型:布尔值(bool)、数字(number)、字符串(string)。
rule -> ( expr ) => value
expr -> ( expr )
expr -> ( expr op expr )
expr -> ( value op value )
op -> and | or | == | != | < | > | <= | >=
value -> BOOL | "String" | NUMBER | var
var -> String
约束规则描述文本的就是上方的文法定义,只有匹配上方的语法才能被认定为正确的规则描述。
-
rule: 代表一行规则,格式
( 表达式 ) => 输出值
,如( cash > 100 ) => “有钱”
-
expr: 代表一句表达式,它有3种格式。
( expr )
: 用来去掉括号冗余,如( ( cash > 100 ) ) 等价 ( cash > 100 )
( expr op expr )
: 允许嵌套,如( ( cash > 100 ) and ( cash < 500 ) )
( value op value )
: 表示值的对比计算,如( 1 > 2 )、( true == true )
-
op: 代表操作符,我们定义常用的一些逻辑符号,这些符号在编程语言中很常见。
and
、or
、==
、!=
、<
、>
、<=
、>=
-
value: 代表值,它存储我们定义的数据类型(布尔、数字、字符串),而字符串要求两端带上双引号。
5、true、false、-100.8、“hello”
变量(var) 是特殊的值,它要在预设的变量表中用变量名获取值。
这些文法指出了规则的逻辑组成方式,只有符合这些文法的句子才能生成正确的语法结构。
词法分析
词法分析把一个句子拆分成很多个部分,然后逐个识别出单词(词素),遇到不认识的单词要抛出错误。
像这个句子:
( money > 0 )
用空格分隔后,可以识别出如下词素:
( | money | > | 0 | ) |
---|---|---|---|---|
左括号 | 变量 | 操作符 | 数字值 | 右括号 |
如果遇到下面这个句子则需要报错,因为文法没有定义 &
这个符号,所以词法分析失败:
( money & 0 )
词法分析的结果是词素列表,但是它们在逻辑上可能是错的,像这样:
) money == 1 (
语法分析
在语法分析阶段,按顺序逐个对词素做检查,确保句子的逻辑正确,如果正确,则可以建立出与原句等价的模型。否则就要报错。
语法分析的过程可以引入状态机模式,定义出一系列的状态,每个状态只识别一部分词素,读到不识别的词素就说明这个句子有语法错误。若状态机能走到终态,则成功构建出语法结构。
这里用 JavaScript 来表达那些文法的模型:
class Rule { field; result; } // 规则模型
class Expr { left; op; right; } // 表达式模型
class Op { op; } // 操作符模型
class Value { type; _raw; } // 值模型
class Var extends Value { name; } // 变量模型,它是特殊的值模型,用变量名才能获得值
针对这份规则的文法和结构定义,可以建立这些状态机:
状态 | 描述 | 识别词素 |
---|---|---|
Begin | 初始 | - |
ReadLeftBracket | 读左括号 | ( |
ReadLeft | 读左侧 | (、var、value |
ReadOp | 读操作符 | and 、or 、== 、!= 、< 、> 、<= 、>= |
ReadRight | 读右侧 | (、var、value |
ReadRightBracket | 读右括号 | ) |
End | 终态 | - |
-
Begin: 初始状态
-
ReadLeftBracket: 读左括号状态,读到的词素必须是左括号,表示表达式的开始
-
ReadLeft: 读表达式左侧
根据文法 expr -> ( expr ),读到的词素可以是左括号,表示冗余的开始
根据文法 expr -> ( expr op expr ),读到的词素可以是左括号,表示嵌套表达式的开始
根据文法 expr -> ( value op value ),读到的词素可以是值(布尔、数字、字符串)或者是变量
-
ReadOp: 读表达式中间的操作符,读到的词素必须是操作符
但根据文法 expr -> ( expr ),读到右括号时,也可以表示嵌套表达式的结束
-
ReadRight: 读表达式右侧
根据文法 expr -> ( expr op expr ),读到的词素可以是左括号,代表右侧表达式的开始
根据文法 expr -> ( value op value ),读到的词素可以是值或变量
-
ReadRightBracket: 读表达式的右括号,读到的词素必须是右括号,读出来后,进入终态
-
End: 终态,表示已经建立出结构
至此语法分析结束,可以保证建立出完整的逻辑结构了。
语义分析
在语义分析阶段,可以进行语义的检查,包括变量是否存在、类型检查和转换检查等。
这次实验中的规则引擎可以不做类型检查,运行时类型转换处理效仿 JavaScript 的弱类型转换。
对于变量是否定义,可以检查预设的变量表中是否存在指定名称的变量:
checkVariableSemantic (v: Var) {
const name = v.name;
if (!variableStore.findByName(name)) {
throw new VariableNotFoundError(name);
}
}
语义分析完成后,得到的结构就可以直接解释运行了。通用的程序语言在这个阶段还要生成中间语言对结构的逻辑加以优化,然后再生成机器语言。为了轻量和方便,本实验的规则引擎直接用解释器运行。
编写解释器
高级语言的代码都会被翻译成低级语言,最后变成机器码才能运行。规则引擎的解释器也是基于特定的编程语言来实现,在这里我们用 JavaScript 的语法直接实现规则的语法。
下方展示简单的直接利用 js 的运算符做解释:
// 计算表达式的结果
function calcFieldValue (left: Value, op: Op, right: Value) {
switch (op) {
case Op.GT:
return left._raw > right._raw;
case Op.LT:
return left._raw < right._raw;
case Op.EQ:
return left._raw == right._raw;
// ...
}
}
// 比较2个表达式的结果
function calcExprExpr (left: Expr, op: Op, right: Expr)
switch (op) {
case Operator.AND:
return calcFieldValue(left) && calcFieldValue(right)
case Operator.OR:
return calcFieldValue(left) || calcFieldValue(right)
// ...
}
除了逻辑比较运算,作为弱类型语言的解释器,它还要对文法定义的类型(bool, number, string)作类型转换,这个过程可以直接效仿 JavaScript 类型转换,如 1 转布尔为 true,0 转布尔为 false。
function castNumberFor(value: Value) {
switch(value.type){
case Type.STRING:
return parseFloat(value._raw)
case Type.BOOL:
return value === true ? 1 : 0
// ...
}
}
具体的实现复杂一点,因为还要检查表达式的左侧是否为嵌套的表达式、或是一个值等。
完整的引擎实现会放在附录处
运行效果 & 编写测试
现在可以看看效果,同时用测试验证引擎的健全性,写测试是软件工程的重要部分。这里我用 JEST 做单元测试。
表达式测试
test('true != false', () => {
const context = {
variableStore: new VariableStore([]), // 变量池
};
const source = `( false == true )`; // 输入表达式
const expr = Facade.buildExpr(context, source); // 解析出表达式模型
expect(Interpreter.interpretExpr(expr)).toBe(false); // 执行,验证输出结果
});
test('1 == true', () => {
const context = {
variableStore: new VariableStore([]),
};
const source = `( 1 == true )`; // 隐式类型转换会将 1 转换为 true,所以结果应为 true
const expr = Facade.buildExpr(context, source);
expect(Interpreter.interpretExpr(expr)).toBe(true);
});
带上变量的表达式可以应用在业务逻辑上:
test('integer constant preset', () => {
const context = {
variableStore: new VariableStore([
Variable.defineNUMBER('order_status', -1), // 订单当前状态
Variable.defineNUMBER('OrderStatus_Created', 0), // 创建状态
Variable.defineNUMBER('OrderStatus_Paid', 1), // 已支付
Variable.defineNUMBER('OrderStatus_Exception', -1), // 订单异常
]),
};
const source = `( order_status == OrderStatus_Exception )`;
const expr = Facade.buildExpr(context, source);
expect(Interpreter.interpretExpr(expr)).toBe(true);
});
规则测试
规则就是多个带输出的表达式列表,如果引擎执行了一列表达式都没看到输出(所有的条件都不符合),它就会报错。
检测 PM2.5 是否超过阈值,返回 OK 或警报
test('as variable', () => {
const context = {
variableStore: new VariableStore([
Variable.defineNUMBER('pm25', 80),
Variable.defineNUMBER('RESULT_OK', 0),
Variable.defineNUMBER('RESULT_WARN', -1),
]),
};
const sources = [
`( pm25 > 75 ) => RESULT_WARN`, //
`( pm25 <= 75 ) => RESULT_OK`,
];
const rules = Facade.buildRules(context, sources);
expect(Interpreter.interpretRules(rules).valueHolder.asNumber()).toBe(-1);
});
回到本实验开头的 “客户折扣” 描述
输入的客户等级是 “黄金客户”,所以引擎执行后,会输出 75(7.5折)。
test('business', () => {
const context = {
variableStore: new VariableStore([
Variable.defineSTRING('level', 'gold'),
Variable.defineSTRING('GUEST_LEVEL_BRONZE', 'bronze'),
Variable.defineSTRING('GUEST_LEVEL_SILVER', 'silver'),
Variable.defineSTRING('GUEST_LEVEL_GOLD', 'gold'),
Variable.defineSTRING('GUEST_LEVEL_NONE', 'none'),
]),
};
const sources = [
`( level == GUEST_LEVEL_GOLD ) => 75`,
`( level == GUEST_LEVEL_SILVER ) => 80`,
`( level == GUEST_LEVEL_BRONZE ) => 90`,
];
const rules = Facade.buildRules(context, sources);
expect(Interpreter.interpretRules(rules).valueHolder.asNumber()).toBe(75);
});
执行后没有结果的报错处理
当引擎执行得不到结果时,应该报错,交回主业务代码处理,或是写入异常日志,或是当作 “没有优惠”。
test('no result', () => {
const context = {
variableStore: new VariableStore([
Variable.defineSTRING('level', 'none'),
Variable.defineSTRING('GUEST_LEVEL_BRONZE', 'bronze'),
Variable.defineSTRING('GUEST_LEVEL_SILVER', 'silver'),
Variable.defineSTRING('GUEST_LEVEL_GOLD', 'gold'),
Variable.defineSTRING('GUEST_LEVEL_NONE', 'none'),
]),
};
const sources = [
`( level == GUEST_LEVEL_GOLD ) => 75`,
`( level == GUEST_LEVEL_SILVER ) => 80`,
`( level == GUEST_LEVEL_BRONZE ) => 90`,
];
const rules = Facade.buildRules(context, sources);
expect(() => Interpreter.interpretRules(rules)).toThrow(NoRuleResultError);
});
当然也可以在描述的最后一行编写 ( true == true ) => 100
,这个表达式一定会返回值 100。
附录
Github 项目及源代码 (https://github.com/luo3house/simple-expr-engine)
参考了《编译原理》