0. 前言

在某一天业务方需要做一个可通过自定义函数录入的功能来帮助自己动态配置一些数值的计算,而面临的问题是只有java开源程序能够进行公式的动态配置和计算。作为一个强迫症患者,npm上现有的包并不能满足需求,于是就踏上了从零开始撸公式解析器的道路。

友情提示:查看源码请拉到最后

1. 分析

我们的公式解析器需要能够对语法进行验证,保证公式输入的内容是符合语法且可以任意分拆操作的。同时,还需要对自定义的函数参数进行验参。于是我们把整个解析划分成了两部分。

  1. 令牌流解析:把公式解析成顺序的令牌
  2. 语法树解析:把解析完成的令牌流转化成语法树内容

2. 实现令牌流的思路

由于令牌流中并不考虑公式的执行问题,所以只需从左至右对一个公式字符串使用正则进行解析,并把相同的内容合并生成一个令牌。

2.1. 带变量的简单四则运算解析

10+a我们可以分拆为10+a 3个令牌。

我们会把每个令牌形成一个如下内容的对象:

// 令牌内容
export interface ITokenItem {
    type: TokenType; // 类型
    subType: TokenSubType; // 子类型
    token: string; // 令牌内容
    loc?: { // 定位
        start: number, // 起始节点
        end: number, // 结束节点
    };
}

当然,实现上面一个功能非常简单,我们只需要以下父类型以及子类型就可以覆盖所有的四则运算,如:

  1. 1+1
  2. a+1%
  3. 3/b
// 令牌类型
export enum TokenType {
    TYPE_START = 'start', // 公式起始符
    TYPE_OPERAND = 'operand', // 操作对象
    TYPE_OP_PRE = 'operator-prefix', // 前置操作符
    TYPE_OP_IN = 'operator-infix', // 居中操作符
    TYPE_OP_POST = 'operator-postfix', // 后置表达式
    TOK_TYPE_UNKNOWN = 'unknow' // 未知类型
}
// 令牌子类型
export enum TokenSubType {
    SUBTYPE_START = 'start', // 子类型起始符
    SUBTYPE_STOP = 'stop', // 子类型结束符
    SUBTYPE_VARIABLE = 'variable', // 子类型变量
    SUBTYPE_NUMBER = 'number', // 数字类型
    SUBTYPE_MATH = 'math', // 数学计算符号
}

2.2. 类型判断

如果出现1+这种错误公式情况的话,我们肯定不能算作成功,而需要对该错误数据做出反应。
同时,为了提高判断的效率,我们需要对之前令牌的类型进行判断,猜测接下来的数据是什么。

比如,当类型为公式起始时,我们判断接下来不是前置操作符-就是数字或变量,而数字或变量的概率又更高一些。

于是,我们在解析令牌时,做了如下的动作:

  1. 根据上一令牌,判断下个令牌是什么,比如数字后一定是跟居中操作符或后置表达式
  2. 如果与预期不符不能匹配到内容,则报错
  3. 需要判断最后一个令牌是否是结束预期

2.3. 嵌套的公式

对于含有括号/函数/集合({1,2,3})等多级嵌套内容的公式,除了以上的判断以外,我们还需要判断是否闭合。所以:

  1. 我们会创建一个父级token的栈,当有嵌套开始时,则入栈,当有嵌套结束时,则出栈。
  2. 当公式结束时,应判断栈内是否有内容,如果有则说明没有闭合

同时,由于我们的公式解析括号/集合的开始闭合时,并不想保留原始的内容在token数据内。所以我们额外增加了sourceToken

// 令牌内容
export interface ITokenItem {
    parentType?: TokenType; // 父类型
    type: TokenType; // 类型
    subType: TokenSubType; // 子类型
    sourceToken: string; // 令牌原始匹配内容
    token: string; // 令牌内容
    loc?: { // 定位
        sourceStart: number, // 原始公式字符串节点
        sourceEnd: number, // 原始公式字符串结束点
        start: number, // 起始节点
        end: number, // 结束节点
    };
}

2.4. 空白符和换行的解析

当然,作为强迫症患者,对于1 + 1这种公式或者换行的公式,我们也是要能解析拉,所以我们还需要扩展一下现有的内容。

  1. 当下一个字符解析为空白时,则直接跳过。
  2. 使字符串按行解析。

2.5. 优化

当相同一公式再次提交时,我们应该直接使用缓存数据。

2.6. 剩余问题

读到最后,如果要实现下面功能该怎么做呢?

  1. 如果我们需要添加注释的话,需要注意什么呢
  2. 如何对公式进行格式化

第二部分内容

  1. 语法树解析与变换
  2. 根据语法树进行自定义验证

请查看从零开始撸一个可扩展函数的数学公式解析轮子(第2部分)

源码地址

最后多谢阅读,希望能有帮助