rai*_*syn 12 parsing lalr parser-generator
许多网站都声称packrat解析器可以在线性时间内解析输入.
所以初看起来他们比由工具yacc或bison构建的LALR解析器更快.
我想知道当使用公共输入(如编程语言源文件)而不是任何理论输入进行测试时,packrat解析器的性能是否比LALR解析器的性能更好/更差.
有没有人可以解释这两种方法之间的主要区别.
谢谢!
我不是packrat解析的专家,但你可以在维基百科上解析表达式语法.
我没有挖到它,所以我假设packrat解析的线性时间表征是正确的.
L(AL)R解析器也是线性时间解析器.所以从理论上讲,packrat和L(AL)R解析器都不是"更快".
重要的是,实际上,当然是实施.L(AL)R状态转换可以在很少的机器指令中执行("在向量中查找令牌代码,获得下一个状态和动作"),因此它们在实践中可以非常快.通过"编译"L(AL)R解析到机器代码,你可以得到闪电般快速的解析器,如1986年Tom Pennello关于非常快速LR解析的论文所示.(机器现在比他写论文时快20年!).
如果packrat解析器正在存储/缓存结果,它们可能是线性时间,但我猜测常量开销会非常高,然后实际上L(AL)R解析器会更快.我听到的YACC和Bison实现非常好.
如果您关心答案,请仔细阅读基本技术论文; 如果你真的关心,那么实现其中一个并检查开销常量.我的钱很强在L(AL)R上.
观察:大多数语言前端不会花费大部分时间"解析"; 相反,他们花了很多时间进行词汇分析.优化(你的生物说你是),解析器速度无关紧要.
(我曾经构建过LALR解析器生成器和相应的解析器.我不再这样做了;而是使用GLR解析器,它在实践中是线性时间但是处理任意无上下文的grammmars.我放弃了一些性能,但我可以[和do,see bio]为许多语言构建了数十种解析器而没有太多麻烦.)
我是LRSTAR的作者,LRSTAR是一个开源LR(k)解析器生成器.因为人们对此感兴趣,所以我已将产品重新上线到 LRSTAR.ORG.
多年来,我研究过LALR解析器和DFA词法分析器的速度.Tom Pennello的论文非常有趣,但更多的是学术练习,而不是编译器的真实解决方案.但是,如果您只想要一个模式识别器,那么它可能是您的完美解决方案.
问题是现实世界的编译器通常需要做的不仅仅是模式识别,例如对传入符号的符号表查找,错误恢复,提供期望列表(语句完成信息),以及构建抽象语法树,同时解析.
1989年,我将LRSTAR解析器的解析速度与"yacc"进行了比较,发现它们的速度是"yacc"解析器的2倍.LRSTAR解析器使用文章中发表的想法:"便携式编译器的解析器表的优化".
对于lexer(词法分析)速度,我在2009年发现"re2c"产生了最快的词法分析器,大约是"flex"产生的速度的两倍.那时我正在重写LRSTAR词法分析器生成器部分,并找到了一种方法,使得词法分析器几乎和"re2c"一样快,而且要小得多.但是,我更喜欢LRSTAR生成的表驱动词法分析器,因为它们几乎一样快,代码编译速度更快.
BTW,LRSTAR生成的编译器前端可以以每秒2,400,000行或更快的速度处理源代码.LRSTAR生成的词法分析器每秒可处理30,000,000个令牌.测试计算机是一台3.5 GHz的机器(从2010年开始).