谁更快:PEG还是GLR

Who is faster: PEG or GLR?

本文关键字：还是 GLR PEG      更新时间：2024-06-06

我正在尝试为C/AL编程语言创建某种lint工具。因此，基本上我需要对源代码执行语法和词法分析。我曾计划从头开始编写解析器，但后来发现有很多工具可以帮助自动生成这些解析器。

我需要性能，因为在一个片段中检查20兆字节的代码是正常的情况，并且我需要该工具可以通过自定义规则进行扩展。所以我决定使用JavaScript。

到目前为止，我已经找到了两个可以使用Jison和PEG.js的生成器。

它们中的哪一个给了我更高的解析性能？也许不是比较库，而是比较算法？

哪一种更适合我的需求（解析通用编程语言）？

更新：我发现了类似的问答；As：

  • Packrat解析与LALR解析
  • 解析器的性能：PEG与LALR（1）或LL（k）

"我需要性能（20Mb）。。。所以我决定使用Javascript；。这些都是矛盾的。

精心编码的递归下降语法分析器可能非常快，但您必须编写大量代码。一般来说，LALR（1）解析器（由Bison根据语法等生成）非常快速，并且非常容易编码。（有展示如何将LALR解析器直接编译为机器代码的技术论文；这些解析器速度极快，但您需要实现许多自定义机制来构建一个）。

如果您想用最少的精力进行全面的高性能解析，您应该考虑LRStar。（我了解并高度尊重作者，但除此之外，我与此无关）。这会产生非常快的LALR解析器。缺点：你必须使你的语法LALR兼容。您将不得不延长您的"；规则"；和你一样扩展任何其他C程序：通过编写C代码。这似乎并不差多少与编写JavaScript IMHO相比，但规则的执行速度可能会快得多在你考虑的范围内，这将很重要。

GLR解析必然比LALR慢，因为它要做更多的记账工作。但这只是一个不变的因素。与LRStar这样的高性能发动机相比，它可能意义重大（例如，100倍）。这可能是值得的，因为它更容易使你的语法成形，而不那么复杂的语法可能会使编写自定义规则变得更容易。如果你真的有数百万行代码，这些解析器最好是中等速度。

PEG基本上是一种回溯。它必须尝试一些事情，当它们不起作用时就反悔。它们必须比LALR解析器慢至少它们的回溯量。你也有语法形成的问题。

不过，您会发现，如果您想进行解析，那么解析根本不够任何稍微有点复杂的东西。在这种情况下，您不希望优化解析；您希望优化程序分析的基础结构。在上查看我的文章分析另一种选择后的生活。

通常，您会从shift-reduce解析器（如Jison实现的解析器）中获得非常好的解析性能。这可能有点老派，但它可以在非常严格的内存要求和线性时间内工作。

PEG产生了一种不同类型的解析器，这种解析器可能更有能力，但需要更多的内存才能产生相同的结果。也就是说，PEG将需要与输入成比例的内存量，而LALR解析器将在更少的空间（一些表和一个小堆栈）中完成这项工作。

到目前为止，我已经找到了两个可以使用Jison和PEG.js的生成器。它们中的哪一个给了我更高的解析性能？

根据我创建的JavaScriptParserLibraries基准PEG.js似乎更快（至少在Chrome/V8上）。

您可以在此处在线运行：http://sap.github.io/chevrotain/performance/

请注意，此基准测试使用非常简单的JSON语法进行比较解析库的性能不是一个更大、更复杂的程序语言语法。

相关文章：