7

我正在寻找一个好的解析器生成器，可用于在我们的大型商业应用程序中读取自定义文本文件格式。目前，这种特定的文件格式是使用手工递归解析器读取的，但格式已经增长和复杂化，以至于这种方法变得无法管理。

似乎最终的解决方案是为这种格式构建一个适当的语法，然后使用像 yacc 这样的真正的解析器生成器来读取它，但我无法决定使用哪个这样的生成器，或者即使它们值得麻烦一点也不。我看过 ANTLR 和 Spirit，但我们的项目有超出早期答案的特定限制，这让我想知道它们是否适合我们。特别是，我需要：

  • 使用 MSVC 生成 C 或 C++ 代码的解析器。ANTLR 3 不支持 C++；它声称可以生成直接的 C，但是关于让它实际工作的文档有点令人困惑。
  • 严重限制内存使用。在我们的应用程序中，内存非常宝贵，即使是微小的泄漏也是致命的。我需要能够覆盖解析器的内存分配器以使用我们的自定义 malloc()，或者至少我需要给它一个连续的池，它从中提取所有内存（并且我可以在之后解除分配整体）。我可以为解析器可执行文件本身腾出大约 200kb 的空间，但是它在解析中分配的任何动态堆都必须在之后被释放。
  • 很好的表现。这不太重要，但我们应该能够在 3ghz 处理器上在一秒钟内解析 100kb 的文本。
  • 必须是无 GPL 的。我们不能使用 GNU 代码。

我喜欢 ANTLRworks 的 IDE 和调试工具，但看起来让它的 C 目标真正与我们的应用程序一起工作将是一项艰巨的任务。在我开始讨论之前，ANTLR 是适合这项工作的工具吗？

有问题的文本格式类似于：

attribute "FluxCapacitance"  real constant

asset DeLorean
{
    //comment foo bar baz
    model "delorean.mdl"
    animation "gullwing.anm"
    references "Marty"
    loadonce
}

template TimeMachine
{
    attribute FluxCapacitance 10      
    asset DeLorean
}
4

7 回答 7

4

我们在应用程序中成功使用了Boost Spirit 。Boost 许可证是一个非常自由的许可证，因此在商业应用程序中使用它是没有问题的。

从文档中引用：

Spirit 是一个使用模板元编程技术实现的面向对象的递归下降解析器生成器框架。表达式模板允许我们在 C++ 中完全近似扩展巴科斯范式 (EBNF) 的语法。Spirit 框架使目标语法能够专门用 C++ 编写。内联 EBNF 语法规范可以与其他 C++ 代码自由混合，并且由于 C++ 模板的生成能力，可以立即执行。回想起来，传统的编译器-编译器或解析器-生成器必须执行从源 EBNF 代码到 C 或 C++ 代码的额外翻译步骤。

于 2009-04-21T00:49:54.707 回答
4

ANTLR 3 不支持 C++；它声称可以生成直接的 C，但是关于让它实际工作的文档有点令人困惑。

它确实生成 C，此外，它适用于 Visual Studio 和 C++。我知道这一点是因为我以前做过并提交了一个补丁来让它与 stdcall 一起工作。

在我们的应用程序中，内存非常宝贵，即使是微小的泄漏也是致命的。我需要能够覆盖解析器的内存分配器以使用我们的自定义 malloc()，或者至少我需要给它一个连续的池，它从中提取所有内存（并且我可以在之后解除分配整体）。我可以为解析器可执行文件本身腾出大约 200kb 的空间，但是它在解析中分配的任何动态堆都必须在之后被释放。

我上次检查的 antlr3c 运行时没有内存泄漏，并使用您描述的内存池范例。但是，它的 API 有一个缺点是作者拒绝改变的，那就是如果你请求一个节点的字符串，它每次都会创建一个新的副本，直到你释放整个解析器。

我对使用自定义 malloc 的易用性没有评论，但它确实有一个宏来定义在整个项目中使用的 malloc 函数。

至于可执行文件大小，我的编译大小约为 100 kb，包括一个小型解释器。

我对你的建议是继续学习 ANTLR，因为它仍然符合你的要求，而且你可能需要牺牲更多的时间才能开始为你工作。

于 2009-04-21T07:09:11.660 回答
2

手动编码的递归下降解析器实际上非常快并且可以非常紧凑。唯一的缺点是您必须小心编写本质上的 LL(1) 语法。[如果你使用 ANTLR，你有类似的限制，所以这没什么大不了的]。

您可以将此类解析器的代码编写为普通的递归 C 代码。（有关完整详细信息，请参阅此答案： 是否有可用于 8 位嵌入式系统的 flex/bison 替代方案？）

如果您的空间真的很紧，您可以定义一个解析虚拟机，并构建一个微型 C 解释器来运行它。早在 70 年代初，我就曾经以这种方式构建 BASIC 解释器。

通过坚持使这些解析器实际工作的非常简单的约定，您可以保证没有由解析机制引起的内存泄漏。（当然，您可以将任意操作附加到解析器识别感兴趣的项目的位置；这些操作是否泄漏是一般编程问题，而不是解析器）。

这些想法来自 Val Schorre 1964 年关于元编译器的论文，他展示了如何在 10 页中构建完整的编译器。Shorre 的微型解析器生成器产生了非常好的递归下降解析器。可以在 http://www.bayfronttechnologies.com/metaii.html找到描述本文并准确展示如何构建此类解析器的站点

在我厌倦了手工编写复杂的语法之后，我在 70 年代后期使用了 Schorre 的方法来构建 Basic 编译器。

于 2009-06-27T02:15:00.677 回答
2

请查看我为 ANTLR 发布的新 C++ 目标。它还可以选择限制解析器的内存使用，并以特征的形式公开所有必要的内存管理例程。

http://www.antlr.org/wiki/pages/viewpage.action?pageId=29130826

于 2012-03-01T01:17:42.150 回答
1

那你为什么不使用 flex/yacc 呢？它生成 C 代码，可以从 MSVC 运行，在开发时考虑到了效率，可以覆盖 malloc（google for yymalloc），它们本身就是 GPL，但生成的代码（您在项目中使用的代码）AFAIK 不是。

或者使用手工制作的解析器。

于 2009-04-21T06:58:47.923 回答
0

ANTLR 解析器，实际上任何使用 LALR 等构建的解析器往往都很大。您对此有实际的语法吗？看起来它可能最容易用手写的递归下降解析器解析，但它并不是一个样本。

糟糕，我的错误，因为 ANTLR 显然会生成递归下降。尽管如此，我还是遇到了 ANTLR 生成大型解析器的问题。

于 2009-04-21T00:19:39.943 回答
0

实际上，如果您的语法相对较小，并且不包含很多歧义或解析复杂性，那么使用递归下降解析器或移位归约解析器应该没关系。

我想说看看 ANTLR 和 Spirit，也看看 Flex 和 Bison。还有其他鲜为人知的解析器，例如 Coco/R（包含许多语言的生成器，包括 C++）。

于 2009-06-17T15:31:50.507 回答