解析器的性能:PEG与LALR(1)或LL(k) [英] Performance of parsers: PEG vs LALR(1) or LL(k)

问题描述

我已经看到一些主张，通常说来，优化的PEG解析器不能比优化的LALR(1)或LL(k)解析器快. (当然，解析的性能取决于特定的语法.)

我想知道PEG解析器是否有任何特定限制，无论是对一般语法还是对某些使它不如LALR(1)或PEG语法的子集有效的语法， LL(k)性能方面.

我特别对解析器生成器感兴趣，但是假设可以在任何特定情况下调整它们的输出以提高性能.我还假设解析器已经过优化，如果需要提高性能，可以对特定语法进行一些调整.

解决方案

找到了一个很好的有关Packrat与LALR解析的答案 .引述以下内容:

L(AL)R解析器也是线性时间解析器.因此，从理论上讲，packrat和L(AL)R解析器都不是更快"的.

在实践中，重要的当然是实施. L(AL)R状态转换可以用很少的机器指令(在向量中查找令牌代码，获取下一个状态和动作")执行，因此它们在实践中可以非常快.

观察:大多数语言前端不会将大部分时间都花在解析"上；相反，他们花费大量时间进行词法分析.优化它，解析器的速度就没多大作用了.

I've seen some claims that optimized PEG parsers in general cannot be faster than optimized LALR(1) or LL(k) parsers. (Of course, performance of parsing would depend on a particular grammar.)

I'd like to know if there are any specific limitations of PEG parsers, either valid in general or for some subsets of PEG grammars that would make them inferior to LALR(1) or LL(k) performance-wise.

In particular, I'm interested in parser generators, but assume that their output can be tweaked for performance in any particular case. I also assume that parsers are optimized and it is possible to tweak a particular grammar a bit if that's needed to improve performance.

解决方案

Found a good answer about Packrat vs LALR parsing. Some quotes from it:

L(AL)R parsers are linear time parsers, too. So in theory, neither packrat nor L(AL)R parsers are "faster".

What matters, in practice, of course, is implementation. L(AL)R state transitions can be executed in very few machine instructions ("look token code up in vector, get next state and action") so they can be extremely fast in practice.

An observation: most language front-ends don't spend most of their time "parsing"; rather, they spend a lot of time in lexical analysis. Optimize that ..., and the parser speed won't matter much.

这篇关于解析器的性能:PEG与LALR(1)或LL(k)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！