谁更快:PEG还是GLR？

Question

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

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

据我发现两个发生器我可以使用Jison和PEG.js.

哪一个给我更多的解析性能？也许不是比较库,而是算法？

哪一个更适合我的需求(解析通用编程语言)？

更新: 我发现了类似的问答:

• Packrat解析与LALR解析
• 解析器的性能:PEG与LALR(1)或LL(k)

Answer 1

通常,你会从一个shift-reduce解析器中获得非常好的解析性能,例如Jison实现的解析器.这可能是一个老派,但它可以在非常严格的内存要求和线性时间内工作.

PEG产生一种可能更强大的不同类型的解析器,但是需要更多的内存来产生相同的结果.即PEG将需要与输入成比例的一定量的内存,而LALR解析器将在更少的空间(一些表和一个小堆栈)中执行它.

Answer 2

"我需要性能(20Mb)...所以我决定使用Javascript".这些都是矛盾的.

精心编码的递归下降解析器可以非常快,但您必须编写大量代码.通常,LALR(1)解析器(由Bison从语法等生成)非常快,并且非常容易编码.(有技术论文显示如何将LALR解析器直接编译为机器代码;这些解析器速度非常快,但您需要实现大量自定义机制来构建一个).

如果你想要轻松解决高性能解析,你应该考虑LRStar.(我知道并高度尊重作者,但在其他方面没有任何关系).这会产生非常快速的LALR解析器.缺点:你必须使你的语法LALR兼容.您必须像扩展任何其他C程序一样扩展"规则":编写C代码.这似乎并不比编写JavaScript恕我直言更糟糕,但规则可能会执行得更快,并且在您考虑的规模上这将很重要.

GLR解析必然比LALR慢,因为它有更多的簿记要做.但这只是一个不变因素.与LRStar等高性能引擎相比,它可能很重要(例如,100倍).这可能是值得的,因为将语法写成形状要容易得多,而语法较少的复杂可能会使编写自定义规则更容易.如果你真的有1个MSLOC文件,那么这些解析器最好是中速.

PEG基本上是回溯.它必须尝试,并在它们不起作用时回溯.它们必须比LALR解析器慢至少它们所做的回溯量.你也有语法形成问题.

但是,你会发现,如果你想做任何最微妙的事情,解析就不够了.在这种情况下,您不希望优化解析; 您希望优化基础架构以进行程序分析.请参阅我的论文 "解析后的生活"中的另一种选择.