Published on

Eval 拜拜👋🏻!手摸手教你实现写一个AST数实现公式解析引擎

Authors
  • avatar
    Name
    Hansuku
    Twitter
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?如果纯手撸的话,代码量可以说是非常之吓人了,索性前端领域有一些非常好用的解析构建工具,比如:

Chevrotain

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篮球'
*/}