- Published on
Eval 拜拜👋🏻!手摸手教你实现写一个AST数实现公式解析引擎
- Authors
- Name
- Hansuku
IF(AND(OR({self.text\_14}=="-税-运(自提)",{self.text\_14}=="-税-运+送",{self.text\_14}=="-税+运(自提)",{self.text\_14}=="-税+运+送"),{self.array\_4.text\_2}=="0.04"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}*0.97/1.1)-1)* 100,2),IF(AND(OR({self.text\_14}=="-税-运(自提)",{self.text\_14}=="-税-运+送",{self.text\_14}=="-税+运(自提)",{self.text\_14}=="-税+运+送"),{self.array\_4.text\_2}=="0.02"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}*0.97/1.1)-1)* 100,2),IF(AND(OR({self.text\_14}=="-税-运(自提)",{self.text\_14}=="-税-运+送",{self.text\_14}=="-税+运(自提)",{self.text\_14}=="-税+运+送"),{self.array\_4.text\_2}=="0.01"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}*0.97/1.06)-1)* 100,2),IF(AND(OR({self.text\_14}=="+税-运(自提)",{self.text\_14}=="+税-运+送",{self.text\_14}=="+税+运(自提)",{self.text\_14}=="+税+运+送"),{self.array\_4.text\_2}=="0.04"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}/1.1)-1)*100,2),IF(AND(OR({self.text\_14}=="+税-运(自提)",{self.text\_14}=="+税-运+送",{self.text\_14}=="+税+运(自提)",{self.text\_14}=="+税+运+送"),{self.array\_4.text\_2}=="0.02"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}/1.1)-1)* 100,2),IF(AND(OR({self.text\_14}=="+税-运(自提)",{self.text\_14}=="+税-运+送",{self.text\_14}=="+税+运(自提)",{self.text\_14}=="+税+运+送"),{self.array\_4.text\_2}=="0.01"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}/1.06)-1)*100,2),IF(AND(OR({self.text\_14}=="-税-运(自提)",{self.text\_14}=="-税-运+送",{self.text\_14}=="-税+运(自提)",{self.text\_14}=="-税+运+送"),{self.array\_4.text\_2}=="0"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}* 0.97/1.02)-1)*100,2),IF(AND(OR({self.text\_14}=="+税-运(自提)",{self.text\_14}=="+税-运+送",{self.text\_14}=="+税+运(自提)",{self.text\_14}=="+税+运+送"),{self.array\_4.text\_2}=="0"),ROUND((({self.array\_4.num\_6}-{self.array\_4.num\_2})/({self.array\_4.num\_1}/1.02)-1)* 100,2),0))))))))
不知道大家看到上面这一段是什么想法...这是用户通过表单系统配置出来的
我们先来定义一下什么是公式,对于我们的领域(类 EXCEL 的非科学领域)公式通常由三部分组成:
算术表达式(Expression)
函数(Function)
代数(Variable)
通俗来说,就是通过对上面那一大坨归类解析,分析成上面的三种类型,并执行对应的结果。什么,你看不懂?没关系,我们翻译成人话:
如果我们遇到了
>,<,==,+- \*/
这种符号,那他就是要执行算数表达式如果我们遇到了 DIVIDE,ADD,SUM 这样的东西,那就是要执行函数,这个特别好理解,我们等同于 JS 里的 Function:
function DIVIDE() { // do some things }
如果我们遇到了
{self.array_4.num_1}
这样的东西,就把他理解为是一个变量,去取值并转换成对应的值即可
好,第一步搞清楚了,我们人是能读懂这些公式了,那电脑呢?

总体来说,在前端领域想要让浏览器、Nodejs 去识别/运行上面那一坨东西,分为两种方案:
动态执行(eval,new Function)
AST(抽象语法树)
比如,大部分情况下是使用 new Function 执行的:
const variable = 'var a = 0;var b = 1;'
new Function(`${variable}return a > b`)()
使用动态脚本和 AST 的区别:
动态脚本 | AST | |
---|---|---|
特性 | 实现成本低,依赖语言本身的能力,JS 的范式是什么样的你的公式就能执行什么(主要是上面三个公式要素,如果超过了这个范围扩展很难) | 自己实现对整个语言的解释,基本不存在能力限制,实现成本高。 |
安全性 | 低 | 高 |
兼容扩展 | 低 | 高 |
执行效率 | 高 | 看代码怎么写,合理的代码效率一致高 |
下面开始我们的正题,用 AST 去解析公式。
对于 AST 来说,最重要的是两个事情:
单词拆分(Token)
词法语义(Rule)
比如在 new Function 的方法里,JS 引擎可以自己去理解 DIVIDE 这样一个标记,JS 引擎自己会在作用域内寻找是否存在这样一个方法或者变量,并尝试执行他,但在 AST 的世界里,首先你得让你的语法树知道你需要拆除一个 DIVIDE 这样的标记,并且你需要给他匹配好对应 DIVIDE 要做什么,这样 AST 才能正常的完成他的使命。
那么问题来了,如何构建一个 AST?如果纯手撸的话,代码量可以说是非常之吓人了,索性前端领域有一些非常好用的解析构建工具,比如:
Home - nearley.js - JS Parsing Toolkit
大体来说,这些解析构建工具都提供了两个核心能力:
Token 定制和解析,即对上面那一坨东西里的内容进行分类提炼,比如,我们遇到 DIVIDE、SUM、ISOWEEKNUMS 这样的东西,我们需要把他归类为函数,那我可以通过正则定义这样的规则:
export const FunctionMark = createToken({ name: 'Function', pattern: /[A-Za-z_]+[A-Za-z_0-9.]*\(/, })
上面正则中这个括号在后文中会解释。
Parser 解析和执行能力,即我们如何使用上面定义好的 Token 进行规则定制,并且完成公式的执行返回结果。
可能这样看会比较难以理解,但没有关系,下面会慢慢讲明白,再回过头来看这两句话就会明白啦。
这里我们使用 chevrotain 解析我们的公式代码。(*主要是 nearley 的文档写的太辣鸡了,对新手极其不友好,且 chevrotain 是用 ts 写的,nearley 是 js 写的)。不管是哪个框架,他们的资料都比较少,其中部分内容非常晦涩难懂,所以还需要一些耐心才可以。
另外还有一个概念需要先讲一下,上文中我们大量的提到了 AST,此外在 chevrotain 中我们看到还有 CST,两者的区别是啥?本质上来说,想要把公式之类的东西运行起来,最重要的事情是解析,初步解析的内容我们称之为解析树(或者叫具体解析树,也就是 CST),而 AST 则是在具体解析树精简以后的结果,即这个过程就是从具体到抽象,关于这块可以读一下这篇
AST 系列(一): 抽象语法树为什么抽象 - 知乎 (zhihu.com)
里面对于具体到抽象的过程讲的比较透彻。
好,我们理论知识和武器都有了,该实操一下了,我们先看几个简单的公式:
1 + 2
SUM(1, 2)
IF(3 > 2, 1, 2)
回想一下我们开始说的,公式的组成三要素:算数表达式、函数、代数,基于这三个,我们其实可以提炼一些规则出来,比如 anythings+anythings 这是一个表达式,所以我们是不是可以定义一个规则,只要找到加号,就把加号左右两边的内容加起来?
比如我们要解析 1+2
,这个时候,我们来先做一下词法拆分:
export const NumberMark = createToken({
name: 'NumberMark',
pattern: /-?\d*\.?\d+/,
})
export const AddMark = createToken({
name: 'AddMark',
pattern: /\+/,
})
然后交给雪佛兰去解析:
;(function jsonGrammarOnlyExample() {
// ----------------- Lexer -----------------
const createToken = chevrotain.createToken
const Lexer = chevrotain.Lexer
const NumberMark = createToken({
name: 'NumberMark',
pattern: /-?\d*\.?\d+/,
})
const AddMark = createToken({
name: 'AddMark',
pattern: /\+/,
})
const AddTokens = [NumberMark, AddMark]
const AddLexer = new Lexer(AddTokens, {
// Less position info tracked, reduces verbosity of the playground output.
positionTracking: 'onlyStart',
})
// for the playground to work the returned object must contain these fields
return {
lexer: AddLexer,
}
})()
我们可以看到数字和加号都被正常的解析出来了。
随后,我们来实现一下具体的加号功能:
;(function calculatorExample() {
// ----------------- lexer -----------------
const createToken = chevrotain.createToken
const tokenMatcher = chevrotain.tokenMatcher
const Lexer = chevrotain.Lexer
const EmbeddedActionsParser = chevrotain.EmbeddedActionsParser
const Plus = createToken({ name: 'Plus', pattern: /\+/ })
const Number = createToken({ name: 'Number', pattern: /[1-9]\d*/ })
// whitespace is normally very common so it is placed first to speed up the lexer
const allTokens = [Plus, Number]
const CalculatorLexer = new Lexer(allTokens)
class Calculator extends EmbeddedActionsParser {
constructor() {
super(allTokens)
const $ = this
$.RULE('additionExpression', () => {
let value, op, rhsVal
value = parseInt($.CONSUME(Number).image)
op = $.CONSUME(Plus)
rhsVal = parseInt($.CONSUME2(Number).image)
value += rhsVal
return value
})
this.performSelfAnalysis()
}
}
// for the playground to work the returned object must contain these fields
return {
lexer: CalculatorLexer,
parser: Calculator,
defaultRule: 'additionExpression',
}
})()
是不是非常简单?总体来看,我们先定义了两个 token,一个是数字的,一个是 add 操作符的,随后我们编写了一个 RULE,先消费($.CONSUME)了一个数字,然后再消费了加号 Plus,再消费了一个数字。雪佛兰会根据这套规则去试着看能不能消费的了,如果可以则会一行一行执行下去,最终完成我们的value += rhsVal
然后我们把值 return 出去就完成了加法。如果没有匹配到,比如我们输入的第一个单位是字符串或者第二个符号是 *,则他会报错:
那接下来就很简单啦,我们只需要把剩下来的 token 补上即可,比如我们再编写一套乘法的规则:
;(function calculatorExample() {
// ----------------- lexer -----------------
const createToken = chevrotain.createToken
const tokenMatcher = chevrotain.tokenMatcher
const Lexer = chevrotain.Lexer
const EmbeddedActionsParser = chevrotain.EmbeddedActionsParser
const Plus = createToken({ name: 'Plus', pattern: /\+/ })
const Mut = createToken({ name: 'Mut', pattern: /\*/ })
const Number = createToken({ name: 'Number', pattern: /[1-9]\d*/ })
// whitespace is normally very common so it is placed first to speed up the lexer
const allTokens = [Plus, Number, Mut]
const CalculatorLexer = new Lexer(allTokens)
class Calculator extends EmbeddedActionsParser {
constructor() {
super(allTokens)
const $ = this
$.RULE('value', () => {
let val
$.OR([
{ ALT: () => (val = $.SUBRULE($.additionExpression)) },
{ ALT: () => (val = $.SUBRULE($.mutExpression)) },
])
return val
})
$.RULE('additionExpression', () => {
let value, op, rhsVal
value = parseInt($.CONSUME(Number).image)
op = $.CONSUME(Plus)
rhsVal = parseInt($.CONSUME2(Number).image)
value += rhsVal
return value
})
$.RULE('mutExpression', () => {
let value, op, rhsVal
value = parseInt($.CONSUME(Number).image)
op = $.CONSUME(Mut)
rhsVal = parseInt($.CONSUME2(Number).image)
value *= rhsVal
return value
})
this.performSelfAnalysis()
}
}
// for the playground to work the returned object must contain these fields
return {
lexer: CalculatorLexer,
parser: Calculator,
defaultRule: 'value',
}
})()
好,那么现在问题来了,现在只能做单个加减乘除的运算,如何支持1+2*3
这样的东西呢?
在雪佛兰的世界里,对于输入内容的解析,他是依靠LL grammar - Wikipedia 语法规则进行解析的,这个规则非常复杂我们不在这里做过多深入,总结下来就是:
从左至右,分析每个词法的右部内容,且一层一层递归分析。
我们举个例子:
假设要分析1+2*3
对于我们编写的雪佛兰程序来说,他应该先把 1 消费掉,然后暂时把 1 存下来,把+也存下来,然后接着去分析2*3
,到了 2 这里,同样也是把 2 存下来,*存下来,去分析 3,如果后面还有东西,就应该依次往下递归,直到最底层他已经解析完成了,再一层一层往上把结果抛回去,上层拿到结果以后执行自己的逻辑再把值抛给他的上层,这里有点像我们程序里的栈(先进后出)概念。
我们再来举个实际的栗子,下面的例子在程序中不是正确的,但能很好地表达 LL 的思想:
1+2*3+4-5
// 程序的执行逻辑会是这样:
// 先标记1和+,然后存下来,然后去分析2*3+4-5
// 再标记2和*,存下来,然后去分析3+4-5
// 再标记3和+,存下来,然后去分析4-5
// 再标记4和-,存下来,然后去分析5
// 到了5这里,5的右边已经没有东西了,所以直接return 5
// 4的那一层规则接收到了5的return,开始执行4-5=-1,然后把-1 return 出去
// 3的那一层接收到了-1,计算3+-1,得到2,然后把2 return 出去
// 2的那一层接收到了2,计算2*2,得到4,把4 return 出去
// 1的那一层接收到了4,计算1+4 得5,最终整个程序return出去了一个5.
好,到这里大家会发现一个问题,按照上面的规则,其实我们这个算出来的结果是错的,因为数学是先乘除后加减,正常1+2*3+4-5
所以这里会有一个规则优先级的概念,我们一起完善下整个程序就知道如何定义这个优先级了:
;(function calculatorExample() {
// ----------------- lexer -----------------
const createToken = chevrotain.createToken
const tokenMatcher = chevrotain.tokenMatcher
const Lexer = chevrotain.Lexer
const EmbeddedActionsParser = chevrotain.EmbeddedActionsParser
// using the NA pattern marks this Token class as 'irrelevant' for the Lexer.
// AdditionOperator defines a Tokens hierarchy but only leafs in this hierarchy
// define actual Tokens that can appear in the text
const AdditionOperator = createToken({ name: 'AdditionOperator', pattern: Lexer.NA })
const Plus = createToken({ name: 'Plus', pattern: /\+/, categories: AdditionOperator })
const Minus = createToken({ name: 'Minus', pattern: /-/, categories: AdditionOperator })
const MultiplicationOperator = createToken({ name: 'MultiplicationOperator', pattern: Lexer.NA })
const Multi = createToken({ name: 'Multi', pattern: /\*/, categories: MultiplicationOperator })
const Div = createToken({ name: 'Div', pattern: /\//, categories: MultiplicationOperator })
const NumberLiteral = createToken({ name: 'NumberLiteral', pattern: /[1-9]\d*/ })
const WhiteSpace = createToken({
name: 'WhiteSpace',
pattern: /\s+/,
group: Lexer.SKIPPED,
})
// whitespace is normally very common so it is placed first to speed up the lexer
const allTokens = [
WhiteSpace,
Plus,
Minus,
Multi,
Div,
NumberLiteral,
AdditionOperator,
MultiplicationOperator,
]
const CalculatorLexer = new Lexer(allTokens)
class Calculator extends EmbeddedActionsParser {
constructor() {
super(allTokens)
const $ = this
$.RULE('additionExpression', () => {
let value, op, rhsVal
// parsing part
value = $.SUBRULE($.multiplicationExpression)
console.log('additionExpression, left-value:', value)
$.MANY(() => {
op = $.CONSUME(AdditionOperator)
console.log('additionExpression, op:', op)
rhsVal = $.SUBRULE2($.multiplicationExpression)
console.log('additionExpression, right-value:', rhsVal)
if (tokenMatcher(op, Plus)) {
value += rhsVal
console.log('additionExpression, a+b:', value)
} else {
value -= rhsVal
console.log('additionExpression, a-b:', value)
}
})
return value
})
$.RULE('multiplicationExpression', () => {
let value, op, rhsVal
// parsing part
value = parseInt($.CONSUME(NumberLiteral).image, 10)
console.log('multiplicationExpression, left-value:', value)
$.MANY(() => {
op = $.CONSUME(MultiplicationOperator)
console.log('multiplicationExpression, op:', op)
rhsVal = parseInt($.CONSUME2(NumberLiteral).image, 10)
console.log('multiplicationExpression, rhsVal:', rhsVal)
if (tokenMatcher(op, Multi)) {
value *= rhsVal
console.log('multiplicationExpression, a*b:', value)
} else {
value /= rhsVal
console.log('multiplicationExpression, a/b:', value)
}
})
return value
})
this.performSelfAnalysis()
}
}
return {
lexer: CalculatorLexer,
parser: Calculator,
defaultRule: 'additionExpression',
}
})()
好,接下来就是去补充下面这几种情况:
比较符
括号表达式
变量
函数
数组
代码太多,这里主要给大家讲一下函数,其他的看源码即可:
Hansuku/super-form-formula: a formula realize, work with form-formula (github.com)
函数的核心在于,我们需要一个规则,去定义函数的提取,比如SUM(self.text_1. self.text_2, ADD(self.text_1, self.text_2))
这样的东西,需要把 text_1+text_2+text_1+text_2。 所以我们先来确认他是一个函数,需要用到的 Token 是:
export const FunctionMark = createToken({
name: 'Function',
pattern: /[A-Za-z_]+[A-Za-z_0-9.]*\(/,
})
export const CloseParen = createToken({
name: 'CloseParen',
pattern: /\)/,
})
只需要一个字母开头+固定的一个左括号,就可以认定这是一个函数开头,再使用右括号结尾:
private FunctionOp = this.RULE('FunctionOp', () => {
let functionName = this.CONSUME(FunctionMark).image;
this.CONSUME2(CloseParen);
});
然后就是中间部分了,这里需要考虑的情况比较多,比如函数嵌套函数像上面的 SUM 里有一个 ADD,或者是别的变量,但是其实总体来说我们会发现一个规律,他每一个部分都是用逗号分隔的,所以这里用到了一个比较重要的方法:MANY_SEP
,可以理解为,我们对self.text_1. self.text_2, ADD(self.text_1, self.text_2
这一段内容使用 js 中的 split(',')方法,然后循环他~
private FunctionOp = this.RULE('FunctionOp', () => {
let functionName = this.CONSUME(FunctionMark).image;
functionName = functionName.substr(0, functionName.length - 1);
const params: Array<any> = []; // 存放所有参数
this.MANY_SEP({
SEP: CommaMark, // 使用逗号循环
DEF: () => {
// 每次循环需要干的事情
const subParams = this.SUBRULE1(this.SummaryEntry);
params.push(subParams);
},
});
this.CONSUME2(CloseParen);
return this.ACTION(() => {
return this.SummaryFunction[functionName] && this.SummaryFunction[functionName](...params)
});
});
我们使用了一个数组来记录每个逗号之间分隔的内容,并且这个内容我们已经通过this.SUBRULE1(this.SummaryEntry);
从我们整个程序入口的地方去计算每一项里面需要做什么了,最后,我们看一下SummaryFunction
中的内容:
...
COUNT: function(...arr: Array<any>) {
return count([...arr]);
},
COUNTIF: function(array: Array<any>, criteria: string) {
/[<>=!]/.test(criteria) || (criteria = '=="' + criteria + '"');
let matches = 0;
for (let args = flatten(array), i = 0; i < args.length; i++) {
let computCharacters = 'string' !== typeof args[i] ? `return ${args[i]}${criteria}` : `return '${args[i]}'${criteria}`
new Function(computCharacters)() && matches++
}
return matches;
},
SUMIF: function(array: Array<number>, criteria: string) {
/[<>=!]/.test(criteria) || (criteria = '=="' + criteria + '"');
const args = flatten(array);
let matches = 0;
for (let i = 0; i < args.length; i++) {
if (new Function(`return ${args[i]}${criteria}`)()) {
matches += args[i];
}
}
return matches;
},
...
这里面就是一些纯 js 方法,通过this.SummaryFunction[functionName] && this.SummaryFunction[functionName](...params)
调用可以把函数体中的参数计算好然后传入给这个方法一起计算~
那么基本上到这里就讲完了,其实本身难度不大,主要是思路绕的过来就很好理解了。
最后给大家可以想一下,怎么把下面这一段转换成一段 js:
今有一人,名曰“蔡徐坤”。
其年岁之大,“二十三”是也。
其神通之大,“唱跳RAP篮球”是也。
转换成:
const person = new Person({ name: '蔡徐坤' })
person.age = '二十三'
person.skill = '唱跳RAP篮球'