ANTLR解析器生成器最适合具有受限内存的C ++应用程序吗?

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

似乎最终的解决方案是为这种格式构建一个正确的语法,然后使用像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 } 

ANTLR 3不支持C ++; 它声称直接产生C,但是让它实际工作的文档有点令人困惑。

它确实生成了C,而且它适用于Visual Studio和C ++。 我知道这一点,因为我之前已经完成了它,并提交了一个补丁,以使其与stdcall一起使用。

内存在我们的应用程序中占据了巨大的优势,即使是微小的泄漏也是致命的。 我需要能够覆盖解析器的内存分配器以使用我们的自定义malloc(),或者至少我需要为它提供一个连续的池,从中抽取所有内存(之后我可以解除分配)。 我可以为解析器可执行文件本身节省大约200kb,但是它在解析时分配的任何动态堆都必须在之后释放。

上次检查时antlr3c运行时没有内存泄漏,并使用您描述的内存池范例。 但是,它确实在API中存在一个缺点,即作者拒绝更改,即如果您请求节点的字符串,它将每次创建一个新副本,直到您释放整个解析器。

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

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

我建议你继续学习ANTLR,因为它仍然符合你的要求,你可能需要再花一点时间才能开始为你工作。

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

从文档中引用:

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

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

您可以将此类解析器的代码手动编写为纯递归C代码。 (有关完整的详细信息,请参阅此答案: 是否有可用于8位嵌入式系统的flex / bison替代方案? )

如果你对空间非常紧张,你可以定义一个解析虚拟机,并构建一个微小的C解释器来运行它。 我曾经在70年代早期以这种方式建立BASIC解释器。

通过坚持使这些解析器实际工作的非常简单的约定,您可以保证解析机制不会导致内存泄漏。 (当然,您可以将任意操作附加到解析器,它会识别感兴趣的项目;这些操作是否泄漏是一般编程问题,而不是解析器)。

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

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

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

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

那你为什么不使用flex / yacc? 它生成C代码,可以从MSVC运行,开发时考虑到效率,可以有malloc覆盖(google for yymalloc),它们本身就是GPL,但结果代码(你在项目中使用的代码)AFAIK没有。

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

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

哎呀,我的错误,因为ANTLR显然会产生递归下降。 尽管如此,我还是遇到了ANTLR产生大解析器的问题。

实际上,如果你的语法相对较小,并且不包含许多含糊不清或解析复杂性,那么使用递归下降解析器或shift-reduce解析器应该无关紧要。

我会说看看ANTLR和Spirit,还看看Flex和Bison。 还有其他一些鲜为人知的解析器,如Coco / R(包含许多语言的生成器,包括C ++)。