Packrat解析与LALR解析 [英] Packrat parsing vs. LALR parsing
问题描述
许多网站指出，packrat解析器可以在线性时间内解析输入.
因此，乍一看，它们比由yacc或bison工具构造的LALR解析器要快.
A lot of websites states that packrat parsers can parse input in linear time.
So at the first look they me be faster than LALR parser contructed by the tools yacc or bison.
我想知道在用普通输入(例如编程语言源文件)而不用任何理论输入进行测试时，packrat解析器的性能是否比LALR解析器的性能更好/更差.
I wanted to know if the performance of packrat parsers is better/worse than the performance of LALR parser when tested with common input (like programming language source files) and not with any theoretical inputs.
任何人都可以解释这两种方法之间的主要区别.
谢谢！
Does anyone can explain the main differences between the two approaches.
Thanks!
推荐答案
I'm not an expert at packrat parsing, but you can learn more at Parsing expression grammar on Wikipedia.
我没有深入研究它，所以我假设packrat解析的线性时间表征是正确的.
I haven't dug into it so I'll assume the linear-time characterization of packrat parsing is correct.
L(AL)R解析器也是线性时间解析器.因此，从理论上讲，packrat和L(AL)R解析器都不是更快"的.
L(AL)R parsers are linear time parsers too. So in theory, neither packrat nor L(AL)R parsers are "faster".
在实践中，重要的当然是实施. L(AL)R状态转换可以在很少的机器指令中执行(在向量中查找令牌代码，获取下一个状态和动作")，因此在实践中可以非常快地执行.通过将L(AL)R解析编译"为机器代码，您可以得到闪电般的快速解析器，如
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. By "compiling" L(AL)R parsing to machine code, you can end up with lightning fast parsers, as shown by this 1986 Tom Pennello paper on Very Fast LR parsing. (Machines are now 20 years faster than when he wrote the paper!).
如果packrat解析器正在存储/缓存结果，它们可能是线性时间，但是我想恒定的开销会很高，然后L(AL)R解析器在实践中会更快.从我听到的内容来看，YACC和Bison的实现非常好.
If packrat parsers are storing/caching results as they go, they may be linear time, but I'd guess the constant overhead would be pretty high, and then L(AL)R parsers in practice would be much faster. The YACC and Bison implementations from what I hear are pretty good.
如果您在乎答案，请仔细阅读基本技术文章；如果您真的很在意，则实现其中一种，并检查开销常量.我的钱主要依靠L(AL)R.
If you care about the answer, read the basic technical papers closely; if you really care, then implement one of each and check out the overhead constants. My money is strongly on L(AL)R.
观察:大多数语言前端不会将大部分时间都花在解析"上；相反，他们花费大量时间进行词法分析.对其进行优化(您的简历说的是您)，解析器的速度就无关紧要了.
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 (your bio says you are), and the parser speed won't matter much.
(我曾经构建LALR解析器生成器和相应的解析器.我不再这样做；相反，我使用 GLR解析器在实践中是线性时间，但可以处理任意上下文无关的语法，虽然我放弃了一些性能，但是我可以(并且可以看到bio)为许多语言构建数十个解析器而没有很多麻烦. ).
(I used to build LALR parser generators and corresponding parsers. I don't do that anymore; instead I use GLR parsers which are linear time in practice but handle arbitrary context-free grammmars. I give up some performance, but I can [and do, see bio] build dozens of parsers for many languages without a lot of trouble.).
这篇关于Packrat解析与LALR解析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
