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

StackOverflow https://stackoverflow.com/questions/8356206

题

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

有帮助吗？

解决方案

我会尝试boost :: spirit。它通常非常快（即使是解析整数之类的简单事物，它也可能比atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html ）

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

它有很多优点：仅标头，因此具有依赖关系，具有自由许可证。

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

其他提示

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

大多数解析器生成器旨在简化运行中的解析器，因此执行时间通常会受到影响。

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

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

如果表达式的语法足够简单，请考虑制作一个手写的递归下降解析器。它可以非常快速地运行，并且（足够谨慎）使您能够很好地报告特定语法错误。

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

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

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

代替 expr 让你语法识别 sequence-of-expr.

编辑：

而不是（野牛语法）：

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

有：

start: expr_seq ;

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

我编写了许多解析器，而手工编码的递归下降就是我这样做的方式。它们易于编写，并且几乎是最佳选择。

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

下面是显示的 幻灯片组 怎么做。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top