用于解析 C++ 中的许多小文本的最佳解析器生成器？

Question

出于性能原因，我将 C# 库移植到 C++。在正常操作期间，该库除其他事项外，还需要解析大约 150,000 个平均长度小于 150 个字符的数学表达式（例如 Excel 公式）。

在C#版本中，我使用GOLD解析器来生成解析代码。它可以在一秒内解析所有 150,000 个表达式。

因为我们正在考虑扩展我们的语言，所以我认为转向 C++ 可能是转向 ANTLR 的好机会。我已将（简单）语法移植到 ANTLR 并从中生成了 C 代码。解析 150'000 个表达式需要超过 12 秒，因为对于每个表达式，我需要创建一个新的 ANTL3_INPUT_STREAM、令牌流、词法分析器和解析器 - 至少在版本 3.4 中，无法重用它们。

如果有人能给我一个建议，我将不胜感激 - GOLD 当然是一个选项，尽管生成 C++ 或 C 代码似乎比 C# 代码复杂得多。我的语法与 LALR 和 LL(1) 兼容。最重要的是解析小输入的性能。

Answer 1

我会尝试提升::精神。它通常非常快（即使是解析整数等简单的东西，它也比 C 函数 atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html)

http://boost-spirit.com/home/

它有很好的东西：只有标题，所以依赖地狱，自由许可证。

但请注意，学习曲线很困难。它是现代 C++（没有指针，但有很多模板和非常令人沮丧的编译错误），因此来自 C 或 C#，您可能会不太舒服。

Answer 2

如果要解析的语法很简单，您可能只需手动编写解析器即可。

大多数解析器生成器的设计目的是让您可以轻松地启动一个可用的解析器，而执行时间通常会因此受到影响。

Answer 3

我在解析中看到的最佳性能来自 Boost.Spirit.Qi，它使用元模板编程在 C++ 中表达语法。但这不适合胆小的人。

这需要很好地隔离，并且包含解析器的文件的编译时间将增加到几秒钟（因此最好确保那里的时间尽可能少）。

Answer 4

如果表达式的语法足够简单，请考虑制作一个手写的递归下降解析器。它可以运行得非常快，并且使您能够（足够小心）报告良好且具体的语法错误。

您也可以使用 bison，但我相信手写的递归解析器可能会更快。

您可以使用 flex 生成的词法分析器进行词法分析，并以递归方式手动进行解析下降方式。

供您参考，GCC 编译器有自己的 C++ 和 C++ 递归下降解析器。至少C。它不再使用解析器生成器（例如 bison 或 ANTLR）。

Answer 5

而不是 expr 让您在语法上识别 sequence-of-expr。

编辑：

而不是（野牛语法）：

start: expr { process_expr ($1); }
     ;

有：

start: expr_seq ;

expr_seq:   expr          { process_expr ($1); }
          | expr_seq expr { process_expr ($2); }
          ;

Answer 6

我已经编写了很多解析器，并且手工编码的递归下降是我的做法。它们很容易编写并且几乎是最佳的。

也就是说，如果您追求的是速度，那么无论您写什么，都有足够的空间来加快速度。
这些方式可能会让你感到惊讶，因为任何你能想到的事情，你都已经做过了。

这是幻灯片集展示了如何操作它。