现有的Marpa解析器能否用于改进 Perl 5 的解析（例如，替换全部或部分现有 Perl 解释器的解析器）？
我在理论上提出问题，例如忽略实际考虑，例如“如果可以，将花费 10,000 工时”。
如果不是，阻止使用马尔巴的具体问题是什么？（再次，最好是理论上的）。
关于这为什么有趣的背景，Jeffrey Kegler（Marpa 的作者）于 2008 年在 PerlMonks 上发表了一篇颇有名气的文章“Perl 无法解析：正式证明”，该文章受到了他当时在 Marpa 上的工作的影响。
问问题
369 次
1 回答
10
谢谢你的提问。perlmonks 帖子和我当前的解析工作解决了两个不同的相关问题。问题 1：Perl 解析是否可以由图灵机确定？问题 2：实际上，Marpa 可以解析 Perl 5 吗？
您可能会比较这两个问题：“每个 C 程序的行为都是可判定的吗？” 和“机器 X 可以运行用 C 编译的程序吗？” 对于所有实际目的和 X 的合理选择，答案分别是“否”和“是”。因此，我的 perlmonks 帖子（在此处更新）是关于 Perl 程序的语法在其完全通用性中是否可判定的理论问题。请注意，在这种情况下 Perl 解析的可判定性与 Marpa、递归下降、野牛等无关——它与图灵机有关。
问题 2 是“Marpa 可以驱动一个实用的 Perl 5 解析器吗？” 当前的 Perl 5 解析器是 LALR，具有单独的词法分析器和大量的程序辅助。Marpa 比 LALR 更强大，允许单独的词法分析器，并且比 LALR 提供更多的程序代码帮助。我在最近的一篇博文中解决了速度问题：“Earley 的解析速度够快吗？” 我刚才所说的非常电报——但我希望它能够概述我如何证明我对问题 2 的“是”回答是合理的。
Marpa 驱动的 Perl 5 解析器没有任何深层次的架构问题。在这一点上，这确实是一个舒适程度的问题。
于 2013-05-08T01:52:49.363 回答