2013-05-07 21 views
10

可以使用现有的Marpa解析器来改进Perl 5的解析(例如,替换全部或大块的现有Perl解释器的解析器)?Can Marpa可以用来加速Perl解释器的解析吗?

我在理论层面上问,忽视实际考虑,如“如果可以,将花费10,000个工作小时”。

如果不是,阻止使用Marpa的具体问题是什么? (再次,最好是理论的)。

Jeffrey Kegler(Marpa的作者)于2008年在PerlMonks上发布了一篇着名的文章"Perl Cannot Be Parsed: A Formal Proof",这受到他当时在Marpa工作的影响。

+0

作为一个告诫,我宁愿 - 如果可能的话 - 超越琐碎的答案“[没有语法分析器可以解析Perl代码,因为您可以在编译阶段执行BEGIN代码块](http://stackoverflow.com/questions/1280594 /可-perl的待静态解析?RQ = 1)”。例如。说明如何以及为什么Marpa不能像词法分析器那样缠绕perl的当前解析器似乎基于我的普通人的理解;或者为什么 - 即使它可以 - 马尔帕会比现有的解析器差。 – DVK 2013-05-07 20:13:19

+2

我已将此问题的链接发送给Jeffrey Kegler的Marpa Google Groups,希望他会根据他的老式PerlMonks文章“[Perl无法解析:正式证明]”(http://www.perlmonks.org)回答问题。 /?node_id = 663393)“ – DVK 2013-05-07 20:22:23

+0

你怎么能不告诉别人? – ikegami 2013-05-07 21:09:50

回答

9

感谢您的询问。 perlmonks文章和我目前的解析工作解决了两个不同的相关问题。问题1:Perl解析是否完全一般,可由图灵机决定?问题2:作为一个实际问题,Marpa可以解析Perl 5吗?

您可能会比较两个问题:“每个C程序的行为是否可确定?”和“机器X可以运行用C编译的程序吗?”答案分别是“否”和“是为了所有实际目的和X的合理选择”。所以我的perlmonks文章(更新here)是关于Perl程序的语法是否完全一致的可判定的理论问题。请注意,在这种情况下Perl解析的可判定性与Marpa,递归下降,野牛等等无关 - 它是关于图灵机的。

问题2是“Can Marpa驱动一个实用的Perl 5解析器吗?”当前的Perl 5语法分析器是LALR,具有单独的词法分析器和大量的程序帮助。 Marpa比LALR更强大,允许使用单独的词法分析器,并且比LALR提供更多程序代码的帮助。我在a recent blog post中解决了速度问题:“Earley解析速度够快吗?”我刚才所说的是非常电报 - 但我希望它能够概述我如何证明我对问题2的“是”的答案。

没有深层的建筑问题阻碍了Marpa驱动Perl 5解析器。在这一点上,这确实是一个舒适程度的问题。