1

出于性能原因，我正在将 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) 兼容的。最重要的是解析小输入的性能。

4

6 回答 6

9

我会尝试提升::精神。它通常非常快（即使解析像整数这样的简单事物，它也可以比 C 函数 atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html更快）

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

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

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

于 2011-12-02T12:25:56.920 回答
4

如果要解析的语法很简单，可以手动编写解析器。

大多数解析器生成器旨在使构建工作解析器变得容易，因此执行时间通常会受到影响。

于 2011-12-02T12:30:53.367 回答
3

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

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

于 2011-12-02T12:24:07.597 回答
2

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

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

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

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

于 2011-12-02T12:31:25.147 回答
1

我写过很多解析器，手工编码的递归下降是我这样做的方式。它们很容易编写并且几乎是最佳的。

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

这是一个幻灯片集，展示了如何做到这一点。

于 2011-12-02T13:31:54.190 回答
1

而不是expr让你语法识别sequence-of-expr。

编辑：

而不是（野牛语法）：

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

有：

start: expr_seq ;

expr_seq:   expr          { process_expr ($1); }
          | expr_seq expr { process_expr ($2); }
          ;
于 2011-12-02T12:22:07.563 回答