我有一个应用程序，其中包含一个 3 运算符 (& | ！) 布尔表达式计算器，带有变量和常量。一般来说，表达式不会太长(最多可能 50 个术语，但通常要少得多)。可以有很多表达式 - 我预计上限约为一百万。目前我有一个手写的解析器，它有一个非常简单的评估器，它只是递归遍历解析树。一个约束是，这必须可以从C++调用。我在表达式之间没有共享。我想研究一下加快速度。
我看到了两种研究途径。
- 添加共享并存储指示表达式节点是否已计算的状态。
- 提取常用子表达式。
此外，我希望代码生成方法将比处理解析树或类似结构的解释方法更快。生成一些C++代码可能相当简单，但考虑到函数的长度，我不知道像 GCC 这样的编译器是否能够优化 CSE。
我已经看到有一些库可用于表达式评估，但在我的工作环境中添加第三方库并不简单，而且与我的需求相比，它们似乎都非常复杂。
最后，我最近一直在看Antlr4，所以这可能适合我。过去，我从事过 C 代码生成工作，但我没有使用 LLVM 之类的东西进行优化和代码生成的经验。
关于走哪条路有什么建议吗？
据我了解，您的问题更多的是关于更快的表达式评估，而不是关于更快的表达式解析。所以我的回答将集中在前者。毕竟，解析不应该成为瓶颈，因为您的表达式语言看起来很简单，可以为它实现手动调优的解析器。
因此，为了加快评估速度，可以考虑使用 LLVM 对公式进行 JIT 执行。也就是说，给定您的公式F您可以(相对)轻松地生成相应的LLVM IR并直接对其进行评估。这个 SMT 求解器就是这样做的。IR 代码生成在此处的单个 C++ 类中实现。 请注意，您提到的布尔表达式是该求解器支持的 SMT 语言的子集。此外，您可以轻松调整 LLVM 优化器需要的激进程度。
但是，IR 生成和优化有其开销。因此，如果给定公式的计算频率不足以摊销初始开销，那么我建议直接解释。在这种情况下，您可以寻找找到结构相似性和共同子表达式的机会。
尽管我想建议ANTLR4，但我担心它不能满足您的性能需求。 它的自适应LL(*)算法有很多事情要做，尽管有一些常见的技巧可以提高其性能，但简单地在运行时跟踪ANTLR4解释器表明，除非你当前的表达式计算器效率非常低，否则它可能比ANTLR4更快，ANTLR4是一个工业引擎，旨在支持比你复杂得多的语法。当 LALR(1) DFA 移位-归约引擎不支持我的语法时，我会使用 ANTLR，并利用性能下降来换取 ANTLR4 的额外解析能力。