使用Chevrotain构建简单的数学公式解析器

前言

最近做BI产品，客户提了个需求，期望在表格展示的时候可以配置汇总行，类型Excel中的SUM函数，配置了汇总的列可以自动计算所有行数据的和进行展示。

单纯的SUM或者其他数学函数其实是不复杂的，难点在于，部分列的定义，直接相加没有意义。比如CTR这种指标，本身是百分比，算汇总需要将点击数和展示数分别汇总然后相除。

一些BI工具提供简单的计算公式，可以对指标进行计算操作，Excel或者在线编辑的表格等，则提供更复杂的函数。

在上述的场景中，如果提供输入框给用户可以输入公式及数学表达式，功能层面会灵活很多，但是技术实现层面则没法通过简单的正则解析等操作进行处理。产品经理基于一般场景，设计了通用计算模板，功能类似下拉框选择公式和操作符。但是个人总觉得不是很优雅，觉得是个中间产物。

于是我尝试用大学学的一些编译原理的皮毛，看如果解决输入解析的问题，直接提供输入框供用户输入是不是可以达到比较灵活的效果。

编译原理简述

大学教材用的《编译原理》，人称龙书，因为书的封面是一条紫色的龙，英文书名其实是“Compilers: Principles, Techniques, and Tools”。

编译器大致的步骤如下

                                 high level
                                  language
                                     │
                           ┌─────────▼─────────┐
                           │ lexical analyzer  │
                           └─────────┬─────────┘
                                     │
                           ┌─────────▼─────────┐
                           │  syntax analyzer  │
                           └─────────┬─────────┘
                                     │
                           ┌─────────▼─────────┐
                           │ semantic analyzer │
         ┌──────────────┐  └─────────┬─────────┘    ┌──────────────┐
         │ symbol table │            │              │error handling│
         └──────────────┘  ┌─────────▼─────────┐    └──────────────┘
                           │ intermediate code │
                           │     generator     │
                           └─────────┬─────────┘
                                     │
                           ┌─────────▼─────────┐
                           │  code optimiser   │
                           └─────────┬─────────┘
                                     │
                           ┌─────────▼─────────┐
                           │    target code    │
                           │     generation    │
                           └───────────────────┘
                                     ▼
                               assembly code

完全从0开始构建一个编译器是很难的事情，2020年图灵奖就颁给了《编译原理》的其中两个作者，表彰他们在编程语言实现的基础算法和理论上做出的贡献。才疏学浅，对编译原理相关理论和优化细节就不在这边做过多探讨。

幸运的是，目前有不少工具可以帮助我们构建一些简单的编译器，如yacc和antlr。

探索

基础的算式

我们从最简单的数学算式开始，来探索构建一个解释器的过程。首先我们需要对数学算式的文法进行定义，一个算式是类似如下的形式：

$$ (1 + 2) * 3 $$

算式包含加减乘除，括号，以及数字等基本元素。可以定义如下的文法描述（antlr语法）：

grammar Calculator;

// parser

start : expr | <EOF> ;

expr
   : NUMBER             # DOUBLE
   | '-' expr           # UMINUS
   | '(' expr ')'       # PARENGRP
   | expr mulop expr    # MULOPGRP
   | expr addop expr    # ADDOPGRP
   ;

addop : '+' | '-' ;

mulop : '*' | '/' ;

// lexer

NUMBER : ('0' .. '9') + ('.' ('0' .. '9') +)? ;

WS : [ \r\n\t] + -> skip ;

之前(1 + 2) * 3的示例，按照该文法可以表示为:

工具

上面是用antlr描述的文法定义。前端有个很不错的工具，chevrotain ，可以方便地通过JavaScript编写词法、语法及解析规则，然后在前端代码中进行解析处理生成结果。

我们要用编译原理做一个数学算式的解析器，首先就是先定义其文法。在上面我们其实已经通过antlr的方式定义了数学算式的文法。文法是对语法规则的精确描述，定义了语言中合法的语法结构和组织形式。

下面是用chevrotain提供的工具生成的语法图例：

数学算式 - 词法

上一节中我们看到了使用Chevrotain生成的最终语法图例。实际编写一个解析器，有了文法定义后我们需要先描述其词法规则。在Chevrotain中，我们通过createToken来生成词法单元token，如下：

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 LParen = createToken({ name: "LParen", pattern: /\(/ });
const RParen = createToken({ name: "RParen", pattern: /\)/ });
const NumberLiteral = createToken({
  name: "NumberLiteral",
  pattern: /[1-9]\d*/,
});

// marking WhiteSpace as 'SKIPPED' makes the lexer skip it.
const WhiteSpace = createToken({
  name: "WhiteSpace",
  pattern: /\s+/,
  group: Lexer.SKIPPED,
});

其中我们定义了AdditionOperator, MultiplicationOperator，这两个是抽象的单元，实际词法单元由其叶子节点Plus & Minus及Multi & Div表达。其余的词法单元为左右括号，数字，以及空格。

词法分析的过程就是将原始输入解析成词法单元序列。定义了如上的词法单元后，可以通过提供的Lexer类生成词法解析器。

const allTokens = [
  WhiteSpace, // whitespace is normally very common so it should be placed first to speed up the lexer's performance
  Plus,
  Minus,
  Multi,
  Div,
  LParen,
  RParen,
  NumberLiteral,
  AdditionOperator,
  MultiplicationOperator,
];
const CalculatorLexer = new Lexer(allTokens);

数学算式 - 文法规则

有了词法单元和词法分析器，我们使用CstParser父类来定义我们的文法规则，如下：

class CalculatorPure extends CstParser {
  constructor() {
    super(allTokens);

    const $ = this;

    $.RULE("expression", () => {
      $.OR([
        { ALT: () => $.SUBRULE($.uminusExpression) },
        { ALT: () => $.SUBRULE($.additionExpression) },
      ]);
    });

    $.RULE("uminusExpression", () => {
      $.CONSUME(Minus);
      $.SUBRULE($.expression);
    });

    //  lowest precedence thus it is first in the rule chain
    // The precedence of binary expressions is determined by how far down the Parse Tree
    // The binary expression appears.
    $.RULE("additionExpression", () => {
      $.SUBRULE($.multiplicationExpression, { LABEL: "lhs" });
      $.MANY(() => {
        // consuming 'AdditionOperator' will consume either Plus or Minus as they are subclasses of AdditionOperator
        $.CONSUME(AdditionOperator);
        //  the index "2" in SUBRULE2 is needed to identify the unique position in the grammar during runtime
        $.SUBRULE2($.multiplicationExpression, { LABEL: "rhs" });
      });
    });

    $.RULE("multiplicationExpression", () => {
      $.SUBRULE($.atomicExpression, { LABEL: "lhs" });
      $.MANY(() => {
        $.CONSUME(MultiplicationOperator);
        //  the index "2" in SUBRULE2 is needed to identify the unique position in the grammar during runtime
        $.SUBRULE2($.atomicExpression, { LABEL: "rhs" });
      });
    });

    $.RULE("atomicExpression", () =>
      $.OR([
        // parenthesisExpression has the highest precedence and thus it appears
        // in the "lowest" leaf in the expression ParseTree.
        { ALT: () => $.SUBRULE($.parenthesisExpression) },
        { ALT: () => $.CONSUME(NumberLiteral) },
        // { ALT: () => $.SUBRULE($.powerFunction) },
      ])
    );

    $.RULE("parenthesisExpression", () => {
      $.CONSUME(LParen);
      $.SUBRULE($.expression);
      $.CONSUME(RParen);
    });

    // very important to call this after all the rules have been defined.
    // otherwise the parser may not work correctly as it will lack information
    // derived during the self analysis phase.
    this.performSelfAnalysis();
  }
}

Chevrotain解析器使用如下的规则：

CONSUME - 映射单个词法单元
SUBRULE - 引用其他规则
OR - 多选一
OPTION - 可选规则
MANY - 重复单次或多次
AT_LEAST_ONE - 重复一次或多次
MANY_SEP - 带分隔的重复单次或多次
AT_LEAST_ONE_SEP - 带分隔的重复一次或多次

上述CalculatorPure类通过继承CstParser来生成一个具象语法树（CST - Concrete Syntax Tree）。与之对应，很多人可能对抽象语法树（AST - Abstract Syntax Tree）概念更为熟悉。两者的主要区别如下：

一个抽象语法树通常不会包含所有的语法信息。这意味着无法总是从抽象语法树中完全重构出原始的准确文本。
一个抽象语法树不会表示完整的语法解析树。它通常只包含与特定解析树节点相关的节点，而不是所有节点（主要是叶节点）。

其他一些概念，如文法（Grammar）与语法（Syntax），描述如下（引用自ChatGPT）：

在编译原理中，文法（Grammar）和语法（Syntax）是两个相关但不完全相同的概念。
文法（Grammar）是描述编程语言或自然语言的一组规则。它定义了语言中合法的语法结构和句子形式。文法通常使用产生式（Production）来表示规则，其中左侧是非终结符（Non-terminal），右侧是终结符（Terminal）和/或非终结符的序列。文法分为上下文无关文法（Context-Free Grammar）和上下文相关文法（Context-Sensitive Grammar）等不同类型，其严格规定了语言的语法结构。
语法（Syntax）则是指编程语言中的规则和约定，用于定义合法的程序结构和语句形式。语法规定了程序中可以使用的关键字、运算符、标识符、语句、表达式等元素以及它们之间的组合方式。语法是一种抽象的描述方式，用于确保程序结构的正确性和一致性。编程语言的语法通常是基于某种文法定义的，因此语法可以看作是文法在编程语言中的具体实现。

数学算式 - 语义分析

通过语法分析，我们生成了语法树。语法树只是对输入文本进行文法规则的解析，实际场景中我们还需要使其输出实际的结果或者其他数据结构。像数学算式的例子，解析后其实是期望输出一个最终算式的结果，如(1 + 2) * 3我们其实期望得到9这样的结果。这就是语义分析所做的事情，我们对语法树进行遍历，针对语法树中的每个节点采取对应的动作（semantics），如数学运算，然后最后输出结果，这是一个递归的过程。

Chevrotain提供了针对CST的Vistor类，用来遍历语法树。针对之前CalculatorPure类，可以较为方便的编写其解释器，如下：

const parser = new CalculatorPure([]);
const defaultRuleName = "expression";

// ----------------- Interpreter -----------------
const BaseCstVisitor = parser.getBaseCstVisitorConstructor();

class CalculatorInterpreter extends BaseCstVisitor {
  constructor() {
    super();
    // This helper will detect any missing or redundant methods on this visitor
    this.validateVisitor();
  }

  expression(ctx) {
    if (ctx.additionExpression){
      return this.visit(ctx.additionExpression);
    } else { // uminus
      return this.visit(ctx.uminusExpression);
    }
  }

  uminusExpression(ctx) {
    return -1 * this.visit(ctx.expression);
  }

  additionExpression(ctx) {
    let result = this.visit(ctx.lhs);

    // "rhs" key may be undefined as the grammar defines it as optional (MANY === zero or more).
    if (ctx.rhs) {
      ctx.rhs.forEach((rhsOperand, idx) => {
        // there will be one operator for each rhs operand
        let rhsValue = this.visit(rhsOperand);
        let operator = ctx.AdditionOperator[idx];

        if (tokenMatcher(operator, Plus)) {
          result += rhsValue;
        } else {
          // Minus
          result -= rhsValue;
        }
      });
    }

    return result;
  }

  multiplicationExpression(ctx) {
    let result = this.visit(ctx.lhs);

    // "rhs" key may be undefined as the grammar defines it as optional (MANY === zero or more).
    if (ctx.rhs) {
      ctx.rhs.forEach((rhsOperand, idx) => {
        // there will be one operator for each rhs operand
        let rhsValue = this.visit(rhsOperand);
        let operator = ctx.MultiplicationOperator[idx];

        if (tokenMatcher(operator, Multi)) {
          result *= rhsValue;
        } else {
          // Division
          result /= rhsValue;
        }
      });
    }

    return result;
  }

  atomicExpression(ctx) {
    if (ctx.parenthesisExpression) {
      // passing an array to "this.visit" is equivalent
      // to passing the array's first element
      return this.visit(ctx.parenthesisExpression);
    } else if (ctx.NumberLiteral) {
      // If a key exists on the ctx, at least one element is guaranteed
      return parseInt(ctx.NumberLiteral[0].image, 10);
    }
  }

  parenthesisExpression(ctx) {
    // The ctx will also contain the parenthesis tokens, but we don't care about those
    // in the context of calculating the result.
    return this.visit(ctx.expression);
  }
}

数学算式 - 测试

当我们有了如上词法、语法、语义等处理后，我们可以用相关的定义来处理实际的文本，然后解释生成输出，相关测试代码如下：

import {expect, test} from 'vitest';
import { CalculatorLexer, CalculatorInterpreter, parser, defaultRuleName } from "./calculator.js";

const visitor = new CalculatorInterpreter();

function parse(lexResult, startRuleName) {
  parser.reset();
  parser.input = lexResult.tokens;
  let value = parser[startRuleName]();
  return { value: value, errors: parser.errors };
}

function evaluate(text) {
  let lexResult = CalculatorLexer.tokenize(text);
  let parseResult = parse(lexResult, defaultRuleName);
  if (parseResult.errors.length > 0) {
    return new Error(parseResult.errors);
  }
  let result = visitor.visit(parseResult.value);
  return result;
}


const testData = [{
  message: 'negivate number',
  calc: '-1',
  value: -1
}, {
  message: 'basic add',
  calc: '1+2',
  value: 3
}, {
  message: 'basic minus',
  calc: '1-2',
  value: -1
}, {
  message: 'basic multi',
  calc: '1 * 2',
  value: 2
}, {
  message: 'basic div',
  calc: '10 / 5',
  value: 2
}, {
  message: 'paren',
  calc: '(1+2)*3',
  value: 9
}, {
  message: 'negivate with paren',
  calc: '-(1+2)',
  value: -3
}]

for (const data of testData) {
  const {message, calc, value} = data;
  test(message, () => {
    expect(evaluate(calc)).toBe(value);
  });
}

test('expect error', () => {
  expect(evaluate('abc')).toBeInstanceOf(Error);
});

如运行evaluate('(1 + 2) * 3')将会输出我们期望的数字9。

扩展

上面是针对简单的数学算式，定义了一套文法及解析规则，我们可以对其进行扩展，使其支持函数等符号。扩展的文法定义如下：

grammar formula;

expression
    : '-' expression
    | additionalExpression;

additionalExpression
    : multiplicationExpression (additionalOperator multiplicationExpression)?;

additionalOperator
    : '+' | '-';

multiplicationExpression
    : atomicExpression (multiplicationOperator additionalExpression)?;

multiplicationOperator
    : '*' | '/';

atomicExpression
    : parenthesisExpression | NumberLiteral | formulaExpression;

parenthesisExpression
    : LParen expression RParen;

LParen
    : '(';

RParen
    : ')';

NumberLiteral
    : ('0' .. '9') + ('.' ('0' .. '9') +)? ;

formulaExpression
    : FormulaLiteral LParen ReferenceLiteral RParen;

FormulaLiteral
    : 'SUM' | 'AVG' | 'MAX' | 'MIN';

ReferenceLiteral
    : ('a' .. 'z' | 'A' .. 'Z' | '_' | '0' .. '9') + ;

可视化后效果如下：

其中formulaExpression在语法分析Parser中的定义如下：

$.RULE("formulaExpression", () => {
  $.CONSUME(FormulaLiteral, {LABEL: "formula"});
  $.CONSUME(LParen);
  $.CONSUME(ReferenceLiteral, {LABEL: "reference"});
  $.CONSUME(RParen);
});

对应在语义解释器中的解析如下（this.data是在构造函数中传入的数据）：

formulaExpression(ctx) {
  let formula = ctx.formula[0];
  let reference = ctx.reference[0].image;
  if (!this.data.hasOwnProperty(reference)) {
    throw new Error(`Unknown reference: ${reference}`);
  }
  let values = this.data[reference];
  if (values.length === 0) {
    throw new Error(`Empty reference: ${reference}`);
  }
  if (tokenMatcher(formula, Sum)) {
    return _.sum(values);
  } else if (tokenMatcher(formula, Avg)) {
    return _.sum(values) / values.length;
  } else if (tokenMatcher(formula, Max)) {
    return _.max(values);
  } else if (tokenMatcher(formula, Min)) {
    return _.min(values);
  }
}

完整的代码发布在https://github.com/tomowang/formula-parser-demo

后记

编译原理涉及的知识远不止这些，简单的如LL文法与LR文法的差别，如何消除左递归等，有空的时候再做些整理。