谁更快:PEG还是GLR?

8
我正在尝试为C/AL编程语言创建一种类似于lint的工具。因此,基本上我需要对源代码执行语法和词法分析。我计划从头开始编写解析器,但后来发现有很多工具可以帮助自动生成这些解析器。
我需要高性能,因为在一个文件中检查20兆字节的代码是正常情况,并且我需要该工具可以通过自定义规则进行扩展。因此,我决定使用JavaScript。
据我所知,我可以使用两个生成器JisonPEG.js
哪一个可以提供更好的解析性能?也许不是比较库,而是算法?
哪一个更适合我的需求(解析通用编程语言)? 更新: 我已经找到了类似的问题和答案:
3个回答

9
"I need performance (for 20Mb) ... so I decided Javascript". 这是矛盾的。
精心编写的递归下降解析器可以非常快,但你需要编写大量代码。通常,LALR(1)解析器(由Bison从语法生成等)非常快且很容易编码。(有技术论文展示如何将LALR解析器直接编译成机器代码;这些解析器非常快,但需要实现大量自定义机制来构建一个)。
如果你想要最大限度地提高解析性能而又不费吹灰之力,你应该考虑使用LRStar。(我认识并高度尊重作者,但与此无关)。这会产生非常快的LALR解析器。缺点是:你必须使你的语法兼容LALR。您将不得不通过编写C代码来扩展您的“规则”,就像扩展任何其他C程序一样。在我的看法中,这似乎并不比编写JavaScript更糟糕,但规则可能会执行得更快,在您考虑的规模下,这很重要。
GLR解析必然比LALR慢,因为它有更多的簿记工作要做。但那只是一个恒定因子。与LRStar等高性能引擎相比,它可能会显著(例如100倍)慢。这可能值得一试,因为将语法塑造成形状更简单,编写自定义规则也更容易。如果你真的有数百万行代码,这些解析器最多只能达到中等速度。
PEG基本上是回溯的。它必须尝试并在不起作用时回溯。它们必须比LALR解析器慢至少回溯量。您还需要解决语法塑形问题。
然而,您会发现,如果想要进行稍微复杂的任何操作,仅仅解析是不够的。在这种情况下,您不希望在解析上进行优化;您希望在程序分析基础设施上进行优化。请参阅我关于解析后的生活的文章,了解另一种选择。

谢谢!我已经提到我想在lint中有自定义规则,所以我肯定需要脚本语言,而JavaScript(V8 node.js实现)似乎比Python、Ruby等更快。 - shytikov
我认为你没有理解我的“解析后的生活”观点。你似乎已经固定了JavaScript作为规则语言,但实际上你几乎没有任何基础设施来支持你的分析任务。因此,你可以利用一种广泛可用的编程语言来编写规则,但却没有任何支持这些规则的工具。除非你的规则基本上是微不足道的......否则这有什么意义呢?我对你的实际成功持悲观态度。 - Ira Baxter
我正在阅读《解析之后的生活》。它很长,而且我很不耐烦。抱歉。我看了一下 JavaScript,因为有一些带有源代码的“lint”工具是用 JavaScript 编写的。我希望这会对我有所帮助。但你说得对。任务很艰巨... - shytikov
什么是“MSLOC”? - Paweł Badeński
"百万行源代码"。我修改了答案以使其更清晰。 - Ira Baxter

7
一般来说,像Jison实现的移进-规约解析器这样的解析器可以提供非常好的解析性能。它可能有点老派,但在非常紧凑的内存要求和线性时间中可以发挥作用。
PEG生成了一种不同类型的解析器,可能更加强大,但需要更多的内存才能产生相同的结果。即PEG将需要与输入成正比的数量的内存,而LALR解析器则只需要很少的空间(一些表格和一个小栈)。

如果从GLR或LALR这样的LR解析器对您的语法施加了限制(GLR仅使用更多的内存,速度稍慢),那么LR可能是更快的解析器。然而,生成解析器需要更长时间,因为它需要计算其表格。但在一般情况下,LR解析器是非常高效的机器。 - Dervall
除了使用语法解析器生成器的人,没有人会在意生成器运行需要多长时间。即使是他也不太关心;大型语法解析器可以在几秒钟内生成,至少对于我所知道的 LALR 解析器生成器和其他大部分解析器生成器来说。 - Ira Baxter

3
我发现了两个可以使用的生成器,它们分别是Jison和PEG.js。哪一个能提供更高的解析性能呢?
根据我创建的JavaScript Parser Libraries基准测试结果来看,似乎PEG.js更快(至少在Chrome/V8上)。
您可以在这里在线运行: http://sap.github.io/chevrotain/performance/ 请注意,此基准测试使用非常简单的JSON语法比较解析库的性能,而不是一个更大更复杂的编程语言语法。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接