如何编写一个高效的Java表达式求值程序

如何编写一个高效的 Java 表达式求值程序

虽然这个标题略显夸张，但我确实完成了这样一个目标（关于是否完全相信基准测试结果，那是另一个话题）。

上周，我一直在寻找一个小型、实用的数学表达式计算类库。偶然间，我在 StackOverflow 上看到了一个帖子，里面推荐的库（Expr）确实很快，且基本拥有我需要的所有特性。但不幸的是，它不支持限制变量范围（在虚拟机里面，所有变量都位于一个全局命名空间）。

于是，我做了一件通常不建议做的事情：重新发明轮子，自己编写一个解析器和执行器。那是一个下雨的周六，我想到用一个小型递归向下的解析器，构建一个简化版的、可计算表达式的抽象语法树（AST）。抽象语法树配合一个小型变量管理助手，看起来并没有什么大不了，但它并非无用。我做出了一个初步的实现，执行速度特别快。在进行了一些测试后，结果更让我充满信心：它执行的所有运算都正确无误。

我想与前面提到的类库相比，确认这个计算器到底有多快。在没有对每个内部循环和其他执行细节进行优化前，我并不报太大期望，毕竟有不少类库是成熟的商业软件。但当我看到测试结果时，我感到很惊讶。下面的清单展示了一个小的基准测试，使用不同的类库计算同一个表达式。parsii 是我编写的库，测试时用的是最终版本。这个版本做了一些简化，比如预先计算了常量表达式，但没有使用任何“黑魔法”，比如生成字节码或者其他类似的操作。

性能基准测试

在性能评估中，用例是执行表达式 2 + (7 – 5) * 3.14159 * x^(12-10) + sin(-3.141)。其中变量 x 的取值范围测试参考了 Expr 的相关设定，迭代次数为 0 到 1,000,000。测试时先运行 10 次对 JIT 进行预热，然后再运行 15 次计算平均时间：

现在我敢肯定，每一个类库都有自己的优势，所以不能直接对它们进行绝对比较。尽管如此，令人吃惊的是一个简单实现的程序可以拥有这么好的表现。

核心架构

如果读者对于编译器的原理不太了解，下面是一个关于编译器运行机制的简单介绍。

词法分析 (Tokenizer)

同其他的解析器或者编译器一样，parsii 使用了传统的 分词器。它将字符流转化成词法单元流（Token Stream）。例如 "4 + 38"，也就是字符数组 '4', ' ', '+', ' ', '3', ' ', ' ', '8' 被转化成：

• 4 (整数)
• + (符号)
• 38 (整数)

分词器读取一个字符，接着判断是一个什么类型的词法单元，然后再读入属于该词法单元的所有字符。每一个词法单元都有类型、文本内容，并且知道起始位置（行号和字符偏移）。网上有很多深入的教程，所以在这里就不详细讲解了。你可以看一下源代码，但正如我说的，它只是一个初步的实现。

语法解析 (Parser)

解析器 用来将传入的词法单元流翻译成可以执行的 AST（抽象语法树）。它是一个传统的自上而下递归解析器（Recursive Descent Parser）。这是实现解析器最简单的方式，完全手写，没有利用工具生成。像这样的解析器只拥有一个包含所有语法规则的方法。

错误处理

同样，关于这种类型的解析器有很多教程，但是如何恰当地处理错误却缺少相关的示例。除了解析表达式的速度和正确性外，优秀的错误处理机制是一个优秀解析器的最核心因素之一。

正如在源代码里看到的那样，实现起来并不是太困难。因为解析器在解析表达式的过程中从来不会立即抛出异常，所有的错误都被收集起来，并且继续尽可能进行解析。即使在第一个错误发生以后已经不能成功解析生成 AST，重要的是要能够尽可能继续解析，因为在一次的执行中我们需要报告尽可能多的错误。这样的方法也同样用在了分词器报告上，比如报告非法格式的词法单元（例如带有两个小数点的浮点数），将它们放到同样的错误列表中。

表达式执行

执行一个解析完成后的抽象语法树非常简单。每一个抽象语法树节点都包含一个计算方法，调用从根节点开始，父节点会调用子节点的该方法。这里的执行结果就是表达式的结果。一个简单的例子就是 算数运算，包含了 +、-、* 等操作。

性能优化

为了减少执行时间，程序里运用了 3 种优化措施：

1. 常量折叠 (Constant Folding)
   在完成解析 AST 后，在根节点上进行一个简化的方法调用，并且会扩散到每一个子节点。每一个节点判断自己的子表达式中是否有简化的表达形式。例如：对于 算数运算，我们检查两个操作数是不是都是常量（数字）。如果是数字，我们将计算表达式并且返回一个包含计算结果的常量。对于函数，如果所有的参数都是常量的话，也会进行此类优化。
2. 变量缓存 (Variable Caching)
   在表达式中使用变量时会执行第二种优化。这里使用 map 用来在需要的时候对变量的值进行读写。这肯定是有效的，但会进行很多次的查找。所以我们有一个叫做 Variable 类，它包含了变量名称和变量值。在进行表达式解析时，变量在作用域范围内（仅是一个 map）只被 查找 一次，之后就可以一直使用。由于每次查找都返回相同的实例，所以在计算表达式值时变量的访问就像读写字段一样廉价，因为我们刚刚获取了 Variable 类的 值。
3. 延迟运算 (Lazy Evaluation)
   第三个也是最后一个优化很可能不是经常起作用，但由于易于实现，还是应用了这种优化。它的功能基本上和名字“延迟运算”一样，主要用于函数调用。函数不会自动计算所有参数值并且调用函数，而“延迟运算”会检查所有的参数，自行决定哪些参数需要计算。在 if 函数 中可以看到它应用的实例。

开源许可与源代码

parsii 遵循 MIT 许可证授权。在 GitHub 上可以找到所有的源代码，并且包含了预编译的 jar 包。

原文链接：dzone

说明：本文内容基于较早的技术背景与基准测试数据，文中提及的部分第三方类库（如 JEP、MathEval 等）版本可能已更新，性能表现仅供参考。代码示例与架构思路适用于理解表达式求值原理，实际生产环境请结合最新技术栈评估。