Rom*_*iko 12 parsing lalr peg parser-generator ll-grammar
我已经看到一些声称优化的PEG解析器通常不会比优化的LALR(1)或LL(k)解析器更快.(当然,解析的性能取决于特定的语法.)
我想知道PEG解析器是否存在任何特定限制,无论是一般有效还是PEG语法的某些子集都会使它们在性能方面低于LALR(1)或LL(k).
特别是,我对解析器生成器很感兴趣,但是假设在任何特定情况下都可以调整它们的输出以提高性能.我还假设解析器已经过优化,如果需要提高性能,可以稍微调整一下特定的语法.
Rom*_*iko 11
找到一个关于Packrat vs LALR解析的好答案.一些引用:
L(AL)R解析器也是线性时间解析器.所以从理论上讲,packrat和L(AL)R解析器都不是"更快".
重要的是,实际上,当然是实施.L(AL)R状态转换可以在很少的机器指令中执行("在向量中查找令牌代码,获得下一个状态和动作"),因此它们在实践中可以非常快.
观察:大多数语言前端不会花费大部分时间"解析"; 相反,他们花了很多时间进行词汇分析.优化...,解析器速度无关紧要.
PEG解析器可以使用无限前瞻(平均保持线性解析时间,通过packrat),不像(默认)LL(k),或LR(k)使用有限前瞻的解析器,同时保持线性解析时间.
最近(2014-2015)ANTLR4进行了扩展以处理任意前瞻(如PEG),同时保持平均线性解析时间(据说比packrat算法更有效),但是这包含了LR解析算法的新扩展和变体(而不是默认LR算法).
所述packrat解析器(和针对关联的解析器LL,LR)不是necesarily实用,但对解析提供了理论的限制,以比较可以进行.
但需要注意的是无限的先行可以用来解析语法/语言线性时间(例如通过packrat或antlr),这是不可能通过解析LL(k)或者LR(k)甚至在非线性的时间,所以要了解是很重要的东西是比什么.